Perché la lista vuota è usata come terminatore di lista in Lisp?

Una lista Lisp è non realmente terminata con una lista vuota - è terminata con un valore speciale, tradizionalmente chiamato nil . Come accade, anche questo viene tradizionalmente valutato come false - il che lo rende il più vicino possibile al puntatore nullo di C (in C, una costante di puntatore nullo è una costante intera uguale a zero, che valuta anche a false ).

UnalistavuotaèfondamentalmentesolounmodopiuttostocortodiesprimereNIL-dalmomentochenonhainemmenounasingolacella,tuttociòchetirimaneèilNILcheterminalalista.Inaltreparole,nonècheunalistasiaterminataconunalistavuota-ècheunalistavuotaconsisteinsolounterminatore.

Usandolanotazioneapunti,èpossibilecollegarelecelledicontrolloinsiemeinaltrimodi,mailrisultatononèun"elenco" poiché il termine è normalmente utilizzato.

Gli elenchi di Lisp non hanno realmente un valore di 'terminazione'. In realtà Lisp non ha nemmeno una struttura di dati di lista primitiva. Gli elenchi sono costruiti fuori dalla lista vuota e una catena di celle di controllo collegate che puntano al contenuto dell'elenco.

Gli elenchi sono definiti in modo ricorsivo:

• la lista vuota è ()
• una lista newlist è il risultato di (CONS element list) , dove (FIRST newlist) è element e (REST newlist) è list .

Una lista è vuota quando è la lista vuota o (NULL list) è vera.

Poiché newlist è il risultato di (CONS element list) è in realtà un oggetto cella cons e '(la nuova lista CONSP) è vera.

Nei vecchi tempi FIRST era chiamato CAR e REST era CDR . Oggi è buono da usare nelle operazioni lista FIRST e REST . CAR e CDR è meglio utilizzato quando si sfrutta la funzionalità che qualcosa (albero, coda, lista, ...) è costruita fuori dalle celle.

Storicamente (e ancora in Common Lisp che mira ad essere retrocompatibile), la lista vuota è anche il simbolo univoco NIL . L'elenco vuoto valuta se stesso ed è anche il valore falso . Nello schema Lisp-dialect, la lista vuota NON è il valore falso.

CL-USER 12 > (setq l1 ())
NIL

CL-USER 13 > (setq l2 (cons 1 (cons 2 l1)))
(1 2)

CL-USER 14 > (consp l1)
NIL

CL-USER 15 > (consp l2)
T

CL-USER 16 > (null l1)
T

CL-USER 17 > (null l2)
NIL

CL-USER 18 > (first l2)
1

CL-USER 19 > (rest l2)
(2)

CL-USER 20 > (rest (rest l2))
NIL

CL-USER 21 > (consp (rest l2))
T

CL-USER 22 > (consp (rest (rest l2)))
NIL

Ti darò la risposta filosofica alla tua domanda filosofica:

Mi sembra che il terminatore di lista in Lisp potrebbe essere qualsiasi valore arbitrario. [...] Esiste un motivo filosofico per cui la lista vuota è stata scelta per terminare le liste?

La risposta alla tua domanda è questa: il termine elenco è un valore arbitrario . È così arbitrario che diversi dialetti Lisp usano un valore diverso per esso e tuttavia rimangono concettualmente compatibili.

Common Lisp usa un oggetto simbolo: il simbolo nil . Un simbolo! Che cosa ha a che fare un simbolo con le liste? Niente.

(Tranne che quando lavoriamo con oggetti matematici con carta e matita, usiamo i simboli: un cerchio con un trattino o {} rappresenta un insieme vuoto, ecc. Quindi, perché non usare i simboli macchina allo stesso modo?)

Scheme usa una lista vuota, l'oggetto () che non è un simbolo.

Lo Schema () e il Common Lisp nil sono abbastanza diversi, eppure terminano adeguatamente un elenco, esattamente in linea con la tua osservazione che potrebbe essere qualsiasi valore arbitrario!

Quindi, c'è una ragione filosofica per cui la lista vuota termina le liste? Sì! Il motivo è che qualsiasi oggetto che si intende terminare una lista è , per definizione, la lista vuota. Se si utilizza il numero 42 come terminatore dell'elenco, quindi () significa 42.

Matematicamente, ogni lista ha la lista vuota come suffisso (proprio come ogni set ha il set vuoto come sottoinsieme). Poiché la rappresentazione della lista Lisp è basata su suffissi (una lista non vuota è un riferimento a un oggetto che contiene il primo elemento e il suffisso di tale lista), ci deve essere qualcosa per gestire il caso quando una lista ha un solo elemento e il suo suffisso appropriato è (matematicamente) la lista vuota. Qualunque oggetto sia installato come il suffisso viene quindi inteso come la lista vuota, e per coerenza e unità, quell'oggetto deve essere usato meglio come rappresentazione della lista vuota autonoma, non solo come rappresentazione del vuoto suffisso dell'elenco di un elemento.

Questa potrebbe non essere una spiegazione specifica del linguaggio e un po 'anti-scientifica, ma potrebbe darti dei pensieri.

Potresti pensare alla lingua come a un insieme di tutti i fatti relativi al "mondo" o "universo" creato da quella lingua. Poiché questo è un set, è necessario disporre di un set di complementi per tutti i fatti esclusi dalla lingua, cioè qualcosa che significa "non in questo set". In alcune condizioni di luce nil (o false o altre varianti di "nullità" possono essere intese come "non in questo set"). Poiché il contro è uno degli elementi costitutivi fondamentali del linguaggio, l'atomo assunto per indicare il nulla viene utilizzato per qualsiasi valore non ancora creato. Quindi, non si termina la lista con una lista vuota (come si possono quindi terminare le liste vuote?), È solo ad un certo punto che non c'è nulla che il contro sta puntando e nil è il modo di dirlo.

Come hanno spiegato Rainer e Jerry, gli elenchi di Lisp sono costruiti da cons-cell, quindi non è veramente e lista vuota. Concettualmente è spesso utile pensare in questo modo quando si definiscono le funzioni ricorsive. È un po 'più ovvio se guardiamo la definizione del tipo di dati di List in (ad esempio) Haskell.

data List a = Cons a (List a)
            | Empty <<== nil in Lisp

Ciò che dice è che abbiamo una cella Cons con un elemento seguito da una coda o da una lista vuota. Quindi una lista di 1 elemento è (Cons 1 Empty). Questo è utile per definire funzioni ricorsive come la mappa.

map f (Cons e tail) = Cons (f e) (map f tail)
map f Empty = Empty

Quale in Lisp potrebbe essere

(defmethod fmap (f (lst cons))
  (cons (funcall f (car lst))
        (fmap f (cdr lst))))

(defmethod fmap (f (lst null))
  nil)

Quindi pensare concettualmente a un elenco come terminato dalla lista vuota può essere molto utile,