Ich versuche Lisp-ähnliche Listen in JavaScript zu emulieren (nur eine Übung ohne praktischen Grund), aber ich habe Mühe herauszufinden, wie man eine leere Liste am besten darstellt.
Ist eine leere Liste nur ein nil -Wert oder ist sie unter der Haube in einer Cons-Zelle gespeichert?
Ich kann:
%Vor% aber eine leere Liste kann sicher nicht (cons nil nil) sein, da sie nicht von einer Liste zu unterscheiden wäre, in der ein einzelnes nil gespeichert ist. Es müsste einen anderen speziellen Wert speichern.
Wenn andererseits eine leere Liste nicht aus einer Cons-Zelle aufgebaut wird, scheint es unmöglich zu sein, eine konsistente High-Level-Schnittstelle zum Anhängen eines einzelnen Wertes an eine bestehende Liste zu haben. Eine Funktion wie:
%Vor%würde sein Argument ändern, aber nur, wenn es keine leere Liste ist, was hässlich erscheint.
Eine leere Liste ist einfach das Symbol% co_de% (und Symbole sind definitionsgemäß keine Conse). nil und car sind so definiert, dass cdr zurückgegeben wird, wenn nil angegeben wird.
Wie bei Listen-Mutationsfunktionen geben sie einen Wert zurück, den Sie Ihrer Variablen zuweisen sollen. Betrachten Sie zum Beispiel die Spezifikation für die Funktion nil : Sie kann die angegebene Liste ändern oder nicht, und Sie sollten den Rückgabewert verwenden und nicht darauf vertrauen, dass er direkt geändert wird.
Sogar nreverse , die grundlegende Destruktiv-Append-Funktion, funktioniert so: seine Rückgabewert ist die angehängte Liste, die Sie verwenden sollen. It ist angegeben, um die angegebenen Listen (außer der letzten) an Ort und Stelle zu ändern, aber wenn Sie nconc als erstes Argument angeben, kann es das nicht sehr gut ändern, also Sie immer noch muss den Rückgabewert verwenden.
Es gibt Dialekte, die man als eine Art Lisp zu bezeichnen wagt, bei der leere Listen Cones oder Aggregationsobjekte irgendeiner Art sind und nicht nur ein Atom wie nil .
Zum Beispiel sind in "MatzLisp" (besser Ruby genannt) Listen Arrays.
In NewLisp sind Listen Container: Objekte vom Listentyp, die eine verkettete Liste der Elemente enthalten, also leere Listen sind leere Container. [Referenz] .
In Lisp-Sprachen, die keine spektakulären Cluster-Fumbles dieser Art sind, sind leere Listen Atome, und nicht leere Listen sind binäre Zellen mit einem Feld, das das erste Element enthält, und einem anderen Feld, das den Rest der Liste enthält . Listen können Suffixe verwenden. Bei einer Liste wie (1 2 3) können wir cons verwenden, um (a 1 2 3) und (b c 1 2 3) zu erstellen, die beide den Speicher für (1 2 3) teilen.
(In ANSI Common Lisp ist das leere Listenatom () dasselbe Objekt wie das Symbol% co_de%, das sich selbst berechnet und auch als Boolean false dient. In Schema ist nil kein Symbol. und unterscheidet sich von dem Booleschen falschen Objekt () . Schema-Listen bestehen jedoch immer noch aus Paaren und enden mit einem Atom.)
Die Möglichkeit, #f auszuwerten, ergibt sich nicht automatisch aus der Liste der Cons-und-Nil-Darstellungen, und wenn wir alte Lisp-Dokumente wie das Lisp 1.5-Handbuch von Anfang 1960 betrachten, werden wir das finden das war nicht vorhanden. Anfangs war (car nil) genau eine Möglichkeit, auf ein Feld der Cons-Zelle zuzugreifen, und erforderte streng ein Cons-Cell-Argument.
Gute Ideen, wie car auf Just Work zu setzen (damit Hacker viele nutzlose Codezeilen aus ihren Programmen entfernen konnten), erschienen nicht über Nacht. Die Idee, (car nil) zuzulassen, ist möglicherweise von InterLisp gekommen. In jedem Fall behauptet Evolution Of Lisp Papier, dass MacLisp (einer der wichtigen Vorgänger von Common Lisp, nicht verwandt mit dem Apple Macintosh, der zwanzig Jahre später kam), dieses Feature von InterLisp (einem anderen der bedeutende Vorgänger).
Kleine Details wie diese machen den Unterschied zwischen angenehmer Programmierung und Fluchen auf dem Monitor: siehe zum Beispiel Eine kurze Ballade, die dem Wachstum von Programmen gewidmet ist , inspiriert durch den Kampf eines Lisp-Programmierers mit einem bretcherischen Dialekt, in dem leere Listen nicht mit (car nil) aufgerufen werden können und nicht als boolescher false dienen .
NIL ist in Common Lisp etwas seltsam, weil
symbolp T zurückgibt) consp gibt NIL zurück) CAR und CDR davon trotzdem übernehmen Beachten Sie, dass die Gründe dafür wahrscheinlich auch historisch sind und Sie sollten nicht denken, dass dies die einzig vernünftige Lösung ist. Andere Lisp-Dialekte haben unterschiedliche Entscheidungen getroffen.
Versuchen Sie es mit Ihrem Lisp-Interpreter:
%Vor% Mehrere Operationen sind speziell für unorthogonale (oder sogar merkwürdige :-) Dinge, wenn sie in nil / einer leeren Liste arbeiten. Das Verhalten von car und cdr , das Sie untersucht haben, ist eines dieser Dinge.
Die Identität von nil als leere Liste ist eines der ersten Dinge, die Sie über Lisp lernen. Ich habe versucht, einen guten Google-Treffer zu erzielen, aber ich wähle nur einen aus, weil es so viele gibt: Ссылка