IL LINGUAGGIO LISP Marco Broglia

IL LINGUAGGIO LISP

²

±

¯

°Marco Broglia

Lisp: carta d’identita ci.1

Carta d’Identita

• Nome: Lisp (List Processor)

• Nato il: autunno 1958

• Genere: interprete

• Padre: John McCarthy

• Incubazione: IBM 704

• Segni particolari:

– notazione prefissa: (+ 1 1 2 3 5 8)

– utilizzo di (((((( parentesi ))))))

• Pseudo-acronimi:

– Lots of Irritating Superfluous Parentheses

– Lost In a Sea of Parentheses

IL LINGUAGGIO LISP

®

©

ªwelcome

Lisp: welcome welcome.1

(quote ’)

L’operatore quote, abbreviato spesso con ilsimbolo quote (’), accetta un solo argomento e lorestituisce senza valutarlo:

> (quote (+ 1 2))

(+ 1 2)

> ’(* 3 4)

(* 3 4)

Esercizio [w.1] Valutare

> ’’(the list (a b c) has (+ 1 2) elements)

Soluzione [w.1]

’(THE LIST (A B C) HAS (+ 1 2) ELEMENTS)

quote object ⇒ object


(list (cons ’l (cons ’i ’(s t))))

Le liste vengono costruite con l’operatore cons

oppure con l’operatore list:

> (cons ’a ’(b c d))

(A B C D)

> (cons ’a (cons ’b nil))

(A B)

> (cons ’(a) ’(b))

((A) B)

> (cons nil ’(a))

(NIL A)

> (list ’a ’b)

(A B)

> (list ’my (* 1 2) "Sons")

(MY 2 "Sons")

La lista vuota e rappresentata da nil:

> ()

NIL

> nil

NIL

cons object1 object2 ⇒ ( object1 . object2 )

list object* ⇒ ( object* )


(1 2 3)

Esercizio [w.2] Fornire tre diversecons-espressioni che restituiscono (1 2 3).

Soluzione [w.2]

1. (cons 1 ’(2 3))

2. (cons 1 (cons 2 ’(3)))

3. (cons 1 (cons 2 (cons 3 nil)))


append vs cons vs list

Esercizio [w.3] Valutare le seguenti espressioni:

1. (cons ’(i am) ’(a cons))

2. (list ’(i am) ’(a list))

3. (append ’(i am) ’(an append))

Soluzione [w.3]

1. ((I AM) A CONS)

2. ((I AM) (A LIST))

3. (I AM AN APPEND)

append list* ⇒ ( elements of list* )


(list (car ’(c d r))

(car (cdr ’(c a r))) ’r)

Le funzioni primitive per l’estrazione deglielementi di una lista sono car (Contents of theAddress part of Register number) e cdr (Contentsof the Decrement part of Register number):

> (car ’(a b c))

A

> (cdr ’(a b c))

(B C)

> (car (cdr (cdr ’(a b c d))))

C

> (caddr ’(a b c d))

C

car cons ⇒ first object in cons

cdr cons ⇒ second object in cons

cadr list ⇒ car (cdr list)


myfourth and myreverse

Esercizio [w.4] Sia lst la lista (a b c d e).Utilizzando solo le funzioni car e cdr, fornireun’espressione che estragga il quarto elemento.

Soluzione [w.4]

> (car (cdr (cdr (cdr lst))))

D

> (fourth lst)

D

Esercizio [w.5] Sia lst la lista (a b c).Utilizzando solo le funzioni c[ad]*r e cons,invertire la lista.

Soluzione [w.5]

> (cons (caddr lst) (cons (cadr lst)

(cons (car lst) nil)))

(C B A)

> (reverse lst)

(C B A)


let ((me see))

L’operatore di assegnamento piu generale e setf:

> (setf lst ’(1 2 3))

(1 2 3)

> (setf (car lst) 4)

4

> lst

(4 2 3)

L’operatore let viene utilizzato per definirevariabili locali:

> (let ((a 1) (b 2))

(+ a b))

3

> (let ((n 1))

(setf n 2)

n)

2

> n

error: n unbound

setf (object value)* ⇒ ( object ⇐ value )*

