Linguaggi di Programmazione LISP - people.dti.supsi.chpeople.dti.supsi.ch/~lepori/lisp.pdf ·...

$: Linguaggi di Programmazione LISP - people.dti.supsi.chpeople.dti.supsi.ch/~lepori/lisp.pdf · Introduzione In questa parte del corso \Linguaggi di programmazione" a ronteremo al-cune$
Linguaggi di ProgrammazioneLISP

Carlo LeporiScuola di Ingegneria del Canton Ticino

(STS)

Introduzione

In questa parte del corso “Linguaggi di programmazione” affronteremo al-cune tematiche riguardanti la struttura e l’interpretazione dei programmiper calcolatore, rifacendoci al testo: H. Abelson e G. Sussman, Structureand Interpretation of Computer Programs, Mit Press. Altri temi, comel’introduzione a linguaggi specifici (C++, C, ADA, ecc) e un’introduzionealla teoria dei linguaggi formali (compilazione) sono sviluppati in altre partidel corso.Come nel testo citato, useremo il linguaggio Lisp, e questo per vari motivi:

• L’uso di un linguaggio non ancora conosciuto e di tipo diverso da quellinoti, permette di cogliere gli aspetti piu importanti, in maniera menocondizionata.

• Il Lisp per la sua struttura semplice e per la sua versatilita e partico-larmente adatto a questo tipo di approccio.

• La conoscenza del Lisp sara vantaggiosa per la lezione “Intelligenzaartificiale”.

Prima di iniziare sembra opportuno riassumere le nostre conoscenze sui di-versi linguaggi di programmazione: sono state proposte molte classificazionidei linguaggi:

imperativi: orientati alla descrizione di algoritmi; strettamente legati almodello di macchina detto di von Neumann (questo gruppo comprendequasi tutti i linguaggi noti);

dichiarativi: approccio matematico, legato al concetto di funzione, comeil Lisp, oppure in termini di relazioni logiche (calcolo dei predicati),come il Prolog.

Si vedano anche la Tabella I.1 “Evoluzione storica” e la Tabella I.2 “Cinquegenerazioni”.

1

2

definizione linguaggio uso< ’54 Assembler generale

’54–’57 FORTRAN calcolo numerico’58–’60 ALGOL 60 calcolo numerico’59–’60 COBOL business DP’56–’60 APL array processing’56–’62 LISP manipolazione simbolica’63–’64 BASIC generale/educativo’63–’64 PL/I generale’63–’68 ALGOL 68 generale

’71 Pascal generale/educativo’72 PROLOG programmazione logica’74 C programmazione di sistema’75 Concurr. Pascal programmazione concorrente’77 Modula programmazione concorrente’80 Modula-2 generale, grandi sistemi’83 Ada generale, grandi sistemi,

real-time’84 Common Lisp generale, manipolazione simbolica

’86–’89 C++ C a oggetti (rel. 1 e 2)’89 CLOS Lisp a oggetti’95 Ada95 Ada a oggetti

Table I.1: Evoluzione storica

Table I.2: 5 generazioni di linguaggi

• prima: linguaggio macchina, assembler;

• seconda: linguaggi procedurali non strutturati: Fortran, Cobol;

• terza: linguaggi procedurali strutturati: Pascal, C, Modula-2, Ada;

• quarta: linguaggi applicativi, query languages;

• quinta: linguaggi logici, linguaggi funzionali: Prolog, Lisp.

Chapter 1

La funzione come astrazione

Per questo corso disponiamo di ambienti Lisp su PC (Allegro Common Lisp)e su Macintosh (Macintosh Common Lisp) al momento non sono disponibiliversioni su AXP.Poiche lo scopo di questo corso non e di imparare il Lisp nella sua com-pletezza, gli elementi del linguaggio verranno introdotti man mano, lasciandoa chi si interessa di consultare testi e manuali per acquistare una maggioreesperienza.

1.1 Il linguaggio Lisp

1.1.1 L’interprete

Il Lisp si presenta come interprete, ma e anche possibile compilare i pro-grammi, disponendo quindi contemporaneamente dell’ambiente confortevoledi un inteprete e della velocita di un compilatore. Per accedere all’interpretesi lancia l’applicazione. L’interprete Lispsi annuncia con un messaggio e unprompt (il testo del prompt naturalmente non ha nessuna importanza):

Lisp>

L’idea di fondo e che il Lisp e in attesa di una espressione da valutare.Egli cioe legge un’espressione, la valuta e ne scrive il valore: si dice chel’interprete si trova in una read-eval-print loop.L’elemento base della sintassi del Lisp, l’espressione, puo essere un ato-mo, e si distinguono tra l’altro numeri e simboli, oppure una lista (elencodi espressioni, senza virgola, racchiuse da parentesi rotonde). Si noti la

