Le radici del Lisp

Questo post è una traduzione di "The Roots of Lisp" di Paul Graham.

Nel 1960 John McCarthy pubblicò un eccezionale articolo in cui fece per la programmazione qualcosa di simile a quello che Euclide fece per la geometria. 1 Egli mostrò come costruire, data una manciata di semplici operatori e una notazione per le funzioni, un intero linguaggio di programmazione. Chiamò questo linguaggio Lisp da "List Processing", poiché una delle idee chiave fu di usare una semplice struttura dati chiamata lista sia per il codice sia per i dati.

Vale la pena capire ciò che scoprì McCarthy non solo in quanto pietra miliare della storia dell'Informatica, ma come modello di quello che la programmazione diventerà pian piano. Mi sembra infatti che siano esistiti due modelli di programmazione realmente chiari e consistenti: quello del C e quello del Lisp. Questi paiono quasi come due alture inframezzate da bassopiani acquitrinosi. Via via che i computer sono diventati sempre più potenti, i linguaggi che vengono sviluppati tendono sempre più verso il modello del Lisp. Una ricetta in voga negli ultimi 20 anni per produrre nuovi linguaggi di programmazione consiste nel partire dal modello del C e aggiungervi pezzo a pezzo caratteristiche di quello del Lisp, come per esempio la risoluzione dei tipi a tempo di esecuzione o il garbage collection.

In questo post proverò a spiegare nel modo più semplice possibile che cosa scoprì McCarthy. Il punto non è soltanto imparare un risultato teorico raggiunto da qualcuno quaranta anni fa, ma mostrare dove si stiano dirigendo i linguaggi. La cosa strana del Lisp — in effetti, la proprietà che lo caratterizza — è che può essere scritto nel linguaggio stesso. Per capire che cosa intendesse McCarthy con ciò ripercorreremo i suoi passi, avendo tradotto la sua notazione matematica con codice Common Lisp funzionante.

Sette primitive

Per prima cosa definiamo il concetto di espressione. Un'espressione è un atomo, cioè una sequenza di lettere (per esempio foo), oppure una lista di zero o più espressioni, separate da degli spazi e racchiuse fra parentesi. Ecco alcune espressioni:

foo
()
(foo)
(foo bar)
(a b (c) d)

L'ultima espressione è una lista di quattro elementi, il terzo dei quali è a propria volta una lista di un elemento.

In aritmetica l'espressione 1 + 1 ha il valore 2. Allo stesso modo, le espressioni valide del Lisp hanno valori. Se un'espressione e produce il valore v diciamo che e ritorna v. Il nostro successivo passo è definire che tipi di espressioni possono esistere, e che valori ciascun tipo ritorna.

