Cons (funzione)

In informatica, cons è una funzione fondamentale dei dialetti Lisp. Essa costruisce (in inglese construct) in memoria oggetti contenenti due valori o puntatori a valore. Questi oggetti vengono chiamati celle cons, coppie cons o semplicemente cons.

Nel gergo Lisp, l'espressione "fare il cons di x su y" significa costruire un nuovo oggetto tramite (cons x y). L'oggetto risultante è una coppia, la cui metà sinistra è indicata con car (il primo elemento) e la metà destra (il secondo elemento) con cdr.

Questa funzione è legata alla nozione di costruttore presente nella programmazione orientata agli oggetti, che crea un nuovo oggetto a partire da alcuni argomenti, e, più da vicino, è legata alla funzione costruttore dei sistemi a tipo dati algebrico.

La parola "cons" e l'espressione "fare il cons su" vengono anche utilizzate più genericamente nel gergo della programmazione funzionale. A volte operatori che compiono una funzione simile, specialmente quando si lavora con le liste, sono pronunciati "cons". Un esempio è l'operatore :: del linguaggio ML, che aggiunge un elemento all'inizio di una lista.

Utilizzo

Sebbene le celle cons possano essere utilizzate per implementare coppie ordinate di dati, vengono più comunemente usate per costruire strutture dati più complesse, specialmente liste concatenate e alberi binari.

Per esempio, l'espressione Lisp (cons 1 2) costruisce una cella contenente 1 nella sua metà sinistra (il cosiddetto campo car) e 2 nella sua metà destra (il cosiddetto campo cdr). Nella notazine Lisp, il valore (cons 1 2) viene mostrato come:

(1 . 2)

Liste

In Lisp, le liste vengono implementate a partire dalle coppie cons. Più specificamente, ogni struttura lista in Lisp può essere:

1. o una lista vuota, cioè un oggetto speciale solitamente chiamato nil,
2. o una cella cons, il cui car è il primo elemento della lista e il cui cdr è la lista contenente il resto degli elementi.

Illustrazione delle celle cons della lista (42 69 613)

Ciò fornisce le fondamenta per una semplice struttura lista singolarmente concatenata, il cui contenuto può essere manipolato tramite cons, car e cdr. Si noti che nil è l'unica lista che non è al tempo stesso una coppia cons. Per esempio, si consideri una lista i cui elementi sono 1, 2 e 3. Questa lista può essere creata in tre passi:

1. cons di 3 su nil, la lista vuota
2. cons di 2 sul risultato
3. cons di 1 sul risultato

che è equivalente alla singola espressione:

(cons 1 (cons 2 (cons 3 nil)))

o alla sua abbreviazione:

(list 1 2 3)

Il valore risultante è la lista:

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

cioè

 *--*--*--nil
 |  |  |
 1  2  3

generalmente abbreviata come:

(1 2 3)

Quindi, cons può essere utilizzato per aggiungere un elemento all'inizio di una lista concatenata già esistente. Per esempio, se x è la lista sopra definita, allora (cons 5 x) produrrà la lista:

(5 1 2 3)

Un'altra utile procedura per operare con le liste è append, che concatena due liste esistenti (cioè combina due liste in una singola lista).

Alberi

Anche gli alberi binari, che conservano i dati nelle proprie foglie, sono facilmente costruibili tramite la funzione cons. Per esempio, il codice:

(cons (cons 1 2) (cons 3 4))

crea l'albero:

((1 . 2) . (3 . 4))

cioè

   *
  / \
 *   *
/ \ / \
1 2 3 4

Tecnicamente, la lista (1 2 3) dell'esempio precedente è anch'essa un albero binario, ma particolarmente non bilanciato. Infatti, si può riordinare il diagramma:

 *--*--*--nil
 |  |  |
 1  2  3

nel seguente modo equivalente:

   *
  / \
 1   *
    / \
   2   *
      / \
     3  nil

Uso colloquiale

Il termine cons è entrato a far parte del gergo tecnico informatico e, a volte, viene anche usato nelle conversazioni, specialmente presso l'università del MIT.

Non indispensabilità

Dato che il Lisp possiede funzioni di prima classe (cioè funzioni che possono essere passate come parametri ad altre funzioni e possono essere restituite come valori di ritorno da altre funzioni), tutte le strutture dati, comprese le celle cons, non sono indispensabili al linguaggio, potendo essere implementate attraverso l'utilizzo di funzioni. Per esempio, il seguente codice Scheme:

 (define (cons x y)
   (lambda (m) (m x y)))
 (define (car z)
   (z (lambda (p q) p)))
 (define (cdr z)
   (z (lambda (p q) q)))

implementa gli operatori cons, car e cdr usando una funzione come "cella cons". Questo è il modo usuale di creare strutture dati nel lambda calcolo puro, un modello di computazione teorico astratto che è legato da vicino allo Scheme.

Questa implementazione, nonostante sia interessante dal punto di vista teorico, non ha però interessi pratici, in quanto rende le celle cons indistinguibili dalle ordinarie procedure Scheme, oltre ad introdurre inutili inefficienze computazionali.

Voci correlate

• Lisp
• Car e cdr