Lisp/Liste

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search
Indice del libro

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[modifica]

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