3

CHAPTER 1. LA FUNZIONE COME ASTRAZIONE 4

ricorsivita della definizione: un elemento di una lista puo essere a sua voltauna lista, ecc.Il valore di un atomo numerico e il numero stesso:

Lisp> 486486

Un simbolo puo avere un valore a esso legato (bound), oppure no:

Lisp> pi3.14 . . .

Lisp> aerror: unbound value . . .

Break 1>

A causa dell’errore precedente (la valutazione di un simbolo cui non e legatoalcun valore), l’interprete si trova ora nello stato di debugging che per-mette una correzione interattiva del programma. L’interpete, a secondadell’implementazione, puo essere settato in modo da reagire in altro modo.Quando deve valutare un’espressione non atomica (detta anche una forma,in questo contesto), il Lisp considera il primo elemento della lista come unafunzione e gli altri elementi come argomenti della funzione:

Lisp> (+ 317 349)666

Lisp> (* 5 99)495

Come si vede, il Lisp usa una notazione algebrica di tipo a prefisso e nonquella tradizionale di tipo a infisso: questa scomodita e compensata dauna notevole uniformita sintattica. Le funzioni matematiche usate in questiesempi, permettono anche un numero indeterminato di argomenti: graziealla notazione a prefisso non ci sono ambiguita:

Lisp> (* 25 4 12)1200

Un altro vantaggio e la possibilita di avere argomenti che sono essi stessiespressioni:


Lisp> (+ (* 3 5) (- 10 6))19

Le funzioni primitive, cioe predefinite nel sistema Lisp non comprendonosolo le funzioni aritmetiche fondamentali, ma anche molte altre che verrannointrodotte secondo il bisogno. Per es.:

Lisp> (sqrt 9.0)3.0

Lisp> (sin (/ pi 6))0.5

1.1.2 La definizione di funzioni (e simboli)

In Lisp la possibilta di definire nuove funzioni e fondamentale! Si usa laforma defun che prende come argomenti il nome della nuova funzione, lalista dei suoi argomenti e il corpo (body) che la definisce, formato da una opiu espressioni: il valore della funzione sara determinato dall’ultima espres-sione. La forma defun non segue la sintassi ordinaria: i suoi argomenti nonvengono valutati, ma usati per modificare l’ambiente Lisp; forme di questotipo verranno chiamate improprie.1

Lisp> (defun square (x) (* x x))square

Il Lisp restituisce sempre un valore!2 in questo caso il nome della funzionedefinita. Ora questa funzione fa parte dell’interprete Lisp per tutto il col-legamento:

Lisp> (square (+ 2 5))49

E anche possibile definire un simbolo (o meglio: dargli un valore):

Lisp> (defvar dieci 10)dieci

1Il Common Lisp distingue forme speciali (special forms) predefinite, e macro, formeimproprie che possono essere definite dall’utente.

2In realta la risposta e di solito scritta maiuscola: il Common Lisp non distinguemaiuscolo e minuscolo e archivia i simboli in maiuscolo. Noi useremo la scrittura minuscolaper leggibilita.


Lisp> dieci10

Si tratta evidentemente di una forma impropria3: il simbolo non viene valu-tato, anzi l’importante e proprio l’effetto collaterale (side-effect) di legare unvalore al simbolo! A questo scopo si usa anche la forma impropria setq, ilcui scopo e pero di modificare il valore di un simbolo! Se si vuole mantenereil carattere strettamente funzionale del linguaggio, questo non e permesso.

Lisp> (setq dieci 22)22

Lisp> dieci22

1.1.3 L’editor

Di solito le nuove funzioni non sono definite direttamente nell’interprete,ma sono preparate in un editor e poi caricate nell’ambiente Lisp. Qualsiasieditor va bene, ma dato il numero assai grande di parentesi che si possonotrovare in una definizione e la necessita di alternare il lavoro nell’editor e nelLisp, e conveniente usare un editor incorporato. Esso puo venire invocatocon la funzione4

(ed "nome-del-file")

Normalmente si accede all’editor con un comando di menu. L’editor se-gnala la chiusura delle parentesi e permette di realizzare l’indentazione,usando p. es. tab dopo return, per aumentare la leggibilita del programma(pretty-printing).Per caricare la funzione nel Lisp, prima bisogna selezionare tutta la defini-zione e poi bisogna valutarla, con i comandi appositi.Per salvare il lavoro fatto nell’editor, si salvera su disco il buffer (finestra)corrispondente.

3Altre forme con lo stesso effetto, ma piccole differenze stilistiche sono: defparameter

e defconstant.4Una stringa (espressa in Common Lisp con le virgolette) e un atomo che ha se stesso

