Jaki jest cel używania NIL do reprezentowania zerowych węzłów?

W moim kursie Algorytmy i struktury danych profesorowie, slajdy i książka ( Wstęp do algorytmów, wydanie trzecie ) używali tego słowaNIL aby na przykład określić dziecko węzła (w drzewie), które nie istnieje.

Pewnego razu, podczas wykładu, zamiast powiedzieć NIL, powiedział mój kolega z klasy null, a profesor poprawił go i nie rozumiem, dlaczego profesorowie podkreślają to słowo.

Czy istnieje powód, dlaczego ludzie używają słowa NILzamiast null, albo none, lub innego słowa? Czy NILma jakieś szczególne znaczenie, którego nie mają inni? Czy jest jakiś historyczny powód?

Zauważ, że widziałem także kilka miejsc w sieci, w których np. nullUżyto tego słowa NIL, ale zwykle używa się tego ostatniego.

O ile mi wiadomo, null, nil, nonei nothingsą wspólne nazwy dla tego samego pojęcia: wartość, która reprezentuje „braku wartości”, a która jest obecna w wielu różnych typach (tzw zerowalne typów ). Ta wartość jest zwykle stosowana tam, gdzie wartość jest zwykle obecna, ale można ją pominąć, na przykład parametr opcjonalny. Różne języki programowania wdrażają to inaczej, a niektóre języki mogą nie mieć takiej koncepcji. W językach ze wskaźnikami jest to wskaźnik zerowy . W wielu językach obiektowych null nie jest obiektem: wywołanie dowolnej metody na nim jest błędem. Aby podać kilka przykładów:

• W Lisp niljest powszechnie używany do oznaczenia braku wartości. W przeciwieństwie do większości innych języków nilma strukturę - jest to symbol o nazwie"NIL" . Jest to również pusta lista (ponieważ lista powinna być komórką przeciw, ale czasami nie ma komórki przeciw, ponieważ lista jest pusta). To, czy jest implementowane przez zerowy wskaźnik pod maską, czy jako symbol jak każdy inny, zależy od implementacji.
• W Pascal nil jest wartością wskaźnika (prawidłową dla dowolnego typu wskaźnika), której nie można odrzucić.
• W C i C ++ każdy typ wskaźnika zawiera NULL wartość, która różni się od jakiegokolwiek wskaźnika do poprawnego obiektu.
• W Smalltalk nil jest obiektem bez zdefiniowanej metody.
• W Javie i w C # nulljest wartością dowolnego typu obiektu. Każda próba dostępu do pola lub metodynull wyzwala wyjątek.
• W Perlu undefróżni się od innych wartości skalarnych i jest używany w całym języku i bibliotece do wskazywania braku „rzeczywistej” wartości.
• W Pythonie Noneróżni się od innych wartości i jest używany w całym języku i bibliotece do wskazywania braku „prawdziwej” wartości.
• W ML (SML, OCaml), Nonejest wartością dowolnego typu w schemacie typów 'a option, który zawiera Nonei Some xdla dowolnego xtypu 'a.
• W Haskell podobna koncepcja używa nazw Nothingi Just xwartości oraz Maybe atypu.

W prezentacjach algorytmów, której nazwa jest używana, wywodzi się z tła prezentera lub języka używanego w przykładach kodu.

W prezentacjach semantyki można używać różnych nazw w odniesieniu np. Do NULLidentyfikatora, który oznacza stałą wskaźnika w języku oraz wartości w semantyce. Nie sądzę, aby istniał jakiś standardowy schemat nazewnictwa, a niektóre prezentacje pozostawiają różnicę czcionek lub wcale nie przechodzą w konkretną składnię.$\mathsf{nil}$

