Lisp/Liste

Il Lisp si basa sul concetto di elaborazione delle liste, infatti il nome Lisp deriva da "List Processor".

Una lista è un insieme di celle chiamate cons, ovvero una struttura di nodi collegati in modo sequenziale che possono essere a N livelli.

È importantissimo capire come funziona la struttura di una lista!

Esempio di lista vuota:

( ) --> apertaparentesi+chiusaparentesi significa lista vuota e corrisponde al simbolo: nil .
La struttura interna di questa lista è rappresentata dal simbolo: nil .

Esempio di lista con un solo elemento (un nodo):

(nome) --> è una lista formata da un solo elemento, un simbolo che abbiamo chiamato nome.
La medesima lista si può scrivere anche cosi: (nome . nil).

La struttura interna della lista in questione può essere schematizzata nel seguente modo:

 nodo:0
+---+---+
|car|cdr+-----> nil
+-|-+---+
  | 
  v
nome

Esempio di lista con due elementi (due nodi):

(nome cognome) --> è una lista formata da due elementi, due simboli che abbiamo chiamato nome e cognome.

La medesima lista si può scrivere anche cosi: (nome . (cognome . nil)).

La struttura interna della lista in questione può essere schematizzata nel seguente modo:

 nodo:0         nodo:1
+---+---+      +---+---+
|car|cdr+----->|car|cdr+-----> nil
+-|-+---+      +-|-+---+
  |              |
  v              v
nome           cognome

Esempio di lista composta da due liste (struttura a due livelli):

(nome cognome (località provincia)) --> è una lista composta da due liste contenenti due simboli ciascuna, e nel primo livello un link (nodo:2) che fa da puntatore alla seconda lista (nodo:3 - 4).

Infatti nel primo livello gli elementi sono 3, mentre nel secondo livello gli elementi sono 2!

La struttura interna della lista in questione può essere schematizzata nel seguente modo:

 nodo:0         nodo:1         nodo:2
+---+---+      +---+---+      +---+---+
|car|cdr+----->|car|cdr+----->|car|cdr+-----> nil
+-|-+---+      +-|-+---+      +-|-+---+
  |              |              |
  v              v              |
nome           cognome          v nodo:3         nodo:4
                                +---+---+      +---+---+
                                |car|cdr+----->|car|cdr+-----> nil
                                +-|-+---+      +-|-+---+
                                  |              |
                                  v              v
                                località        provincia

Ogni nodo di una lista corrisponde a una cella di memoria chiamata CONS.

Ogni cons contiene internamente sempre due valori: un valore chiamato car e un valore chiamato cdr.

La funzione car restituisce sempre il primo elemento di una lista, sia esso un simbolo o una lista:

 >('''car''' '()) => nil
 >('''car''' '(uno)) => uno
 >('''car''' '(uno due tre)) => uno
 >('''car''' '((uno) due tre)) => (uno)

La funzione cdr invece restituisce sempre il resto della lista racchiuso fra parentesi:

 >('''cdr''' '()) => nil
 >('''cdr''' '(uno)) => nil
 >('''cdr''' '(uno due tre)) => (due tre)
 >('''cdr''' '(uno (due tre))) => ((due tre))

N.B. quasi tutto in Lisp viene rappresentato attraverso le liste!

Ora proviamo a scrivere alcuni comandi direttamente nell'interprete Lisp:

 >('''car''' '(nome cognome (località provincia)))
 >nome
 
 >('''cdr''' '(nome cognome (località provincia)))
 >(cognome (località provincia))
 
 >('''car''' ('''cdr''' '(nome cognome (località provincia))))
 >cognome
 
 >('''cdr''' ('''cdr''' '(nome cognome (località provincia))))
 >((località provincia))
 
 >('''car''' ('''cdr''' ('''cdr''' '(nome cognome (località provincia)))))
 >(località provincia)
 
 >('''car''' ('''car''' ('''cdr''' ('''cdr''' '(nome cognome (località provincia))))))
 >località

N.B. L' apostrofo serve per passare una costante letterale o strutturata ().

Manipoliamo le liste

(0(1 2 3)(4 5)6(7 8)9)