come valore.


1.1.4 Espressioni condizionali e predicati

Usando solo le funzioni viste, la nostra capacita espressiva e assai piccola.Per sempio ci e impossibile definire la funzione my-abs5 che calcoli il valoreassoluto di un numero. Per distinguere i vari casi possibili si usa la formaimpropria cond: come sempre in Lisp, anche cond restituisce un valore! Ilsuo uso lo si capisce piu facilmente con un esempio:

(defun my-abs (x)(cond ((> x 0) x)

((= x 0) 0)((< x 0) (- x))))

Gli argomenti di cond sono liste (dette clausole (clauses)) il cui primo ele-mento e detto antecedente e il resto conseguenza. L’antecedente e un pre-dicato: e cioe un’espressione il cui valore puo essere vero o falso. In Lisp,“falso” e il valore del simbolo nil, ogni altro valore viene considerato come“vero”; talvolta si usa il simbolo t.6

La valutazione di un’espressione condizionale segue la seguente regola: vienevalutato il primo predicato; se esso e falso, viene valutato il secondo predicatoecc. , finche si trova un predicato che e vero, cioe che da un valore non-nil:in questo caso si valutano le forme che compongono la conseguenza: il valoredell’ultima e il valore di tutta l’espressione condizionale. Se nessun predicatoe vero, l’espressione condizionale ha il valore nil. Anche se piu predicatifossero veri, solo il primo di essi causa la valutazione della sua conseguenza:l’ordine delle clausole e quindi importante!Un altro modo di definire il valore assoluto:

(defun my-abs (x)(cond ((< x 0) (- x))

(t x)))

Qui e stato usato il simbolo t che, essendo vero, fa scattare l’esecuzione dellaforma corrispondente: e buona abitudine terminare la forma condizionalecon una clausola che inizia con t. Ancora un’altra possibilita:

(defun my-abs (x)(if (< x 0) (- x) x))

5Volendo definire funzioni che sono gia primitive Lisp, useremo nomi che iniziano conmy- o nomi in italiano per evitare confusione.

6Gli atomi nil e t hanno se stessi come valore.


La forma impropria if valuta il primo argomento (il predicato): se e vero,restituisce come valore il valore del secondo argomento, in caso contrarioquello del terzo (gli argomenti devono essere singole forme!).

1.1.5 L’applicazione di funzioni

Esaminiamo piu in dettaglio il meccanismo di valutazione usato normal-mente dall’interprete Lisp (escludendo quindi le forme improprie):

1. Tutte le sotto-espressioni della forma vengono valutate.

2. La funzione (il valore funzionale della prima sotto-espressione) vieneapplicata agli argomenti (i valori delle altre sotto-espressioni).

Questa semplice regola presenta aspetti interessanti: il primo passo indicache per valutare una forma si devono valutare i suoi elementi. La regola divalutazione e quindi ricorsiva per natura: essa cioe contiene, come uno deisuoi passi, la necessita di applicare la regola stessa!Nel caso di funzioni che non sono primitive, viene valutato il loro corpo,sostituendo ogni parametro formale con il corrispondente valore dell’argo-mento. Si considerino le seguenti definizioni:

(defun sum-of-squares (x y)(+ (square x) (square y)))

Lisp> (sum-of-squares 3 4)25

(defun f (a)(sum-of-squares (+ a 1) (* a 2)))

Lisp> (f 5)136

Seguiamo in dettaglio il processo di valutazione per quest’ultimo esempio;per valutare

(f 5)

si deve prima di tutto ricuperare il corpo di f:

(sum-of-squares (+ a 1) (* a 2))


poi si sostituisce il parametro formale a con il valore dell’argomento (che inquesto caso e 5, trattandosi di un numero):

(sum-of-squares (+ 5 1) (* 5 2))

Il processo continua: i valori degli argomenti (+ 5 1) e (* 5 2), e cioe 6 e10, vengono sostituiti nel corpo di sum-of-squares:

(+ (square 6) (square 10))

Utilizzando la definizione di square, si ottiene:

(+ (* 6 6) (* 10 10))

che si riduce a

(+ 36 100)

e quindi a

136

Il processo qui descritto e detto modello di sostituzione (substitution model);esso serve per dare un significato all’idea di applicazione di una funzione.D’altra parte si tratta di un modello che non rispecchia necessariamenteil funzionamento reale dell’interprete e in ogni caso non e sufficientementepotente per descrivere casi piu complessi, in cui si accetti la mutabilita deidati, come vedremo piu avanti. Si parla talvolta di pure Lisp per indicareil sotto-insieme del linguaggio che aderisce a una visione strettamente fun-zionale.Si osservi che ci sono altre interpretazioni possibili: un’alternativa potrebbeessere di espandere le definizioni di funzioni fino ad ottenere un’espressioneche contenga solo funzioni primitive e procedere solo allora alla valutazione.