let ( ( var value )* ) body ⇒ ( var ⇐ value )* body


(if cond ition)

Il condizionale piu semplice e l’operatore if:

> (if (oddp (random 10)) ’odd ’even)

ODD or EVEN

> (setf e (exp 1))

2.7182818284590451

> (if (< e pi) (/ pi e))

1.1557273497909217

Il terzo argomento e opzionale (default: nil).

Il condizionale piu classico e l’operatore cond:

> (setf googol (expt 10 100))

1000000000 . . . (1 seguito da 100 zeri)

> (cond ((= (mod googol 3) 1) ’3k+1)

((= (mod googol 3) 2) ’3k-1)

(t ’3k))

3K+1

if test expr1 expr2 ⇒ if (test) expr1 else expr2

cond ( ( test expr )* ) ⇒ first expr with true test


(and t (not ’false))

Il simbolo t rappresenta il valore vero, nil ilvalore falso:

> (and t (+ 1 2))

3

> (not 3)

NIL

Le funzioni che valutano la verita o la falsita diun’espressione sono dette predicati :

> (listp ’(a b c))

T

> (list (numberp 1) (atom ())

(listp 27) (consp ’(a b)))

(T T NIL T)

and expr* ⇒ if (any expr = nil) nil else last expr

or expr* ⇒ if (all expr* = nil) nil else first true expr

not object ⇒ if (object = nil) t else nil

null object ⇒ if (object = nil) t else nil

listp object ⇒ if (object is a list) t else nil


(and (or (not (null nil))))

Esercizio [w.6] Valutare le seguenti espressioni:

1. (list 1 (+ 2 3))

2. (if (listp 1) (+ 1 2) (+ 3 4))

3. (list (and (listp 3) t) (+ 1 2))

4. (list (and 0) (null nil) (not nil)

(not (listp nil)))

5. il titolo

Soluzione [w.6]

1. (1 5)

2. 7

3. (NIL 3)

4. (0 T T NIL)

5. NIL


(f (u (n (z (i (o ’(n i)))))))

La definizione di nuove funzioni avviene tramite lafunzione defun:

> (defun mythird (lst)

(car (cdr (cdr lst))))

MYTHIRD

> (mythird ’(a b c d))

C

Esercizio [w.7] Definire la funzione 3> che,data una lista di 3 valori lst, verifica se essi sonoin ordine strettamente decrescente.

Soluzione [w.7]

> (defun 3> (lst)

(and (> (car lst) (cadr lst))

(> (cadr lst) (caddr lst))))

3>

> (list (3> ’(3 2 1)) (3> ’(1 2 3)) (3> ’(1 1 0)))

(T NIL NIL)

defun fname ( parameters ) body ⇒ fname


max2

Esercizio [w.8] Definire la funzione max2 cherestituisce il maggiore tra due argomenti.

Soluzione [w.8]

> (defun max2 (x y)

(if (> x y) x y))

MAX2

> (setf e (exp 1))

2.7182818284590451

> pi

3.1415926535897931

> (max2 (expt e pi) (expt pi e))

23.140692632779267

> (expt pi e)

22.459157718361041


(r (e (c (u (r ’(s i o n))))))

Molto naturale in Lisp, la ricorsione rappresentauno dei piu eleganti stili di programmazione a cuisi riferiscono i seguenti due classici.

La funzione fattoriale:

n! =

