common-lisp
Tegens cellen en lijsten

Lijsten als een conventie

Sommige talen bevatten een lijst datastructuur. Common Lisp en andere talen in de Lisp-familie maken uitgebreid gebruik van lijsten (en de naam Lisp is gebaseerd op het idee van een LISt-processor). Common Lisp bevat echter geen primitief lijstgegevenstype. In plaats daarvan bestaan lijsten volgens afspraak. De conventie hangt af van twee principes:

1. Het symbool nul is de lege lijst.
2. Een niet-lege lijst is een tegenscel waarvan de auto het eerste element van de lijst is en wiens cdr de rest van de lijst is.

Dat is alles wat er is aan lijsten. Als u het voorbeeld met de naam Wat is een nadelencel hebt gelezen ? , dan weet je dat een nadelencel wiens auto X is en wiens cdr Y is, kan worden geschreven als (X. Y) . Dat betekent dat we een aantal lijsten kunnen schrijven op basis van de bovenstaande principes. De lijst met elementen 1, 2 en 3 is eenvoudig:

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

Omdat lijsten echter zo vaak voorkomen in de Lisp-talenfamilie, zijn er speciale afdrukconventies die verder gaan dan de eenvoudige gestippelde paarnotatie voor nadelencellen.

1. Het symbool nul kan ook worden geschreven als () .
2. Wanneer de cdr van de ene tegenscel een andere lijst is (of () of een tegenscel), wordt in plaats van de ene tegenscel met de gestippelde paarnotatie te schrijven, de "lijstnotatie" gebruikt.

De lijstnotatie wordt het duidelijkst weergegeven door verschillende voorbeelden:

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

Het idee is dat de elementen van de lijst in opeenvolgende volgorde tussen haakjes worden geschreven totdat de definitieve cdr in de lijst is bereikt. Als de laatste cdr nul is (de lege lijst), wordt de laatste haakjes geschreven. Als de laatste cdr niet nul is (in welk geval de lijst een onjuiste lijst wordt genoemd), wordt een punt geschreven en wordt die laatste cdr geschreven.

Wat is een nadelencel?

Een tegenscel, ook bekend als een gestippeld paar (vanwege de gedrukte weergave), is gewoon een paar van twee objecten. Een cel wordt voorzien door de functie cons en elementen in het paar geëxtraheerd met de functies car en cdr .

(cons "a" 4)

Dit retourneert bijvoorbeeld een paar waarvan het eerste element (dat met car kan worden geëxtraheerd) "a" is en waarvan het tweede element (dat met cdr kan worden geëxtraheerd) 4 .

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

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

Nadelen cellen kunnen worden afgedrukt in een gestippelde paarnotatie:

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

Tegenscellen kunnen ook worden gelezen in de stippelparennotatie, zodat dat

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

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

(De afgedrukte vorm van nadelencellen kan ook een beetje ingewikkelder zijn. Zie het voorbeeld over nadelencellen als lijsten voor meer informatie.)

Dat is het; nadelen cellen zijn slechts paren van elementen gecreëerd door de functie cons , en de elementen kunnen worden geëxtraheerd met car en cdr . Vanwege hun eenvoud kunnen nadelencellen een nuttige bouwsteen zijn voor complexere gegevensstructuren.

Cons cellen schetsen

Om de semantiek van conses en lijsten beter te begrijpen, wordt vaak een grafische weergave van dit soort structuren gebruikt. Een nadelencel wordt meestal weergegeven met twee contactvakken, die twee pijlen bevatten die naar de car en cdr waarden wijzen, of direct de waarden. Bijvoorbeeld het resultaat van:

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

kan worden weergegeven met een van deze tekeningen:

Merk op dat deze voorstellingen zijn louter conceptueel en niet geven van het feit dat de waarden zijn opgenomen in de cel, of zijn gericht uit de cel: in het algemeen, dit is afhankelijk van de uitvoering, het type van de waarden, het niveau van de optimalisatie, etc In de rest van het voorbeeld gebruiken we de eerste soort tekening, die vaker wordt gebruikt.

Dus bijvoorbeeld:

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

wordt weergegeven als:

terwijl:

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

wordt weergegeven als:

Hier is een boomachtige structuur:

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

Het laatste voorbeeld laat zien hoe deze notatie ons kan helpen om belangrijke semantische aspecten van de taal te begrijpen. Eerst schrijven we een uitdrukking vergelijkbaar met de vorige:

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

die op de gebruikelijke manier kan worden weergegeven als:

Vervolgens schrijven we een andere uitdrukking, die blijkbaar equivalent is aan de vorige, en dit lijkt bevestigd door een gedrukte weergave van het resultaat:

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

Maar als we het diagram tekenen, kunnen we zien dat de semantiek van de uitdrukking anders is, omdat dezelfde cel de waarde is van zowel het car onderdeel als het cdr deel van de buitenste cons (dit is, cell-a wordt gedeeld ) :

en het feit dat de semantiek van de twee resultaten daadwerkelijk verschilt op taalniveau, kan worden geverifieerd door de volgende tests:

(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)

De eerste eq is onwaar omdat de car en cdr van c1 structureel gelijk zijn (dat is waar door equal ), maar niet "identiek" zijn (dwz "dezelfde gedeelde structuur"), terwijl in de tweede test het resultaat waar is omdat de car en cdr van c2 zijn identiek , dat wil zeggen dat ze dezelfde structuur hebben .