(f 5)

diventerebbe successivamente

(sum-of-squares (+ 5 1) (* 5 2))

(+ (square (+ 5 1)) (square (* 5 2)))


(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))

riducendosi poi a

(+ (* 6 6) (* 10 10))

(+ 36 100)

136

Questo ordine di valutazione e detto normale (normal-order evaluation), incontrasto con quello visto prima, detto applicativo (applicative-order evalu-ation). Si puo dimostrare che i due ordini di valutazione sono equivalenti,se e valido il modello di sostituzione.

1.2 Funzioni e processi di calcolo

1.2.1 Ricorsione e iterazione lineari

Si consideri il comunissimo esempio della funzione fattoriale, definita comesegue:

n! = n · (n− 1) · (n− 2) · · · 3 · 2 · 1

Una definizione ricorsiva sarebbe:

n! = n · (n− 1)!

1! = 1

Questa definizione puo essere programmata in Lisp direttamente:

(defun factorial (n)(if (= n 1)

1(* n (factorial (- n 1)))))

D’altra parte, usando la prima definizione, si puo procedere accumulando ivalori delle successive moltiplicazioni e contando il numero di moltiplicazioni:

prodotto← contatore · prodotto

contatore← contatore + 1


(defun factorial (n)(fact-iter 1 1 n))

(defun fact-iter (product counter max-count)(if (> counter max-count)

product(fact-iter (* counter product)

(+ counter 1)max-count)))

Sebbene ambedue le definizioni abbiano forma ricorsiva (le funzioni sono de-finite invocando se stesse), i processi di calcolo creati dalle due funzioni sonomolto differenti: nel primo caso si ha un numero eventualmente elevato dimoltiplicazioni in sospeso: l’interprete ha bisogno di una quantita crescentedi memoria (proporzionale a n) per mantenere l’informazione necessaria: unprocesso di questo tipo si dice linearmente ricorsivo (si veda la Tabella 1.1).

(factorial 6)(* 6 (factorial 5))(* 6 (* 5 (factorial 4)))(* 6 (* 5 (* 4 (factorial 3))))(* 6 (* 5 (* 4 (* 3 (factorial 2)))))(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))(* 6 (* 5 (* 4 (* 3 (* 2 1)))))(* 6 (* 5 (* 4 (* 3 2))))(* 6 (* 5 (* 4 6)))(* 6 (* 5 24))(* 6 120)720

Table 1.1: Processo ricorsivo

Nel secondo caso in ogni momento la situazione e definita dal valore delletre variabili del programma: un processo di questo tipo e detto linearmenteiterativo (si veda la Tabella 1.2).Non si confonda la forma della definizione della funzione, con il tipo di pro-cesso generato! Quando una funzione ricorsiva genera un processo iterativo,si parla di tail recursion.Nei linguaggi tradizionali un processo iterativo viene descritto con strutturesintattiche apposite (esistono anche in Lisp), per evitare lo spreco di memo-ria inerente a un uso inutile di processi ricorsivi. Un buon Lisp dovrebbe


(factorial 6)(fact-iter 1 1 6)(fact-iter 1 2 6)(fact-iter 2 3 6)(fact-iter 6 4 6)(fact-iter 24 5 6)(fact-iter 120 6 6)(fact-iter 720 7 6)720

Table 1.2: Processo iterativo

essere in grado di riconoscere la tail recursion e quindi la presenza di strut-ture sintattiche iterative non e indispensabile. Strutture sintattiche magaricomode, ma non essenziali, sono dette sintactic sugar.

1.2.2 La ricorsione ad albero

In alcuni casi la ricorsione presente nella definizione di una funzione non elineare ma ad albero (tree recursion). Un esempio molto semplice e il calcolodella successione detta di Fibonacci, in cui ogni numero e la somma dei dueprecedenti:

0, 1, 1, 2, 3, 5, 8, 13, 21, . . .

In generale i numeri di Fibonacci possono essere definiti come segue:

F (n) =

0 se n = 01 se n = 1F (n− 1) + F (n− 2) altrimenti

La definizione puo essere tradotta immediatamente in una funzione ricorsiva:

(defun fib (n)(cond ((= n 0) 0)

((= n 1) 1)(t (+ (fib (- n 1))

(fib (- n 2))))))

Per calcolare (fib 5) si devono calcolare (fib 4) e (fib 3) e cosı di se-guito, con un processo che si biforca ad ogni passo.E un esempio interessante, ma naturalmente esistono metodi piu efficientiper calcolare i numeri di Fibonacci: qui si ripetono continuamente calcoli


