Linguaggi di Programmazione
(AA 2002/2003)
Corso di Laurea in Informatica
Introduzione ai linguaggi funzionali
I linguaggi imperativi
Basati sull’architettura di Von Neumann:
– memoria costituita da celle identificate da un indirizzo,
contenenti dati o istruzioni
– unità di controllo e aritmetica
– variabili = celle, nome = indirizzo
– azione unitaria: istruzione
– programma: combinazione di istruzioni
Concetto di assegnamento di valori a variabili
Ogni valore calcolato deve essere esplicitamente memorizzato,
cioè assegnato ad una cella
Concetto di iterazione
un programma consiste nell’esecuzione iterativa di una
sequenza di passi elementari
I linguaggi imperativi
Caratteristiche negative dei linguaggi imperativi:
gli 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
I linguaggi imperativi
• 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)
I linguaggi imperativi
• Trasparenza 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
Esempio:
– 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 della
sostituzione, né che f(x)+ g(x) = g(x)+ f(x), né che f(x)+f(x) =
2* f(x)
I linguaggi funzionali
Programmi = funzioni matematiche
– concetto base: funzioni primitive
– combinazione di funzioni primitive per produrne di più potenti
– conservano la trasparenza referenziale della matematica
Funzione: regola per associare gli elementi di un insieme
(dominio) a quelli di un altro (codominio)
• Una funzione può essere applicata a un elemento del dominio
• L’applicazione produce (restituisce) un elemento del codominio
Esempio:
quadrato(x) = x*x, dove x è un numero intero, detto
parametro, che indica un generico elemento del dominio
x è una variabile matematica, non di programma (non ha senso
pensare di modificarla!)
Programmazione funzionale:
combinazione 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
Esempio:
alla_quarta = quadratoºquadrato
quindi:
alla_quarta(5) = quadrato(quadrato(5))
Programmazione funzionale:
ricorsione
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
In matematica:
– In termini di applicazione di altre funzioni (spesso
ricorsivamente)
Esempio:
– fattoriale(n) = if n = 0 then 1 else n*fattoriale(n-1)
Nella programmazione funzionale pura non
esiste la possibilità di generare effetti collaterali
Programmazione funzionale:
caratteristiche
• La principale modalità di calcolo è l’applicazione di funzioni
• Il calcolo procede valutando espressioni. Non ci sono effetti
collaterali.
• Le funzioni sono oggetti di prima classe: possono
essere componenti di una struttura dati, o costituire
l’argomento o il valore di altre funzioni.
• 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
• 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.
Il linguaggio Lisp
• 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
• In seguito sono state introdotte caratteristiche non funzionali
per aumentare l’efficienza
• Oggi è comunque il linguaggio che più si avvicina al modello
di linguaggio funzionale
• Standard attuale: Common Lisp
Il linguaggio Lisp
• Il Lisp è un linguaggio interpretato
• L’interazione avviene attraverso una finestra detta listener
• 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)
Il linguaggio Lisp
• Gli unici oggetti (strutture dati) Lisp sono espressioni simboliche:
– Atomi
– Liste
• Atomi
– sono rappresentati da stringhe di caratteri
– es.: A, John, c3po (simboli), 68000, -15, 1.502,
1.24E-3 (numeri)
• Liste
– sono sequenze ordinate di oggetti, cioè atomi o liste
(ricorsivamente)
Esempi: (A), (A John c3po 68000), ((A John) c3po (68000)), ()
Anche i programmi Lisp sono espressioni costituite da atomi o liste!
Quindi dati e programmi sono rappresentati nello stesso
modo.
Il linguaggio Lisp
Formalmente le S-espressioni (espressioni simboliche) sono
definite come:
Il linguaggio Lisp
simboli
• Usati per dare un nome a variabili, costanti, funzioni
Sequenze di caratteri che possono includere: numeri, lettere,
alcuni caratteri alfanumerici:*-+/@$%^& _ < > ~
(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
• Simboli speciali:
– T (“vero”),
– NIL (“falso”,ma anche lista vuota)
• Predicato: symbolp (restituisce T per i simboli)
Il linguaggio Lisp
numeri
• Tipo: number
• integer, float
• Es. 0.5, 3.1415, 602E+21 (60221) …
• NB: le frazioni, come 2/3, 25/100 … non sono simboli ma
vengono trattati come numeri frazionari
• Operazioni:
– +, -, *, /, sqrt, abs …
• Predicati: numberp, integerp …, plusp, zerop …=, >, <, >=,
<= …
Il linguaggio Lisp
le liste
Una lista ha una definizione ricorsiva:
– () (lista vuota, o NIL)
ricorsione
– (l1 … ln) S-espressioni separate da spazi (li atomo o lista)
Esempi:
• (a b c) lista semplice (elementi al primo livello sono atomi)
• (( alfa 1) beta (gamma delta (5 127) ro)) e` una lista di liste
Liste hanno profondità illimitata orizzontale e verticale
• (a ((b b )) (c d (e)))
• ((((a))) ((((b) c))))
Espressioni Lisp
Le S- espressioni sono usate per rappresentare:
– dati
– definizioni di funzioni
– applicazioni di funzioni
• In Lisp esistono tre tipi di espressioni valide:
– atomi
– funzioni
– espressioni speciali (special form)
• Atomi
– <nome atomo>
• Funzioni
(<nome funzione> <arg1> … <argn>)
• Espressioni speciali (funzioni speciali)
(<nome espressione speciale> <arg1> … <argn>)
Valutazione di espressioni Lisp
– Atomi:
la valutazione restituisce il valore associato (se non esiste: errore)
– Liste:
Atomo
Atomi o liste
• Applicazione di funzione (<nome funzione> <arg1> … <argn>):
si passa alla funzione il risultato della valutazione degli argomenti
• Espressioni speciali (<nome espressione> <arg1> … <argn>):
si passano all’espressione gli argomenti non valutati
La distinzione dipende dal nome (primo atomo della lista)
si noti la notazione prefissa!
Funzioni predefinite
Funzioni matematiche:
+, -, *, /, mod, exp, sqrt, sin, cos
Esempio: (+ 1 2), (* 3 5), (mod 5 2)
Funzioni predefinite per l’elaborazione di liste
a) Costruzione di liste: funzione cons: S-Exp  List  List
(cons <atomo> <lista>) inserisce <atomo> in testa a <lista>
Esempio: (cons 1 ()) = (1), (cons 1 (cons 2 ())) = (1 2)
Funzioni predefinite
b) Selezione di elementi: funzioni car (first) e cdr (rest)
car: List S-Exp
cdr: List  List
car restituisce primo elemento di una lista
cdr restituisce la lista senza primo elemento
(car = content of address register, cdr =content of decrement
register)
Esempi: (car (cons 1 (cons 2 ()))) = 1,
(car (cons (cons 1 (cons 2 ())) (cons 2 (cons 4 ()))))
= (1 2)
(cdr (cons (cons 1 (cons 2 ())) (cons 2 (cons 4 ()))))
= (3 4)
((x) b (c)) ha come first: (x), come rest: (b (c))
Con cons, car e cdr è possibile eseguire qualsiasi operazione
sulle liste (fusione, inserimento, estrazione, ecc.)
Funzioni predicato predefinite
Sono funzioni che restituiscono T o NIL
(Per rappresentare True e False in Lisp si usano gli atomi T e NIL)
Predicati di confronto
– per i numeri: plusp, zerop …=, >, <, >=, <=
(= 1 1) = T, (= (car (cons 1 (cons 2 ()))) 2) = NIL
(> 1 5) = NIL, (< 1 2) = t, (<= 5 5) = t
– null: per liste (T se lista e’ vuota, NIL altrimenti)
Per controllare se un oggetto è un atomo o una lista:
(atom 5) = T, (atom nil) = T, (atom (cons 1 ())) = NIL,
(atom (car (cons 1 ())) = T (listp 2) = NIL, (listp (cons 5 ())) = T
Predicati per test di tipo:
symbolp, numberp, integerp, floatp, atom, listp
Funzioni predicato predefinite
Predicato and
(and <e 1 > … <e n >)
– se il risultato della valutazione di tutte le espressioni <e 1 >
… <e n > è diverso da NIL, and restituisce il risultato della
valutazione di <e n >;
– altrimenti restituisce NIL
Predicato or
(or <e 1 > … <e n >)
– 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
Programmi come dati
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
Valutazione di S-espressioni
L’interprete Lisp presenta un prompt ed esegue un ciclo
“leggi-valuta-stampa”.
• 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
Esempio:
> (+ 5 9) forma da valutare
14
Valutazione di S-espressioni
Una S- espressione è automaticamente valutata dalla funzione
eval, all’interno di un ambiente che utilizza regole:
Se s e’ costante numerica o uno dei simboli speciali T e NIL,
eval(s) = s
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
Diverso comportamento per le funzioni speciali (cond, if, etc.)
Esempi di valutazione
>
>
>
>
>
>
>
33
TT
NIL  NIL
(*(+ 2 4)(/ 14 7))  12
(+ 1 2 3 4)  10
(= (+ 1 2) 3)  T
(= (+ 1 1) 3)  NIL
Funzioni condizionali
• Implementa il costrutto di controllo
• E’ necessaria per la definizione di nuove funzioni
Sintassi:
(cond (<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 condizionali
Lisp ha altre possibilità di espressione di strutture di
selezione: if, case, when,...
1) (if e1 e2 e3)
Il valore restituito è quello di e2 se e1 è valutata t, altrimenti è
e3 (e’ if..then..else)
2) (if e1 e2) e’ come (if e1 e2 nil)
Esempio: (if (< x 0)(- x) x))
if è forma speciale perché valuta solo una S-Exp
fra e2 e e3 (valutazione cortocircuitata):
(if (> x 0) (/ y x) y)
(/ y x) e’ indefinito per x = 0!
Definizione di funzioni utente
Funzione speciale DEFUN:
(defun abs (x) (if (< x 0) (- x) x))
Argomenti: 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)  4
NB: defun restituisce come valore la funzione definita.
Valutazione di funzioni utente
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 legame fluido viene rilasciato
Definizione di funzioni utente: esempio
>(defun double (n) (* 2 n))
estende l’ambiente globale con il binding tra double
e 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: esempi
>(defun second (L) (first (rest L))
>(second '(a b c))  b
>(defun cons2 (x y L) (cons x (cons y L)))
>(cons2 'a 'b '(c d e))  (a b c d e )
Ricorsione
• 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
RICORSIONE
• Lisp non e’ in realtà un linguaggio funzionale puro,
ma in origine lo era
Ricorsione: esempio
Il fattoriale
0! = 1, n! = n *(n-1)! per n>0
(DEFUN FATT (N)
(IF (ZEROP N) 1
(* N (FATT (- N 1)))))
Ricorsione: valutazione del fattoriale
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
Le operazioni di moltiplicazione sono sospese su pila dei
record di attivazione, su cui vengono salvati i valori intermedi
di n (da 3 a 0).
Ricorsione con liste
• Struttura ricorsiva delle liste si presta molto bene a
programmazione ricorsiva.
• Metodo:
–scrivere il valore della funzione nel caso banale
(usualmente la lista vuota)
–ridursi ricorsivamente al caso banale operando su
un argomento ridotto
Funzioni 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)))))
Esempio di valutazione
(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)))
9
2) (+ 4 (sum (5)))
5
4) (+ 5 (sum ()))
0
Esempio di ricorsione
•Lunghezza di una lista: numero di elementi al
primo 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 valutazione
• (lung ‘(a b))
• (eval (lung ‘(a b))
[L  (a b)]
= (if (null L) 0 (+ 1 (lung (rest L))))
= (+ 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 una
condizione di uscita
Un altro esempio
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))))
Ricorsioni semplici e doppie
Ricorsione semplice (“ricorsione cdr”): la
ricorsione e’ sempre definita sul rest di una lista
Non è sempre sufficiente. Es: conta atomi in S-exp
–(conta-atomi '((a b c) 1 (xyz d)))  6
– Base: ()  0, atomo  1 (due casi, perche’ Sexp
puo’ essere sia lista sia atomo)
–Ip: (conta-atomi (rest L))  n. atomi di rest di L
Ricorsioni car e cdr
• Passo: se (first L) e’ atomo 
(+ 1 (conta-atomi (rest L))
altrimenti...????
• Ricorsione “car-cdr” (“doppia”): ricorsione
anche sul car (first) di una lista
– |(first L)|<|L|: possiamo usare Ip.Ric.:
(conta-atomi (first L)) e (conta-atomi (rest L))
contano correttamente
– Unica cosa importante e’ che Ip.Ric. sia su
oggetti piu’ piccoli di L
Passo e composizione
Passo:
(+ (conta-atomi (first L)) (conta-atomi (rest L)))
(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))))))
Esempio ric. car-cdr: profondita’
• 0. Profondita’ massima di annidamento di una Sexp
(n. max parentesi aperte):
atomo  0, ( )  1, (a (b ((c)) (d)))  4
• 1. Base: ovvia (caso banale atomo o lista vuota)
• 2. Ip.Ric: (prof (first x)), (prof (rest x))
• 3. Passo: prof di x e’ max fra (prof (first x)) e
(prof (rest x))
–usiamo funz. lisp predefinita max:
(defun max (m n) (if (> m n) m n)))
Composizione
(defun prof (x)
(cond ((null x) 1)
((atom x) 0)
(T (max (+ 1 (prof (first x)))
(prof (rest x))))))
Valutazione
X = (a (b))
1) T  (max (+1 (prof a)) (prof ((b)))
2
1
2) (prof a) = 0
(prof ((b)))  (max (+ 1 (prof (b))) (prof ()))
2
1
3) (prof ()) = 1
(prof (b))  (max (+ 1 (prof b)) (prof ()))
1
3) (prof b) = 0
(prof ()) = 1
1
Esempio: SQUASH
Appiattire una S-Exp:
(SQUASH '((a (b (c d)) e) f))  (a b c d e f)
(SQUASH 'a)  (a)
Base:
lista vuota  non cambia,
atomo  (lista atom)
Ip.Ric.: Squash di first, squash di rest
Passo: append di Squash del first con squash del
rest
Composizione
(defun squash (x) ; x e’ s-espressione
(cond ((null x) x)
((atom x) (list x)) ;
(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...
Valutazione
X = (a (b))
1) T  (append (sqs (first (a (b)))) (sqs (rest (a (b)))))
a
((b))
append (a) (b)
2) (squash a) = (a)
squash ((b))  (append (sqs (first ((b)))) (sqs (rest ((b)))))
(b)
3) (squash ()) = ()
()
append (b) ()
squash (b)  (append (sqs (first (b))) (sqs (rest (b))))
b
3) (squash b) = (b)
(squash ()) = ()
()
append (b) ()
Esempio: MIRROR
Immagine speculare di S-Exp:
(MIRROR '(a (b (c d)) e) f))  (f (e ((d c) b) a)
Base: lista vuota o atomo  non cambia
Ip.Ric.: L = (e1 … en): (MIRROR e1), (MIRROR
(e2 .. en))
Passo: (Mirror (e1 e2 … en)) =>(Mirror e2 .. en)
(Mirror e1)
append di Mirror del rest con lista del mirror
del first
Composizione
(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 al
mirror del first...
Inversione di una lista
0: Data L = (e1 … en), (INVERTI L)  (en…e1)
1: (INVERTI NIL)  NIL
2: (INVERTI (REST L))  (en ... e2)
3: e1 va posto in coda a (en … e2): allora
supponiamo che ci sia funzione CONS_END che lo
faccia: (CONS_END L S)  (e1 … en S)
Poi definiremo CONS_END (procediamo top-down)
Composizione
4: (defun inverti (x)
(cond ((null x) x)
((atom x) x) ;;anche S-exp...
(T (cons-end (first x)
(inverti (rest x))))))
Cons_end
1:
2:
3:
4:
(cons_end () S)  (S)
(cons_end (rest L) S) e' corretta
(cons (first L) (cons_end (rest L))))
(defun cons-end (i x)
(if (null x) (list i)
(cons (first x)
(cons-end i (rest x)))))
Backquote
CONS, APPEND, LIST molto utili per costruire
liste: (list 'A 'B 'C)  (A B C)
Esiste un altro modo per costruire liste in cui solo
alcune parti sono quotate e le altre valutate
Es: vogliamo lista ((A B C) D) in cui A,C, D
quotati e B valutato: (LIST (LIST 'A B 'C) 'D))
Per semplificare si usa Backquote (acc. grave `):
`((A ,B C) D)  ((A 3 C) D) (se B  3)
`((A ,(sin 30) , (reverse x))  ((A 0.5 (A B C))
–se x  (D E F)
Caratteristiche non funzionali del LISP
Motivazione: aumentare l’efficienza di esecuzione
Principale caratteristica non funzionale: introduzione di
“variabili”
Ad ogni simbolo può essere associato (binding) un
oggetto Lisp (valore) modificabile
Assegnazione: espressione speciale setq:
(setq <simbolo> <oggetto>)
Esempio: (setq a 5) assegna all’atomo a il valore
(atomo!) 5
Da notazione prefissa
a notazione infissa
•Data funzione a 1 o 2 argomenti, in notazione
prefissa, tradurla in forma infissa
• Es: (pretoinf '(* (COS (LOG X)) (* X 1)))
((COS (LOG X)) * (X * 1))
Non consideriamo precedenza fra operatori e
usiamo anche parentesi ridondanti. Espressione
deve essere ben formata.
(defun pre2inf (f)
(cond ((null f) f)
((atom f) f)
((equal (length f) 3) ; 2 argomenti
(list (pre2inf (cadr f))
(first f)
(pre2inf (caddr f))))
((equal (length f) 2) ; 1 argomento
(list (first f) (pre2inf (cadr f))))
(T f)))
Da notazione infissa
a notazione prefissa
Ignoriamo precedenze operatori e ipotizziamo
coppia di parentesi attorno a ogni sottoespressione
(se cosi’ non fosse, si complica molto perche’
occorre trattare operatore per operatore: v.
Linguaggi e Traduttori).
(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")))