common-lisp
Cons Zellen und Listen

Listet als Konvention auf

Einige Sprachen enthalten eine Listendatenstruktur. Common Lisp und andere Sprachen der Lisp-Familie verwenden Listen umfassend (und der Name Lisp basiert auf der Idee eines LISt-Prozessors). Common Lisp enthält jedoch keinen primitiven Listendatentyp. Stattdessen existieren Listen nach Konvention. Die Konvention hängt von zwei Prinzipien ab:

1. Das Symbol Null ist die leere Liste.
2. Eine nicht leere Liste ist eine Cons-Zelle, deren Auto das erste Element der Liste ist und deren cdr der Rest der Liste ist.

Das ist alles, was Listen gibt. Wenn Sie das Beispiel " Was ist eine Nachteile-Zelle" gelesen haben ? Dann wissen Sie, dass eine Cons-Zelle, deren Auto X ist und deren Cdr Y ist, als (X, Y) geschrieben werden kann . Das bedeutet, dass wir einige Listen auf der Grundlage der obigen Prinzipien erstellen können. Die Liste der Elemente 1, 2 und 3 ist einfach:

(1 . (2 . (3 . nil)))

Da Listen jedoch in der Lisp-Sprachfamilie so häufig vorkommen, gibt es spezielle Druckkonventionen, die über die einfache Punkt-Paar-Notation für Cons-Zellen hinausgehen.

1. Das Symbol Null kann auch als () geschrieben werden .
2. Wenn die cdr einer Cons-Zelle eine andere Liste ist (entweder () oder eine Cons-Zelle), wird anstelle der Ein-Cons-Zelle mit der Notation mit gepunkteten Paaren die "Listennotation" verwendet.

Die Listennotation wird am deutlichsten durch mehrere Beispiele gezeigt:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

Die Idee ist, dass die Elemente der Liste in aufeinanderfolgender Reihenfolge in Klammern geschrieben werden, bis die endgültige CD-ROM in der Liste erreicht ist. Wenn die letzte cdr null ist (die leere Liste), wird die letzte Klammer geschrieben. Wenn die letzte CD nicht Null ist (in diesem Fall wird die Liste als unzulässige Liste bezeichnet ), wird ein Punkt geschrieben, und dann wird die letzte CD geschrieben.

Was ist eine Nachteile Zelle?

Eine Cons-Zelle, auch bekannt als gepunktetes Paar (aufgrund ihrer gedruckten Darstellung), ist einfach ein Paar von zwei Objekten. Eine cons-Zelle wird von der Funktion cons , und Elemente im Paar werden mit den Funktionen car und cdr extrahiert.

(cons "a" 4)

Zum Beispiel wird ein Paar zurückgegeben, dessen erstes Element (das mit car extrahiert werden kann) "a" ist und dessen zweites Element (das mit cdr extrahiert werden kann) 4 .

(car (cons "a" 4))
;;=> "a"

(cdr (cons "a" 4))
;;=> 3

Cons-Zellen können in gepunkteter Schreibweise gedruckt werden:

(cons 1 2)
;;=> (1 . 2)

Cons-Zellen können auch in gepunkteter Schreibweise gelesen werden

(car '(x . 5))
;;=> x

(cdr '(x . 5))
;;=> 5

(Die gedruckte Form von cons-Zellen kann auch etwas komplizierter sein. Weitere Informationen finden Sie im Beispiel über cons-Zellen als Listen.)

Das ist es; cons-Zellen sind nur Elementpaare, die von der Funktion cons , und die Elemente können mit car und cdr extrahiert werden. Aufgrund ihrer Einfachheit können cons-Zellen ein nützlicher Baustein für komplexere Datenstrukturen sein.

Skizzieren von Nachteile

Um die Semantik von Konses und Listen besser zu verstehen, wird häufig eine grafische Darstellung dieser Art von Strukturen verwendet. Eine Cons-Zelle wird normalerweise mit zwei Kästen in Kontakt dargestellt, die entweder zwei Pfeile enthalten, die auf die car und cdr Werte zeigen, oder direkt die Werte. Zum Beispiel das Ergebnis von:

(cons 1 2)   
;; -> (1 . 2)

kann mit einer dieser Zeichnungen dargestellt werden:

Beachten Sie, dass diese Darstellungen rein begrifflicher sind, und bezeichnen nicht die Tatsache , dass die Werte in die Zelle enthalten sind, oder aus der Zelle zeigen: im Allgemeinen dies hängt von der Implementierung, die Art des Wertes, die Höhe der Optimierung, usw. Im Rest des Beispiels verwenden wir die erste Art der Zeichnung, die häufiger verwendet wird.

So zum Beispiel:

(cons 1 (cons 2 (cons 3 4)))   ; improper “dotted” list
;; -> (1 2 3 . 4)

wird dargestellt als:

während:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

wird dargestellt als:

Hier ist eine baumartige Struktur:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

Das letzte Beispiel zeigt, wie diese Notation uns helfen kann, wichtige semantische Aspekte der Sprache zu verstehen. Zuerst schreiben wir einen Ausdruck, der dem vorigen ähnlich ist:

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

das kann wie üblich dargestellt werden als:

Dann schreiben wir einen anderen Ausdruck, der offensichtlich dem vorherigen entspricht, und dies scheint durch die gedruckte Darstellung des Ergebnisses bestätigt zu werden:

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

Wenn wir jedoch das Diagramm zeichnen, können wir sehen, dass die Semantik des Ausdrucks unterschiedlich ist, da dieselbe Zelle den Wert sowohl des car als auch des cdr Teils der äußeren cons (das heißt, cell-a wird geteilt ) ist. :

und die Tatsache, dass sich die Semantik der beiden Ergebnisse tatsächlich auf der Sprachebene unterscheidet, kann durch folgende Tests überprüft werden:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

Der erste eq ist falsch, da car und cdr von c1 strukturell gleich sind (d. H. Durch equal wahr ), aber nicht "identisch" sind (dh "dieselbe gemeinsame Struktur"), während im zweiten Test das Ergebnis seit dem wahr ist car und cdr von c2 sind identisch , das heißt, sie haben dieselbe struktur .