gia fatti, per cui il processo impiega un tempo che cresce esponenzialmentecon n; lo spazio richiesto invece cresce linearmente. Questo comportamentoe tipico dei processi con ricorsione ad albero.Un approccio iterativo a questo esempio, si basa sull’idea che partendo condue numeri interi a e b inizializzati a 1 e 0 rispettivamente, con la trasfor-mazione simultanea

a← a+ b

b← a

dopo n trasformazioni b sara uguale a F (n).

(defun fib (n)(fib-iter 1 0 n))

(defun fib-iter (a b count)(if (= count 0)

b(fib-iter (+ a b) a (- count 1))))

Questo metodo e una iterazione lineare. Benche la differenza del tempo im-piegato dai due metodi sia notevolissima, non si deve concludere che le ricor-sioni ad albero siano inutili. In altri campi l’approccio ricorsivo rappresentaun mezzo naturale e potente (Si ricordi che il funzionamento dell’interpretee stato descritto in questi termini!).

1.3 Funzioni di ordine superiore

Gli esempi visti finora riguardavano funzioni che hanno come argomenti deinumeri. Definire una funzione rappresenta un’astrazione dai casi particolari,rappresentati dai valori che gli argomenti possono prendere: cosı

(defun cube (x) (* x x x))

definisce come calcolare il cubo di un numero, a prescindere dal suo valorecontingente. Si potrebbero usare espressioni del tipo:

(* 3 3 3)

(* y y y)


ma naturalmente questo sarebbe assai scomodo, essendo obbligati a lavo-rare al livello delle funzioni predefinite e senza la possiblita di esprimere ilconcetto dell’elevazione alla terza potenza. Per questo i linguaggi, tranne ipiu primitivi, offrono la possibilta di definire nuove funzioni.Un passo in avanti nel livello di astrazione e rappresentato da funzioni chemanipolano altre funzioni, come parametri o come risultati.

1.3.1 Funzioni come parametri

Si considerino le seguenti funzioni: la prima calcola la somma degli interi daa a b:

(defun sum-int (a b)(if (> a b)

0(+ a (sum-int (+ a 1) b))))

La seconda calcola la somma dei cubi nell’intervallo definito:

(defun sum-cubes (a b)(if (> a b)

0(+ (cube a) (sum-cubes (+ a 1) b))))

La terza calcola un’approssimazione, non molto buona, di π/8:

(defun pi-sum (a b)(if (> a b)

0(+ (/ 1 (* a (+ a 2))) (pi-sum (+ a 4) b))))

Evidentemente questi tre esempi hanno una struttura simile; in matematicasi usa la notazione seguente:

b∑n=a

f(n) = f(a) + · · ·+ f(b)

Vorremmo definire anche in Lisp una funzione del tipo:

