common-lisp
Nackdelar och listor

Listor som en konvention

Vissa språk innehåller en listadatasstruktur. Vanliga Lisp och andra språk i Lisp-familjen använder sig av listor (och namnet Lisp bygger på idén om en LISt-processor). Men Common Lisp inkluderar faktiskt inte en primitiv datatyp. I stället finns listor enligt konvention. Konventet beror på två principer:

1. Symbolen noll är den tomma listan.
2. En icke tom lista är en nackdelar vars bil är det första elementet i listan och vars cdr är resten av listan.

Det är allt som finns i listor. Om du har läst exemplet som heter What is a cons cell? , då vet du att en nackcell vars bil är X och vars cdr är Y kan skrivas som (X. Y) . Det betyder att vi kan skriva några listor baserade på principerna ovan. Listan över elementen 1, 2 och 3 är helt enkelt:

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

Eftersom listor är så vanliga i Lisp-språkfamiljen finns det dock speciella utskriftskonventioner utöver den enkla prickade parnotationen för nackceller.

1. Symbolen noll kan också skrivas som () .
2. När cdr för en cons-cell är en annan lista (antingen () eller en cons-cell), istället för att skriva en cons-cellen med den prickade parnotationen, används "listnotation".

Listnotationen visas tydligast av flera exempel:

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

Tanken är att elementen i listan skrivs i successiv ordning inom parentes tills den sista cdr i listan har nåtts. Om den sista cdr är noll (den tomma listan) skrivs den slutliga parentesen. Om den sista cdr inte är noll (i vilket fall listan kallas en otillbörlig lista ), skrivs en punkt och sedan skrivs den sista cdr.

Vad är en nackdel cell?

En nackcell, även känd som ett prickat par (på grund av dess tryckta representation), är helt enkelt ett par av två objekt. En cons cell skapas av funktions cons och elementen i paret extraheras med hjälp av funktioner car och cdr .

(cons "a" 4)

Till exempel returnerar detta ett par vars första element (som kan extraheras med car ) är "a" och vars andra element (som kan extraheras med cdr ) är 4 .

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

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

Nackdelar kan skrivas ut med prickade parnotation:

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

Nackdelar celler kan också läsas i prickade par notation, så att

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

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

(Den tryckta formen för nackceller kan också vara lite mer komplicerad. För mer om detta, se exemplet om nackceller som listor.)

Det är allt; nackdelar celler är bara par av element skapade av funktionen cons , och elementen kan extraheras med car och cdr . På grund av deras enkelhet kan nackceller vara en användbar byggsten för mer komplexa datastrukturer.

Skissar nackceller

För att bättre förstå semantiken för konser och listor används ofta en grafisk representation av denna typ av strukturer. En nackdel representeras vanligtvis med två rutor i kontakt, som innehåller antingen två pilar som pekar på car och cdr värdena eller direkt värdena. Till exempel resultatet av:

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

kan representeras med en av dessa ritningar:

Observera att dessa representationer är rent konceptuellt, och inte beteckna det faktum att värdena återfinns i cellen, eller pekas från cellen: i allmänhet detta beror på genomförandet, vilken typ av värdena, graden av optimering, etc I resten av exemplet kommer vi att använda den första typen av ritning, som är den som oftast används.

Så, till exempel:

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

representeras som:

medan:

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

representeras som:

Här är en trädliknande struktur:

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

Det sista exemplet visar hur denna notation kan hjälpa oss att förstå viktiga semantikaspekter på språket. Först skriver vi ett uttryck som liknar det föregående:

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

som kan representeras på vanligt sätt som:

Sedan skriver vi ett annat uttryck, vilket tydligen motsvarar det föregående, och detta verkar bekräftas av tryckt framställning av resultatet:

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

Men om vi ritar diagrammet kan vi se att uttryckets semantik är annorlunda, eftersom samma cell är värdet både på car och cdr delen av den yttre cons (detta är, cell-a delas ) :

och att de två resultatens semantik faktiskt skiljer sig på språknivå kan verifieras med följande test:

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

Den första eq är falsk eftersom car och cdr för c1 är strukturellt lika (det är sant med equal ), men är inte "identiska" (dvs "samma delade struktur"), medan resultatet i det andra testet är sant eftersom car och cdr för c2 är identiska , det vill säga att de är samma struktur .