Se un'espressione è una lista chiamiamo il primo elemento operatore e i restanti argomenti. Definiamo ora sette operatori primitivi (nel senso di assiomi): quote, atom, eq, car, cdr, cons e cond.

  1. (quote x) ritorna x. Per questioni di leggibilità abbrevieremo (quote x) con 'x.

     > (quote a)
 a
 > 'a
 a
 > (quote (a b c))
 (a b c)

  2. (atom x) ritorna l'atomo t se il valore di x è un atomo o la lista vuota. Altrimenti ritorna (). In Lisp conveniamo di usare l'atomo t per rappresentare un valore di verità, la lista vuota per un valore di falsità.

    > (atom 'a)
t
> (atom '(a b c))
()
> (atom '())
t

Ora che abbiamo un operatore che calcoli il valore del proprio argomento possiamo mostrare a che cosa serva quote. Di una lista a cui viene applicato questo operatore non viene calcolato il valore. Altrimenti una lista passata come parametro a un operatore come atom viene trattata come del codice:

> (atom (atom 'a))
t

Invece una lista a cui viene applicato quote è trattata come una semplice lista, in questo caso una lista di due elementi:

> (atom '(atom 'a))
()

Questo corrisponde al modo in cui usiamo le virgolette nella prosa scritta. Cambridge è una città nel Massachusetts di circa 90,000 abitanti. "Cambridge" è una parola di nove lettere.

L'operatore quote può sembrare un concetto esotico, perché pochi altri linguaggi possiedono qualcosa del genere. Ciò è strettamente legato a una delle caratteristiche salienti del Lisp: codice e dati sono fatti della stessa struttura dati, e l'operatore quote è il modo in cui distinguamo l'uno dall'altro.

  1. (eq x y) ritorna t se i valori di x e y sono lo stesso atomo o entrambi la lista vuota, () altrimenti.

    > (eq 'a 'a)
t
> (eq 'a 'b)
()
> (eq '() '())
t

  2. (car x) richiede che il valore di x sia una lista, e ne ritorna il primo elemento.

    > (car '(a b c))
a

  3. (cdr x) richiede che il valore di x sia una lista, e ritorna tutto tranne il primo elemento.

    > (cdr '(a b c))
(b c)

  4. (cons x y) richiede che il valore di y sia una lista, e ritorna una lista contenente il valore di x seguito dagli elementi del valore di y.

    > (cons 'a '(b c))
(a b c)
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (car (cons 'a '(b c)))
a
> (cdr (cons 'a '(b c)))
(b c)

  5. (cond (p_1 e_1) … (p_n, e_n)) viene calcolato come segue. Le espressioni p vengono calcolate in ordine finché una di esse ritorna t. Quando questa viene trovata, il valore della corrispondente espressione e viene ritornata come valore dell'intera espressione cond.

    > (cond ((eq 'a 'b) 'first)
        ((atom 'a)  'second))
second

In cinque dei nostri sette operatori primitivi, gli argomenti vengono calcolati quando viene calcolata un'espressione che cominci con quell'operatore. 2 Chiameremo funzione un operatore di questo tipo.

Denotare le funzioni

Definiamo poi una notazione per descrivere le funzioni. Una funzione si esprime come (lambda (p_1 … p_n) e), dove p_1 … p_n sono atomi (detti parametri) ed e è un'espressione. Un'espressione il cui primo elemento sia in tale forma, come

((lambda (p_1 … p_n) e) a_1 … a_n)

è detta invocazione di funzione e il suo valore è calcolato come segue. Si calcola il valore di ogni espressione a_i. Poi si calcola e. Nel calcolo di e il valore di ciascuna occorrenza dei p_i è il valore del corrispondente a_i nella chiamata di funzione più recente. Per esempio:

> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda x y) (cons x (cdr y)) 'z '(a b c))
(z b c)

Se un'espressione ha come primo elemento un atomo f che non sia uno degli operatori primitivi, come

(f a_1 … a_n)

e il valore di f è una funzione (lambda (p_1 … p_n) e), allora il valore dell'espressione è il valore di

((lambda (p_1 … p_n) e) a_1 … a_n)

In altre parole i parametri possono essere usati sia come operatori nelle espressioni sia come parametri:

> ((lambda (f) (f '(b c)))
   '(lambda (x) (cons 'a x)))
(a b c)

Esiste un'ulteriore notazione per denotare funzioni che permette alla funzione di fare riferimento a se stessa, dandoci con ciò un comodo metodo per definire le funzioni ricorsive. 3 La notazione

(label f (lambda (p_1 … p_n) e))

denota una funzione che si comporta come (lambda (p_1 … p_n) e), con la proprietà aggiuntiva che ciascuna occorrenza di f in e verrà calcolata con l'espressione label, come se f fosse un parametro della funzione.

Supponiamo di voler definire una funzione (subst x y z) che prenda in ingresso un'espressione x, un atomo y e una lista z, e ritorni una lista simile a z in cui ogni occorrenza di y (a qualunque livello di annidamento) in z viene sostituita da x.

> (subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)

Possiamo denotare questa funzione come

(label subst (lambda x y z)
               (cond ((atom z)
                      (cond ((eq z y) x)
                            ('t z)))
                     ('t (cons (subst x y (car z))
                               (subst x y (cdr z))))))

Abbrevieremo f = (label f (lambda (p_1 … p_n) e)) con (defun f (p_1 … p_n) e), perciò possiamo scrivere

(defun subst (x y z)
  (cond ((atom z)
         (cond ((eq z y) x)
               ('t z)))
         ('t (cons (subst x y (car z))
                   (subst x y (cdr z))))))

Per inciso, vediamo qui come ottenere un comportamento di default in un'espressione di tipo cond. Un ramo il cui primo argomento sia 't verrà certamente eseguito. Quindi

(cond (x y) ('t z))

è equivalente a quello che potremmo scrivere in un linguaggio con sintassi del tipo

if x then y else z

Alcune funzioni

Ora che abbiamo un modo di esprimere funzioni, ne definiamo di nuove in termini dei nostri sette operatori primitivi. Converrà prima introdurre alcune abbreviazioni per dei pattern comuni. Useremo cxr, dove x è una sequenza di a o d, come abbreviazione della corrispondente composizione di car e cdr. Quindi per esempio (cadr e) è un'abbreviazione di (car (cdr e)), la quale ritorna il secondo elemento di e.

> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)

Useremo inoltre (list e_1 … e_n) al posto di (cons e_1 … (cons e_n '()) …).

> (cons 'a (cons 'b ( cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)

Definiamo ora alcune nuove funzioni. Ne ho cambiato i nomi aggiungendo un punto alla fine. Questo distingue le funzioni primitive da quelle definite in termini di esse, ed evita inoltre che entrino in conflitto con le esistenti funzioni del Common Lisp.

  1. (null. x) verifica se il proprio argomento è la lista vuota.

     (defun null. (x)
   (eq x '()))

 > (null. 'a)
 ()
 > (null. '())
 t

  2. (and. x y) ritorna t se entrambi gli argomenti ritornano t, () altrimenti.

     (defun and. (x y)
   (cond (x (cond (y 't) ('t '())))
         ('t '())))

 > (and. (atom 'a) (eq 'a 'a))
 t
 > (and. (atom 'a) (eq 'a 'b))
 ()

  3. (not. x) ritorna t se il proprio argomento ritorna (), () se ritorna t.

     (defun not. (x)
   (cond (x '())
         ('t 't)))

 > (not (eq 'a 'a))
 ()
 > (not (eq 'a 'b))
 t

  4. (append. x y) prende due liste e ritorna la loro concatenazione.

     (defun append. (x y)
   (cond ((null. x) y)
         ('t (cons (car x) (append. (cdr x) y)))))

 > (append. '(a b) '(c d))
 (a b c d)
 > (append. '() '(c d))
 (c d)

  5. (pair. x y) prende due liste della stessa lunghezza e ritorna una lista delle successive coppie di elementi prese da ciascuna.

     (defun pair. (x y)
   (cond ((and. (null. x) (null. y)) '())
         ((and. (not. (atom x)) (not. (atom y)))
           (cons (list (car x) (car y))
                 (pair. (cdr x) (cdr y))))))

 > (pair. '(x y z) '(a b c))
 ((x a) (y b) (z c))

  6. (assoc. x y) prende un atomo x e una lista y del tipo creato da pair. e ritorna il secondo elemento della prima lista in y il cui primo elemento sia x.

     (defun assoc. (x y)
   (cond ((eq (caar y) x) (cadar y))
         ('t (assoc. x (cdr y)))))

 > (assoc. 'x '((x a) (y b)))
 a
 > (assoc. 'x '((x new) (x a) (y b)))
 new

La sorpresa

Insomma possiamo definire funzioni che concatenano liste, sostituiscono un' espressione al posto dell'altra e così via. Una notazione elegante, forse, ma quindi? Ora arriva la sorpresa. Salta fuori che possiamo scrivere una funzione che agisca come un interprete del nostro linguaggio: una funzione cioè che prenda come argomento qualunque espressione del Lisp e ritorni il suo valore. Eccola qua:

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
      (cond
        ((eq (car e) 'quote) (cadr e))
        ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
        ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                     (eval. (caddr e) a)))
        ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
        ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
        ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                     (eval. (caddr e) a)))
        ((eq (car e) 'cond)  (evcon. (cdr e) a))
        ('t (eval. (cons (assoc. (car e) a)
                         (cdr e))
                   a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))

La definizione di eval. è più lunga di tutte quelle finora viste. Andiamo a esaminare in dettaglio come funziona ogni sua parte.

La funzione prende due argomenti: e, l'espressione da valutare, e a, una lista che rappresenti i valori assegnati ai corrispondenti atomi come parametri di invocazione di funzioni. Questa lista è detta un ambiente, ed è della forma ritornata da pair.. In effetti abbiamo definito pair. e assoc. in modo da poter costruire e cercare all'interno di queste liste.

La spina dorsale di eval. è un'espressione cond composta di quattro casi. Il modo in cui calcoliamo il valore di un'espressione dipende dal suo tipo. Il primo caso gestisce gli atomi. Se e è un atomo andiamo a vedere il suo valore nell'ambiente:

> (eval. 'x '((x a) (y b)))
a

Il secondo caso di eval. è un'altra cond per gestire espressioni del tipo (a …), dove a è un atomo. Queste includono tutti gli usi degli operatori primitivi, e abbiamo un caso per ciascuno di essi.

> (eval. '(eq 'a 'a) '())
t
> (eval. '(cons x '(b c))
         '((x a) (y b)))
(a b c)

Tutte queste (ad eccezione di quote) invocano eval. per trovare il valore dei propri argomenti.

Gli ultimi due casi sono più complicati. Per calcolare il valore di un'espressione di tipo cond invochiamo una funzione ausiliaria chiamata evcon., la quale attraversa ricorsivamente i vari casi finché non trova la prima che ritorni t. Quando la trova ritorna il valore del secondo elemento.

> (eval. '(cond ((atom x) 'atom)
          ('t 'list))
         '((x '(a b))))
list

L'ultima parte del secondo caso di eval. gestisce le invocazioni di funzioni passate come parametro. Funziona rimpiazzando l'atomo con il suo valore (che dovrà essere un'espressione lambda o label) e calcolando il valore della risultante espressione. Quindi

(eval. '(f '(b c))
       '((f (lambda (x) (cons 'a x)))))

diventa

(eval. '((lambda (x) (cons 'a x)) '(b c))
       '((f (lambda (x) (cons 'a x)))))

che ritorna (a b c).

Gli ultimi due casi di eval. gestiscono le invocazioni di funzioni in cui il primo elemento è un'espressione di tipo lambda o label. Un'espressione label è calcolata aggiungendo prima la coppia formata dal nome della funzione e dalla funzione stessa all'inizio dell'ambiente, e poi chiamando eval. su un'espressione in cui l'espressione di tipo lambda è sostituita al posto dell'espressione label. Cioè

(eval. '((label firstatom (lambda (x)
                            (cond ((atom x) x)
                                  ('t (firstatom (car x))))))
         y)
       '((y ((a b) (c d)))))

diventa

(eval. '((lambda (x)
           (cond ((atom x) x)
                 ('t (firstatom (car x)))))
         y)
       '((firstatom
         (label firstatom (lambda (x)
                            (cond ((atom x) x)
                                  ('t (firstatom (car x)))))))
       (y ((a b) (c d)))))

che alla fine ritorna a.

Infine, per calcolare il valore di un'espressione del tipo ((lambda (p_1 … p_n) e) a_1 … a_n), si invoca evlis per ottenere la lista (v_1 … v_n) dei valori degli argomenti a_1 … a_n, per poi calcolare e con (p_1 v_1) … (p_n v_n) come prime coppie dell'ambiente. Quindi

(eval. '((lambda (x y) (cons x (cdr y)))
          'a
          '(b c d))
       '())

diventa

(eval. '(cons x (cdr y))
       '((x a) (y (b c d))))

che alla fine ritorna (a c d).

Conseguenze

Ora che abbiamo capito come funzioni eval. facciamo un passo indietro e riflettiamo su che cosa significhi. Quello che abbiamo è un modello di calcolo notevolmente elegante. Usando soltanto quote, atom, eq, car, cdr, cons e cond possiamo definire una funzione, eval., la quale in effetti implementa il nostro linguaggio, e poi usando questa possiamo definire tutte le funzioni che desideriamo.

Ovviamente esistevano già modelli di calcolo — il più noto dei quali è la Macchina di Turing. Ma i suoi programmi non sono particolarmente edificanti da leggere. Se voleste un linguaggio per descrivere algoritmi, potreste preferire qualcosa di più astratto, e questo era uno degli scopi di McCarthy quando definì il Lisp.

Mancavano molte cose al linguaggio definito nel 1960. Non aveva side effect, esecuzione sequenziale (che comunque è utile soltanto avendo i side effect), nessun modo pratico per definire numeri 4, scope dinamico. Ma questi limiti possono essere aggirati con sorprendentemente poco codice. Steele e Sussman mostrano come farlo in un famoso articolo dal titolo "The Art of the Interpreter". 5

Una volta capita la funzione eval di McCarthy avete capito qualcosa di più di uno stadio nell'evoluzione dei linguaggi. Queste idee sono ancora il nucleo semantico del Lisp odierno. Quindi studiare l'articolo originale di McCarthy ci mostra, in un certo senso, quello che è il Lisp è in realtà. Non è qualcosa che McCarthy abbia progettato, è più qualcosa che ha scoperto. Non è intrinsecamente un linguaggio per l'Intelligenza Artificiale, per costruire rapidamente prototipi o per qualunque altro compito di quel tipo. È quello che ottenete (o una delle cose che ottenete) quando provate ad assiomatizzare il calcolo.

Nel corso del tempo il linguaggio medio, cioè il linguaggio usato dal programmatore medio, si è via via avvicinato al Lisp. Perciò capendo eval. avrete capito quello che sarà probabilmente il modello di calcolo principale nel futuro.

Note

Nel tradurre la notazione di McCarthy in codice ho provato a cambiare il minimo possibile. Sono stato tentato dal rendere il codice più leggibile, ma ho voluto mantenere il gusto originale.

Nell'articolo di McCarthy la falsità è rappresentato da f, non dalla lista vuota. Ho usato () per rappresentare la falsità in modo che gli esempi funzionassero in Common Lisp. Il codice non dipende in nessuna parte dal fatto che l'essere falso sia anche la lista vuota; niente viene mai concatenato al risultato di un predicato.

Ho saltato la costruzione delle liste come dotted pairs perché non serve per capire eval. Ho evitato inoltre di menzionare apply, sebbene nel 1960 McCarthy chiamò apply (una forma piuttosto primitiva, il cui scopo principale era applicare quote agli argomenti) la funzione universale; eval era soltanto una subroutine invocata da apply per fare tutto il lavoro.

Ho definito le abbreviazioni list e cxr perché così fece McCarthy. In effetti le cxr potevano essere definite come normali funzioni. Allo stesso modo avremmo potuto definire list se avessimo facilmente modificato eval in modo da permettere che le funzioni potessero avere un numero arbitrario di argomenti.

L'articolo di McCarthy aveva soltanto cinque operatori primitivi. Egli faceva uso di cond e quote, ma è possibile che li pensasse come parte del suo metalinguaggio. Allo stesso modo non definì gli operatori logici and e not, ma questo è un problema minore poiché è facile definirne versioni adeguate come funzioni.

Nella definizione di eval. abbiamo invocato altre funzioni come pair. e assoc., ma ogni invocazione di queste funzioni che abbiamo definito in termini degli operatori primitivi potrebbe essere rimpiazzata da un'invocazione di eval.. Cioè

(assoc. (car e) a)

potrebbe essere scritta come

(eval. '((label assoc.
                (lambda (x y)
                  (cond ((eq (caar y) x) (cadar y))
                        ('t (assoc. x (cdr y))))))
        (car e)
        a)
        (cons (list 'e e) (cons (list 'a a) a)))

La funzione eval di McCarthy aveva un piccolo bug. La riga 16 era (equivalente a) (evlis. (cdr e) a) invece di soltanto (cdr e), il che calcolava due volte gli argomenti di una funzione con nome. Questo suggerisce che questa descrizione di eval non fosse stata ancora implementata nel linguaggio macchina dell'IBM 704 quando l'articolo fu inviato alla rivista. Inoltre mostra quanto sia difficile essere sicuri della correttezza di programmi di qualunque lunghezza senza aver provato a eseguirli.

Ho trovato un altro problema nel codice di McCarthy. Dopo aver dato la definizione di eval, continua dando qualche esempio di funzioni di ordine superiore — cioè funzioni che prendono come argomenti altre funzioni. Definisce maplist come:

(label maplist
       (lambda (x f)
         (cond ((null x) '())
               ('t (cons (f x) (maplist (cdr x f)))))))

poi la usa per scrivere una semplice funzione diff che calcoli simbolicamente la derivata. Ma diff passa a maplist una funzione che usa x come parametro, e il riferimento a questo è catturato dalla x che compare in maplist. 6

Il fatto che il primo esempio in assoluto di funzioni di ordine superiore in Lisp soffrisse di questo bug testimonia in modo eloquente i pericoli dello scoping dinamico. Potrebbe essere che McCarthy non fosse del tutto consapevole delle sue conseguenze nel 1960. Esso rimase nelle implementazioni del Lisp per un periodo sorprendentemente lungo — finchè Sussman e Steele svilupparono Scheme nel 1975. Lo scoping lessicale non complica granchè la definizione di eval, ma potrebbe rendere un compilatore più difficile da scrivere.

  1. “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.” Communications of the ACM 3:4, April 1960, pp. 184-195 ↩

  2. Le espressioni che cominciano per gli altri due operatori, quote e cond, sono calcolate in modo diverso. Quando viene calcolato il valore di un'espressione di tipo quote il suo argomento non viene calcolato, ma viene semplicemente ritornato come valore dell'intera espressione. Invece in una valida espressione di tipo cond viene calcolato il valore di un solo cammino a forma di L. ↩

  3. Logicamente non avremmo bisogno di definire nuova notazione per questo. Potremmo definire funzioni ricorsive nella notazione che già abbiamo utilizzando una funzione di funzioni chiamata Y Combinator. Potrebbe darsi che McCarthy non lo conoscesse quando scrisse il proprio articolo; a ogni modo la notazione che fa uso di label risulta più leggibile. ↩

  4. Si può fare aritmetica nel Lisp di McCarthy del 1960 usando per esempio una lista di n atomi per rappresentare il numero n. ↩

  5. Guy Lewis Steele, Jr. e Gerald Jay Sussman, “The Art of the Interpreter, or the Modularity Complex (Parts Zero, One, and Two)”, MIT AI Lab Memo 453, May 1978 ↩

  6. Al giorno d'oggi i programmatori Lisp qui userebbero mapcar al posto di maplist. Questo esempio chiarisce un mistero: come mai maplist appaia in Common Lisp. Fu la prima funzione map, e mapcar venne aggiunta in seguito. ↩