(defun sum (f a step b)...


dove f e la funzione da applicare a ogni termine e step e il passo per calcolareil prossimo termine. Questo e possibile in Common Lisp ma e necessarioavvertire l’interprete quando si intende usare un parametro come funzionetramite funcall:

(defun sum (f a step b)(if (> a b)

0(+ (funcall f a)

(sum f (+ step a) step b))))

Quando si usa sum e necessario avvertire l’interprete che alcuni parametrisono da usare come funzioni; in Common Lisp questo avviene ponendo #’prima del nome della funzione7. Cosı, utilizzando la funzione Common Lisp+ (che, usata con un solo argomento, restituisce l’argomento stesso) si puoottenere l’effetto di sum-int:

Lisp> (sum #’+ 1 1 10)55

E anche possibile definre sum-int tramite sum:

(defun sum-int (a b)(sum #’+ a 1 b))

Per calcolare sum-cubes usiamo la funzione cube, che abbiamo gia definito:

Lisp> (sum #’cube 1 1 10)3025

Per il terzo esempio si dovrebbe definire la funzione pi-f:

(defun pi-f (n)(/ 1 (* n (+ n 2))))

Lisp> (* 8 (sum #’pi-f 1 4 1000))3.13959

In generale e pero scomodo dover definire col proprio nome funzioni chenon hanno un’utilita generale. Per definire pi-sum tramite sum sarebbe

7In realta si dovrebe usare la forma impropria function, ma per comodita di scritturai caratteri #’ hanno un effetto equivalente: (function sin) e #’sin sono la stessa cosa.


opportuno poter esprimere direttamente la funzione pi-f all’interno di sum.Questo e possibile tramite la forma impropria lambda8, che serve a definirefunzioni anonime (usando la stessa sintassi di defun):

(defun pi-sum (a b)(sum #’(lambda (n) (/ 1 (* n (+ n 2))))

a4b))

Lisp> (* 8 (pi-sum 1 1000))3.13592

La funzione definita tramite lambda e una funzione come le altre (ma nonha un nome), e puo essere usato negli stessi contesti:

Lisp> ((lambda (x) (* x x)) 5)25

1.3.2 Funzioni come valori

In Lisp e possibile ottenere funzioni come valori di altre funzioni. Illustria-mo questa possibilita con un esempio tratto dal calcolo infinitesimale: “laderivata di x3 e 3x2.” Questo puo essere interpretato dicendo che “derivata”e un operatore che, applicato alla funzione x3 da come valore la funzione 3x2.Definiamo la derivata tramite la formula (per il limite dx→ 0):

f ′(x) =f(x+ dx)− f(x)

dx.

Usando lambda possiamo esprimere questa formula con la funzione9:

(lambda (x)(/ (- (funcall f (+ x dx)) (funcall f x))

dx))

Si puo andare oltre e definire la funzione deriv che prende come argomentiuna funzione f e un valore (piccolo) per dx e restituisce come valore laderivata della funzione.

8Il nome ha origine dalle teorie logiche sulla computabilita delle funzioni. Non bisognapero lasciarsi spaventare: in Lisp serve solo allo scopo indicato!

9Si tratta ancora di un calcolo numerico della derivata; vedremo in seguito che in Lispe possibile anche darne una definizione simbolica.


(defun deriv (f dx)#’(lambda (x)

(/ (- (funcall f (+ x dx)) (funcall f x))dx)))

Possiamo ora usare la funzione cosı definita per calcolare la derivata dellafunzione cube nel punto 5 (il valore esatto e naturalmente 75):

Lisp> (funcall (deriv #’cube 0.0001) 5)75.015

Anche in questo caso, in Common Lisp e necessario usare funcall perindicare l’applicazione di una funzione e #’ per evitare che venga usato ilvalore dell’atomo cube.

Il metodo di Newton per gli zeri di una funzione

Per mostrare le possibilita offerte dal calcolo della funzione derivata, voglia-mo implementare l’algoritmo di Newton per gli zeri di una funzione differen-ziabile. Se x0 e una approssimazione dello zero,

x1 = x0 −f(x0)f ′(x0)

e una approssimazione migliore.L’approssimazione successiva, a partire da un valore iniziale (qui chiamatoguess), viene espressa in Lisp come segue:

(defun newton (f guess)(if (< (abs (funcall f guess)) 0.00001)

guess(newton f (improve-guess f guess))))

Il miglioramento dell’approssimazione avviene con la funzione deriv:

(defun improve-guess (f guess)(- guess (/ (funcall f guess)

(funcall (deriv f 0.00001) guess))))

Possiamo ora controllare il funzionamento di newton:

Lisp> (newton #’(lambda (x) (- (cos x) x)) 1)0.739

Chapter 2

I dati come astrazione

Finora abbiamo visto funzioni che hanno come valore numeri (o eventual-mente altre funzioni), ma un linguaggio evoluto deve dare la possibilita di us-are forme piu complesse di valori, i cosiddetti dati strutturati. La definizionedi questo tipo di dati puo essere difficoltosa: ripieghiamo sull’approccioseguente:

• Devono esistere funzioni dette costruttori (constructors) che permet-tono di costruire il dato strutturato a partire da dati piu semplici.

• Devono esistere funzioni dette selettori (selectors) che, a partire daldato strutturato, permettono di estrarre i dati piu semplici che li com-pongono.

Studieremo prima di tutto le strutture tipiche del Lisp, per poi affrontare iltema in generale.

2.1 La lista

La struttura di dati fondamentale nel linguaggio Lisp e la lista1: essa e purela forma sintattica fondamentale, realizzando la completa identita tra dati eprogrammi, tipica del Lisp. Abbiamo gia definito la lista a pag. 3, dicendoche e un elenco di espressioni (simboliche) racchiuso da parentesi rotonde;un’espressione a sua volta puo essere un atomo o una lista.

1Lisp significa appunto LISt Processing (e non Lots of Insane and Stupid Parentheses,come affermano i detrattori)

18

CHAPTER 2. I DATI COME ASTRAZIONE 19

Il costruttore: cons

Data la definizione ricorsiva di lista, il costruttore avra un approccio ricor-sivo alla costruzione: esso aggiunge un elemento in testa alla lista data.Supponiamo che il valore di lis sia (5 7 9):

Lisp> lis(5 7 9)

Lisp> (cons 3 lis)(3 5 7 9)

Lisp> lis(5 7 9)

Il costruttore non modifica l’argomento! In un certo senso il valore fornitoe una nuova lista. Per poter porre il primo elemento, bisogna aggiungerloalla lista vuota; questa puo essere rappresentata come () oppure come nil.nil e contemporaneamente un atomo (il simbolo il cui valore e nil) e unalista (la lista vuota ()): questa (unica!) coincidenza rispecchia il ruolo dinil come “elemento neutro” della costruzione di liste.

Lisp> (cons 1 ())(1)

In questo modo si possono p.es. costruire liste di risultati: supponiamo didisporre del predicato primep che verifica se un numero e primo; per costru-ire la lista dei primi inferiori a n, definiamo la funzione seguente:

(defun prim-list (n)(cond ((zerop n) ())

((primep n) (cons n (prim-list (1- n))))(t (prim-list (1- n)))))

Si osservi che, per ora, cons puo esser usato solo se il secondo argomento euna lista!

I selettori: first e rest

I selettori eseguono il compito inverso a quello di cons: data una lista,essi selezionano la prima espressione (first) e il resto della lista (rest)2:

2Per motivi storici, i nomi piu diffusi per queste primitive sono car e cdr; in altricontesti si usano anche i nomi testa (head) e coda (tail), che non sono pero predefiniti inCommon Lisp.


l’argomento deve essere una lista!

Lisp> lis(5 7 9)

Lisp> (first lis)5

Lisp> (rest lis)(7 9)

Lisp> lis(5 7 9)

Anche i selettori non modificano l’argomento! Data la loro definizione eevidente che, per una lista qualsiasi, vale:

Lisp> lis(5 7 9)

Lisp> (cons (first lis) (rest lis))(5 7 9)

Lisp> (first (cons 3 lis))3

Lisp> (rest (cons 3 lis))(5 7 9)

Le espressioni simboliche

Una caratteristica del Lisp e la possibilita di lavorare a livello simbolico:finora gli atomi visti erano numeri e i simboli avevano come valore un nu-mero. Questa restrizione non e necessaria! Per poter operare con i simboli,dobbiamo superare una difficolta: nell’esempio:

Lisp> (cons 1 ())(1)

l’interprete segue la regola di valutazione e valuta gli argomenti, trovando 1e nil; passa poi alla costruzione della lista. Non e invece possibile costruirein questo modo la lista (a):


Lisp> (cons a ())Error . . .

L’interprete vuole il valore di a! Dobbiamo quindi poter disporre di unaforma impropria che eviti la valutazione dell’espressione. Lo stesso prob-lema lo si ritrova nel linguaggio di tutti i giorni: alla domanda “Dimmicome ti chiami” ci aspettiamo un nome in risposta, ma all’invito “ripeti‘Come ti chiami?’ per favore” vorremmo sentir ripetere la domanda citatatra virgolette! Anche in Lisp si dice che un’espressione da non valutare vienecitata (quoted) e si indica con un apice3 davanti ad essa:

Lisp> ’aa

Lisp> ’(mele pere)(mele pere)

Lisp> (defvar lista ’(mele pere noci))lista

Lisp> (first lista)mele

Lisp> (rest ’(mele pere noci))(pere noci)

Per poter lavorare a livello simbolico sono indispensabili due predicati (cheinsieme a cons, car e cdr formano le 5 funzioni base del Lisp): atom e vero(t) se il suo unico argomento e un atomo (cioe non e una lista)4; eq ha dueargomenti (che dovrebbero essere atomi): esso e vero (t) se i due atomi sonoidentici5.Sia per esempio da definire una funzione my-member che controlli se unsimbolo sia presente in una lista:

3Si tratta di una stenografia per la forma impropria quote: (quote expr) e ’expr

sono la stessa cosa. Questi caratteri che influenzano il modo in cui l’interprete legge leespressioni sono detti macro-characters (vedi anche la nota a pag. 15).

4Attenzione: atom e uno dei pochi predicati che non terminano con la lettera p. Eanche disponibile il predicato listp che da la risposta contraria.

5Va usato solo per atomi simbolici: negli altri casi si usi equal e per i numeri =; sonoa disposizione anche predicati per casi particolari: null controlla se l’argomento e nil ola lista vuota, zerop controlla se un numero e zero, ecc.


(defun my-member (at lis)(cond ((null lis) nil)

((eq at (first lis)) t)(t (my-member at (rest lis)))))

Questo esempio illustra il metodo per lavorare con una lista: prima si studiail first della lista e poi il rest con una chiamata ricorsiva. Qual e il valoredella funzione boh?

(defun boh (lista)(cond ((null lista) nil)

(t (cons (first lista) (boh (rest lista)))))

Due primitive molto utili, lavorando con liste, sono list e append. Laprima prende un numero variabile di espressioni come argomenti e crea unalista che le contiene; la seconda prende un numero variabile di liste comeargomenti e ne fa una lista sola:

Lisp> (list ’miele ’zucchero ’saccarina)(miele zucchero saccarina)

Lisp> (append ’(a b) ’(c d e) ’(f))(a b c d e f)

Se ci si limita a due argomenti, la loro definizione a partire dalle primitivefondamentali e evidente.

Che cos’e una lista?

In realta il costruttore cons accetta come argomenti due espressioni qualsiasie da come valore una coppia detta puntata (dotted pair), i cui elementipossono essere selezionati con car e cdr6:

Lisp> (cons ’a ’b)(a . b)

Lisp> (defvar pair (cons ’a ’b))pair

Lisp> (car pair)a

6In questo contesto l’uso dei nomi storici sembra piu adatto.


Lisp> (cdr pair)b

Un metodo di visualizzare questo fatto e il seguente: gli atomi a e b vengonorappresentati da celle: cons crea una nuova cella che contiene i puntatoriai due atomi come si vede nella Fig. 2.1. Una lista di uno o piu atomi,

r r��

@@@R

a b

(a . b)

Figure 2.1: Coppia puntata.

formata con l’applicazione successiva di cons, viene rappresentata come nellaFig. 2.2. L’interprete usa la notazione con il punto solo quando non e in

nilr��

a

(a . nil)

(a)

r��

a

rHHHjr��

b

rHHHjr��

c

nil

(a . (b . (c . nil)))

(a b c)

Figure 2.2: Liste di atomi.

grado di usare la notazione tipica con le liste. I selettori forniscono quindiuno dei puntatori, senza modificare la struttura esistente! Lo stesso atomo(o la stessa lista) puo far parte di differenti strutture. La Fig. 2.3 mostrauna lista nella quale la prima espressione e a sua volta una lista. Questarappresentazione rende chiari alcuni meccanismi, altrimenti un po’ astrusi.Il predicato eq per esempio considera uguali due oggetti identici: se si tieneconto del fatto che cons costruisce in ogni caso una nuova cella, questi esempirisulteranno chiari:


r��9r��

a

rHHHjr��

b

nil

rXXXXXXXzr��

c

nil

((a . (b . nil)) . (c . nil))

((a b) c)

Figure 2.3: Lista con sottolista.

Lisp> lista(mele pere noci)

Lisp> (eq ’lista ’lista)t

Lisp> (eq lista lista)t

Lisp> (eq lista ’(mele pere noci))nil

Lisp> (eq (car lista) ’mele)t

Per i numeri il Common Lisp lascia liberta agli implementatori di usarepuntatori o rappresentazioni esplicite e permette l’uso di copie, per motividi efficienza: questo rende l’uso di eq con numeri dipendente dall’imple-mentazione (Si dovra quindi partire dall’idea che due numeri, anche con lostesso valore, non saranno necessariamente eq). La funzione append usa ilpuntatore all’ultima lista; per le altre liste crea copie delle strutture, che siriferiscono agli stessi atomi, per non modificare gli argomenti (vedi Fig. 2.4).Cosı lavora la maggior parte delle funzioni che operano su liste. Esistonoanche funzioni che modificano gli argomenti: benche siano talvolta piu effi-cienti, il loro uso non e compatibile con un approccio puramente funzionale.


lista1(a b)

-

(append lista1 lista2) -

lista2(c d)

-

r?

a

r - r?

b

nil

r6 r - r6 r?r?

c

r - r?

d

nil

Figure 2.4: Effetto di append.

Contents

1 La funzione come astrazione 3

1.1 Il linguaggio Lisp . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.1 L’interprete . . . . . . . . . . . . . . . . . . . . . . . . 31.1.2 La definizione di funzioni (e simboli) . . . . . . . . . . 51.1.3 L’editor . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.4 Espressioni condizionali e predicati . . . . . . . . . . . 71.1.5 L’applicazione di funzioni . . . . . . . . . . . . . . . . 8

1.2 Funzioni e processi di calcolo . . . . . . . . . . . . . . . . . . 101.2.1 Ricorsione e iterazione lineari . . . . . . . . . . . . . . 101.2.2 La ricorsione ad albero . . . . . . . . . . . . . . . . . . 12

1.3 Funzioni di ordine superiore . . . . . . . . . . . . . . . . . . . 131.3.1 Funzioni come parametri . . . . . . . . . . . . . . . . 141.3.2 Funzioni come valori . . . . . . . . . . . . . . . . . . . 16

2 I dati come astrazione 18

2.1 La lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

26

Linguaggi di Programmazione LISP - people.dti.supsi.chpeople.dti.supsi.ch/~lepori/lisp.pdf ·...

Documents

Transcript of Linguaggi di Programmazione LISP - people.dti.supsi.chpeople.dti.supsi.ch/~lepori/lisp.pdf ·...