Możliwe jest, że Twój wykładowca chce użyć słowa nulldla stałej wskaźnika zerowego w języku programowania używanym w kursie (Java lub C #?) I NILwskazać brak węzła w niektórych strukturach danych, które mogą, ale nie muszą być zaimplementowane jako stała wskaźnika zerowego (na przykład, jak widać powyżej, w Lisp, NILczęsto nie jest implementowana jako wskaźnik zerowy). To rozróżnienie byłoby istotne przy omawianiu technik implementacji struktur danych. Przy omawianiu samych struktur danych koncepcja zerowej stałej wskaźnikowej jest nieistotna, liczy się tylko koncepcja nie równości z żadną inną wartością.

Nie ma standardowego schematu nazewnictwa. Inny wykładowca lub podręcznik mógłby używać innych nazwisk.

Uważam, że powodem użycia zarówno wartości zerowej, jak i zerowej jest to, że ten pierwszy jest rzeczownikiem, a drugi przede wszystkim przymiotnikiem (sprawdziłem w Internecie i w moim papierowym słowniku: American Heritage 1992).

Jeśli chodzi o znaczenie i historię, NIL jest skrótem od łacińskiego „nihil”, co oznacza „nic”.

O ile mi wiadomo, użycie nazwy niloznaczającej wskaźnik zerowy zostało wprowadzone w języku programowania Lisp (1958).

Pustego wskaźnika jest wartość wskaźnika, który ma wskazywać na nic, i nie powinno być zatem dereferencjonowane. W większości przypadków wskaźniki to po prostu adresy pamięci. Każda zmienna (tj. Dowolna lokalizacja), która ma zawierać taki wskaźnik, zawsze będzie zawierała pewną konfigurację bitów, a każdą taką konfigurację można odczytać jako adres pamięci. Dlatego często zdarza się, że wartością nilbędzie adres obszaru pamięci, który jest zabroniony dla programu, powodując w ten sposób pewną formę awarii (być może przerwania), jeśli program spróbuje wyrejestrować nil, co może być tylko błędem.

Posiadanie unikalnej predefiniowanej wartości standardowej do odgrywania tej roli jest niezbędne w językach, w których jawnie używa się wskaźników, ponieważ ważne jest, aby móc przetestować, czy wskaźnik wskazuje na jakąś lokalizację pamięci, czy nie. Zazwyczaj w Lisp lista była budowana jako szereg par „wad” zawierających wskaźnik „samochód” do elementu listy i wskaźnik „cdr” do następnej pary. W ostatniej parze listy drugim wskaźnikiem był nil.

Odpowiada to rekurencyjnej definicji listy jako pustej listy lub elementu listy połączonego z listą. Stąd lista bez elementu była reprezentowana przez nil. Ta pusta lista to tożsamość monoidu listy.

Ponieważ listy mogą być używane do reprezentowania zestawów, pusty zestaw może być w tym przypadku również reprezentowany przez nil.

Tak więc nilhistorycznie była to specjalna wartość wskaźnika, ale zaczęła być rozumiana jako specjalna wartość tożsamości dla innych bardziej abstrakcyjnych domen, takich jak listy lub zestawy.

Wskaźnik równy nilbył zerowemu wskaźnikowi, null byłby przymiotnikiem, a nie rzeczownikiem (tj. Rzeczownikiem).

Skoordynowane użycie obu słów jako przymiotnika i rzeczownika jest dość spójne z innymi praktykami. Kwalifikator null jest często używany do zera struktury algebraicznej, takiej jak tożsamość monoidu: element zerowy . Listy tworzą monoid , gdzie wartością zero jest tożsamość. To samo dotyczy zbiorów (choć tworzą one algebrę o wiele innych właściwościach). Mówi się podobnie, że liczba całkowita jest zerowa, gdy wynosi zero.

Istnieje wiele odmian użycia tych słów i innych, takich jak brak, w zależności od autorów i osobliwości języków programowania.

Dwie główne konotacje są , jak wyjaśniono powyżej

• jako standardowa „wartość nieokreślona”, faktycznie reprezentująca brak jakiejkolwiek użytecznej wartości.

• jako wartość tożsamości niektórych domen

To pokazuje, że twierdzenie, że NIL jest „ wartością, która reprezentuje„ brak wartości ”, nie jest dość dokładne , jak to zrobił Gilles w przyjętej odpowiedzi . To zależy od języka i jego zastosowań. Język programowania LISP prawdopodobnie wprowadził NIL w terminologii programowania 55 lat temu. W LISP, NILjest pustą listą, i można w równy sposób zauważyć, ()która jest naturalną reprezentacją pustej listy.Nie oznacza to braku wartości. Czasami jest używany jako symbol zastępczy dla brakujących wartości, chociaż często tego należy unikać właśnie dlatego, że pusta lista jest wartością. Co oznacza brakującą wartość w strukturze dowolnego dowolnego obiektu wybranego przez programistę, którego nie można pomylić z dopuszczalnymi wartościami.

Te dwie koncepcje są raczej różne, chociaż wykazaliśmy powyżej, że można je ze sobą powiązać. Interesujące może być posiadanie trybu szczegółowej taksonomii użycia terminologii wyliczonej przez Gilles'answer, aby zobaczyć, czy użycie każdego z tych słów jest bardziej ukierunkowane na jedną konotację, czy drugą.

Nazwy nie są niczym więcej niż tym, co mają oznaczać w danym kontekście, przez każdego, kto definiuje dyskurs. Niektóre zastosowania są bardziej powszechne, bardziej naturalne lub bardziej spójne, ale zawsze należy sprawdzać definicje i upewnić się, jakie znaczenie było zamierzone w każdym kontekście. I nie zawsze należy oczekiwać, że terminologia zostanie wybrana ze smakiem lub konsekwencją.

NIL to obiekt o wartości, która informuje programistę, że obiekt jest niepoprawny. Jest to szczególnie przydatne w C ++, gdzie NULL jest zdefiniowane jako 0. Jeśli usuniesz odwołanie do NULL w C ++, otrzymasz niezdefiniowane zachowanie. Jeśli usuniesz odniesienie do NIL (wskaźnik do pustego obiektu, który zdefiniowałeś), otrzymasz obiekt, o którym możesz powiedzieć, że znajduje się poza końcem struktury danych. Doskonale nadaje się do zapobiegania katastrofalnym awariom programu i wykrywania błędów.

Możesz użyć NIL w przypadkach takich jak podwójnie połączone listy, mając na początku i na końcu listy, aby śledzić zarówno głowę, jak i ogon, i upewnij się, że -> dalej i -> poprzednie wskaźniki nigdy nie usuwają odniesienia do wartości NULL.