{1 n = 0

n (n− 1)! n >= 1

viene spesso implementata:

> (defun ! (n)

(if (= n 0)

1

(* n (! (- n 1)))))

!

> (! 10)

3628800

> (! 100)

933262154439441526816992388562 ...

... 916864000000000000000000000000

(158 cifre)


La funzione di Fibonacci:

Fn =

0 n = 0

1 n = 1

Fn−1 + Fn−2 n > 1

viene spesso implementata:

> (defun fib (n)

(if (< n 2)

n

(+ (fib (- n 1)) (fib (- n 2)))))

FIB

> (fib 10)

55

> (fib 100)

354224848179261915075


0123456789

Esercizio [w.9] Il piu piccolo numero diFibonacci contenente tutte le cifre da 0 a 9 e F74:

> (fib 74)

1304969544928657

Utilizzando la precedente definizione della funzionefib, quante volte essa viene invocata per calcolareF74?

Soluzione [w.9] Sia C(n) il numero diinvocazioni della funzione fib con argomento n.

n 0 1 2 3 4 5 6 7 8

Fn 0 1 1 2 3 5 8 13 21

C(n) 1 1 3 5 9 15 25 41 67

Si ha C(n) = 2Fn+1 − 1, dunque fib vieneinvocata

C(74) = 2F75 − 1 = 4 222 970 155 956 099

volte.


$ = super !

Esercizio [w.10] Implementare in modoricorsivo la funzione superfattoriale cosı definita:

n$ =

n∏i

i! = 1! · 2! · · ·n!

Soluzione [w.10]

> (defun $ (n)

(if (= n 1)

(! 1)

(* (! n) ($ (- n 1)))))

$

> ($ 10)

6658606584104736522240000000 (28 cifre)

> ($ 100)

270317685765174997105580900275 ...

... 000000000000000000000000000000

(6941 cifre)


λ expression

Una λ expression, detta anche anonymousfunction, definisce una funzione senza associarlaad un nome.

Sintatticamente e una lista formata da tre parti: ilsimbolo lambda, una lista di parametri e il corpodella funzione.

Ad esempio, l’espressione

(lambda (x) (* x x))

definisce la funzione che calcola il quadrato:

> ((lambda (x) (* x x)) 111111111)

12345678987654321

Esercizio [w.11] Definire la λ expression chedetermina il minore tra due numeri.

Soluzione [w.11]

(lambda (x y) (if (< x y) x y))


f(x) = g(h(x))

E possibile passare funzioni come argomenti adaltre funzioni:

> (apply #’+ ’(1 1 2 3 5))

12

> (mapcar #’oddp ’(1 1 2 3 5))

(T T NIL T T)

> (mapcar #’+ ’(1 1 2 3 5) ’(1 2 6 24 120))

(2 3 8 27 125)

oppure definire funzioni che restituiscono funzionicome valori di ritorno:

> (defun addn (n) #’(lambda (x) (+ x n)))

ADDN

> (setf add10 (addn 10))

internals

> (mapcar add10 ’(1 2 3))

(11 12 13)

apply f ( args ) ⇒ ( f args )

mapcar f ( list )* ⇒ ( ( f elem1 ) . . . ( f elemn ) )

lambda ( parameters ) body ⇒ function

IL LINGUAGGIO LISP

²

±

¯

°esercizi semplici

Lisp: exercises exer.1

lisp-equazioni

Esercizio [e.1] Risolvere le seguentilisp-equazioni in x:

1.> (car (x (cdr ’(a (b c) d))))

B

2.> (x 13 (/ 1 0))

13

3.> (x #’list ’(1 nil))

(1 NIL)

Soluzione [e.1]

1. x = car

2. x = or

3. x = apply


la funzione che non funziona

Esercizio [e.2] Un giovane Lisper sta provandoa scrivere la funzione mysum che somma tutti glielementi non nil di una lista. Egli ne scrive duediverse versioni, ma entrambe non risultanofunzionanti. Dove sta sbagliando? Riusciamo adaiutarlo?

1.(defun mysum1 (lst)

(remove nil lst)

(apply #’+ lst))

2.(defun mysum2 (lst)

(let ((x (car lst)))

(if (null x)

(mysum2 (cdr lst))

(+ x (mysum2 (cdr lst))))))

remove object list ⇒ list without object


la funzione che ora funziona

Soluzione [e.2]

1. la funzione remove non modifica la listaoriginaria> lst

(1 2 NIL 3)

> (remove nil lst)

(1 2 3)

> lst

(1 2 NIL 3)

> (mysum1 ’(1 2 () 3))

error: +: operand 3 and NIL

2. nella condizione di uscita, in entrambi i casiviene invocata la funzione ricorsivamente,provocando un loop infinito


Possiamo correggere i due errori cosı:

1.> (defun mysum1 (lst)

(apply #’+ (remove nil lst)))

MYSUM1

2.> (defun mysum2 (lst)

(let ((x (car lst)))

(cond ((null lst) 0)

((null x) (mysum2 (cdr lst)))

(t (+ x (mysum2 (cdr lst)))))))

MYSUM2

IL LINGUAGGIO LISP

²

±

¯

°esercizi: (le liste)


mylast

Esercizio [e.3] Definire la funzione mylast che,data una lista lst, restituisce l’ultimo elemento.

> (mylast ’(a b c d))

D

> (mylast ’(a b (c (d))))

(C (D))

> (mylast ’())

NIL

> (last ’(a b (c (d))))

((C (D)))

> (car (last ’(a b (c (d)))))

(C (D))

Soluzione [e.3]

> (defun mylast (lst)

(cond ((null (cdr lst)) (car lst))

(t (mylast (cdr lst)))))

MYLAST


presente?

Esercizio [e.4] Definire il predicato presentp

che determina se un atomo a compare in una lista,a qualsiasi livello. Confrontare il predicatopresentp con la funzione predefinita member.

> (setf lst1 ’(1 2 3)

lst2 ’((1) 2 (3)))

((1) 2 (3))

> (list (member 1 ())

(member 1 lst1)

(member 1 lst2))

(NIL (1 2 3) NIL)

member object list ⇒ sublist starting with object


presente!

Soluzione [e.4]

> (defun presentp (a lst)

(cond ((atom lst) (eql a lst))

(t (or (presentp a (car lst))

(presentp a (cdr lst))))))

PRESENTP

> (setf lst1 ’(1 2 3)

lst2 ’((1) 2 (3)))

((1) 2 (3))

> (list (member 1 ())

(member 1 lst1)

(member 1 lst2))

(NIL (1 2 3) NIL)

> (list (presentp 1 ())

(presentp 1 lst1)

(presentp 1 lst2))

(NIL T T)


lol

Esercizio [e.5] Definire la funzione lol che,data una lista lst, determina se contiene liste.

> (lol ’(1 2 3))

NIL

> (lol ’(1 () 2 3))

T

> (lol ’(()))

T

Soluzione [e.5]

> (defun lol (lst)

(cond ((null lst) nil)

((listp (car lst)) t)

(t (lol (cdr lst)))))

LOL


nlol

Esercizio [e.6] Definire la funzione nlol che,data una lista lst, conta le liste presenti al suointerno.

> (nlol ’(1 2 3))

0

> (nlol ’(1 () (2)))

2

> (nlol ’(()))

1

Soluzione [e.6]

> (defun nlol (lst)


((listp (car lst))

(+ 1 (nlol (cdr lst))))

(t (nlol (cdr lst)))))

NLOL


nlol-r

Esercizio [e.7] Definire la funzione nlol-r

che, data una lista lst, conta il numero di listepresenti al suo interno, a qualsiasi livello.

> (nlol-r ’(1 2 3))

0

> (nlol-r ’(1 () ((2))))

3

> (nlol-r ’((())))

2

Soluzione [e.7]

> (defun nlol-r (lst)


((listp (car lst))

(+ 1 (nlol-r (car lst))

(nlol-r (cdr lst))))

(t (nlol-r (cdr lst)))))

NLOL-R


sum-r

Esercizio [e.8] Definire la funzione sum-r che,data una lista lst, somma tutti i numeri presenti,a qualsiasi livello.

> (sum-r ’((1 (a)) 2 ’(3 b (() (4)))))

10

> (sum-r ’())

0

Soluzione [e.8]

> (defun sum-r (lst)

(cond ((atom lst) (if (numberp lst) lst 0))

(t (+ (sum-r (car lst))

(sum-r (cdr lst))))))

SUM-R


rmn

Esercizio [e.9] Definire la funzione rmn che,data una lista lst, rimuove tutti i numeripresenti, a qualsiasi livello.

> (rmn ’(a 5 (c) (((4))) e ()))

(A (C) ((NIL)) E NIL)

> (rmn ’(1))

NIL

> (rmn ’())

NIL

> (rmn ’(()))

(NIL)

Soluzione [e.9]

> (defun rmn (lst)


((numberp (car lst)) (rmn (cdr lst)))

((atom (car lst))

(cons (car lst) (rmn (cdr lst))))

(t (cons (rmn (car lst))

(rmn (cdr lst))))))

RMN


rms

Esercizio [e.10] Definire la funzione rms che,data una lista lst, rimuove tutti gli atomi nonnumerici presenti, a qualsiasi livello.

> (rms ’(a 5 (c) (((4))) e ()))

(5 NIL (((4))) NIL)

> (rms ’(1))

(1)

> (rms ’())

NIL

> (rms ’(()))

(NIL)

Soluzione [e.10]

> (defun rms (lst)


((listp (car lst)) (cons

(rms (car lst)) (rms (cdr lst))))

((numberp (car lst)) (cons

(car lst) (rms (cdr lst))))

(t (rms (cdr lst)))))

RMS


verym

Esercizio [e.11] Definire la funzione myrev che,data una lista lst, inverte l’ordine degli elementi.

> (myrev lst)

inverte l’ordine degli elementi della lista lst

> (myrev ’(a c e t o n e))

(E N O T E C A)

> (myrev ’(a (b (c)) ()))

(NIL (B (C)) A)

> (myrev ’())

NIL

> (myrev (myrev ’(l i v e)))

(L I V E)

Soluzione [e.11]

> (defun myrev (lst)

(cond ((atom lst) nil)

(t (append (myrev (cdr lst))

(list (car lst))))))

MYREV


very myrev

Esercizio [e.12] Definire la funzione myrev-r

che, data una lista lst, inverte l’ordine deglielementi, a qualsiasi livello.

> (myrev-r lst)

inverte l’ordine degli elementi di qualsiasi livello

della lista lst

> (myrev-r ’(a (b (c)) ()))

(NIL ((C) B) A)

> (myrev-r ’())

NIL

> (myrev-r (myrev ’(e s (t a) t o)))

(E S (A T) T O)

Soluzione [e.12]

> (defun myrev-r (lst)

(cond ((atom lst) lst)

(t (append (myrev-r (cdr lst))

(list (myrev-r (car lst)))))))

MYREV-R


prodotto × cartesiano

Esercizio [e.13] Definire la funzione cart che,date due liste v1 e v2, ne calcola il prodottocartesiano.

> (cart ’(a b c) ’(1 2))

((A 1) (A 2) (B 1) (B 2) (C 1) (C 2))

Soluzione [e.13]

> (defun distl (x v)

(cond ((null v) nil)

(t (cons (list x (car v))

(distl x (cdr v))))))

DISTL

> (distl ’a ’(1 2 3))

((A 1) (A 2) (A 3))

> (defun cart (v1 v2)

(cond ((null v1) nil)

(t (append (distl (car v1) v2)

(cart (cdr v1) v2)))))

CART


what?

Esercizio [e.14] Descrivere il comportamentodelle seguenti funzioni e valutare il risultato dellaloro invocazione con l’argomento

(a 5 (c) (((4))) e ())

1.(defun what1 (x)

(cond ((null x) 0)

((listp (car x))

(+ 1 (what1 (cdr x))))

(t (what1 (cdr x)))))

2.(defun what2 (x)

(cond ((null x) 0)

((numberp (car x))

(+ 1 (what2 (cdr x))))

(t (what2 (cdr x)))))


that!

Soluzione [e.14]

1. la funzione what1 conta il numero di listepresenti nella lista x al primo livello> (what1 ’(a 5 (c) (((4))) e ()))

3

2. la funzione what2 conta i numeri presenti nellalista x al primo livello> (what2 ’(a 5 (c) (((4))) e ()))

1


an odd mystery

Esercizio [e.15] Descrivere il comportamentodelle seguenti funzioni:

1.(defun odd (x)

(cond ((null x) nil)

((atom x) x)

(t (cons (odd (car x))

(odd (cdr x))))))

2.(defun mystery (x)

(cond ((null x) 1)

((atom x) 0)

(t (max (+ (mystery (car x)) 1)

(mystery (cdr x))))))

Soluzione [e.15]

1. la funzione odd ritorna il proprio input

2. la funzione mystery calcola la profondita di x


mysteries

Esercizio [e.16] Descrivere il comportamentodelle seguenti funzioni:

1.(defun mystery1 (x)

(and (not (null x))

(or (null (car x))

(mistery1 (cdr x)))))

2.(defun mystery2 (x y)

(if (null y) nil

(if (eql x (car y)) 0

(let ((z (mystery2 x (cdr y))))

(and z (+ z 1))))))

Soluzione [e.16]

1. la funzione mistery1 determina se x contieneelementi nulli al primo livello

2. la funzione mystery2 ritorna la posizione di xnella lista y al primo livello


fastfib

Esercizio [e.17] La funzione di Fibonacci vienespesso implementata come segue:

(defun fib (n)

(if (< n 2)

n

(+ (fib (- n 1)) (fib (- n 2)))))

Individuare il problema principale di efficienza edefinire la funzione fastfib, piu efficiente.

Soluzione [e.17]

> (defun fib1 (fib fib+1 m)

(if (= m 0)

fib

(fib1 fib+1 (+ fib fib+1) (- m 1))))

FIB1

> (defun fastfib (n)

(fib1 0 1 n))

FASTFIB

> (fastfib 10)

55

> (fastfib 100)

354224848179261915075


fast$?

Esercizio [e.18] La funzione superfattoriale,

n$ =

n∏i

i! = 1! · 2! · · ·n!

viene spesso implementata come segue:

> (defun $ (n)

(if (= n 1)

(! 1)

(* (! n) ($ (- n 1)))))

$

Individuare il problema principale di efficienza edefinire la funzione fast$, piu efficiente.


fast$

Soluzione [e.18] La funzione $ invoca n voltela funzione !, con valori compresi tra 1 e n,eseguendo cosı piu volte gli stessi prodotti.

Considerando che

(n + 1)! = n! (n + 1)

(n + 1)$ = n$ (n + 1)!

si puo utilizzare lo schema seguente:

> (defun $1 (k k! $k m)

(if (= m 0)

$k

(let ((k+1! (* k! (+ k 1))))

($1 (+ k 1) k+1! (* $k k+1!)

(- m 1)))))

$1

> (defun fast$ (n)

($1 0 1 1 n))

FAST$


la funzione di Ackermann

La funzione di Ackermann e la piu semplicefunzione (Turing) computabile (ricorsiva) nonprimitiva ricorsiva:

A(x, y) =

y + 1 x = 0

A(x− 1, 1) x > 0, y = 0

A(x− 1, A(x, y − 1)) x > 0, y > 0

x, y 0 1 2 3 4

0 1 2 3 4 5

1 2 3 4 5 6

2 3 5 7 9 11

3 5 13 29 61 125

4 13 65533 265536 − 3 2265536 − 3 ?


ack

Esercizio [e.19] Definire la funzione ack checalcola la funzione di Ackermann.

Soluzione [e.19]

> (defun ack (x y)

(cond ((= x 0) (+ y 1))

((= y 0) (ack (- x 1) 1))

(t (ack (- x 1) (ack x (- y 1))))))

ACK

> (ack 0 10)

11

> (ack 1 10)

12

> (ack 2 10)

23

> (ack 3 10)

8189

> (ack 4 1)

stack overflow


Willard Van Orman Quine

Filosofo americano, analitico e logico, studio inmodo approfondito le tecniche dell’autoreferenza.

Un quine e un (meta)programma che produce inoutput il codice di cui e composto.

Esercizio [e.20] Definire una funzione quine.

Soluzione [e.20]

> ((lambda (x) (list x (list ’quote x)))

’(lambda (x) (list x (list ’quote x))))

((LAMBDA (X) (LIST X (LIST ’QUOTE X)))

’(LAMBDA (X) (LIST X (LIST ’QUOTE X))))

La λ expression ha argomento(lambda (x) (list x (list ’quote x))) erestituisce una lista formata da due elementi:

1. il primo e l’argomento x

2. il secondo e: (list ’quote x) ⇒(list (quote quote) x) ⇒ (quote x) ⇒ ’x

IL LINGUAGGIO LISP Marco Broglia

Documents

Transcript of IL LINGUAGGIO LISP Marco Broglia