Bibliografia
1
Scheme ∗
(per principianti)
quaderno 1
2 gennaio 2014
e-mail: [email protected]
Bibliografia
3
∗. This document has been written using the GNU TEXMAC S text editor (see www.texmacs.org).
Indice
Glossario
. . . .. . . . .. . . .. . . . .. . . .. . . . .. . . .. . . . .. . . .. . . 7
1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1 Primi passi . . . . . . . . . . .
1.2 Le espressioni . . . . . . . . .
1.3 Le procedure . . . . . . . . . .
1.4 Espressioni numeriche . . . .
1.5 Le liste . . . . . . . . . . . . .
1.6 Esercizi . . . . . . . . . . . . .
1.7 Le espressioni contenenti let
1.8 Espressione lambda . . . .
1.9 Define . . . . . . . . . . . . . .
1.10 Espressioni con condizione
1.10.1 Esercizi . . . . . . . . .
1.11 Ricorsione . . . . . . . . . . .
1.12 Assegnamento . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 9
10
11
13
14
18
24
27
32
38
42
43
49
Indice analitico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5
Glossario
commento . . . . . . . . . . . . . . . . . . . . .
;
define
definisce una procedura o il valore di una variabile
definisce una lista . . . . . . . . . . . . . . . . .
accento ’
quote <lista>
definisce una lista . . . . . . . . . . . . . . . . .
car <lista>
estrae la testa di <lista> . . . . . . . . . . . . .
cdr <lista>
estrae la coda di una lista . . . . . . . . . . . . .
cons <oggetto > <lista> aggiunge, in testa, l’oggetto alla lista . . . . .
simbolo . . . . . . . . . . . . . . . . . . . . . . .
’a
coppia . . . . . . . . . . . . . . . . . . . . . . .
(a . b)
(let (assegnazioni) (corpo)) . . . . . . . . . . . .
let
espressione lambda
(lambda (var1 var2 .....) esp.1 esp.2 .....) . . . . . .
(if test espr_test_vero espr_test_falso) . . . . .
if
(and expr1 expr2 expr3 ......) . . . . . . . . . . .
and
(or expr1 expr2 expr3 .......) . . . . . . . . . . . .
or
cond
(cond (test exp.) (test exp.) ...... (else exp.)) . . .
7
. .
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
11
14
14
15
15
15
16
16
24
27
38
40
40
41
Capitolo 1
Introduzione
1.1 Primi passi
Per scrivere questo documento useremo Texmacs ho infatti scoperto che Scheme
può essere usato all’interno di Texmacs, basta aprire una sessione di scheme
premendo
e scegliendo
scheme
si ottiene questo:
Scheme] (+ 22 3)
25
2 msec
Scheme] (+ 2 5 7); somma multipla
14
Scheme] ;; commento
(* 3 5)
15
Scheme]
9
10
Introduzione
I commenti si ottengono usando il ;
Il testo di riferimento é il seguente Scheme tutorial [1, The Scheme programming language] facilmente reperibile su Internet.
1.2 Le espressioni
Una espressione é una cosa di questo tipo:
Scheme] (define a 10)
Scheme] (+ a 5)
15
Scheme] (* a a)
100
Scheme]
Ad a viene attribuito il valore 10
Scheme] (+ a a)
20
Scheme] ;possiamo ridefinire la a
#<eof>
Scheme] (define a 8)
Scheme] (* a a)
64
Scheme]
Si può anche lavorare sui caratteri, ad esempio
Scheme] (define stringa ’(a b c d e))
Scheme] (car stringa)
a
Scheme] (cdr stringa)
(b c d e)
Scheme] (define stringabis ’(x y z))
Scheme] (cons stringa stringabis)
((a b c d e) x y z)
Scheme] (car (cons stringa stringabis))
(a b c d e)
Scheme]
1.3 Le procedure
11
Gli esempi precedenti illustrano bene come manipolare le stringhe e i caratteri, non sono esempi dettagliati ma le regole da seguire nell’usare le funzioni
citate mi sembrano facilmente intuibili, maggiori spiegazioni potrebbero apparire pedanti, l’unica cosa da sottolineare é l’ultimo esempio dove il risultato
(output) di una funzione viene usato come parametro (imput) di un’altra funzione.
1.3 Le procedure
Cominciamo con il vedere qualche cosa sulle procedure iniziando a definire la
procedura quadrato.
Scheme] (define quadrato (lambda (n)(* n n)))
Scheme] ;; usiamo la procedura appena definita
#<eof>
Scheme] (quadrato 3)
9
Scheme]
Le procedure possono anche avere più parametri, ad esempio:
Scheme] (define area_rettangolo (lambda (altezza base)(* base
altezza)))
Scheme] (area_rettangolo 20 10)
200
Scheme]
Le regole sintattiche cominciano a diventare chiare e semplici:
•
•
Ogni istruzione deve essere compresa tra parentesi rotonde
Gli operatori sono sempre prefissi, tra operatori e operandi e tra gli operandi ci vogliono degli spazi.
Le procedure possono richiamare altre procedure, esempio:
Scheme] (define volume_parallelepipedo
(lambda (base spessore altezza)
(* (area_rettangolo base spessore) altezza)))
Scheme] (volume_parallelepipedo 10 20 30)
6000
Scheme]
Vediamo un altro esempio significativo:
Scheme] (define reciproco (lambda (n)
(if (= n 0) "infinito" (/ 1 n))))
Scheme] (reciproco 4)
12
Introduzione
1/4
Scheme] (reciproco 0)
"infinito"
Scheme]
Se dopo aver scritto l’esempio precedente voi chiudete Texmacs e successivamente lo riavviate succede una cosa di questo tipo:
Scheme] (reciproco 4)
unbound-variable
Scheme]
La funzione reciproco non esiste più, per riottenerla si può procedere nel
seguente modo:
•
andate nel blocco dove essa é definita e premete il tasto destro
1.4 Espressioni numeriche
•
scegliete Evaluate all
•
infine provate a ripetere l’operazione che prima non era riuscita
13
Scheme] (reciproco 4)
1/4
Scheme] (reciproco 1/10)
10
Scheme] (reciproco (reciproco 2/4))
1/2
Scheme] 2/4
1/2
Scheme]
e tutto torna a funzionare.
1.4 Espressioni numeriche
In scheme la gamma di numeri che si possono usare é molto ampia, si possono
usare:
−
−
−
−
numeri interi relativi e non
frazioni
numeri con la virgola
numeri complessi
di seguito sono riportate espressioni che usano questi numeri
Scheme] (+ 1/2 1/3)
5/6
Scheme] (* 3/4 16/9)
4/3
Scheme] (+ -3/5 -1/5)
-4/5
Scheme] (- 1.5 -3/2)
3.0
Scheme] (- -3/2 +1.5)
-3.0
14
Introduzione
Scheme] (+ 3+2i 7-4i)
10.0-2.0i
Scheme] (* 3 6-4i)
18.0-12.0i
Scheme] (* 3+2i 3-2i)
13.0
Scheme] (* 3-4i 3-4i)
-7.0-24.0i
Scheme]
1.5 Le liste
La lista é un tipo di dati strutturati simile al vettore (array) del C , Pascal,
Java. La lista si indica nel seguente modo
Scheme] ’(1 3 56) ; lista di numeri
(1 3 56)
Scheme] ’(a c g h j) ; lista di caratteri
(a c g h j)
Scheme]
Vi é un secondo metodo per indicare le liste:
Scheme] (quote (x r t s))
(x r t s)
Scheme] (quote ("as" "ghj" "contorno")); lista di stringhe
("as" "ghj" "contorno")
Scheme]
Questo secondo metodo é evidentemente più scomodo del precedente.
Si possono anche formare liste di liste:
Scheme] ’(’(a c d) ’(1 4 6) ’() ’("ancora" "certo"))
((quote (a c d)) (quote (1 4 6)) (quote ()) (quote ("ancora"
"certo")))
Scheme]
Si possono formare delle liste miste con oggetti di tipo diverso:
1.5 Le liste
15
Scheme] ’(1 a "ancora" ’(a b c))
(1 a "ancora" (quote (a b c)))
Scheme]
Le liste hanno una testa e una coda, la testa non é una lista ma é costituita
dal primo elemento, la coda é una lista ed é formata da tutti gli altri elementi
tranne il primo.
Per ottenere la testa si usa la funzione car , per ottenere la coda si usa la
funzione cdr .
Scheme] (define lista1 ’(a b c))
Scheme] (car lista1)
a
Scheme] (cdr lista1)
(b c)
Scheme] (cdr (cdr (cdr lista1)))
()
Scheme] (car (cdr lista1))
b
Scheme] (define lista2 (cdr lista1))
Scheme] (cdr lista2)
(c)
Scheme]
Per unire due liste si usa la funzione cons
Scheme] (define lista1 ’(a b c d))
Scheme] (define lista2 ’(1 2 3 4))
Scheme] (cons lista1 lista2)
((a b c d) 1 2 3 4)
Scheme]
Cons forma una lista il cui primo oggetto , la testa, é lista1 e il resto della
lista , la coda, é lista2, mi viene il sospetto che cons si possa usare con molta
disinvoltura:
Scheme] (cons a b)
unbound-variable
16
Introduzione
Scheme] ; non funziona, se mettiamo ’a e ’b forse li scambia per dei
caratteri.
#<eof>
Scheme] (cons ’a ’b)
(a . b)
Scheme] (pair? (cons ’a ’b))
#t
Scheme] ;Uau (a . b) e’ un tipo di lsta chiamata coppia ,sulle
coppie si possono fare delle bellissime cose ma lo vedremo
piu’ tardi.
#<eof>
Scheme] (cons ’a lista2)
(a 1 2 3 4)
Scheme] ; ’a è un carattere che viene aggiunto in testa alla lista2
#<eof>
Scheme] (cons (car lista1) lista2)
(a 1 2 3 4)
Scheme] (cons (car (cdr lista1)) lista2)
(b 1 2 3 4)
Scheme]
La funzione cons sembra essere molto complicata, non consente di unire due
liste ma aggiunge un oggetto ad una lista. Le righe di codice precedenti ci
hanno insegnato due cose:
•
•
la lettera a é una variabile, mentre ’a é un simbolo
(a . b) é una coppia
Quindi esistono i simboli e le variabili, che cosa sarà ’parola ?
Scheme] ’parola
parola
Scheme] (define qualchecosa ’parola)
Scheme] (car qualchecosa)
wrong-type-arg
Scheme] qualchecosa
parola
Scheme] (string? qualchecosa)
17
1.5 Le liste
#f
Scheme] (symbol? qualchecosa)
#t
Scheme]
é un simbolo e null’altro.
Le liste tipo (a . b) sono molto particolari:
Scheme] (define coppia ’(a . b))
Scheme] (car coppia)
a
Scheme] (cdr coppia)
b
Scheme] ;osservare che b e’
l’oggetto ’b non la lista (b)
#<eof>
Scheme] (string? (cdr coppia))
#f
Scheme] (char? (cdr coppia))
#f
Scheme] (symbol? (cdr coppia))
#t
Scheme] (symbol? ’b)
#t
Scheme] (symbol? b)
unbound-variable
Scheme] (symbol? ’simbolo)
#t
Scheme]
Come si vede il concetto di simbolo é molto gettonato, entra in gioco
questa nuova categoria, ed é un qualche cosa da porre accanto al concetto di
numero, numero complesso, stringa, lista, variabile, nome di funzione, etc...
vedremo sicuramente meglio in seguito di che cosa si tratta.
Vediamo ancora qualche cosa sulle liste con il . :
Scheme] (define lista-punto ’(a b c d e . f))
Scheme] (car lista-punto)
18
Introduzione
a
Scheme] (cdr lista-punto)
(b c d e . f)
Scheme] (define lista-punto2 ’(a b c . d e f))
read-error
Scheme] (define lista-punto2 ’(a b c . ’(d e f))
Scheme] (car lista-punto2)
)
a
Scheme] (cdr lista-punto2)
(b c quote (d e f))
Scheme]
1.6 Esercizi
Esercizio 1.1. Valutare con Scheme la seguenti espressioni
2
4 5
4
a) 3 + 9 11 − 9
Scheme] (* (+ 2/3 4/9) (- 5/11 4/9))
10/891
Scheme]
1
b) 1.2 2 − 3 + (−8.7)
Scheme] (+ (* 1.2 (- 2 1/3)) -8.7)
-6.7
Scheme]
c) 1 +
1
1
2+
1+
1
2
Scheme] (+ 1 (/ 1 (+ 2 (/ 1 (+ 1 1/2)))))
11/8
Scheme]
d) 1 · (−2) ·3· (−4) ·5· (−6) ·7
Scheme] (* 1 (* -2 (* 3 (* -4 (* 5 (* -6 7))))))
-5040
Scheme]
Esercizio 1.2. Fai degli esperimenti con le procedure + - * / usando argomenti numerici di
diverso tipo e ricava le regole seguite da Scheme.
1.6 Esercizi
Scheme] (+ 1 2)
3
Scheme] (+ 1.0 2.0)
3.0
Scheme] ; osservare che quando si usano i decimali anche il valore della
procedura e’ decimale
#<eof>
Scheme] (+ 1 2.0)
3.0
Scheme] ; e’ sufficiente che uno solo sia decimale
#<eof>
Scheme] (- 3 9)
-6
Scheme] (+ 3 1/3)
10/3
Scheme] ; se uno degli argomenti e’ frazionario anche + e’ frazionario
#<eof>
Scheme] (+ 1 2 3 4)
10
Scheme] ; gli argomenti di + possono essere piu’ di due
#<eof>
Scheme] (* 1 2 3 4 5 6 7)
5040
Scheme] ; anche quelli di *
#<eof>
Scheme] (- 10 9 7)
-6
Scheme] ; anche quelli di #<eof>
Scheme] (/ 10 2 5)
1
Scheme] ; anche quelli di /
#<eof>
Scheme] (/ 5 2)
5/2
Scheme] (/ 5 4 2)
5/8
Scheme] (/ 10.0 3)
3.33333333333333
Scheme] 3+2i
19
20
Introduzione
3.0+2.0i
Scheme] (+ 3 3+2i)
6.0+2.0i
Scheme] (/ 10-4i 2)
5.0-2.0i
Scheme] (/ 10-4i 2.0)
5.0-2.0i
Scheme] (+ 1/4+5/6i 1/2)
0.75+0.833333333333333i
Scheme] (+ 1/4+5/6i 1/2+0i)
0.75+0.833333333333333i
Scheme]
Esercizio 1.3. Determinare il valore delle seguenti espressioni:
a) (cons ’car ’cdr)
Scheme] (cons ’car ’cdr)
(car . cdr)
Scheme] ; coppia con punto
#<eof>
Scheme]
b) (list ’this ’(is silly))
Scheme] (list ’this ’(is silly))
(this (is silly))
Scheme]
c) (cons ’is ’(this silly?))
Scheme] (cons ’is ’(this silly?))
(is this silly?)
Scheme]
d) (quote (+ 2 3))
Scheme] (quote (+ 2 3))
(+ 2 3)
Scheme]
e) (cons ’+ ’(2 3))
Scheme] (cons ’+ ’(2 3))
(+ 2 3)
Scheme]
f) (car ’(+ 2 3))
21
1.6 Esercizi
Scheme] (car ’(+ 2 3))
+
Scheme]
g) (cdr ’(+ 2 3))
Scheme] (cdr ’(+ 2 3))
(2 3)
Scheme]
h) cons
Scheme] cons
#<primitive-procedure cons>
Scheme]
i) (quote cons)
Scheme] (quote cons)
cons
Scheme] (quote (cons))
(cons)
Scheme] (car (quote cons))
wrong-type-arg
Scheme] (car (quote (cons)))
cons
Scheme]
j) (quote (quote cons))
Scheme] (quote (quote cons))
(quote cons)
Scheme] (car (quote (quote cons)))
quote
Scheme]
k) (+ 2 3)
Scheme] (+ 2 3)
5
Scheme]
l) (+ ’2 ’3)
Scheme] (+ ’2 ’3)
5
Scheme]
m) (+ (car ’(2 3)) (car (cdr ’(2 3))))
22
Introduzione
Scheme] (+ (car ’(2 3)) (car (cdr ’(2 3))))
5
Scheme]
n) ((car (list + - * / )) 2 3)
Scheme] ((car (list + - * /)) 2 3)
5
Scheme]
Esercizio 1.4. L’espressione (car (car ’((a b) (c d)))) produce a , verificarlo e stabilire
quale combinazioni di car e cdr producono rispettivamente: b , c , d .
Scheme] (define lista ’((a b) (c d)))
Scheme] (car (car lista)); verifica
a
Scheme] (car
lista)
(a b)
Scheme] (car (car ’(’(a b) ’(c d))))
quote
Scheme] (car
(a b))
unbound-variable
Scheme] (list? (car lista))
#t
Scheme] (list? (car ’(’(a b) ’(c d))))
#t
Scheme]
Scheme]
Scheme]
Scheme]
(define lista1 ’(a b))
(define lista2 ’(c d))
(define lista3 ’(lista1 lista2))
(car (car lista3))
wrong-type-arg
Scheme] (car lista3)
lista1
Scheme] (list? (car lista3))
#f
Scheme] (list? lista1)
#t
Scheme] (symbol? (car lista3))
#t
Scheme] (list? (car (car ’(’(a b) ’(c d)))))
#f
Scheme]
23
1.6 Esercizi
Questa parte dell’esercizio introduce parecchi dubbi, intanto ’((a b) (c d)) non é la
stessa cosa di ’(’(a b) ’(c d)) , almeno per quanto riguarda la funzione car , non solo ma
definendo lista1 –> ’(a b) , lista2 –> ’(c d) e lista3 –> ’(lista1 lista2) si ottiene che
lista3 non é la stessa cosa di ’(’(a b) ’(c d)) e nemmeno di ’((a b) (c d)) , evidentemente
sulle liste vi sono ancora molte cose da imparare perché la logica che sta dietro a questo
concetto é per ora molto confusa.
Vediamo se riusciamo a svolgere la seconda parte dell’esercizio:
Scheme] (car (cdr (car lista))); primo risultato
b
Scheme] (car (car (cdr lista))); secondo risultato
c
Scheme] (car (cdr (car (cdr lista)))); terzo risultato
d
Esercizio 1.5. Scrivi i passi necessari per valutare le seguenti espressioni:
a) ((car (cdr (list + - * /))) 17 5)
I. (list + - * /) é la lista (+ - * /)
II. (cdr (list + - * /)) produce la lista (- * /)
III. (car (cdr (list + - * /)))
Scheme] ((car (cdr (list + - * /))) 17 5)
12
Scheme]
b) (cons (quote -) (cdr (quote (+ b c))))
I. (cdr (quote (+ b c)) produce la lista (b c)
II. Quindi il risultato sarà (- b c)
Scheme] (cons (quote -) (cdr (quote (+ b c))))
(- b c)
Scheme]
c) (cdr (cdr ’(a b c)))
I. (cdr ’(a b c)) produce la lista (b c)
II. Il risultato sarà quindi la lista (c)
Scheme] (cdr (cdr ’(a b c)))
(c)
Scheme] (cdr (cdr (quote (a b c))))
(c)
Scheme] ; equivalenza tra
quote
e
’
d) (cons ’d (cdr (cdr ’(a b c d e f))))
I. (cdr (cdr ’(a b c d e f))) produce la lista (c d e f)
24
Introduzione
II. Il risultato sarà quindi la lista (d c d e f)
Scheme] (cons ’d (cdr (cdr ’(a b c d e f))))
(d c d e f)
Scheme]
e) (cons (+ ’2 1/2) (list (- ’3 1/3) (+ ’4 1/4)))
1.1
1 5
=
2 2
1 8
II. (- ’3 1/3) produce 3 − =
3 3
1 17
III. (+ ’4 1/4) produce 4 + =
4
4
I. (+ ’2 1/2) produce 2 +
IV. Il risultato sarà dunque la lista
5 8 17
2 3 4
Scheme] (cons (+ ’2 1/2) (list (- ’3 1/3) (+ ’4 1/4)))
(5/2 8/3 17/4)
Scheme]
1.7 Le espressioni contenenti let
Consideriamo la seguente espressione:
Scheme] (+ a b)
unbound-variable
Scheme] ;non funziona, ma se scriviamo
#<eof>
Scheme] (let ((a 5) (b 2)) (+ a b))
7
Scheme] (+ a b)
unbound-variable
Scheme]
Alla variabile a viene assegnato il valore 5, a b viene assegnato il valore 2 poi
viene eseguita (+ a b), c’é da osservare che queste assegnazioni valgono solo per
questa istruzione infatti la successiva (+ a b) non ha successo.
1.1. Osservare che ’2=2
25
1.7 Le espressioni contenenti let
Supponiamo di voler calcolare l’espressione :
√
1
a2 + b2 + √
a2 + b2
√
con a=4 e b=3, siccome la sottoespressione a2 + b2 compare due volte possiamo porre:
Scheme] (let ((e (sqrt (+ (* 4 4) (* 3 3))))) (+ e (/ 1 e)))
5.2
Scheme]
E’ possibile ottenere un risultato analogo anche in questo modo:
Scheme] (let ((a 4) (b 3)) (let ((e (sqrt (+ (* a a) (* b b))))) (+
e (/ 1 e))))
5.2
Scheme]
Il secondo let va messo nella definizione del risultato del primo non nelle
assegnazioni.
L’espressione precedente é complicata, impariamo a scriverla correttamente:
corpo di let
I. (let () ())
zona assegnazioni
prima assegnazione
II. (let ((a 4)) ())
III. (let ((a 4) (b 3)) ())
seconda assegnazione
il secondo let va messo nel corpo del primo
IV. (let ((a 4) (b 3)) (let () ()))
solo nel corpo del primo let sono visibili le sue assegnazioni
nel corpo del primo let a=4 e b=3
V. (let ((a 4) (b 3)) (let (e (sqrt (+ (* a a) (* b b)))) (+ e (/ 1 e))))
nel corpo del secondo let e =
√
a2 + b2 .
26
Introduzione
Osserviamo attentamente il comportamento della seguente espressione:
Scheme] (let ((x 9)) (* x (let ((x (/ x 3))) (+ x x))))
54
Scheme]
Come funziona questa espressione? La variabile x é oggetto di due assegnazioni, una più esterna dove a x viene assegnato il numero 9 e una più interna
dove, essendo il secondo let nel corpo del primo, a x viene assegnato il valore
(/ 9 3), cioé 3, quindi é come se facessimo 9*6=54. Osservare che l’assegnazione
più interna oscura, nel corpo del relativo let, quella più esterna.
Consideriamo la seguente espressione (3a − b) + (3a + b) che come é evidente
coincide con 6a , in scheme si potrebbe scrivere nel seguente modo:
Scheme] (define a 3)
Scheme] (define b 2)
Scheme] (+ (- (* 3 a) b) (+ (* 3 a) b))
18
Scheme] ; l’espressione (* 3 a) viene valutata due volte
#<eof>
Scheme] (let ((a 3) (b 2)) (let ((a (* 3 a))) (+ (- a b) (+ a b))))
18
Scheme] ; con l’uso di let viene valutata solo una volta
#<eof>
Scheme] (let ((a (* 3 a))) (+ (- a b) (+ a b)))
18
Scheme] ; define ha ancora effetto su questa espressione, non e’
necessario porre (a 3) (b 2), cioe’ il primo let non era
necessario.
#<eof>
Scheme]
Esercizio 1.6. Riscrivi la seguente espressione:
Scheme] (cons (car (list ’a ’b ’c)) (cdr (list ’a ’b ’c)))
(a b c)
Scheme]
usando let e ricalcola l’espressione
Scheme] (let ((x (list ’a ’b ’c))) (cons (car x) (cdr x)))
1.8 Espressione lambda
27
(a b c)
Scheme]
1.8 Espressione lambda
Un’espressione lambda é, dal punto di vista sintattico, una cosa di questo tipo:
(lambda (var.1 var.2 .....) esp.1 esp.2 ......) , facciamo alcuni esempi:
Scheme] ((lambda (x) (* x x)) 2)
4
Scheme] ; un solo parametro e una sola espressione
#<eof>
Scheme] ((lambda (x y) (* x y) (+ x y)) 2 3)
5
Scheme] ; due parametri e due espressioni, apparentemente viene
considerata solo l’ultima ma non credo sia cosi’
#<eof>
Scheme] ((lambda (x y) (define a (* x y)) (+ x y)) 2 3)
5
Scheme] a
unbound-variable
Scheme] ; sembra proprio che non venga considerata , ma....
#<eof>
Scheme] ((lambda (x y) (define a (* x y)) (+ x y a)) 2 3)
11
Scheme] ;a viene vista solo nel corpo di lambda
Invece di usare define si può usare let, tenendo conto di tutte le regole che
riguardano let, ad esempio:
Scheme] (let ((a 3) (b 4)) ((lambda (x y) (sqrt (+ (* x x) (* y
y))))a b))
5.0
Scheme]
Vediamo come funziona:
28
Introduzione
assegnazioni di let
corpo di let
(let ( (a 3) (b 4) ) ( (lambda (x y) (sqrt (+ (* x x) (* y y)))) a b ))
parametri passati a lambda
parametri di lambda
(lambda ( x y ) ( sqrt (+ (* x x) (* y y)) ))
corpo di lambda
L’esempio seguente é veramente sconcertante e getta una nuova luce sul
valore che possono assumere i parametri di una espressione lambda.
Scheme] (define v_assoluto (lambda (x y) (sqrt (+ (* x x) (* y
y)))))
Scheme] (define operazione (lambda (simbolo op1 op2) (simbolo op1
op2)))
Scheme] (operazione + 3 2)
5
Scheme] (operazione v_assoluto 12 16)
20.0
Scheme] (operazione - (v_assoluto -8 -0) (operazione * 2 1))
6.0
Scheme] (operazione v_assoluto (* 36 3) (* 36 4))
180.0
Scheme] (operazione / (* 8 3) (* 8 2))
3/2
Scheme] (operazione + (operazione v_assoluto (* 36 3) (* 36 4))
(operazione - (v_assoluto -8 -0) (operazione * 2 1)))
186.0
Scheme]
I parametri di una espressione lambda possono essere di qualunque tipo,
anche il nome di un’altra espressione lambda.
Vogliamo ora introdurre un altro problema mediante il seguente esempio
Scheme] (define op_imp (lambda (x) (+x y)))
Scheme] (op-imp 3)
29
1.8 Espressione lambda
unbound-variable
Scheme] (define y 4)
Scheme] (op_imp 3)
unbound-variable
Scheme] (let ((y 4)) (op_imp 3))
unbound-variable
Scheme] (let ((y 4)) ((lambda (x) (+ x y)) 3))
7
Scheme] (define y 4)
Scheme] (define op_imp1 (lambda (x) (+x y)))
Scheme] (op-imp1 3)
unbound-variable
Scheme]
Come si vede dagli esempi precedenti non si possono usare delle funzioni
lambda che abbiano dei parametri non dichiarati nella apposita sezione e senza
assegnare loro un valore, per fare una cosa del genere bisogna inserire lambda
nel corpo di una espressione let e assegnare un valore al parametro non dichiarato nella apposita sezione dell’istruzione let. Sembra che solo let riesca a funzionare, ma vediamo qest’altro esempio:
Scheme] ((lambda (y) ((lambda (x) (+ x y)) 3)) 4)
7
Scheme]
anche un lambda più esterno può servire allo scopo. La variabile y, per il
lambda interno si chiama variabile libera , ma se vogliamo che l’espressione
possa essere valutata detta variabile libera deve essere legata ad un opportuno
valore o da una let più esterna o da una lambda più esterna.
Osserviamo questo altro interessantissimo esempio:
Scheme] (let ( (x ’a) )
assegnazione del primo let
corpo del primo let
(let ( (f (lambda (y) (list x y))) ) ( f ’b) ) )
assegnazione del secondo let
corpo secondo let
(a b)
Scheme]
Il secondo let si trova nel corpo del primo e quindi tutto ciò che é stato
legato nelle assegnazioni del primo let é visibile, infatti l’espressione funziona.
30
Introduzione
Modifichiamo l’esempio precedente nel seguente modo:
assegnazione secondo let
corpo secondo let
Scheme] (let ( (f (let ( (x ’a) ) ( lambda (y) (list x y) ))) )
assegnazione primo let
( f ’b ))
corpo primo let
(a b)
Scheme]
come si vede il risultato é sempre lo stesso.
Un’evoluzione della precedente espressione può essere la seguente:
Scheme] (let ((f (let ((x ’a)) (lambda (y) (list x y)))))
nel corpo del primo let
( let ( (x ’non) ) (f ’b)) )
ridefiniamo x, ma non succede nulla
(a b)
Scheme]
Il valore della variabile x rimane quello che aveva quando la funzione lambda
é stata costruita, anche se lo si varia, con un terzo let, prima di usare la
lambda , questa variazione viene ignorata.
L’espressione lambda ha una struttura di questo tipo
parametri racchiusi tra parentesi
(lambda ( parametro1 parametro2 ) (corpo))
Se si mette un solo parametro non racchiuso tra parentesi e poi alla funzione
si passa un numero qualsivoglia di parametri il comportamento sarà il seguente,
si forma una lista con i parametri passati e all’unico parametro dichiarato viene
passata questa lista, ad esempio:
unico parametro non racchiuso tra parentesi
Scheme] (define f (lambda x (cdr x)))
31
1.8 Espressione lambda
Scheme] (f 1 2 3 4 ’a ’(a m n))
vengono passati piu’ parametri
(2 3 4 a (a m n))
Scheme]
Un altro esempio
Scheme] (let ((f (lambda x (cons ’+ x)))) (f 2 3))
(+ 2 3)
Scheme] (+ 2 3)
5
Scheme]
Un ultimo modo di usare lambda é il seguente:
occhio al punto
(lambda (p1 p2 . pr) (corpo di lambda) val1 val2 val3
valn)
Le parentesi sono necessarie
in questo modo al parametro p1 viene attribuito il valore val1 , al parametro p2 viene attribuito il valore val2 , i valori restanti formano la lista
(val3 valn) che viene attribuita al parametro pr .
Esempio:
parametri
corpo
Scheme] ((lambda (p1 p2 . pr) (+ (* p1 p2) (+ (car pr) (car (cdr pr))))) 2 3 4
2
5 7 8)
3
’(4 5 7 8)
6
4
5
Scheme]
Il risultato dell’esempio sarà 15.
Una funzione lambda può quindi avere un numero predeterminato di parametri oppure averne un numero arbitrario.
Vediamo ulteriori esempi:
Scheme] ((lambda (p1 p2 . pr) (+ (* p1 p2) ((car pr) (car (cdr pr))
(car (cdr (cdr pr)))))) 2 4 + 5 6 ’a - 3)
19
32
Introduzione
Scheme]
Vediamo come funziona questo esempio
p2 ≡ 4
primo addendo
parametri
(car pr) ≡ +
((lambda (p1 p2 . pr)
(+ ( * p1 p2 ) ( (car pr) (car (cdr pr))
corpo
p1 ≡ 2
pr ≡ ’(+ 5 6 ’a - 3)
secondo addendo
(car (cdr (cdr pr))) )) ) 2 4 + 5 6 ’a - 3)
valori passati
1.9 Define
Quanto dichiarato nella zona assegnazioni di una istruzione let o nella zona
parametri di una istruzione lambda viene visto solo nel corpo di queste espressioni, ben diversamente si comporta define le cui assegnazioni vengono viste da
tutte le espressioni successive fine a quando non viene oscurata da qualche altra
assegnazione. Le associazioni stabilite da define vengono chiamate top-level ,
questa caratteristica fa si che define sia molto importante , infatti é una espressione che abbiamo già usato parecchie volte in precedenza, la sua sintassi é:
assumerà come valore: espressione
(define variabile espressione)
qualunque espressione valida
Vediamo alcuni esempi con define:
Scheme] ; quanto definito con define puo’ essere oscurato da let
oppure lambda
#<eof>
Scheme] (define addizione (+ 3 2))
Scheme] addizione
5
33
1.9 Define
Scheme] (let ((addizione ’(n o n - n u m e r o))) addizione)
(n o n - n u m e r o)
Scheme] ( (lambda (addizione) (+ addizione 2))
25)
27
Scheme] ; quanto definito con define puo’ essere oscurato solo nel
corpo di let o lambda ma successivamente a un let o un
lambda ritorna visibile
#<eof>
Scheme] (define a 3)
Scheme] ((lambda (a) (* a a)) 5 )
25
Scheme] (* a a)
9
Scheme]
Introduciamo due nuove funzioni che operano sulle liste:
Scheme] (define a ’(+ - + /))
Scheme] (cadr a)
Scheme] ;La funzione cadr restituisce il secondo elemento di una
lista
#<eof>
Scheme]
La funzione cadr é definita nel seguente modo:
Scheme] (define cadr (lambda (x) (car (cdr x))))
Scheme] (cadr a)
Scheme]
La seconda funzione che vogliamo introdurre é cddr
Scheme] (define lista (quote(! ? ^ % $ £)))
Scheme] (cddr lista)
(^ % $ £)
Scheme] ; cddr restituisce la lista alla quale sono stati tolti i
primi due elementi. La definizione di cddr e’ la seguente:
34
Introduzione
#<eof>
Scheme] (define cddr (lambda (y) (cdr (cdr y))))
Scheme] (cddr lista)
(^ % $ £)
Scheme] ; se la lista restituita e’ vuota ecco che cosa succede
#<eof>
Scheme] (cddr (cddr (cddr lista)))
()
Scheme]
Importante 1.1. Quando define é usato in combinazione con lambda la parola
lambda si può sopprimere, l’esatta sintassi da seguire dipende da come sono
definiti i parametri di lambda.
•
Se i parametri di lambda sono racchiusi tra parentesi e sono quindi in
numero predefinito si procede in questo modo:
(define nome (lambda (var1 var2 ...... varn) exp1 exp2 ...... ))
diventa
(define (nome var1 var2 ...... varn) exp1 exp2 ...... )
esempio:
Scheme] (define area (lambda (b h) (* b h)))
Scheme] (area 10 20)
200
Scheme] ;diventa
#<eof>
Scheme] (define (area b h)(* b h))
Scheme] (area 4 8)
32
Scheme]
•
Lambda ha un solo parametro non racchiuso tra parentesi
(define nome (lambda var exp1 exp2 ......))
diventa
(define (nome . var) exp1 exp2 ....)
Esempio:
Scheme] (define terza (lambda parola (car (cddr parola))))
Scheme] (terza 1 2 3 4 5)
3
35
1.9 Define
Scheme] ;diventa
#<eof>
Scheme] (define (terza . parola) (car (cddr parola)))
Scheme] (terza 1 2 3 4 5 6)
3
Scheme]
•
L’ultimo caso si ha quando lambda ha un parametro residuo, cioé é del
tipo:
parametro residuo
(lambda (p1 p2 ..... pn . pr) exp1 exp2 .......)
l’espressione define sarà quindi:
(define nome (lambda (p1 p2 ..... pn . pr) exp1 exp2 .......))
la quale si può abbreviare nel seguente modo:
(define (nome p1 p2 ......pn . pr) exp1 exp2 .......)
Esempio:
Scheme] (define operazione (lambda (p1 p2 . op) ((cadr op) p1
p2)))
Scheme] (operazione 6 3 + - * /)
3
Scheme] ;diventa
#<eof>
Scheme] (define (operazione p1 p2 . op) ((cadr op) p1 p2))
Scheme] (operazione 6 3 + - * /)
3
Scheme]
Queste abbreviazioni tendono a rendere il codice meno leggibile per cui sarà
opportuno farne un uso molto parco.
Consideriamo ora alcuni modi, molto interessanti, per usare define, ci sono
molte operazioni che hanno un solo parametro cioé che prendono un oggetto x
fanno qualche cosa e restituiscono un risultato, possiamo definire queste operazioni nel seguente modo:
Scheme] (define monadica (lambda (operazione)
(lambda (x) (operazione x x))))
Scheme] ;definiamo l’operazione monadica doppio
36
Introduzione
#<eof>
Scheme] (define doppio (monadica +))
Scheme] (doppio 2)
4
Scheme] (define quadrato (monadica *))
Scheme] (quadrato 7)
49
Scheme] (define coppia (monadica cons))
Scheme] (coppia ’a)
(a . a)
Scheme] ;definiamo una nuova operazione binaria
#<eof>
Scheme] (define modulo_vettore (lambda (x y) (sqrt (+ (* x x) (* y
y)))))
Scheme] (define mod_vett_45 (monadica modulo_vettore))
Scheme] (mod_vett_45 10)
14.142135623731
Scheme] (* (mod_vett_45 10) (mod_vett_45 10))
200.0
Scheme] ;osservare questa espressione
#<eof>
Scheme] (define monadica_tutto (lambda (op x) ((monadica op) x)))
Scheme] (monadica_tutto modulo_vettore 10)
14.142135623731
Scheme] (monadica_tutto + 6)
12
Scheme]
In define una procedura può anche usare il nome di una procedura non ancora
definita, esempio:
Scheme] (define es_a (lambda (x y) (es_b x y)))
Scheme] ;come si vede tutto e’ andato bene e non e’ stato
evidenziato il fatto che es_b non e’ definita, ma se
proviamo a usare es_a ecco che cosa succede
#<eof>
Scheme] (es_a 8 7)
unbound-variable
1.9 Define
37
Scheme] ;viene evidenziato il fatto che esiste una variabile
sconosciuta, ma se definiamo es_b succede che:
#<eof>
Scheme] (define es_b *)
Scheme] ;ripetiamo quanto fatto prima
#<eof>
Scheme] (es_a 8 7)
56
Scheme]
Osservazione 1.2. Le istruzioni car e cdr hanno alcune varianti che illustriamo
con i seguenti esempi:
Scheme] (define str (quote(((1 2) 3) a b c d e f g h i l m n)))
Scheme] (car str)
((1 2) 3)
Scheme] (caar str)
(1 2)
Scheme] (caaar str)
1
Scheme] (caaaar str)
wrong-type-arg
Scheme] (cdr str)
(a b c d e f g h i l m n)
Scheme] (cddr str)
(b c d e f g h i l m n)
Scheme] (cdddr str)
(c d e f g h i l m n)
Scheme] (cddddr str)
(d e f g h i l m n)
Scheme] (cdddddr str)
unbound-variable
Scheme] ;arriva fino a 5 d
#<eof>
Scheme] ; le due cose si possono combinare assieme
#<eof>
38
Introduzione
Scheme] (cadr str)
a
Scheme] (caddr str)
b
Scheme] (cdar str)
(3)
Scheme] (cdaar str)
(2)
Scheme] (cdaaar str)
wrong-type-arg
Scheme]
Vediamo nel dettaglio il funzionamento di uno di questi esempi
1 - il primo a fa il car di str e restituisce ((1 2) 3)
2 - il secondo a fa il car del 1 passo e restituisce (1 2)
cdaar str
3 - il primo d fa il cdr del 2 passo e restituisce (2)
1.10 Espressioni con condizione
Cominciamo con l’istruzione if la sua forma é di questo tipo:
if test espressione_test_vero espressione_test_falso
Vediamo alcuni esempi:
Scheme] (if (< 3 2) (* 3 2) (+ 3 2))
5
Scheme] (if (=
3 3) (quote(vero)) (quote(falso)))
(vero)
Scheme] (if (=
3 6) (quote(vero)) (quote(falso)))
(falso)
Scheme] ; esempio complicato
1.10 Espressioni con condizione
39
#<eof>
Scheme] (define calcolo_radici (lambda (a b c) (if (>= (- (* b b) (*
4 a c)) 0) (quote(ci sono radici)) (quote(non ci sono
radici)))))
Scheme] (calcolo_radici 1 3 2)
(ci sono radici)
Scheme] (calcolo_radici 10 2 -9)
(ci sono radici)
Scheme] (calcolo_radici 100 -5 6)
(non ci sono radici)
Scheme]
Con if si possono usare tutte le possibili espressioni booleane ma anche le
altre, ad esempio:
Scheme] (if (not(= 3 3)) (quote(vero)) (quote(falso)))
(falso)
Scheme] (if (<= (+ 8 2) (* 5 2)) ’(vero) ’(falso))
(vero)
Scheme] (define a 3)
Scheme] (define b 5)
Scheme] (if (> a b) ’(vero) ’(falso))
(falso)
Scheme] (if (+ a b) ’(vero) ’(falso))
(vero)
Scheme] (if (/ a 0) ’(vero) ’(falso))
numerical-overflow
Scheme] (if (/ 0 a) ’(vero) ’(falso))
(vero)
Scheme] (if (sqrt (* -1 a)) ’(vero) ’(falso))
(vero)
Scheme] (if (define c 16) ’(vero) ’(falso))
(vero)
Scheme] (sqrt c)
4.0
Scheme] (sqrt (* -1 c))
40
Introduzione
0.0+4.0i
Scheme]
Si possono anche usare le operazioni booleane and e or
Scheme] (if (or (< 5 4) (= 0 (- 5 5))) ’(vero) ’(falso))
(vero)
Scheme] (if (and (+ 4 5) (< 3 28) (= 6 (+ 3 3))) "vero" "falso")
"vero"
Scheme]
Una espressione booleana si può anche testare direttamente:
Scheme] (< 8 2)
#f
Scheme] ;#f vuol dire
false
#<eof>
Scheme] (= (* 6 7) 42)
#t
Scheme] ;#t significa
true
#<eof>
Scheme] (or #t #f #t)
#t
Scheme] (and #t #f #t)
#f
Scheme] (or #f (and #t #t) #f)
#t
Scheme]
Molto interessante é l’uso del punto interrogativo
Scheme] (null? (- 5 5))
#f
Scheme] ;null non significa nullo ma insieme vuoto
#<eof>
Scheme] (null? (cdr(quote(a))))
#t
Scheme] (symbol? *)
41
1.10 Espressioni con condizione
#f
Scheme] (integer? 3)
#t
Scheme] (real? 6)
#t
Scheme] (complex? (sqrt -4))
#t
Scheme] (procedure? *)
#t
Scheme] (define quadrato (lambda (x) (* x x)))
Scheme] (procedure? quadrato)
#t
Scheme] (procedure? quadrato1)
unbound-variable
Scheme]
Questa roba può essere utile per scrivere del codice robusto come in questo
esempio
Scheme] (define piu (lambda (x y) (if (and (number? x) (number? y))
(+ x y) "fai attenzione pirla")))
Scheme] (piu 3 5)
8
Scheme] (piu ’a ’g )
"fai attenzione pirla"
Scheme] (piu 3 =)
"fai attenzione pirla"
Scheme]
Un’altra espressione simile a if é cond
, la sua sintassi é la seguente:
(cond (test1 esp1) (test2 exp2.) .......... (testn expn.) (else exp.))
else si può anche omettere
Vediamo un esempio con cond:
42
Introduzione
Scheme] (define controllo (lambda (x) (cond ((>= x 100) "x>100")
((and (> x 0) (< x 100)) "x compreso tra 10 e 100") (else
"e’ da un’altra parte"))))
Scheme] (controllo 123)
"x>100"
Scheme] (controllo 56)
"x compreso tra 10 e 100"
Scheme] (controllo -125)
"e’ da un’altra parte"
Scheme]
1.10.1 Esercizi
Esercizio 1.7. Definisci il predicato atomo? che restituisce vero se il suo unico argomento
non é una coppia falso se invece é una coppia.
Soluzione.
Scheme] (define atomo? (lambda (arg) (if (not(pair? arg)) "vero"
"falso")))
Scheme] (atomo? 5)
"vero"
Scheme] (atomo? ’(a.b))
"falso"
Scheme] (atomo? ’(a b))
"falso"
Scheme] (atomo? ’(a b c))
"falso"
Scheme] (atomo? +)
"vero"
Scheme] (atomo? ’(12 . 4))
"falso"
Scheme] (atomo? (+ 3 2))
"vero"
Scheme] (pair? ’(a b c d e f))
#t
Scheme] ; pair? ha un funzionamento un poco strano
#<eof>
1.11 Ricorsione
43
Scheme] (atomo? (a b))
unbound-variable
Scheme]
Esercizio 1.8. La procedura length accetta come parametro una lista e ne restituisce la
sua lunghezza. Scrivere una procedura ListaCorta che accetta come parametri due liste e
restituisce la più corta.
Soluzione.
Scheme] (define ListaCorta (lambda (l1 l2) (if (<= (length l1)
(length l2)) l1 l2)))
Scheme] (ListaCorta ’(a b) ’(1 2 3 4))
(a b)
Scheme] (ListaCorta ’(a b c d) (cdr ’(a b c d)))
(b c d)
Scheme]
1.11 Ricorsione
Consideriamo le seguenti righe di codice:
Scheme] (define pot
(lambda (base esp)
(if (= esp 1) base
(* (pot base (- esp 1)) base))))
Scheme] (pot 2 1)
2
Scheme] (pot 2 2)
4
Scheme] (pot 2 3)
8
Scheme] (pot 2 4)
16
Scheme] (pot 2 5)
32
Scheme] (pot 2 6)
64
44
Introduzione
Scheme] (pot 2 7)
128
Scheme] (pot 15 5)
759375
Scheme]
Vediamo di capire come funzione la procedura pot precedentemente definita:
Scheme] (define pot
(lambda (base esp)
passo base , quando viene eseguita questa
(if (= esp 1) base parte la ricorsione finisce
passo ricorsivo
(* (pot base (- esp 1)) base))))
viene richiamata pot con esp diminuito di 1
La procedura deve contenere al suo interno due parti: il passo base e il
passo ricorsivo , il passo base é quella parte del codice che termina la ricorsione, infatti quando esp diventa 1 pot assume il valore della base e non viene
richiamata pot stessa; poi vi é il passo ricorsivo , in questa fase viene richiamata pot, infatti pot assume il valore dato dal prodotto di pot, con la stessa
base e esponente diminuito di 1, per la base stessa.
Sicuramente si arriva a esp=1 perché lo si diminuisce sempre di 1, nel passo
ricorsivo, quindi la ricorsione ha sicuramente termine.
Vediamo come funziona ad esempio (pot 2 4)
| (pot 2 4)
richiamo di 24
|| (pot 2 3)
richiamo di 23
||| (pot 2 2)
richiamo di 22
|||| (pot 2 1)
richiamo e calcolo di 21
2
|||
4
calcolo di 22
||
8
calcolo di 23
16
calcolo di 24
|
45
1.11 Ricorsione
In matematica ci sono parecchie definizioni date in modo ricorsivo una di
queste è la definizione di fattoriale di un numero: n! = (n − 1)! · n, se n=1 1!=1
vediamo come tradurre questa definizione in una procedura ricorsiva:
Scheme] (define fatt (lambda (n) ;parametro
(if (= n 1) 1 ;corpo di lambda - passo base
(* (fatt (- n 1)) n)))); passo ricorsivo
Scheme] (fatt 2)
2
Scheme] (fatt 6)
720
Scheme] (fatt 50)
30414093201713378043612608166064768844377641568960512000000000000
Scheme]
Esempio 1.3. Scrivere una procedura che presa una lista e un oggetto restituisca la sottolista, se esiste, che inizia con l’oggetto passato e va fino alla fine
della lista, altrimenti restituisce falso.
Scheme] (define sottolista (
lambda (og ls)
(cond ((null? ls) #f ) ((eqv? (car ls) og) ls )
(else (sottolista og (cdr ls))))))
Scheme] (sottolista ’c ’(a b c d e))
(c d e)
Scheme] (sottolista ’x ’(a b c d e f))
#f
Scheme]
Osservazione 1.4. L’esempio precedente é piuttosto interessante perché
sono due passi base
ci
Scheme] (define sottolista (
lambda (og ls)
10 passo base
(cond ((null? ls) #f ) ((eqv? (car ls) og) ls )
passo ricorsivo
2o passo base
(else (sottolista og (cdr ls))))))
46
Introduzione
Scheme] (sottolista ’c ’(a b c d e))
(c d e)
Scheme] (sottolista ’x ’(a b c d e f))
#f
Scheme]
Esempio 1.5. Scrivere una procedura avente due parametri, un oggetto e una
lista di quel tipo di oggetti e cancellare dalla lista tutte le occorrenze
dell’oggetto e restituire la nuova lista.
Scheme] (define lista-epurata
(lambda (og ls)
(cond ((null? ls) ’())
((eqv? (car ls) og) (lista-epurata og (cdr ls)))
(else (cons (car ls) (lista-epurata og (cdr
ls)))))))
Scheme] (lista-epurata ’a ’(a y z a))
(y z)
Scheme] (lista-epurata ’h ’(q w e s))
(q w e s)
Scheme] (lista-epurata ’a ’(a a a a))
()
Scheme] (lista-epurata 3 2)
wrong-type-arg
Questo esempio é interessante perché ha due passi ricorsivi
Scheme] (define lista-epurata
(lambda (og ls)
(cond ((null? ls) ’())
10 passo ricorsivo
passo base
((eqv? (car ls) og) (lista-epurata og (cdr
20 passo ricorsivo
ls)))
(else (cons (car ls) (lista-epurata og (cdr
ls)))))))
Vediamo ora una nuova procedura, la procedura map , per introdurla consideriamo il seguente esempio, supponiamo di avere una lista di numeri e di voler
ottenere la lista dei loro doppi, potremmo procedere con la ricorsione come
segue:
1.11 Ricorsione
47
Scheme] (define lista-doppia (lambda (ingr)
(if (null? ingr) ’()
(cons (* 2 (car ingr))
(lista-doppia(cdr ingr))))))
Scheme] (lista-doppia ’(2 3 4 5))
(4 6 8 10)
Scheme]
In pratica su ogni elemento della lista viene fatta la stessa operazione,
Scheme ha una funzione apposta per fare questo ed é map:
Scheme] (map (lambda (x) (* 2 x)) ’(2 3 4 5))
(4 6 8 10)
Scheme]
Dopo map bisogna mettere l’operazione da fare su ogni elemento della lista e
poi la lista.
Scheme] (map abs ’(-1 2 -8 3 -4 -9))
(1 2 8 3 4 9)
Scheme] (map cdr ’((a b) (s h) (3 5 9)))
((b) (h) (5 9))
Scheme]
Osserviamo questa interessante applicazione di map
Scheme] (map * ’(1 3 2 5) ’(4 5 6 9))
(4 15 12 45)
Scheme]
Se passiamo a map due liste della stessa lunghezza e indichiamo cosa fare tra
gli elementi dello stesso posto delle due liste verrà restituita una lista costituita
dai risultati di questa operazione.
Scheme] (map (lambda (x y) (+ 1 (* x y))) ’(3 4 5) ’(1 2 3))
(4 9 16)
Scheme] (map cons ’((a b) c (1 2 3)) ’((1 2) s (4 5)))
(((a b) 1 2) (c . s) ((1 2 3) 4 5))
Scheme]
48
Introduzione
Esercizio 1.9. Scrivere una procedura che fonda due liste in una sola cioé data ad esempio
la lista ’(a b c) e la lista ’(1 2 3) restituisca la lista ’(a b c 1 2 3)
Scheme] (define fusione (lambda (ls1 ls2)
(if (null? ls1) ls2
(cons (car ls1) (fusione (cdr ls1) ls2)))))
Scheme] (fusione ’(a b c) ’(1 2 3))
(a b c 1 2 3)
Scheme]
Esercizio 1.10. Scrivere una funzione che prende in ingresso un numero n intero positivo
non nullo e un qualsiasi oggetto e restituisce in uscita una lista contenente n oggetti tutti
uguali all’oggetto passata in ingresso.
Scheme] (define lstn (lambda (n og)
(if (= n 0) ’()
(cons og (lstn (- n 1) og)))))
Scheme] (lstn 4 ’a)
(a a a a)
Scheme] (lstn 5 3)
(3 3 3 3 3)
Scheme] (lstn 3 ’(+))
((+) (+) (+))
Scheme]
Esercizio 1.11. Scrivere una funzione che prenda in ingresso due liste e restituisca la più
corta.
Scheme] (define lung (lambda (l) (if (null? l) 0
(+ 1 (lung (cdr l))))))
Scheme] (lung ’(a s d))
3
Scheme] ; dopo aver ridefinito la funzione lenght possiamo utilizzarla come
gia’ fatto in precedenza
#<eof>
Scheme] (define corta (lambda (l1 l2)
(if (< (lung l1) (lung l2)) l1 l2)))
Scheme] (corta ’(1 2 3 3 4) ’(a s d))
(a s d)
Scheme] (corta ’() ’(1 2 3))
()
Scheme] (corta ’(m n b) ’(1 2 3))
(1 2 3)
Scheme]
1.12 Assegnamento
49
Esercizio 1.12. Scrivere due funzioni una che richiama l’altra realizzando così una ricorsione indiretta.
Scheme] (define a (lambda (n)
(if (= n 0) 0 (* n (b (- n 1))))))
Scheme] (define b (lambda (m)
(if (= m 0) 1 (+ m (a (- m 1))))))
Scheme] (a 3)
9
Scheme] (b 4)
13
Scheme] (b 5)
25
Scheme] (a 8)
1256
Scheme]
Esercizio 1.13. Scrivere una funzione che prenda una lista di coppie, come ad esempio
((a . 1) (b . 2) (c . 3)), e restituisca una coppia di liste , ad esempio ((a b c) (1 2 3))
Scheme] (define duo (lambda (lc)
(cons (map car lc)
(list(map cdr lc)))))
Scheme] (duo ’((a . 1) (b . 2) (c . 3)))
((a b c) (1 2 3))
Scheme]
1.12 Assegnamento
La funzione di assegnamento serve a ridefinire una variabile alla quale é già
stato assegnato un valore tramite qualche altra funzione, l’istruzione che la rappresenta é set! , vediamo alcuni esempi:
Scheme] (define a 5)
Scheme] a
5
Scheme] (set! a ’(a b c))
Scheme] a
(a b c)
Scheme] ;cambia il valore che la variabile a aveva assunto grazie a
define
#<eof>
50
Introduzione
Scheme] (set! b 7)
unbound-variable
Scheme] ; non si puo’ usare set! su una variabile non ancora
definita
#<eof>
Scheme] (define g (lambda (x) (set! a x)))
Scheme] a
(a b c)
Scheme] (g 9)
Scheme] a
9
Scheme] ;la funzione g ha come unico effetto quello di cambiare il
valore della variabile a
#<eof>
Scheme] (let ((a1 2) (a2 4)) (set! a1 10) (set! a2 20) (* a1 a2))
200
Scheme]
Sul nostro testo di riferimento [1, a pag. 38] c’é un esempio svolto che
riguarda la soluzione delle equazioni di 2ř grado, é molto interessante e quindi
proviamo a risolvere una equazione di 2ř grado:
Scheme] (define equ-secondo (lambda (a b c)
(let ((meno_b 0) (delta 0) (rad_delta 0) (den 0) (x1 0) (x2
0))
(set! meno_b (- 0 b))
(set! delta (- (* b b) (* 4 a c)))
(set! rad_delta (sqrt delta))
(set! den (* 2 a))
(set! x1 (/ (+ meno_b rad_delta) den))
(set! x2 (/ (- meno_b rad_delta) den))
(cons x1 x2))))
Scheme] (equ-secondo 1 -5 6)
(3.0 . 2.0)
Scheme] (equ-secondo 1 5 6)
(-2.0 . -3.0)
Scheme] (equ-secondo 1 2 5)
(-1.0+2.0i . -1.0-2.0i)
Scheme] ;usa con molta disinvoltura i numeri complessi
1.12 Assegnamento
51
#<eof>
Scheme]
Sempre sullo stesso testo [1, a pag. 38 ] c’é tutta una lamentela sull’uso di
set! , e , se ho capito bene (é tutto scritto in inglese) insiste sull’inutilità
dell’uso di set!, anche se ammette che può rendere più leggibile il codice, e rifà
l’esercizio precedente senza usare set!, proviamoci anche noi.
Scheme] (define equ2 (lambda (a b c)
(let ((mb (- 0 b))
(rd (sqrt (- (* b b) (* 4 a c))))
(dv (* 2 a)))
(cons (/ (+ mb rd) dv)
(/ (- mb rd) dv)))))
Scheme] (equ2 1 -5 6)
(3.0 . 2.0)
Scheme] (equ2 1 -6 9)
(3.0 . 3.0)
Scheme] (equ2 3 8 4)
(-0.666666666666667 . -2.0)
Scheme] (equ2 8 1 20)
(-0.0625+1.57990308247057i . -0.0625-1.57990308247057i)
Scheme] ;fatto
#<eof>
Scheme]
Sempre sul solito testo [1, a pag. 39 ] c’é un interessante metodo per modificare il comportamento di cons facendo si che ogni volta che viene usata cons
non solo si ottenga il solito risultato ma venga incrementato un apposito contatore che in ogni istante ci dice quante volte cons é stata usata, proviamo anche
noi a fare una cosa del genere.
Scheme] (define c 0)
Scheme] c
0
Scheme] (set! cons (let ((vcons cons))
(lambda (x y) (set! c (+ c 1)) (vcons x y))))
Scheme] (cons 3 ’(g h j))
(3 g h j)
52
Introduzione
Scheme] c
2692
Scheme] (cons ’(a s) ’(4 5))
((a s) 4 5)
Scheme] c
5379
Scheme] (cons 1 ’(5))
(1 5)
Scheme] c
9377
Scheme]
Come si vede c assume valori del tutto inspegabili, c’é qualche cosa che
non va, provo a rifare la stessa cosa su un altro sistema DrRacket .
Lanciato DrRacket bisogna seguire le istruzioni riportate in http://tedgao.blogspot.it/2011/08/learning-scheme-using-drracket.html , in particolare
quanto riportato nella figura sottostante:
1.12 Assegnamento
53
e, dopo aver premuto Run , nella sezione più bassa riportare quanto già
fatto nella sezione Scheme , ecco che cosa succede
Non si può ridefinire cons , proviamo a procedere in quest’altro modo che
forse funziona: 1.2
Scheme] (define c 0)
Scheme] c
0
Scheme] (define mcons cons)
Scheme] (set! mcons (lambda (x y) (set! c (+ c 1)) (cons x y)))
Scheme] c
0
Scheme] (mcons 3 ’(g h j))
(3 g h j)
Scheme] c
1
Scheme] (mcons ’(a s) ’(4 5))
((a s) 4 5)
Scheme] c
2
1.2. Ho impiegato due giorni per risolvere il problema ed ho pure dovuto reinstallare il sistema operativo.
54
Introduzione
Scheme] (mcons ’a (mcons ’b ’(1 2 3)))
(a b 1 2 3)
Scheme] c
4
Scheme] ;tutto funziona come deve funzionare.
Set! pare sia molto utilizzata per memorizzare lo stato interno di una funzione, ad esempio proviamo a scrivere una funzione che conta quante volte é già
stata chiamata, ci deve essere al suo interno una variabile che si aggiorna tutte
le volte che la funzione viene chiamata (vedi [1, pag. 40])
Scheme] (define contatore 0)
Scheme] (define conta (lambda () (set! contatore (+ contatore 1))
contatore))
Scheme] (conta)
1
Scheme] (conta)
2
Scheme] (conta)
3
Scheme] ;se rivalutiamo la prima linea (define contatore 0) ecco che
cosa succede
#<eof>
Scheme] (conta)
1
Scheme] ; il contatore viene di nuovo azzerato
Il fatto che il contatore venga inizializzato in una apposita linea di codice
non é una bella cosa, proviamo in questo altro modo:
Scheme] (define conta (let ((contatore 0))
(lambda () (set! contatore (+ contatore 1))
contatore)))
Scheme] (conta)
1
Scheme] (conta)
2
Scheme] (+ (conta) 4)
7
1.12 Assegnamento
55
Scheme] ; etc........
Osservazione 1.6. Vediamo ora di costruire una procedura che crea tutta una
serie di contatori uno indipendente dall’altro.
Scheme] (define crea (lambda ()
(let ((contatore 0))
(lambda () (set! contatore (+ contatore 1))
contatore))))
Scheme] (define cnt1 (crea))
Scheme] (define cnt2 (crea))
Scheme] (cnt1)
1
Scheme] (cnt1)
2
Scheme] (cnt2)
1
Scheme] (+ 6 (cnt2))
8
Scheme] (cnt2)
3
Scheme] (cnt2)
4
Scheme] (cnt1)
3
Scheme]
C’é molta perplessità sul funzionamento di define, let , lambda, set! etc. evidentemente non tutto é stato spiegato. La perplessità nasce dal comportamento
di set!, proviamo con questo esempio:
Scheme] (define pp (let ((a 2) (b 4))
(set! a (+ a 2)) (set! b (+ b 1)) (+ a b)))
Scheme] (pp)
misc-error
Scheme] pp
9
Scheme] pp
9
56
Introduzione
Scheme] ;in questo esempio set! sembra non aver avuto effetto,
proviamo a mettere il corpo di let in una lambda
#<eof>
Scheme] (define pp1 (let ((a 2) (b 4))
(lambda ()
(set! a (+ a 2)) (set! b (+ b 1)) (+ a b))))
Scheme] pp1
#<procedure pp1 ()>
Scheme] ; osservare il risultato
#<eof>
Scheme] (pp1)
9
Scheme] (pp1)
12
Scheme] (pp1)
15
Scheme] ; con lambda set! funziona
Ci sono alcune cose da osservare, nel primo dei due esempi precedenti “define
pp” tratta pp come se fosse un valore, infatti per richiamarlo si usa semplicemente pp e non (pp), nel secondo esempio “define pp1” a pp1 viene associata la
lambda , il let sembra quasi ignorato funziona solo la lambda, tranne che la
prima volta, e per richiamarlo bisogna usare le parentesi (pp1). L’impressione
che ho avuto é che in define il let venga valutato solo al momento della sua
scrittura e poi in pp rimanga sempre lo stesso valore, mentre lambda viene valutato tutte le volte che si richiama la funzione, tutto questo spiega perchè set!
funziona solo dentro un lambda e non dentro let.
Studiamo adesso il seguente esempio:
Scheme] (define pigro1 (lambda (t)
(let ((val #f) (flag #f))
(lambda ()
(if (not flag)
(begin (set! val (t))
(set! flag #t))
val)))))
Scheme] (define pr1 (pigro1
(lambda ()
(display "Solo per questa volta")
(newline) "questo sempre")))
Scheme] (pr1)
Scheme] (pr1)
1.12 Assegnamento
57
"questo sempre"
Scheme] (pr1)
"questo sempre"
Scheme] (display "Solo per questa volta")
Scheme] ; e’ chiaro che la procedura display con Texmacs non
funziona, proviamo con DrRacket
#<eof>
Scheme]
Anche DrRaket , se usa r6rs , non funziona
Non riconosce display come procedura, proviamo a non usare r6rs ma proprio racket.
Proviamo le due procedure precedenti con racket
58
Introduzione
Scheme] (define pigro1 (lambda (t)
(let ((val #f) (flag #f))
(lambda ()
(if (not flag)
(begin (set! val (t))
(set! flag #t))
val)))))
Scheme] (define pr1 (pigro1
(lambda ()
(display "Solo per questa volta")
(newline)
"questo sempre")))
Scheme]
Facciamo funzionare il tutto
Funziona tutto come deve funzionare, vediamo di spiegare il perché di questo
comportamento.
59
1.12 Assegnamento
Scheme] (define pr1 (pigro1
(lambda ()
Stampa la frase sullo schermo
(display "Solo per questa volta")
(newline)
Valore restituito da pr1
"questo sempre")))
La procedura pr1 stampa sullo schermo Solo per questa volta , senza virgolette, e successivamente posiziona il cursore all’inizio di una nuova riga, infine
restituisce la frase “questo sempré’ , il fatto che restituisca questo valore non
vuol dire che lo stamperà sullo schermo, in particolare se verrà chiamata entro
un’altra procedura non verrà stampato.
Vediamo ora come funziona l’altra procedura la pigro1.
(define pigro1 (lambda (t)
(let ((val #f) (flag #f))
(lambda ()
(if (not flag)
(begin (set! val (t))
Blocco if
vero
(set! flag #t))
val)))))
falso
La procedura pigro1 é un lambda con un parametro t e un corpo che é una
let che fissa due parametri booleani, val e flag, a falso ed ha un corpo che é
un’altra lambda la quale non ha parametri ed ha un corpo che é una if. La
pigro1 viene chiamata da pr1 che gli passa la procedura t:
Scheme] (lambda ()
(display "Solo per questa volta")
(newline)
"questo sempre")
La prima volta che pigro1 viene chiamata, non essendo ancora intervenuta
set!, ha i due parametri della let, val e flag, settati a falso dalla let stessa, pertanto dell’if viene eseguita la parte “vero” e quindi le due linee del begin, viene
valutata
(t),
in
particolare
display
stamperà
sullo
schermo
, la lambda poi restituisce “questo sempré’ e val verrà
Solo per questa volta
settata a questo valore dalla set! mentre flag verràs settato a vero dalla successiva set!, la parte falso non viene eseguita. Le volte successive pigro1 ha flag settata a vero e val settata a “questo sempré’ quindi dell’if viene eseguita la parte
60
Introduzione
falso cioé viene restituito “questo sempré’ che essendo il risultato della funzione
chiamata verrà stampato sullo schermo.
In Texmacs la funzione display non viene valutata e questo spiega il funzionamento anomalo visto in precedenza.
Adesso, sempre per la serie “vediamo come si usa set!”, costruiamo un
costruttore di stack. Lo stack è una pila di oggetti che vengono inseriti e estratti
sempre dalla stessa parte:
Lo stack é un oggetto contenente una lista che rappresenta la pila dello stack
e inoltre accetta 4 tipi di messaggi:
1. ’vuoto e l’oggetto risponde con #t se la pila é vuota altrimenti risponde
#f
2. ’push allora aggiunge in testa alla pila un oggetto che verrà passato come
argomento,
3. ’top restituisce l’elemento che sta in cima alla pila
4. ’pop cancella l’elemento che sta in cima alla pila
Scheme] (define fabb-stack (lambda ()
(let ((pila ’()))
(lambda (mess . arg)
(cond
((eqv? mess ’vuoto) (null? pila))
((eqv? mess ’push)
(set! pila (cons (car arg) pila)))
((eqv? mess ’pop)
(set! pila (cdr pila)))
((eqv? mess ’top)
(car pila))
(else "va a ...."))))))
1.12 Assegnamento
61
Scheme] (define stack1 (fabb-stack))
Scheme] (stack1 ’vuoto)
#t
Scheme] (stack1 ’push ’a)
Scheme] (stack1 ’vuoto)
#f
Scheme]
Scheme]
Scheme]
Scheme]
(define
(stack2
(stack2
(stack2
stack2 (fabb-stack))
’push ’ab)
’push ’wacb)
’top)
wacb
Scheme] (stack1 ’top)
a
Scheme] (stack1 ’push ’gh)
Scheme] (stack1 ’push ’avb)
Scheme] (stack1 ’top)
avb
Scheme] (stack1 ’pop)
Scheme] (stack1 ’top)
gh
Scheme] (stack2 ’top)
wacb
Scheme] (stack1 ’pop)
Scheme] (stack1 ’top)
a
Scheme] (stack2 ’top)
wacb
Scheme] (stack2 ’pop)
Scheme] (stack2 ’top)
ab
Scheme]
Molto bene tutto funziona come deve funzionare, questa procedura assomiglia
molto alla procedura vista in 1.6 a pag. 55 anche lì c’era una lambda esterna
priva di parametri, il corpo di detta lambda costituito da una let con un parametro che inizializza la variabile più importante , una lambda nel corpo della let
che definisce la funzione da creare , in entrambi i casi set! serve a tenere traccia
del funzionamento della funzione.
62
Introduzione
Indice analitico
accento ’
.. . .
and . . . . . . . .
car . . . . . . . .
cdr . . . . . . . .
commento ; . . .
cond . . . . . . . .
cons . . . . . . . .
coppia . . . . . . .
define . . . . . . .
DrRacket . . . . .
espressione . . . .
espressione lambda
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
40
15
15
10
41
15
16
11
52
10
27
if . . . . . . .
let . . . . . . .
or . . . . . . .
passo base . .
passo ricorsivo
procedure . . .
quote . . . . .
simbolo . . . .
stringhe . . . .
top-level . . .
variabile libera
63
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
38
24
40
44
44
11
14
16
11
32
29
Bibliografia
[1] R. Kent Dybvig. The Scheme programming language, volume Unico. MIT, 2 edition.
65