1 Linguaggi di Programmazione Corso di Laurea in Informatica Introduzione ai linguaggi funzionali.
-
Upload
uberto-marinelli -
Category
Documents
-
view
225 -
download
6
Transcript of 1 Linguaggi di Programmazione Corso di Laurea in Informatica Introduzione ai linguaggi funzionali.
1
Linguaggi di ProgrammazioneLinguaggi di Programmazione
Corso di Laurea in InformaticaCorso di Laurea in Informatica
Introduzione ai linguaggi funzionaliIntroduzione ai linguaggi funzionali
2
I linguaggi imperativiI linguaggi imperativi
– variabili = celle, nome = indirizzo– azione unitaria: istruzione– programma: combinazione di istruzioni
Basati sull’architettura di Von Neumann:– memoria costituita da celle identificate da un indirizzo,
contenenti dati o istruzioni– unità di controllo e aritmetica
Concetto di assegnamento di valori a variabiliConcetto di assegnamento di valori a variabiliOgni valore calcolato deve essere esplicitamente memorizzato, cioè assegnato ad una cella
Concetto di iterazioneConcetto di iterazioneun programma consiste nell’esecuzione iterativa di una sequenza di passi elementari
3
Effetti collateraliEffetti collaterali
Caratteristiche negative dei linguaggi imperativi: Caratteristiche negative dei linguaggi imperativi: gli effetti collateraligli effetti collaterali
• Effetti collaterali– Modifiche di dati non legati a variabili locali
• Sono utilizzati come mezzo di comunicazione tra le diverse unità di un programma:
– Variabili globali– Passaggio di parametri per indirizzo
• Problemi:– Distinguere tra effetti collaterali desiderati e non desiderati– Leggibilità del programma (l’istruzione di chiamata non rivela quali variabili globali sono coinvolte)– E’ difficile verificare la correttezza di un programma
4
Effetti collateraliEffetti collaterali
• w := x + f(x,y) + z
– f() può modificare x e y se sono passati per indirizzo, e z se è globale– si riduce la leggibilità del programma– non ci si può fidare della commutatività dell’addizione!
• u := x + z + f(x,y) + f(x,y) + x + z
– gli stessi problemi dell’esempio precedente...– ...più l’impossibilità per il compilatore di generare codice ottimizzato valutando una sola volta x + z e f(x,y)
5
Effetti collateraliEffetti collaterali
• Trasparenza referenzialeTrasparenza referenziale: il significato del tutto si può determinare dal significato delle parti
• Tutti i concetti matematici, in particolare le espressioni, possiedono la proprietà di trasparenza referenziale
EsempioEsempio:
– nell’espressione matematica f(x) + g(x) si può sostituire f con f’ se producono valori identici
– linguaggi imperativi tradizionali: non si può essere certi dellasostituzione, né che f(x)+ g(x) = g(x)+ f(x), né che f(x)+f(x) = 2* f(x)
6
I linguaggi funzionaliI linguaggi funzionali
Programmi = funzioni matematicheProgrammi = funzioni matematiche
– concetto base: funzioni primitive– combinazione di funzioni primitive per produrne di più potenti– conservano la trasparenza referenziale della matematica
FunzioneFunzione: regola per associare gli elementi di un insieme (dominio) a quelli di un altro insieme (codominio)
• Una funzione può essere applicata a un elemento del dominio• L’applicazione produce (restituisce) un elemento del codominio
EsempioEsempio:quadrato(x) = x*x, dove x è un numero intero, detto argomentoargomento, che indica un generico elemento del dominiox è una variabile matematica, non di programma (non ha senso pensare di modificarla!)
7
Programmazione funzionale: Programmazione funzionale: combinazione di funzionicombinazione di funzioni
• Consente di creare funzioni complesse a partire da funzioni più semplici
• Se F è definita come composizione di G e H:F = GºH
applicare F equivale ad applicare G al risultato dell’applicazione di H
EsempioEsempio:alla_quarta = quadratoºquadrato
quindiquindi:alla_quarta(5) = quadrato(quadrato(5))
8
Programmazione funzionale: Programmazione funzionale: ricorsionericorsione
Le funzioni nei linguaggi imperativi sono definite in modo procedurale:– Regola di trasformazione dal dominio al codominio: passi da eseguire in un ordine determinato dalle strutture di controllo
Nella programmazione funzionale pura non Nella programmazione funzionale pura non esiste la possibilità di generare effetti esiste la possibilità di generare effetti
collateralicollaterali
In matematicamatematica:– In termini di applicazione di altre funzioni (spesso ricorsivamente)
EsempioEsempio:– fattoriale(n) = if n = 0 then 1 else n*fattoriale(n-1)
9
Programmazione funzionale: Programmazione funzionale: caratteristichecaratteristiche
• La principale modalità di calcolo è l’applicazione di funzioni
• Nei linguaggi funzionali “puri” non esistono strutture di controllo predefinite per la realizzazione di cicli quali for, while, repeat, ma il principale meccanismo di controllo è la ricorsione.
• I linguaggi funzionali consentono l’uso di funzioni di ordine superiore, cioè funzioni che prendono funzioni come argomento o restituiscono funzioni come valore, in modo assolutamente generale
• Le funzioni sono oggetti di prima classe: possono essere componenti di una struttura dati, o costituire l’argomento o il valore di altre funzioni.
• Il calcolo procede valutando espressioni. Non ci sono effetti collaterali.
10
• LISP: acronimo di LISt Processing (elaborazione di liste)
• Prima versione: John McCarthy (1960, “Lisp puro”):completamente funzionale
– non esistevano variabili– le uniche espressioni ammesse erano la
definizione di funzioni e l’applicazione di funzioni
Il linguaggio LispIl linguaggio Lisp
• Standard attuale: Common Lisp
• Oggi è comunque il linguaggio che più si avvicina al modello di linguaggio funzionale
• In seguito sono state introdotte caratteristiche non funzionaliper aumentare l’efficienza
11
• Il Lisp è un linguaggio interpretato
Il linguaggio LispIl linguaggio Lisp
• L’interprete esegue ripetutamente un ciclo read- eval- print:– legge un’espressione inserita dall’utente (read)– la valuta (eval)– scrive il risultato su schermo (print)
• L’interazione avviene attraverso una finestra detta listener
12
• Gli unici oggetti (strutture dati) Lisp sono espressioni espressioni simbolichesimboliche:
– AtomiAtomi– ListeListe
Il linguaggio LispIl linguaggio Lisp
Quindi dati e programmi sono rappresentati nello stesso modo.
Anche i programmi Lisp sono espressioni costituite da atomi o liste!
EsempiEsempi: (A), (A John c3po 68000), ((A John) c3po (68000)), ()
• ListeListe– sono sequenze ordinate di oggetti, cioè atomi o
liste (ricorsivamente)
• AtomiAtomi– sono rappresentati da stringhe di caratteri– es.: A, John, c3po (simboli),
68000, -15, 1.502, 1.24E-3 (numeri)
13
Formalmente le S-espressioni (espressioni simboliche) sonodefinite come:
Il linguaggio LispIl linguaggio Lisp
14
• Usati per dare un nome a variabili, costanti, funzioniSequenze di caratteri che possono includere: numeri, lettere, alcuni caratteri alfanumerici:*-+/@$%^& _ < > ~
Il linguaggio LispIl linguaggio Lisp simbolisimboli
• Predicato: symbolp (restituisce T quando l’argomento dato è un simbolo)
• Simboli speciali:– T (“vero”),– NIL (“falso”, ma anche lista vuota)
(in pratica, ogni identificatore che non e’ un numero e’ un simbolo)– pippo, valore_max, B.3, 7-11 … sono simboli– 3.14, 8, … non sono simboli– Non si fa distinzione tra maiuscole e minuscole
15
Il linguaggio LispIl linguaggio Lispnumerinumeri
• Tipo implicito: number• integer, float• Es. 0.5, 3.1415, 602E+21 (60221) …• NB: le frazioni, come 2/3, 25/100 … non sono simboli mavengono trattati come numeri frazionari• Operazioni:
– +, -, *, /, sqrt, abs …• Predicati: numberp, integerp …, plusp, zerop …=, >, <, >=,<= …
16
Il linguaggio LispIl linguaggio Lisple listele liste
Una lista ha una definizione ricorsiva:ricorsione
Liste hanno profondità illimitata orizzontale e verticale
• (a ((b b )) (c d (e)))• ((((a))) ((((b) c))))
EsempiEsempi:• (a b c) lista semplice (elementi al primo livello sono atomi)
• (( alfa 1) beta (gamma delta (5 127) ro)) e` una lista di liste
– (l1 … ln) S-espressioni separate da spazi (li atomo o lista)
– () (lista vuota, o NIL)
17
18
• In Lisp esistono tre tipi di espressioni valide:– atomi– funzioni– espressioni speciali (special form)
• Atomi– <nome atomo>
• Applicazione di funzioni(<nome funzione> <arg1> … <argn>)
• Espressioni speciali (funzioni speciali)(<nome espressione speciale> <arg1> …
<argn>)
Espressioni LispEspressioni Lisp
Le S-espressioni sono usate per rappresentare:– dati– definizioni di funzioni– applicazioni di funzioni
19
Valutazione di espressioni LispValutazione di espressioni Lisp
– Atomi:la valutazione restituisce il valore associato (se non esiste: errore)
Atomi o listeAtomi o listeAtomoAtomo
si noti la notazione prefissa!
La distinzione dipende dal nome (primo atomo della lista)
• Espressioni speciali (<nome espressione> <arg1> … <argn>):si passano all’espressione gli argomenti non valutati
• Applicazione di funzione (<nome funzione> <arg1> … <argn>):si passa alla funzione il risultato della valutazione dei suoi argomenti
– Liste:
20
Funzioni matematicheFunzioni matematiche:+, -, *, /, mod, exp, sqrt, sin, cosEsempioEsempio: (+ 1 2)
(* 3 5)(mod 5 2)
Funzioni predefiniteFunzioni predefinite
I piu’ semplici programmi da eseguire
21
Funzioni predefinite per l’elaborazione di listeFunzioni predefinite per l’elaborazione di liste
a) Costruzione di liste: funzione a) Costruzione di liste: funzione cons: S-Exp cons: S-Exp List List List List(cons <atomo> <lista>) inserisce <atomo> in testa a <lista> Esempi: Esempi: (cons 1 ()) (1)
(cons 1 (cons 2 ())) (1 2)(cons (1 2) (3)) ((1 2) 3)
per convenzione significa: ha valore uguale a
Funzioni predefiniteFunzioni predefinite
22
Esempi: Esempi: (car (cons 1 (cons 2 ()))) 1 (car (cons (cons 1 (cons 2 ())) (cons 3 (cons 4 ())))) (car ‘((1 2) 3 4)) (1 2)
(cdr (cons (cons 1 (cons 2 ())) (cons 3 (cons 4 ())))) (cdr ‘((1 2) 3 4) (3 4) ((x) b (c)) ha come first: (x), come rest: (b (c))
b) Selezione di elementi: funzioni b) Selezione di elementi: funzioni car (first) e cdr (rest)car (first) e cdr (rest) car: List car: List S-Exp cdr: List S-Exp cdr: List List List
car restituisce il primo elemento di una listacdr restituisce la lista senza il primo elemento
(car = content of address register, cdr =content of decrement register)
Con cons, car e cdr è possibile eseguire qualsiasi operazionesulle liste (fusione, inserimento, estrazione, ecc.)
Funzioni predefiniteFunzioni predefinite
23
Sono funzioni che restituiscono T o NIL(Per rappresentare True e False in Lisp si usano gli atomi T e NIL)
Predicati per test di tipo:Predicati per test di tipo:
symbolp, numberp, integerp, floatp, atom, listp
Funzioni predicato predefiniteFunzioni predicato predefinite
(atom 5) T, (atom nil) T, (atom (cons 1 ())) NIL, (atom (car (cons 1 ())) T (listp 2) NIL, (listp (cons 5 ())) T
Per controllare se un oggetto è un atomo o una lista: Per controllare se un oggetto è un atomo o una lista: atom listp
– null: per liste (T se lista e’ vuota, NIL altrimenti)
– per i numeri: plusp, zerop …=, >, <, >=, <=(= 1 1) T, (= (car (cons 1 (cons 2 ()))) 2) NIL(> 1 5) NIL, (< 1 2) T, (<= 5 5) T
Predicati di confrontoPredicati di confronto
24
Predicato andPredicato and(and e1 … en)
– se il risultato della valutazione di tutte le espressioni e1 … en è diverso da NIL, and restituisce il risultato della valutazione di en;– altrimenti restituisce NIL
Funzioni predicato predefiniteFunzioni predicato predefinite
Predicato orPredicato or(or e1 … en)
– se il risultato della valutazione di tutte le espressioni è NIL, or restituisce NIL;– altrimenti restituisce il risultato della valutazione della prima espressione diversa da NIL
Quindi le espressioni possono non essere valutate tutte.
25
26
27
Altre funzioni sulle liste
list: S-Expression* list: S-Expression* List List trasforma i suoi argomenti in una lista
Esempi:(list '(12) ' a '(b 3) ' d) ((12) a (b 3) d)(list () () ) ( () () )
Append : List x List Append : List x List List List concatena i suoi argomenti in un’unica lista
Esempi:(append ‘((12) a) ‘((b 3) d)) ((12) a (b 3) d) (append () '((b 3) d)) ((b 3) d) (append () () ) ()
28
29
30
31
Un “programma” in Lisp e’ costituito da liste.
Un programma e’ quindi manipolabile come una struttura dati base del Lisp:
– Possibilità di scrivere programmi che manipolano programmi
– Facilitazione dell’interprete che “vede” una rappresentazione del programma come lista.
Programmi come datiProgrammi come dati
32
L’interprete Lisp presenta un prompt ed esegue un ciclo“leggi-valuta-stampa”.
Valutazione di S-espressioniValutazione di S-espressioni
EsempioEsempio:> (+ 5 9) forma da valutare14
• Leggi: parsing di una S-Exp (detta ‘forma’), scritta dall’utente• Valuta: calcola il valore associato alla S-Exp• Stampa: scrive sul video il risultato
33
Se s e’ costante numerica o uno dei simboli speciali T e NIL,
eval(s) = s
Valutazione di S-espressioniValutazione di S-espressioni
Una S- espressione è automaticamente valutata dalla funzione eval, all’interno di un ambiente che utilizza regole:
Diverso comportamento per le funzioni speciali (cond, if, etc.)
Se s è un simbolo, eval(s) = env(s),
dove env(s) restituisce il valore associato al simbolo; se al simbolo non è associato nessun valore: eval(s) = errore.Se s è una lista (s1 s2 … sn): se s1 e’ il nome di una funzione nota, eval valuta gli argomenti s2, .., sn da sinistra a destra e applica la funzione s1 al valore degli argomenti. Se s1 non e’ nota: eval(s) = errore
34
> 3 3> T T> NIL NIL> (*(+ 2 4)(/ 14 7)) 12> (+ 1 2 3 4) 10> (= (+ 1 2) 3) T> (= (+ 1 1) 3) NIL
Esempi di valutazioneEsempi di valutazione
35
• Implementano il costrutto di controllo• Sono necessarie per la definizione di nuove funzioni
SintassiSintassi:
(condcond (p1 e1) … (pn en))
– vengono valutate in sequenza le espressioni p1 …pn , fino alla prima pi il cui valore è diverso da NIL; viene quindi restituito il risultato della valutazione della corrispondente ei– Tipicamente pn è l’espressione T (condizione di default)Esempio: (cond ((< x 0) (* x -1))
((> x 0) (* x x)) (T 1))
Funzioni condizionaliFunzioni condizionali
36
Il Lisp ha altre possibilità di espressione di strutture di selezione: if, case, when,...1) (if e1 e2 e3)(if e1 e2 e3)
Il valore restituito è quello di e2 se e1 è valutata T, altrimenti è e3 (come if..then..else)2) (if e1 e2)(if e1 e2) e’ come (if e1 e2 nil)
if è forma speciale perché valuta solo una S-Exp fra e2 ed e3 (valutazione cortocircuitata)Esempi: (if (< x 0) (- x) x)
(if (> x 0) (/ y x) y)(/ y x) e’ indefinito per x = 0!
Funzioni condizionaliFunzioni condizionali
37
Funzione speciale DEFUNDEFUN:
(defundefun abs (x) (if (< x 0) (- x) x))
ArgomentiArgomenti: nome funzione, lista parametri formali, corpo
DEFUN lega il simbolo ABS alla funzione costituita dal suo terzo argomento
Dal momento della valutazione di (defun abs …), la funzione utente ABS è come una funzione di sistema:
> (abs -4) 4NB: defun restituisce come valore la funzione definita.
Definizione di funzioni utenteDefinizione di funzioni utente
38
Si parte con ambiente “globale” che contiene i legami predefiniti
L’applicazione di una funzione ai suoi argomenti genera un ambiente “locale”
Valutando (ABS -3), il parametro formale x viene legato (“legame fluido”) al parametro attuale -3.
Finchè dura la valutazione di (ABS -3), (eval x) restituisce -3
Alla fine il legame fluido viene rilasciato.
Valutazione di funzioni utenteValutazione di funzioni utente
39
>(defun double (n) (* 2 n))
estende l’ambiente globale con il legame tra doublee la sua definizione
> (double 3)
• estende l’ambiente globale con quello locale che contiene i legami tra parametri formali e valori dei parametri attuali• valuta il corpo della funzione• ripristina l’ambiente di partenza
Definizione di funzioni utente: Definizione di funzioni utente: esempioesempio
40
>(defun second (L) (first (rest L)))
>(second '(a b c)) b
Definizione di funzioni utente: Definizione di funzioni utente: esempiesempi
>(defun cons2 (x y L) (cons x (cons y L)))
>(cons2 'a 'b '(c d e)) (a b c d e)
41
• Linguaggi Funzionali “puri” sono Turing-completi: ogni algoritmo esprimibile con macchina di Turing o di Von Neumann può essere espresso
• Non consentono assegnamenti, iterazioni, salti, ma usano RICORSIONERICORSIONE
• Lisp non e’ in realtà un linguaggio funzionale puro,ma in origine lo era
RicorsioneRicorsione
42
Il fattoriale0! = 1, n! = n *(n-1)! per n>0
(DEFUN FATT (N)(IF (ZEROP N) 1(* N (FATT (- N 1)))))
Ricorsione: esempioRicorsione: esempio
43
Al prompt:> (fatt 3)
n diventa legato a 3:
(eval (fatt 3)) (eval (if (zerop 3) 1 (*3 (fatt (- 3 1))))) (* 3 (fatt 2)) (*3 (* 2 (fatt 1))) (* 3 (* 2 (* 1 (fatt 0)))) (* 3 (* 2 (* 1 1))) … 6
Eval applica la funzione al suo argomento, definendo i legami di N “in cascata” e costruendo una espressione che alla fine verra’ valutata, a partire dalla sotto-espressione piu’ annidata
Ricorsione: valutazione del Ricorsione: valutazione del fattorialefattoriale
44
• la struttura ricorsiva delle liste si presta molto bene alla programmazione ricorsiva.
• Metodo:– scrivere il valore della funzione nel caso banale
(usualmente la lista vuota)– ridursi ricorsivamente al caso base operando suun argomento ridotto
Ricorsione con listeRicorsione con liste
45
Funzioni ricorsiveFunzioni ricorsive
• Specificare la funzione- sommatoria degli elementi di una lista (si assume che
gli atomi siano numeri interi)
- Sum: List Integer
• Specificare la soluzione in modo ricorsivo- se la lista è vuota il risultato è 0: Lista vuota (): 0
- altrimenti: Lista l: first(l)+sum(rest(l))
• Implementazione(defun sum (x)
(if (null x) 0(+ (first x) (sum (rest x)))))
46
(defun sum (x)(if null(x) 0(+ first(x) (sum (rest x)))))
Esempio: sum applicata alla lista eval(sum ‘(3 4 5))
1) (+ 3 (sum (4 5)))
2) (+ 4 (sum (5)))
4) (+ 5 (sum ()))
Esempio di valutazioneEsempio di valutazione
0
5
9
47
Lunghezza di una lista: numero di elementi alprimo livello>(lung '(a b c)) 3>(lung '(((a) b) c)) 2>(lung NIL) 0
Se lista e’ vuota, lung = 0, altrimenti 1+ lung rest:
(defun lung (L)(if (null L) 0(+ 1 (lung (rest L)))))
Esempio di ricorsioneEsempio di ricorsione
48
Esempio di valutazioneEsempio di valutazione
• (lung '(a b))• (eval (lung ‘(a b)) = (if (null L) 0 (+ 1 (lung (rest L)))) [L (a b)]= (+ 1 (lung (rest L))) [L (b)]= (+ 1 (if (null L) 0 (+ 1 (lung (rest L))))= (+ 1 (+ 1 (lung (rest L)))) [L ()]= (+1 (+ 1 0)) = (+ 1 1) = 2
La valutazione si arresta se si raggiunge unacondizione di uscita; la lista NON viene modificata
49
Estrarre n-esimo elemento (al primo livello) da una lista data (che si suppone abbia almeno n elementi)– (ennesimo 3 '(a b c d)) c– (ennesimo 3 '(a (b c) d)) d
(defun ennesimo (n L)(if (= n 1) (first L)(ennesimo (- n 1) (rest L))))
Un altro esempioUn altro esempio
50
Last-l(L)
(defun last-l (lst) ;; in Lisp esiste la funzione predefinita last
(cond ((atom lst) ’errore );; eccezione ((null lst) nil);; eccezione /nil ????/((null (cdr lst)) (car lst) );; caso base(t (last-l (cdr lst)))));; passo induttivo
Funzione che restituisce l’ultimo elemento di L
51
Last-l(L): valutazione• ( last-l '(a b c))
• eval (last-l '(a b c) ) (last-l (cdr '(a b c)))) ( last-l '( b c) ) …. (last-l '(c) ) (car '(c) ) c
52
Liste come risultato
• supponiamo di dover costruire la funzione my-append partire dalle funzioni CAR,CDR,CONS e i condizionali
(defun my-append (l1 l2) (cond ((null l1) l2)
(t (cons (car l1) (my-append (cdr l1) l2)))))
53
But-last(L)
(defun but-last (lst) (cond ((atom lst) lst)
((null lst) nil)((null (cdr lst)) nil)(t (cons (car lst) (but-last (cdr lst))))))
Funzione che restituisce una lista meno l’ultimo elemento
54
But-last(L): valutazione• (but-last '(a b c))
• eval (but-last '(a b c)) (cons (first '(a b c)) (but-last (cdr '(a b c)))) ( cons 'a (but-last '(b c))) …. (cons 'a ( cons 'b '(but-last '(c)))) …. (cons 'a ( cons ’b ())) (a b)
55
Ricorsioni semplici e doppieRicorsioni semplici e doppie
Ricorsione semplice (“ricorsione cdr”): la ricorsione e’ sempre definita sul rest di una lista
Non è sempre sufficiente.
Esempio: contare gli atomi di S-exp
(conta-atomi '((a b c) 1 (xyz d))) 6
56
Ricorsioni car e cdrRicorsioni car e cdr
• Base: () 0, atomo 1 (due casi, perche’ Sexppuo’ essere sia lista sia atomo)
•Ip: (conta-atomi (rest L)) n. atomi di rest di L
• Passo: se (first L) e’ atomo (+ 1 (conta-atomi (rest L))altrimenti...????
57
Ricorsioni car e cdrRicorsioni car e cdr
Ricorsione “car-cdr” (“doppia”): ricorsioneanche sul car (first) di una lista
(first L) e (rest L) sono sottostrutture di L: possiamo usare Ip.Ric.:(conta-atomi (first L)) e (conta-atomi rest L)) contano correttamente i loro atomi
58
Passo: (+ (conta-atomi (first L)) (conta-atomi (rest L)))
Passo e composizionePasso e composizione
(defun conta-atomi (x) ;; x puo' essere S-exp (cond ((null x) 0) ((atom x) 1) (T (+ (conta-atomi (first x)) (conta-atomi (rest x))))))
59
Esempio ric. car-cdr: Esempio ric. car-cdr: profondita’profondita’
• Profondita’ massima di annidamento di una Sexp (n. max parentesi “sospese”):
atomo 0, ( ) 1, (a (b ((c)) (d))) 4
• 3. Passo: prof di x e’ max fra (prof (first x)) + 1
e (prof (rest x))
• 1. Base: ovvia (caso banale atomo o lista vuota)
• 2. Ip.Ric: (prof (first x)), (prof (rest x))
60
(defun prof (x)(cond ((null x) 1) ((atom x) 0) (T (max (+ 1 (prof (first x)))
(prof (rest x))))))
ComposizioneComposizione
Usiamo funz. lisp predefinita max:(defun max (m n) (if (> m n) m n)))
61
X = (a (b))1) T (max (+1 (prof 'a)) (prof '((b)))
1
1
2) (prof 'a) = 0 (prof '((b))) (max (+ 1 (prof '(b))) (prof ()))
3) (prof ()) = 1 (prof '(b)) (max (+ 1 (prof 'b)) (prof ()))
4) (prof 'b) = 0 (prof ()) = 1
11
2
2
ValutazioneValutazione
62
Appiattire una S-Exp:
(SQUASH '((a (b (c d)) e) f)) (a b c d e f)
(SQUASH 'a) (a) ??perche’??
Esempio: Esempio: SQUASHSQUASH
Passo: append di SQUASH (first x) con SQUASH ( rest x)
Ip.Ric.: SQUASH (first x), SQUASH ( rest x)
Base: lista vuota non cambia,atomo (list atom)
63
(defun squash (x) ;; x e’ s-espressione(cond ((null x) x)((atom x) (list x)) ;; serve per usare append(T (append (squash (first x))
(squash (rest x))))))
NB: (atom x) e’ T anche per () (perche’ come NIL):occorre che (null x) lo preceda nel cond...
ComposizioneComposizione
64
X = (a (b))1) T (append (sqs (first '(a (b)))) (sqs (rest '(a (b)))))
2) (squash 'a) (a)(squash '((b))) (append (sqs (first '((b)))) (sqs (rest '((b)))))
3) (squash ()) ()(squash (b)) (append (sqs (first '(b))) (sqs (rest '(b))))
3) (squash 'b) (b) (squash ()) ()
()b
a
ValutazioneValutazione
((b))
(b) ()
append (a) (b)
append (b) ()
append (b) ()
65
Immagine speculare di S-Exp:(MIRROR '(a (b (c d)) e) f)) (f (e ((d c) b) a)
Esempio: Esempio: MIRRORMIRROR
Base: lista vuota o atomo non cambia
Ip.Ric.: L = (e1 … en): (MIRROR 'e1), (MIRROR '(e2 ..
en))Passo:
append di (Mirror '(e2 .. en)) con (list (Mirror 'e1))
66
(defun mirror (x) ; x è s-exp(cond ((atom x) x)(T (append (mirror (rest x))
(list (mirror (first x)))))))
NB: Senza list, append toglierebbe una parentesi almirror del first se questo e’ una lista; darebbe errore di parametro se fosse un atomo
ComposizioneComposizione
67
0: Data L = (e1 … en), (INVERTI L) (en…e1)1: (INVERTI NIL) NIL2: (INVERTI (REST L)) (en ... e2)3: e1 va posto in coda a (en … e2): allorasupponiamo che ci sia funzione CONS_END che lofaccia: (CONS_END S L) (e1 … en S)Poi definiremo CONS_END (procediamo top-down)
Inversione di una listaInversione di una lista
68
(defun inverti (x)(cond ((null x) x)
((atom x) x) ;;anche S-exp... (T (cons-end (first x) (inverti (rest x))))))
ComposizioneComposizione
69
1: Base (cons_end S ()) (S) 2: Ip. Ric. (cons_end S (rest L))3: Passo (cons (first L) (cons_end (rest L))))4: Composizione
(defun cons-end (s x)(if (null x) (list s)(cons (first x) (cons-end s (rest x)))))
Cons_endCons_end
70
circulate(L)Scrivere la funzione circulate in modo che operi come segueal primo livello:
> (circulate '(1 2 3 4) 'left)(2 3 4 1)> (circulate '(1 2 3 4) 'right)(4 1 2 3)
(defun circulate (lst direction)(cond ((atom lst) lst)
((null lst) nil)((equal direction 'left) (append (cdr lst) (list (car lst))))((equal direction 'right) (cons (last-l lst) (but-last lst)))(T lst) ))
71
Remove (item, list) (1° livello)
• Scrivere la funzione remove del LISP, che opera come segue:> (remove 'a '(a b c a d))
(b c d)> (remove 'a '(a b c (a) d))
(b c (a) d)
(defun my-remove (item lst)(cond ((atom lst) lst)
((null lst) nil)((equal (car lst) item) (my-remove item (cdr lst)))(t (cons (car lst) (my-remove item (cdr lst))))))
72
Remove (item, list) (ogni livello)
• Scrivere la funzione remove del LISP, che opera come segue:> (remove ‘a ‘(a b c a d))
(b c d)> (remove ‘a ‘(a b c (a) d))
(b c d)
(defun my-remove (item lst)(cond ((atom lst) lst)
((null lst) nil)((equal (car lst) item) (my-remove item (cdr lst)))((listp (car lst)) (cons (my-remove item (car lst))
(my-remove item (cdr lst))))(t (cons (car lst) (my-remove item (cdr lst))))))
73
(Extract-symbols L)
Data una lista x costruirne una contenente i suoi elementi che sono simboli
74
75
•Data funzione a 1 o 2 argomenti, in notazioneprefissa, tradurla in forma infissa
• Es: (pretoinf '(* (COS (LOG X)) (* X 1))) ((COS (LOG X)) * (X * 1))
Non consideriamo precedenza fra operatori eusiamo anche parentesi ridondanti. Espressionedeve essere ben formata.
Da notazione prefissa Da notazione prefissa a notazione infissaa notazione infissa
76
(defun pre2inf (f) (cond ((null f) f)
((atom f) f)((equal (length f) 3) ;; 2 argomenti
(list (pre2inf (cadr f)) ;; 1° argomento (first f) ;; operatore
(pre2inf (caddr f)))) ;; 2° argomento
((equal (length f) 2) ;; 1 argomento(list (first f) (pre2inf (cadr f))))
(T f)))
77
Ignoriamo precedenze operatori e ipotizziamocoppia di parentesi attorno a ogni sottoespressione(se cosi’ non fosse, si complica molto perche’occorre trattare operatore per operatore: v.Linguaggi e Traduttori).
Da notazione infissa Da notazione infissa a notazione prefissaa notazione prefissa
78
(defun inf2pre (f)(cond ((null f) f)
((atom f) f)((equal (length f) 2)
(list (first f) (inf2pre (second f))))
((equal (length f) 3)(list (second f) (inf2pre (first f))
(inf2pre (third f))))(T "Errore")))
79
Motivazione: aumentare l’efficienza di esecuzionePrincipale caratteristica non funzionale: introduzione di“variabili”Ad ogni simbolo può essere associato (binding) un oggetto Lisp (valore) modificabile
AssegnazioneAssegnazione: espressione speciale setq:(setq <simbolo> <oggetto>)
EsempioEsempio: (setq a 5) assegna all’atomo a il valore (atomo!) 5
Caratteristiche non funzionali del Caratteristiche non funzionali del LISPLISP