È una lista vuota in Lisp costruita da una cella di controllo?

Question

Sto cercando di emulare un elenco simile a Lisp in JavaScript (solo un esercizio senza alcun motivo pratico), ma sto cercando di capire come rappresentare al meglio una lista vuota.

È una lista vuota solo un valore nil o è sotto il cofano memorizzato in una cella di controllo?

posso:

(car '()) 
NIL 
(cdr '()) 
NIL 

ma una lista vuota di sicuro non può essere (cons nil nil), perché sarebbe indistinguibile da un elenco memorizzare un singolo nil. Dovrebbe memorizzare qualche altro valore speciale.

D'altra parte, se una lista vuota non viene costruita da una cella di controllo, sembra impossibile disporre di un'interfaccia di alto livello coerente per l'aggiunta di un singolo valore a un elenco esistente. Una funzione del tipo:

(defun append-value (list value) ... 

Modificherebbe il suo argomento, ma solo se non è una lista vuota, che sembra brutta.

Answer 1

Una lista vuota è semplicemente il simbolo nil (e i simboli, per definizione, non sono consessi). car e cdr sono definiti per restituire nil se fornito nil.

Per quanto riguarda le funzioni di lista-mutazione, restituiscono un valore che si suppone debba riassegnare alla variabile. Ad esempio, guarda le specifiche per la funzione nreverse: può modificare la lista data o no, e tu dovresti usare il valore restituito, e non fare affidamento su di esso per essere modificato sul posto.

Anche nconc, la quintessenziale funzione di aggiunta distruttiva, funziona in questo modo: il suo valore di ritorno è l'elenco aggiunto che si suppone utilizzi. È è specificato per modificare gli elenchi dati (tranne l'ultimo) sul posto, ma se lo si dà nil come primo argomento, non può essere modificato molto bene, quindi è ancora necessario utilizzare il valore restituito.

Answer 2

provare con l'interprete Lisp:

(eq nil '()) 
=> t 

Diverse operazioni sono speciali prima lettera maiuscola per fare unorthogonal (o anche curiosi cose :-) quando si opera su nil/una lista vuota. Il comportamento di car e cdr che stavi investigando è una di quelle cose.

L'idenità di nil come elenco vuoto è una delle prime cose che si apprendono su Lisp. Ho provato a trovare un buon hit di Google, ma ne selezionerò uno perché ce ne sono così tanti: http://www.cs.sfu.ca/CourseCentral/310/pwfong/Lisp/1/tutorial1.html

Answer 3

Che ci crediate o meno, questa è in realtà una questione religiosa.

Ci sono dialetti a cui la gente osa riferirsi come una sorta di Lisp in cui le liste vuote sono consi o oggetti aggregati di qualche tipo, piuttosto che un semplice atomo come nil.

Ad esempio, in "MatzLisp" (meglio noto come Ruby) gli elenchi sono in realtà matrici.

In NewLisp, gli elenchi sono contenitori: oggetti di tipo elenco che contengono un elenco collegato degli elementi, quindi gli elenchi vuoti sono contenitori vuoti.[Reference].

Nei linguaggi Lisp che non sono spettacolari senza cluster di questo tipo, le liste vuote sono atomi e le liste non vuote sono celle binarie con un campo che contiene il primo elemento e un altro campo che contiene il resto del elenco. Le liste possono condividere suffissi. Dato un elenco come (1 2 3), possiamo utilizzare cons per creare (a 1 2 3) e (b c 1 2 3) che condividono entrambi lo spazio di archiviazione per (1 2 3).

(In ANSI Common Lisp, l'elenco atomo vuota () è lo stesso oggetto come il simbolo nil, che valuta se stessa e serve anche come booleano falso. Nello schema, () non è un simbolo, ed è distinto dal Boolean false #f oggetto. Tuttavia liste regime sono sempre costituita da coppie, e terminato da un atomo.)

la capacità di valutare (car nil) non segue automaticamente dalla rappresentazione cons-e-nil di liste, e se guardiamo nell'antica documentazione Lisp, come il manuale Lisp 1.5 dei primi anni del 1960, qualcosa, scopriremmo che era assente. Inizialmente, car era strettamente un modo per accedere a un campo della cella di controllo e richiedeva rigorosamente un argomento di cella di controllo.

Le buone idee come consentendo (car nil) a Just Work (in modo che gli hacker potrebbero tagliare molte righe di codice inutili dai loro programmi) non appariva durante la notte. L'idea di consentire (car nil) potrebbe essere stata visualizzata da InterLisp. In ogni caso, la rivista Evolution Of Lisp afferma che MacLisp (uno degli importanti predecessori di Common Lisp, non correlato a Apple Macintosh che venne vent'anni dopo), imitò questa funzione da InterLisp (un altro dei predecessori significativi).

piccoli dettagli come questo fanno la differenza tra piacevole programmazione e giurando sul monitor: si veda ad esempio A Short Ballad Dedicated to the Growth of Programs ispirato lotta di un programmatore Lisp con un dialetto bletcherous in cui le liste vuote non è possibile accedere con car, e non servono da booleano falso.

Answer 4

NIL è un po 'una bestia strana in Common Lisp, perché

• È un simbolo (il che significa che symbolp rendimenti T)
• è una lista
• non è una cella di cons (consp rendimenti NIL)
• potete prendere CAR e CDR di esso comunque

Si noti che le ragioni alla base di questo sono probabilmente anche storiche e non si dovrebbe pensare che questa sia l'unica soluzione ragionevole. Altri dialoghi Lisp hanno fatto scelte diverse.