Introduzione al Common Lisp

Il Lisp è uno dei linguaggi più antichi (John McCarthy,1960) utilizzato diffusamente ancora oggi. Il nome deriva da LISt Processor, ma qualcuno dice Long Irritating Series of Parentheses (!), infatti si basa su poche e chiare regole sintattiche, prima delle quali è il concetto di lista. Questo porta a due caratteristiche interessanti: è particolarmente portato per il trattamento di liste ed, essendo lo stesso codice lisp espresso in forma di lista, è facile scrivere codice che a sua volta tratti, generando o modificando, codice lisp. Questo è uno dei motivi che lo rendono molto usato nelle ricerche sull'intelligenza artificiale (l'altro è che McCarthy è stato uno dei padri della AI !). Il lisp è comunque utilizzato in molti ambiti, tra i quali come linguaggio di estensione all'interno di Emacs e dei più diffusi sistemi CAD (AutoCAD, IntelliCAD, ecc.).

Alcune caratteristiche peculiari sono:

• Dynamic redefinition: la possibilità di ridefinizione dinamica del codice, ovvero lo stesso può essere modificato senza interromperne l'esecuzione.
• Dynamic typing: le variabili non hanno tipo predefinito, e non richiedono dichiarazione.
• Garbage collection: gestione automatica dell' allocazione e della liberazione della memoria.

Il codice lisp inoltre può essere eseguito:

• in modo interattivo: attraverso l'interprete che si comporta come un terminale,
• come un linguaggio di scripting
• oppure può essere compilato per ottenere la massima velocità

A parte quanto detto, la caratteristica più evidente del lisp è di non assomigliare a nessun altro linguaggio. Per questo motivo lo studio del lisp, nonostante le iniziali difficoltà, è indicato anche solo a scopo didattico.

Si apprenderà gradualmente come i noti concetti di variabile, funzione, ecc. assumano nel lisp un significato sfumato e differente. In realtà l'uso di questi termini non sarebbe neppure corretto, anche se verranno comunque utilizzati per una più graduale comprensione.

Il programma lisp può essere scritto con qualsiasi editor. E' comunque consigliabile disporre di un editor che faciliti la gestione delle parentesi.

Del lisp esistono vari dialetti (scheme è il piú noto ), mentre oggi la lingua "principale" si indica propriamente come ""Common Lisp" (abbreviato CL). CLtL1, CLtL2 ed ANSI sono le varie versioni standard del Common Lisp. In questo documento ci si riferisce all'implementazione gcl (GNU Common Lisp), aderente a CLtL2 e parzialmente allo standard ANSI.

Il primo approccio con LISP sarà attraverso una shell interattiva, quindi lanciando il comando "gcl" (oppure "clisp", "alisp", oppure con una voce di menu) ci si troverà di fronte ad un prompt pronto ad eseguire comandi LISP. Nel seguito utilizzeremo la seguente convenzione:

>>(lista di simboli separati da spazi)
risultato

• Il Lisp utilizza la notazione prefissa, valutando le espressioni da sinistra a destra.

• Una espressione è una lista, cioè una sequenza di di simboli o valori (detti atomi) separati da spazi, e delimitata da parentesi tonde.

• Il programma lisp è costituito solo da espressioni, ovvero non contiene direttive (goto, break, ecc.), ma solo espressioni, variamente annidate, che restituiscono un valore (o più).

Ad esempio un'operazione di somma è espressa da:

>> (+ 2 2)
4

Ogni simbolo viene valutato. Per non far valutare una lista si utilizza l'operatore quote o, più spesso, la sua abbreviaziazione 'apice.

>>(quote (+ 2 2))
(+ 2 2)

>>'(+ 2 2)
(+ 2 2)

L'apostrofo (backtick in inglese : <AltGr><apice> sulla tastiera italiana) ha la stessa funzione, con la differenza che sarà possibile rientrare in modo "codice" tramite l'uso della virgola:

