common-lisp
Contro le celle e le liste

Elenca come una convenzione

Alcune lingue includono una struttura di dati dell'elenco. Common Lisp e altri linguaggi della famiglia Lisp fanno ampio uso di elenchi (e il nome Lisp è basato sull'idea di un processore LISt). Tuttavia, Common Lisp non include effettivamente un tipo di dati di elenco primitivo. Invece, le liste esistono per convenzione. La convenzione dipende da due principi:

1. Il simbolo nil è la lista vuota.
2. Una lista non vuota è una cella contro la cui auto è il primo elemento della lista e il cui cdr è il resto della lista.

Questo è tutto ciò che c'è da elencare. Se hai letto l'esempio chiamato What is a cons cell? , quindi sai che una cella contro la cui auto è X e il cui cdr è Y può essere scritto come (X. Y) . Ciò significa che possiamo scrivere alcune liste in base ai principi sopra riportati. L'elenco degli elementi 1, 2 e 3 è semplicemente:

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

Tuttavia, poiché gli elenchi sono così comuni nella famiglia di lingue Lisp, esistono convenzioni di stampa speciali oltre la semplice notazione a coppie puntate per le cellule cons.

1. Il simbolo nil può anche essere scritto come () .
2. Quando il cdr di una cella di controllo è un'altra lista (o () o una cella di controllo), invece di scrivere la cella di una contro con la notazione a coppie puntate, viene utilizzata la "notazione elenco".

La notazione elenco è mostrata più chiaramente da diversi esempi:

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

L'idea è che gli elementi della lista siano scritti in ordine successivo tra parentesi finché non viene raggiunto il cdr finale nella lista. Se il cdr finale è nullo (la lista vuota), viene scritta la parentesi finale. Se il cdr finale non è nullo (nel qual caso l'elenco è chiamato elenco errato ), viene scritto un punto e quindi viene scritto quel cdr finale.

Cos'è una cella di controllo?

Una cella contro, nota anche come coppia puntata (a causa della sua rappresentazione stampata), è semplicemente una coppia di due oggetti. Una contro cella viene creata dalla funzione cons , e gli elementi nella coppia vengono estratti usando le funzioni car e cdr .

(cons "a" 4)

Ad esempio, questo restituisce una coppia il cui primo elemento (che può essere estratto con car ) è "a" , e il cui secondo elemento (che può essere estratto con cdr ) è 4 .

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

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

Le celle Contro possono essere stampate in notazione a coppie punteggiate :

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

Le celle Contro possono anche essere lette in notazione a coppie punteggiate, così che

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

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

(Anche la forma stampata delle celle contro può essere un po 'più complicata. Per ulteriori informazioni, vedi l'esempio delle celle contro come liste.)

Questo è tutto; le celle contro sono solo coppie di elementi creati dalla funzione cons , e gli elementi possono essere estratti con car e cdr . A causa della loro semplicità, le celle contro possono essere un elemento utile per strutture di dati più complesse.

Abbozzando le contro cellule

Per comprendere meglio la semantica di consoli e liste, viene spesso utilizzata una rappresentazione grafica di questo tipo di strutture. Una cella contro è solitamente rappresentata con due caselle in contatto, che contengono due frecce che indicano i valori della car e del cdr , o direttamente i valori. Ad esempio, il risultato di:

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

può essere rappresentato con uno di questi disegni:

Si noti che queste rappresentazioni sono puramente concettuali e non indicano il fatto che i valori siano contenuti nella cella o siano puntati dalla cella: in generale ciò dipende dall'implementazione, dal tipo di valori, dal livello di ottimizzazione, ecc. Nel resto dell'esempio useremo il primo tipo di disegno, che è quello più comunemente usato.

Quindi, ad esempio:

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

è rappresentato come:

mentre:

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

è rappresentato come:

Ecco una struttura ad albero:

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

L'ultimo esempio mostra come questa notazione può aiutarci a capire aspetti della semantica importanti della lingua. Per prima cosa, scriviamo un'espressione simile alla precedente:

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

che può essere rappresentato nel solito modo come:

Quindi, scriviamo un'espressione diversa, che è apparentemente equivalente alla precedente, e questo sembra confermato dalla rappresentazione stampata del risultato:

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

Ma, se disegniamo il diagramma, possiamo vedere che la semantica dell'espressione è diversa, poiché la stessa cella è il valore sia della parte car parte cdr dei cons esterni (questa è, cell-a è condivisa ) :

e il fatto che la semantica dei due risultati sia effettivamente diversa a livello di linguaggio può essere verificata con i seguenti 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)

Il primo eq è falso poiché l' car e il cdr di c1 sono strutturalmente uguali (che è vero per equal ), ma non sono "identici" (cioè "la stessa struttura condivisa"), mentre nel secondo test il risultato è vero poiché il car e cdr di c2 sono identici , cioè sono la stessa struttura .