1

Carlo Strapparava - Informatica

Riepilogo: la radice quadrata

Il programma sqrt mostra come il semplice linguaggio introdottosia sufficiente per scrivere piccoli programmi

sqrt-iter mostra come l’iterazione possa essere realizzata conla sola chiamata procedurale senza particolari costrutti iterativi

(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))

(define (improve guess x) (average guess (/ x guess)))

(define (average x y) (/ (+ x y) 2))

(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))

(sqrt 9)=> 3.00009155413138(sqrt (+ 100 37))=> 11.704699917758145(sqrt (+ (sqrt 2) (sqrt 3)))=> 1.7739279023207892(square (sqrt 1000))=> 1000.000369924366

(define (sqrt x) (sqrt-iter 1.0 x))

Carlo Strapparava - Informatica

Riepilogo:regola generale di valutazione

L’interprete prima valuta l’ operatore e glioperandi, poi applica la procedura risultanteagli argomenti risultanti (applicative order).

Lo Scheme implementa l’applicative order Eccezioni alla regole generale di valutazione si

dicono Forme Speciali (Syntactic Sugar)

2

Carlo Strapparava - Informatica

Esercizio: new-if

La signorina Hacker ridefinisce if come

poi, testa la procedura

e, deliziata, ridefinisce sqrt-iter comeQuale sarà ora il comportamento di sqrt-iter ?

(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))

(new-if (= 2 3) 0 5)=> 5(new-if (= 1 1) 0 5)=> 0

(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))

Carlo Strapparava - Informatica

Procedure come black boxes

Il problema di calcolare la radice quadrata sidecompone in un certo numero di sottoproblemi come fare a dire che una proposta di soluzione è

abbastanza buona come fare a migliorare una soluzione …

E’ cruciale che ogni procedura individui uncompito ben preciso

3

Carlo Strapparava - Informatica

Astrazione procedurale

Non importa come sono implementate leprocedure che utilizzo per es. nella scrittura digood-enough?, le vedo come scatole nere

Decomposizione procedurale di sqrt

sqrt

sqrt-iter

good-enough?

square

improve

averageabs

Carlo Strapparava - Informatica

Nomi locali e scope

I nomi dei parametri di una procedura sono localialla procedura: sono variabili legate

La definizione di procedura lega i suoi parametriformali

Una variabile che non è legata si dice libera L’insieme delle espressioni su cui vale il legame di

un nome si dice scope (= portata) di quel nome

(define (square x) (* x x))

(define (square y) (* y y))Sono indistinguibili !

4

Carlo Strapparava - Informatica

Nomi locali e scope (cont.)

Il significato di good-enough? è indipendente dai nomi che scegliamo perguess e x, fintantoché sono distinti tra loro e differenti da < - abs esquare

Il significato di good-enough? non è indipendente dalle sue variabili libere Se ridenominassimo il parametro guess in abs avremmo introdotto un baco

chiamato capturing della variabile abs. Da variabile libera, diventerebbevariabile legata.

(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))

• guess e x sono variabili legate• < - abs square sono variabili libere

Carlo Strapparava - Informatica

Definizioni interne e struttura a blocchi

L’unica procedura che interessa è sqrt Non è permesso definire un’altra procedura chiamatagood-enough? solo perché la usa sqrt

Dobbiamo avere la possibilità di definire procedure localinascondendole dentro sqrt

(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))

(define (improve guess x) (average guess (/ x guess)))

(define (average x y) (/ (+ x y) 2))

(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))

(define (sqrt x) (sqrt-iter 1.0 x))

5

Carlo Strapparava - Informatica

Questa struttura di innestamento di definizioni si chiamastruttura a blocchi

Possiamo non solo nascondere le definizioni, ma anche semplificarle

(define (sqrt x) (define (good-enough? guess ) (< (abs (- (square guess) x)) 0.001)) (define (improve guess ) (average guess (/ x guess))) (define (sqrt-iter guess ) (if (good-enough? guess ) guess (sqrt-iter (improve guess) ))) (sqrt-iter 1.0 ))

Definizioni interne e struttura a blocchi

x

x

x x

x x

x

x

x x

x x

x

x

x x

x x

Carlo Strapparava - Informatica

Definizioni interne e struttura a blocchi

Lexical scoping: le variabili libere in unaprocedura si riferiscono a bindings (= legami)fatti nelle definizioni delle procedure che leincludono

6

Carlo Strapparava - Informatica

Riepilogo

Finora abbiamo considerato alcuni elementi dellaprogrammazione Operazioni aritmetiche primitive Espressioni composte con queste operazioni Astrazioni di queste espressioni composte tramite la

definizione di procedure

Carlo Strapparava - Informatica

Procedure e processi che esse generano

Sapere le regole degli scacchi non implica ilsapere giocare a scacchi

Occorre avere: Conoscenza di quali mosse vale la pena di fare

(=> quali procedure vale la pena definire) Esperienza per prevedere le conseguenze di una mossa