>>`( 5 + 7 = ,(+ 5 7))
(5 + 7 = 12)

I simboli che iniziano con il carattere : (duepunti), sono keyword (etichette), e sono utilizzati nelle strutture, negli array associativi, ecc.

Il simbolo NIL, equivalente della lista vuota '(), ha anche il significato di falso. Sono quindi "true" tutti i valori non-NIL, rappresentati dal carattere T (maiuscolo o minuscolo).

Il lisp è case insensitive, quindi utilizzare caratteri maiuscoli o minuscoli è indifferente.

Il carattere delimitatore dei commenti è il punto-e-virgola.

Una caratteristica particolare è che lo stesso simbolo può rappresentare contemporanemente sia una variabile che una funzione (per setq, defun e lambda si veda più avanti):

>>(defun double (x) (* x 2))   ; definisce la funzione double
>>(setq double 2)              ; definisce la variabile double
>>(double double)              ; chiama la funz. double sulla var double
4

>>(symbol-value 'double)
2

>>(symbol-function 'double)
(LAMBDA-BLOCK DOUBLE (X) (* X 2))

Per capire il lisp, oltre a quanto già visto sulla sintassi di base, è sono necessari solo alcuni concetti, primo fra i quali l'idea di lista.

Per le liste è comodo riferirsi mentalmente alla classica lista dinamica (in realtà è la rappresentazione classica a venire dal lisp). Liste sono rappresentabili da una sequenza di coppie di celle dette CONS. Ogni cons contiene due puntatori: CAR e CDR, che indirizzano il contenuto ed il cons successivo. Nel caso di liste annidate il car può puntare ad un ulteriore cons. Il cdr dell'ultimo elemento contiene NIL (è vuoto). Ad esempio la lista:

("uno" 2 (3 "quattro"))

 car|cdr -- car|cdr -- car|cdr -- nil
  |          |          |
"uno"        2          |
                     car|cdr -- car|cdr -- nil
                      |          |
                      3      "quattro"

Il lisp ammette anche una rappresentazione più esplicita (e basica) dell'oggetto CONS, come coppia puntata:

(car . cdr)

>>'("uno" . nil )
("uno")

("uno" . ( 2 . ( ( 3 . ("quattro" . nil)  ) . nil  ) ) )

Ognuno dei mattoni fondamentali (CONS, car e cdr) ammette un'operatore corrispondente:

>>(cons 'a 'b)  ; forma un cons
(A . B)

>>(cons 1 (cons 2 (cons 3 nil))) ; forma una lista
(1 2 3)

>>(car '(1 2 3)) ; estrae il primo elemento dalla lista
1

>>(cdr '(1 2 3)) ; estrae la restante parte della lista
(2 3)

Per completezza citiamo anche l'operatore atom:

>>(atom 'a)
T

>>(atom '(1 2))
NIL

L'originale lavoro di McCarthy "Recursive Functions of Symbolic Expressions and Their Computation by Machine", dimostra che questi pochi operatori (quote, atom, cons, car, cdr), a cui si aggiungono l'operazione di uguaglianza (eq), un operatore condizionale (cond) e il concetto di funzione (la lambda-expression) chevedremo in seguito, sono sufficienti a definire completamente il linguaggio lisp.

A tal proposito si veda anche "The Root of Lisp" di Paul Graham.

I valori numerici vengono trattati come interi, frazioni, reali o complessi in funzione del contesto. Ad esempio una operazione tra frazioni è valutata in una frazione:

>>(/ 3/5 3)
1/5

Esistono quindi delle funzioni di conversione tra le differenti notazioni:

>>(rational 1.5)
3/2

I numeri complessi si esprimono nella forma:

#C(partereale parteimmaginaria)

>>(complex 1 2)
#C(1 2)

>>(imagpart #C(1 2))
2

>>(realpart #C(1 2))
1

La notazione esponenziale si esprime con il carattere S oppure con il consueto carattere E:

>>1234S10
1.234S13
>>1234e-3
1.234

Oltre alle operazioni di base sono disponibili tutte le funzioni di calcolo più comuni:

mod   ; resto
sqrt  ; radice quadrata
(expt base esponente) ; elevamento a potenza
(log num base) ; logaritmo (la base di default è e)
sin   ; analogamente a cos, tan, atan, ecc. l'argomento è in radianti
abs   ; valore assoluto
round ; arrotondamento intero
min   ; accetta argomenti multipli come anche max
sinh  ; similmente esistono cosh, tanh, atanh ()
lcm   ; minimo comune multiplo , accetta argomenti multipli
gdc   ; massimo comun divisore

Sono inoltre predefinite alcune costanti utili nel calcolo, tra cui:

PI                    ; pigreco
MOST-POSITIVE-FIXNUM  ; il maggior numero intero disponibile

Il carattere delimitatore delle stringhe è il doppio apice. Le stringhe, come le altre costanti, vengono valutate in sè stesse:

>>"ciao"
"ciao"

Come carattere di escape si usa \ (backslash) quindi per inserire un doppio apice si usa

\"

\\

I singoli caratteri sono rappresentati preceduti dalla sequenza #\:

#\A

Alcune funzioni utili sulle stringhe:

>>(char "abc" 1)                    ; estrae il secondo carattere
#\b
>>(concatenate 'string "com" "mon") ; concatena due stringhe
"common"

Inoltre le stringhe sono array di caratteri quindi si possono usare tutte le funzioni relative agli array (si veda più avanti)

Le variabili globali vengono definite dalle due macro defvar e defparameter. La differenza è che defvar non sovrascriverà eventuali simboli già definiti in precedenza. Per convenzione i simboli associati a variabili globali cominciano e finiscono con un asterisco:

(defvar *varglobale* 50.5)

Per definire variabili locali si usa l'operatore let, seguito da due liste, la prima di definizione delle variabili e la seconda è l'ambito di validità delle stesse (cioè il codice nel quale le variabili esistono):

>>(let ((a 20)(b 15)) (+ a b))
35

Per modificare il valore di una variabile si utilizzano gli operatori setq (solo variabili) e setf (più generale):

(setq *varglobale* '3/8)

(setq pigreco 3.14 radicedue 1.41)

Le variabili non sono tipizzate, quindi è possibile assegnare successivamente valori di tipi diversi (ad esempio prima una frazione e poi una stringa). Per verificare che una variabile contenga, in un dato momento, un tipo preciso esiste tutta una serie di funzioni booleane, il cui nome, per convenzione finisce con il carattere "p": floatp, complexp, listp, alpha-char-p, ecc.

Citiamo solo alcune delle moltissime funzioni disponibili per il trattamento delle liste. Si noti che in generale tali funzioni non hanno effetti collaterali, quindi non modificano il contenuto dei simboli implicati. Ad esempio:

>>(setq a '(1 2 3 4 5)) ; assegna ad a la lista (1 2 3..)
(1 2 3 4 5)

>>(cons 0 a)            ; aggiunge alla lista l'elemento 0
(0 1 2 3 4 5)

>>a                     ; ma non modifica il valore di a
(1 2 3 4 5)

>>(setq a (cons 0 a))   ; a meno che non venga utilizzato setq
(0 1 2 3 4 5)

Per estrarre elementi (esistono anche first, second, third, ecc.):

>>(nth 1 '(a b c d)
B

>>(subseq '(a b c d) 1 3)
(B C)

Per concatenare, intersecare, unire, ecc:

>> (union '(a b c) '(b c d))
(a b c d)

>> (intersection '(a b c) '(b c d))
(b c)

>> (append '(a) '(b c d) '(e f))
(a b c d e f)

Per ottenere la dimensione di una lista:

>>(length '(a b c d))
4

Per rimuovere un elemento:

>>(remove c '(a b c d))
(a b d)

Per estrarre il primo elemento o i restanti (analoghe ai già visti car e cdr):

>>(first '(a b c d))
A

>>(rest '(a b c d))
(b c d)

Per estrarre elementi da una lista:

>>(member 'c '(a b c d))
(c d)
>>(find 'a (a b c d))
A

Gli operatori push e pop permettono di lavorare su una lista con la logica dello stack:

>>(setq a nil)
NIL

>>(push 4 a)
(4)

>>(push 5 a)
(5 4)

>>(pop a)
5

L'operatore sort, infine, è molto potente, infatti permette di utilizzare come condizione di ordinamento una funzione booleana arbitraria:

>>(sort '(2 3 7 1) '>)
(7 3 2 1)

Le strutture sono simili a quanto disponibile in C o in Pascal. La macro defstruct definisce una struttura. Ad esempio:

(defstruct login nome password)

>>(make-login)
#S(LOGIN :NAME NIL :PASSWORD NIL)

>>(setq udata (make-login :name "utente"))
#S(LOGIN :NAME "utente" :PASSWORD NIL)

>>(login-name udata)
"utente"

Per trattare coppie del tipo chiave-valore (array associativi) esiste la semplice struttura plist (property list) che è trattabile come una normale lista di coppie di elementi:

>>(setq capitale '(:italia "roma" :francia "parigi"))      ; crea una plist
(:ITALIA "roma" :FRANCIA "parigi")

>>(getf capitale :francia)                                 ; estrae un valore
"parigi"

>>(setq capitale (append capitale '(:germania "berlino"))) ; aggiunge una coppia
(:ITALIA "roma" :FRANCIA "parigi" :GERMANIA "berlino")

Molto simile, ma più raffinata, è la struttura chiama hash table, ottimizzata per offrire un tempo di accesso indipendente dalla dimensione.

>>(setq capitali (make-hash-table))   ;istanza di una nuova hash table

>>(gethash :francia capitali)         ;richiesta di un valore non definito
NIL
NIL

>>(setf (gethash :francia capitali) "parigi") ;assegnazione di un valore

>>(gethash :francia capitali)                 ;richiesta di un valore definito
"parigi"
T

La sruttura array prevede una rappresentazione in forma di lista annidata preceduta dal simbolo #

#((a00 a01 ...a0n) (a10 a11 ...a1n) (am0 am1 ...amn))

Anche gli array sono ottimizzati in modo simile alle hash table:

>>(setq ary (make-array '(3 3)))    ; istanza di un array 3x3

>>(setf (aref ary 0 0) "valore00" ) ; assegnazione dell'elemento 0 0

>>(aref ary 0 0)                    ; richiesta dell'elemento 0 0
"valore00"

>>(array-rank ary)                  ; ritorna l'ordine
2

Per gli array monodimensionali (vettori) sono disponibili alcune funzioi semplificate:

>>(setq v (vector 1 2 3))   ; assegna a v  un vettore
#(1 2 3)
>>(svref v 0)               ; estrae il primo componente
1

Le funzioni sono definite dalla macro defun seguita dal nome, dalla lista degli argomenti e dal corpo della funzione (si noti che il nome della funzione non viene valutato come invece dovrebbe, essendo appunto defun una macro e non un semplice operatore):

(defun incrementa (a) (+ a 1))

>>(incrementa 5/4)
9/4

La lista che definisce il prototipo di una funzione è chiamata lambda-expression:

(lambda (parametri) funzione)

>>( (lambda (x) (* 2 x)) 2)
4

>>(defun make-adder (n) #'(lambda (x) (+ n x)))
>>(setq add2 (make-adder 2))
>>(funcall add2 3)
5

(setf (symbol-function 'incrementa) '(lambda (a) (+ a 1)))

Per definire una lista di argomenti di dimensione variabile si usa l'operatore &rest. Ad esempio:

(defun funzione (a &rest b) ...)

Per definire dei parametri opzionali con i rispettivi valori di default si usa l'operatore &optional. Ad esempio:

(defun funzione(&optional(simbolo val-default)) ...)

Una caratteristica molto interessante è la possibilità di definire degli argomenti opzionali e dotati di nome, che prendono il nome di argomenti keyword:

(defun funzione (&key (nome1 var1)(nome2 var2)...) (...codice))

(funzione :nome2 valore2)
(funzione :nome2 valore2 :nome1 valore1)

>>(defun foo (&key x y) (cons x y))
>>(foo :X 3)
(3)

(funcall 'sqrt 4)

(sqrt 4)

(defun tt (f x) (funcall f (funcall f x)))
>>(tt 'sqrt 16)
2.0

L'operatore apply esegue una funzione utilizzando come argomenti gli elementi una lista:

>>(setq a '(1 2 3))
>>(apply '+ a)
6

>>(mapcar 'sqrt a)
1.0 1.4142135623730951 1.7320508075688772)

(mapcar #'sqrt a)

Il più semplice operatore di loop è appunto loop, che ripete le istruzioni che lo seguono (in nuumero arbitrario). Il loop termina con l'istruzione return.

>>(loop (setq a (+ a 1)) (when (> a 7) (return a)))
8

Più complessa è la struttura do:

(do ((var init step)(var init step)...) (endtest result) (statement)(statement)..)

>>(do ((x 1 (+ x 1))
       (y 1 (* y 2)))
      ((> x 3) y)
    (print y)
    (print 'working))
1
WORKING
2
WORKING
4
WORKING
8

Per effettuare cicli su liste è disponibile l'operatore dolist:

(dolist (var lista ret) (...codice))

L'operatore dotimes invece serve a realizzare cicli su numeri interi. La seguente espressione equivale ad un ciclo for per n da 0 a 9 (compresi):

(dotimes (n 10) (...codice))

Per concatenare più operazioni è disponibile l'operatore progn, che valuta tutte le espressioni che lo seguono, e restituisce il valore dell'ultima:

>>(progn (setq a 5)(setq b 6)(+ a b))
11

Esistono diversi operatori di confronto:

>>(eq 'a 'A)                ; confronto tra simboli
T
>>(= 3 4)                   ; confronto tra numeri
NIL
>>(equal '(1 2 3) '(1 2 3)) ; confronto tra liste
T

L'operatore if necessita sempre di entrambe le condizioni (true e false):

(if test val-true val-false)

Se invece non serve una delle due condizioni si usano gli operatori when e unless:

(when test val-true)
(unless test val-false)

>>(when t (setq a 5) (+ a 6))
11

Se invece le condizioni sono molte esiste l'operatore cond:

(cond ((test1 val1) 
       (test1 val2)
       ...)))

(defun fat (n) 
    (cond ((= n 1) 1)
           (t (* n (fat (- n 1)))
          )
    )
)

Per un confronto tra molti valori è disponibile l'operatore case:

(case var (val1 ret1)(val2 ret2)...)

(case a 
	(0 "zero")
	(1 "uno")
	(2 "due")
)

Gli operatori and e or, molto utilizzati nel controllo di flusso, accettano un numero arbitrario di argomenti, ed effettuano il confronto in modo sequenziale tra di essi.

Per la gestione degli stream sono disponibili i consueti comandi open, close, read, ecc.

>>(setq filep (open "nomefile")) ; apre uno stream in lettura da file
>>(read-line filep)              ; legge una linea come stringa
"prima linea del file"
>>(close filep)                  ; chiude lo stream

DIRECTION   :INPUT, :OUTPUT, :IO, :PROBE
IF-EXISTS   :ERROR, :NEW-VERSION, :RENAME, :RENAME-AND-DELETE, 
            :OVERWRITE, :APPEND, :SUPERSEDE, NIL
IF-DOES-NOT-EXIST  :ERROR, :CREATE, or NIL

Gli stream *standard-input* e *standard-output* sono predefiniti come variabili globali.

La più semplice funzione di output disponibile è print, che stampa qualsiasi oggetto o sequenza di oggetti nella sua reppresentazione lisp:

(print object stream)

Esistono inoltre una serie di varianti della print: prin1, princ, pprint, oltre alla più generale funzione write.

La funzione format formatta una stringa in modo simile ad una printf del linguaggio C:

(format t "hello world ~a~%" nome)

~A ~nA	     stampa l'argomento come farebbe il comando PRINC
~S ~nS 	     stampa l'argomento come farebbe il comando PRIN1
~D ~B ~O ~X  stampa un decimale, binario, ottale, o esadecimale
~C           stampa un carattere
~F           stampa un numero in virgola mobile 
~&           ritorno a capo

Oltre alle funzioni di input/output da file e da terminale molte implementazioni includono librerie grafiche per rendere disponibili funzioni di gestione di finestre, bottoni, ecc. Ad esempio il gcl include gcl-tk per il noto TCL/TK.

Questa sezione è riferita specificatamente all'implementazione gcl (GNU Common Lisp). Ciononostante buona parte di quanto riportato resta valido sostituendo al comando "gcl" quello dell'implementazione CL in uso (alisp, clisp, ecc.)

La variabile globale

si::*command-args*

(comando parametri... argomenti...)

L'uso come linguaggio di scripting prevede di salvare il programma come un semplice file di testo, eventualmente con l'estensione convenzionale .lsp. Il file sarà eseguito dal comando:

gcl -f script.lsp

Nella maggior parte dei sistemi unix-like è possibile rendere il file direttamente eseguibile (chmod 755) ed inserire una prima linea può che richiami l'interprete (attenzione al percorso: il normale comando "gcl" può essere uno shell-script oppure un link). Ad esempio per il gcl su linux:

#!/usr/lib/gcl-2.6.6/unixport/saved_ansi_gcl -f

La prima linea verrà ignorata anche se non contiene il percorso per l'interprete. Va quindi in ogni caso lasciata vuota (o occupata da un commento).

La compilazione si può effettuare dall'interno dell'interprete (o da codice!), tramite il comando:

(compile-file "filesorgente.lsp" :output-file "fileoggetto")

gcl -compile filesorgente.lsp

Specifica del gcl è la possibilità di mantenere i file intermedi in codice c tramite i flag (disponibili anche nell'analoga funzione già vista):

gcl -compile filesorgente.lsp -c-file -h-file

..il flag system-p e l'uso nel C

Sempre dall'interno dell'interprete è disponibile anche il comando:

(compile nomefunzione lambda-expr)

Il caricamento dinamico di codice si effettua tramite la funzione load. La funzione load permette di caricare il codice salvato in un file, indifferentemente sorgente o binario. Ad esempio se la definizione:

(defun double (a) (* 2 a))

(load "/usr/lib/clcommon/double.lsp")

Durante l'interazione con l'interprete si rivela molto comoda la funzione describe:

>>(describe 'defun)
DEFUN - external symbol in LISP package
DEFUN [Special form and Macro]

>>(describe (symbol-function 'double))
(LAMBDA-BLOCK DOUBLE (A) (* 2 A)) - function

>>(describe (symbol-value 'a))
3 - fixnum (32 bits)

La funzione step invece valuta l'argomento passo-passo ed in modo interattivo:

>>(step (+ (* 3 4)(/ 6 7)))
Type ? and a newline for help.
  (+ (* 3 ...) ...)
(* 3 ...)
3
4
    = 12
    (/ 6 ...)
6
7
    = 6/7
  = 90/7
90/7