(=> quali sono le conseguenze dell’esecuzione di unaprocedura)

7

Carlo Strapparava - Informatica

Procedure e processi che esse generano

Dobbiamo essere in grado di visualizzare iprocessi generati da un programma e

Capire quante risorse computazionali (tempoe spazio) consumano i vari tipi di processi

Ci sono alcune “pattern” di processo chebisogna conoscere

Carlo Strapparava - Informatica

Ricorsione lineare e Iterazione lineare

Consideriamo la funzione fattoriale

n! = n ! (n "1) ! (n " 2) ! … ! 3 ! 2 ! 1

0!= 1n!= n ! (n "1)!# $ %

Definizione per ricorrenza (usa il principio di induzione come linea guida)

8

Carlo Strapparava - Informatica

Fattoriale di N

Un modo per calcolare il fattoriale è quello diutilizzare la definizione per ricorrenza

(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))

Carlo Strapparava - Informatica

Fattoriale di N (cont.)(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))

Possiamo usare il modello di sostituzione e vedere questa procedura in azioneProviamo a calcolare 5!

(fact 5)(* 5 (fact 4))(* 5 (* 4 (fact 3)))(* 5 (* 4 (* 3 (fact 2))))(* 5 (* 4 (* 3 (* 2 (fact 1)))))(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))(* 5 (* 4 (* 3 (* 2 (* 1 1)))))(* 5 (* 4 (* 3 (* 2 1))))(* 5 (* 4 (* 3 2)))(* 5 (* 4 6))(* 5 24)120

9

Carlo Strapparava - Informatica

Fattoriale di N (cont.)

Guardiamo al calcolo del fattoriale da unaprospettiva diversa

((1! 2)prodotto! " # ! 3)

prodotto! " $ # $

! 4 !…! N

prodotto! contatore " prodottocontatore ! contatore +1

N! è il valore del prodotto quando il contatore è maggiore di N

Carlo Strapparava - Informatica

Fattoriale di N (cont.)

Possiamo riscrivere la procedura per calcolare ilfattoriale

(define (fact n) (fact-iter 1 1 n))

(define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))

Esercizio: Riscrivere il tutto usando la struttura a blocchi (semplificando)

10

Carlo Strapparava - Informatica

Fattoriale di N (cont.)

Possiamo usare il modello di sostituzione e calcolare 5!

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

(define (fact n) (fact-iter 1 1 n))

(define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))

Carlo Strapparava - Informatica

Processo Ricorsivo e Processo Iterativo

Tutti e due i processi richiedono un numero di passi proporzionale a N(i.e. lineare rispetto a N)

Il primo costruisce una catena di operazioni differite (le moltiplicazioni)=> è un processo ricorsivo

Il secondo non cresce né si contrae => è un processo iterativo Un processo iterativo può essere “descritto” dalle sue variabili di stato

(nel nostro caso product, counter, max-count)

(fact 5)(fact-iter 1 1 5)

(fact-iter 1 2 5)(fact-iter 2 3 5)(fact-iter 6 4 5)

(fact-iter 24 5 5)(fact-iter 120 6 5)120

(fact 5)(* 5 (fact 4))(* 5 (* 4 (fact 3)))(* 5 (* 4 (* 3 (fact 2))))(* 5 (* 4 (* 3 (* 2 (fact 1)))))(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))(* 5 (* 4 (* 3 (* 2 (* 1 1)))))(* 5 (* 4 (* 3 (* 2 1))))(* 5 (* 4 (* 3 2)))(* 5 (* 4 6))(* 5 24)120

11

Carlo Strapparava - Informatica

Processo Ricorsivo vs. Procedura Ricorsiva

Processo ricorsivo: processo caratterizzato dauna catena di operazioni differite

Procedura ricorsiva: una procedura che“sintatticamente” si riferisce a se stessa

Carlo Strapparava - Informatica

Linguaggi di prg. e Tail-Recursion

Purtroppo nella maggior parte dei ling. di prg. (inclusiAda, C, Pascal) tutte le procedure sintatticamentericorsive generano processi ricorsivi, anche se ilprocesso generato è in principio iterativo.

Come conseguenza questi linguaggi devono ricorrerea speciali costrutti iterativi (do, repeat, for, while, …)

Lo Scheme non ha questo difetto: ha la proprietà ditail-recursion

Un linguaggio tail-recursive non ha bisogno di syntactic-sugar per l’iterazione=>

12

Carlo Strapparava - Informatica

Esercizio: ricorsivo o iterativo ?

Per ognuna delle seguenti procedure dire che tipodi processo genera (i.e. ricorsivo o iterativo)

(define (my+ a b) (if (= a 0) b (inc (my+ (dec a) b))))

(define (my+ a b) (if (= a 0) b (my+ (dec a) (inc b))))

Sono supposte già definite le funzioni inc e dec che rispettivamenteincrementano e decrementano il loro argomento di 1