Teaching



Appunti a.a. 2005/2006


Il presente file è destinato agli studenti/studentesse del corso di Informatica Applicata per la Didattica, Facoltà di Scienze della Formazione Primaria dell'Università di Udine. In particolare, questi appunti sono rivolti a quella categoria di studenti che non ha la possibilità di frequentare il corso e ritiene di avere lacune nella preparazione matematica. Per questo fine, l'esposizione è sviluppata in modo dettagliato e progressivo, con corredo di numerosi esempi e indulgendo talora in dettagli e/o spiegazioni probabilmente scontati. Il file è “self-contained”, ossia non presuppone, per essere compreso, che conoscenze di matematica elementare. L'obbiettivo è arrivare a scrivere programmi nel linguaggio di programmazione Scheme che consentano di risolvere semplici problemi nei campi dell'aritmetica e dell'algebra. Ai lettori con esigenze di più ampio spettro e desiderio di approfondimento, va detto che il materiale introdotto non è assolutamente esaustivo, limitandosi ad essere funzionale ai problemi che vengono trattati. Inoltre, in quanto non di immediato impatto da un punto di vista “pratico”, vengono tralasciate tutte le spiegazioni di natura teorica, rimandando il lettore interessato ai testi specifici sull'argomento. Di tanto in tanto compariranno brevi commenti sull'utilizzo dell'applicazione DrScheme. Non tutto il programma del corso è coperto, pertanto è necessaria una integrazione con altro materiale (testi segnalati, appunti del corso). Gli studenti possono chiedere chiarimenti sugli argomenti qua trattati, e sono invitati a proporre suggerimenti/modifiche e correggere gli errori che inevitabilmente farò: sarò lieto di soddisfare, nei limiti del possibile, le richieste che riceverò (all'indirizzo alessi@dimi.uniud.it).


ATTENZIONE: su alcuni monitor non appare una chiara discriminazione degli spazi fra caratteri. Quanto segue è un piccolo test per verificare se riuscite a discernere correttamente l'inserzione di spazi fra caratteri. Osservate la riga sottostante:

(<r 23)       (< r23)       (<r 2 3)       (<r23)       (< r 23)      

Si danno due casi:

Sulle espressioni aritmetiche in Scheme

Le operazioni aritmetiche in Scheme che verranno prevalentemente impiegate sono le seguenti: Queste operazioni, quando gli argomenti sono numeri interi, restituiscono come risultato ancora numeri interi. Altre operazioni utilizzate (il cui risultato può non essere intero) sono:
Riguardo alla doppia possibilità di usare quotient o / per l'operazione di divisione, si tenga presente la distinzione fra la divisione intera (spesso indicata con il simbolo “:”) e la divisione decimale (ad esempio:   13:3 = 4; 13/3 = 4.3333...). La prima richiede due argomenti (dividendo e divisore) interi, e produce come risultato sempre un numero intero, mentre la seconda può produrre un risultato nel campo delle frazioni (o dei numeri reali, se dividendo e/o divisore sono numeri reali). Se un programma richiederà di utilizzare la divisione intera, si sceglierà la procedura quotient. (anche se, in molti casi, l'uso di / resta possibile). Programmi che invece richiedono l'uso di frazioni e/o numeri reali, faranno viceversa ricorso a / per il calcolo della divisione decimale.

Le espressioni aritmetiche, che fanno uso di tutte le operazioni sopra menzionate vengono scritte in Scheme secondo la sintassi

(<operazione>   <argomento1>   <argomento2>)

con l'eccezione della radice quadrata, che vuole un unico argomento. Si presti attenzione alla presenza delle parentesi tonde, e al fatto che l'operazione va scritta dopo l'apertura della parentesi, prima dei suoi argomenti. Si rammenta di lasciare almeno uno spazio a separare operazioni e argomenti, mentre potete scegliere a piacere se lasciare o meno spazi fra parentesi tonde aperte e operazioni, o fra parentesi tonde chiuse e argomenti.
Ecco qualche esempio: la somma 3 + 4, la differenza 10 - 8, il prodotto 5 * 4 si scrivono in Scheme rispettivamente

(+ 3 4)       (- 10 8)       (* 5 4)

Con riferimento alla spaziatura, altre possibilità di scrittura di 3 + 4 sono ad esmpio queste:

(    +     3           4)       (+ 3       4    )

ma non ad esempio

(  +3   4  )       (  + 34 )

La radice quadrata di 3 si scrive in Scheme

(sqrt 3)

Il quoziente della divisione intera e il resto della divisione intera fra 17 e 2 (risultati: 8 e 1 rispettivamente) si scrivono in Scheme come segue:

(quotient 17 2)     (remainder 17 2)

I numeri negativi     Si scrivono in Scheme facendo precedere il valore assoluto del numero dal segno -, SENZA spaziatura. Alternativamente, possono venire scritti facendo precedere il valore assoluto del numero dal segno -, CON spaziatura, il tutto racchiuso da parentesi tonde. Ad esempio la somma (-3) + (-17) può essere scritta nei seguenti due modi:

(+   -3   -17)   oppure   (+   (- 3)   (- 17))

Se una quantità algebrica è preceduta da un segno meno, si usa la seconda opzione. Ad esempio, l'espressione a + (-b) viene scritta

(+   a   (- b))


e non (+   a   -b).

Espressioni più complesse possono essere scritte annidando le traduzioni delle sottoepressioni nel rispetto della sintassi stabilita sopra, e ricordandosi di aggiungere, se occorre, opportune parentesi tonde. Nel passare dalla espressione scritta nell'usuale formato matematico alla sua traduzione in Scheme, è utile procedere passo passo, traducendo prima le sottoespressioni più semplici e via via procedendo verso quelle più complesse. Nella fase intermedia del processo di traduzione, le espressioni già tradotte in Scheme sono riconoscibili per avere l'operazione a sinistra. L'esempio successivo al seguente chiarirà quanto affermato. Ecco qualche esempio: l'espressione 3 + 4*5, viene così riscritta

(+ 3 (* 4 5))

Traduciamo ora l'espressione (4 + 2) * (2/3 + (-5/6)*7). Procediamo in più passi, a partire dalle sottoestressioni più semplici. In quanto segue sotto, la riga iniziale contiene l'espressione di partenza; la riga finale contiene l'espressione interamente tradotta in Scheme; le righe intermedie contengono espressioni spurie, parzialmente tradotte in Scheme. Si presti la massima attenzione alla priorità delle operazioni, decisiva per scrivere correttamente la traduzione in Scheme dell'espressione aritmetica

(4 + 2) * (2/3 + (-5/6)*7)   →
(+ 4 2) * ((/ 2 3) + (/ (- 5) 6)*7)   →
(+ 4 2) * ((/ 2 3) + (* (/ (- 5) 6) 7))   →
(+ 4 2) * (+ (/ 2 3) (* (/ (- 5) 6) 7))   →
(* (+ 4 2) (+ (/ 2 3) (* (/ (- 5) 6) 7)))

Un'espressione già munita di parentesi quadre come [(5 + 4)/(6 * 7) - 8] * 17 viene comunque riscritta usando solo parentesi tonde, come segue:

(* (- (/ (+ 5 4) (* 6 7)) 8) 17)

Una utile semplificazione che si può impiegare è l'utilizzo di una unica operazione di somma o prodotto quando l'espressione da tradurre coinvolge una sola di queste operazione. Ad esempio, l'espressioni aritmetica 3 + 4 + 6 + 10, anziché venire tradotta (correttamente, comunque) come

(+ 3 (+ 4 (+ 6 10)))

può, più brevemente, essere scritta così:

(+ 3 4 6 10)

Una analoga possibilità esiste con i prodotti: (8 * 7 * 9) può essere scritto

(* 8 7 9)


Espressioni algebriche     si scrivono in modo del tutto analogo a quelle aritmetiche (attenzione, però: una espressione algebrica avrà senso solo se inserita in certi contesti, si veda il seguito). Consideriamo ad esempio la formula che dà una delle due soluzioni della equazione di secondo grado ax2 + bx + c = 0. La formula che vogliamo scrivere in Scheme è la seguente:

[-b + √(b2 - 4ac)]/(2a)

Eccone le traduzione in Scheme:

(/ (+ (- b) (sqrt (- (* b b) (* 4 a c)))) (* 2 a))


Sulle definizioni in Scheme

Le definizioni in Scheme vengono impiegate per dare nomi ad espressioni: il nome assegnato ad una data espressione nel processo di definizione è a tutti gli effetti utilizzabile al posto della espressione. Le definizioni, nell'ambiente DrScheme, vengono in genere scritte nella finestra delle definizioni (quella in alto). Per renderle operative, occorrerà poi cliccare sul tasto “Run” o “Execute” (a seconda delle versioni scaricate di DrScheme). Le espressioni a cui si decide di dare un nome possono essere di vario tipo: da oggetti semplici come i numeri a procedure/programmi etc.
Le definizioni sono introdotte dalla parola riservata “define” ed hanno la seguente sintassi:

(define   <nome>   <espressione>)

Il nome può essere scelto a piacimento e consiste in una successione di caratteri alfanumerici (ad esempio: x, y, z, a, b, c, oppure a1, a-1, a_1, a2, x_1, z3 etc, oppure lato1, lato_2, raggio, altezza, etc etc: si veda il seguito). In genere è buona norma usare nomi che siano espressivi del significato della espressioni a cui sono associati.

Esempio 1: Un euro vale 1936.27 lire. Al fine di utilizzare tale fattore di conversione senza dovere ricordare a memoria il numero, possiamo introdurre una definizione per tale costante numerica. Dobbiamo solo scegliere un nome appropriato, come ad esempio: fattore_conversione. La definizione sarà pertanto:

(define fattore_conversione 1936.27)

Una volta scritta questa definizione, il nome “fattore_conversione” resterà associato al numero 1936.27 e potrà essere utilizzato in sua vece. Ad esempio, potremo creare l'espressione aritmetica (* 2 fattore_conversione) che, una volta calcolata, darà come risultato 3872.54.

Esempio 2: una costante della massima importanza in geometria è π, ossia Pi greco, il cui valore approssimato è 3.14. Un valore molto più preciso si può ottenere utilizzando la funzione predefinita acos (arcoseno), calcolando l'arcoseno di -1: ossia, π = acos(-1). Tradotto in Scheme, acos(-1) viene scritto (acos -1) oppure (acos (- 1)). A questo punto possiamo senz'altro passare alla definizione di π, stabilendo per esso il nome “pigreco” (e non “pi greco”: gli spazi fra le lettere del nome non sono ammessi; viceversa la scelta del nome “pi_greco” è altrettanto buona).

(define pigreco (acos -1))

Come nell'esempio precedente, il nome “pigreco” è ora associato al valore di π. Ad esempio, ricordando che πR2 è la formula per il calcolo dell'area di un cerchio (dove R è il raggio del cerchio), l'espressione


calcolerà l'area di un cerchio di raggio 3.
Naturalmente più nomi (precedentemente introdotti in qualche definizione) possono comparire all'interno di una espressione. Ad esempio

(- fattore_conversione pigreco)

calcolerà la differenza (probabilmente di nessuna utilità!) fra 1936.27 e π.


Primi programmi in Scheme

Scrivere programmi in Scheme è relativamente semplice. Da un punto di vista concettuale si richiede poco più che la comprensione del processo definitorio di una usuale funzione matematica.
Partiamo da un esempio: si consideri la funzione

f(x) = 3x - 4

definita sui numeri interi. In questa definizione distinguiamo: La definizione di f sottintende il seguente uso: a f viene passato, di volta in volta, un argomento differente, che verrà sostituito a x, dopo di che si svolgeranno le operazioni prescritte nel secondo membro dell'uguaglianza. Così, ad esempio, calcolare f applicata all'argomento 5, in formule f(5), significa sostituire al posto della x, il valore 5 nella espressione 3x - 4, ottenendo 3*5 - 4, quindi 11 come risultato finale. Similmente f(7) darà 17 come risultato e così via.
Un secondo esempio, che coinvolge un numero maggiore di parametri, è la funzione che esprime il volume di un cilindro in funzione del raggio e dell'altezza del cilindro stesso (rammentiamo la formula: volume del cilindro = π*raggio2*altezza). Se usiamo il nome “rag” per il raggio del cilindro e il nome “alt” per l'altezza, e chiamiamo volume_cilindro la funzione, perverremo a questa definizione

volume_cilindro(rag, alt) = π*rag2*alt

Naturalmente c'è un ampio margine di scelta per quanto riguarda i nomi della funzione e dei parametri: saremmo pervenuti ad una definizione del tutto equivalente a quella data scrivendo ad esempio:

g(a, b) = π*a2*b

avendo convenuto di chiamare “g” la funzione volume, e “a”, “b”, rispettivamente il raggio e l'altezza del cilindro. I nomi scelti nella prima definizione (volume_cilindro, rag, alt) sono più scomodi, in quanto più lunghi, ma anche più espressivi del ruolo giocato dalle quantità coinvolte, e più in linea con le esigenze della programmazione, dove spesso, stante la lunghezza del codice scritto, è utile avere nomi che richiamano il ruolo svolto dalle quantità associate ai nomi stessi.
Nel caso della funzione volume_cilindro, il processo di sostituzione degli argomenti ai parametri avviene in modo ordinato: se noi applichiamo la funzione ai valori 4 e 6 nell'ordine, ossia calcoliamo volume_cilindro(4,6), il numero 4 verrà sostituito a rag e il numero 6 a alt, ottenendo come risultato approssimato 301.59. Calcolare volume_cilindro(6,4) significa viceversa sostiuire 6 al posto di rag, 4 al posto di alt, ottenendo un risultato differente, 452.38 circa.

La scrittura di un programma in Scheme richiede un processo molto simile a quello visto sopra messo in atto per definire le funzioni: i passi sono essenzialmente tre, di cui i primi due semplici, l'ultimo a volte complesso:
  1. stabilire il nome da assegnare al programma;
  2. stabilire quali sono i parametri coinvolti e quali nomi assegnare ad essi;
  3. scrivere il corpo della procedura, che consiste nell'espressione che si dovrà valutare per pervenire al risultato desiderato
Di fatto il secondo e il terzo passo sono associati, e concorrono alla definizione della procedura (che quindi conterrà la lista dei parametri e il corpo, secondo e terzo punto sopra).
Il punto 1 sopra viene assolto dal meccanismo di definizione che abbiamo visto: per definire un programma inizieremo con

(define   <nome_scelto>   <procedura>)

Supponiamo, per fissare le idee, di volere scrivere un programma che calcola l'area di un rettangolo, a partire dalla conoscenza dei due lati, che chiameremo lato1 e lato2. Sembra ragionevole chiamare questo programma area_rettangolo. L'inizio della definizione del nostro programma sarà in questo caso

(define area_rettangolo .......)

Ora occorre riempire lo spazio occupato dai puntini con la scrittura della procedura opportuna.
Come detto, la procedura contiene, nell'ordine, la lista dei parametri impiegati e il corpo, ossia l'espressione che permette di pervenire al risultato.
La sintassi per scrivere una procedura impiega una parola riservata, “lambda”; a seguire, la lista, fra parentesi tonde, dei parametri (si ricordi: i parametri vanno spaziati e NON è ammesso separarli mediante virgole!) e successivamente il corpo della procedura. Ecco la sintassi:

(lambda   (<parametro_1> ... <parametro_n>)   <corpo della procedura> )

Un commento sul modo di distribuire la scrittura. È diffuso l'uso di scrivere sulla stessa riga, “lambda” e la lista dei parametri, mentre il corpo della procedura (che molto spesso, come si vedrà, consiste di una lunga espressione racchiusa fra parentesi tonde) viene scritto andando a capo (e occupando le righe del caso). Ci atteniamo a questo sistema di scrittura che risulta piuttosto comodo per una agevole lettura di programmi/procedure.
Tornando al nostro programma area_rettangolo, la procedura la scriveremo fissando i parametri (possiamo chiamarli come sopra: lato1 e lato2) e scrivendo successivamente il corpo. Come detto, il corpo deve racchiudere l'espressione che consente di pervenire al risultato. Nel caso del nostro esempio, l'area del rettangolo si calcola secondo la notissima formula (scritta nell'usuale linguaggio matematico, scegliendo i nomi come sopra):

area_rettangolo(lato1, lato2) = lato1*lato2

Il secondo membro dell'uguaglianza è la formula che ci interessa e che traduciamo immediatamente in Scheme:

(* lato1 lato2)

Quanto scritto sopra costituisce il corpo della procedura. Ecco pertanto la procedura completa:

(lambda   (lato1 lato2)
    (* lato1 lato2) )

(Si osservino le parentesi: fra gli errori più comuni c'è un improprio uso di esse!). Ed ecco ora la definizione del programma completo:

    (define area_rettangolo
      (lambda   (lato1 lato2)
        (* lato1 lato2) ) )


Questo programma si presta ad essere applicato a qualunque coppia di argomenti numerici. Per testare il programma nell'ambiente DrScheme, scriviamo ad esempio nella finestra delle interazioni (Interaction Window: quella in basso)

(area_rettangolo 6 4)

Dopo avere premuto il tasto INVIO, comparirà il risultato, 24. Similmente scrivendo nella Interaction Window

(area_rettangolo 5 9)

e premendo INVIO, comparirà 45, e così via.


Esercizio 2.1: Scrivere un programma che calcola l'area del quadrato a partire dal lato L.

Sol.   Si può procede come nel caso precedente. Diamo per prima cosa un nome al programma, scegliamo in questo caso il nome inglese “square” (quadrato). Il parametro coinvolto è uno, la misura del lato, che possiamo indicare con L come nel testo dell'esercizio. Infine, il corpo della procedura deve contenere la formula che permette di calcoloare l'area del quadrato, ossia (* L L). Ecco il programma completo:

    (define square
      (lambda   (L)
        (* L L) ) )


Esercizio 2.2: Scrivere un programma che calcola il cubo di un numero.

Sol.   Pochi commenti da fare rispetto all'esercizio precedente. Potremmo chiamare “cubo” il programma, “numero” il nome assegnato al parametro. La formula da inserire nel corpo della procedura è in questo caso (* numero numero numero). Ricordiamo ancora che i nomi dati al programma ed ai parametri sono scelti a piacere. Ecco il programma completo:

    (define cubo
      (lambda   (numero)
        (* numero numero numero) ) )


Esercizio 2.3: Scrivere un programma che calcola il perimetro di un triangolo, a partire dalla misura dei lati.

Sol.   Sinteticamente: Programma completo:

    (define perimetro_triangolo
      (lambda   (lato1 lato2 lato3)
        (+ lato1 lato2 lato3) ) )

Prima di proseguire vediamo un esempio di errata stesura del programma precedente. Provate, prima di leggere i commenti, ad individuare gli errori fatti.

    (define perimetro_triangolo)
      (lambda   (lato1, lato2, lato3)
        (+ a lato2 lato3) ) )

Gli errori sono i seguenti: si chiude impropriamente una parentesi tonda dopo il nome dato al programma (prima riga), nella parentesi dedicata ai parametri, questi sono separati dalle virgole (seconda riga), infine, nel corpo della procedura, compare un parametro “a” che non è stato precedentemente introdotto.


Esercizio 2.4: Scrivere un programma che calcola l'area di un triangolo, conoscendo base e altezza.

Sol.   Programma completo:

    (define area_triangolo
      (lambda   (base altezza)
        (/ (* base altezza) 2) ) )


Esercizio 2.5: Scrivere un programma che calcola l'area di un trapezio, conoscendo la base maggiore, la base minore e l'altezza (la formula è: (somma delle basi * altezza) diviso 2)

Sol.   Programma completo:

    (define area_trapezio
      (lambda   (BASE base altezza)
        (/ (* (+ BASE base) altezza) 2) ) )


Esercizio 2.6: Scrivere un programma che calcola l'area del cerchio a partire dal raggio R (la formula è area = πR2).

Sol.   Questo programma presuppone la definizione di una costante che racchiuda una approssimazione del valore di π. Questo passo è già stato spiegato in una sezione precedente, ma lo riportiamo comunque sotto per comodità del lettore, con una piccola variazione: sceglieremo, per l'approssimazione di π, il nome “pi_greco” (invece di “pigreco”). Ecco il programma, preceduto dalla definizione relativa a π:

    (define pi_greco (acos -1))

    (define area_cerchio
      (lambda   (R)
        (* pi_greco R R) ) )


Esercizio 2.7 Scrivere un programma che prende come argomento un prezzo in euro e lo converte in lire.

Sol.   Procediamo come nel precedente esercizio. Avevamo in altra sezione introdotto il fattore di conversione euro-lire, attraverso la definizione

    (define fattore_conversione 1936.27)

Utilizzeremo questa definizione nella stesura del programma. Ecco il programma completo:

    (define converti_euro->lire
      (lambda (prezzo)
        (* prezzo fattore_conversione) ) )


Esercizio 2.8: Nel paese X i redditi vengono tutti tassati del 8%. Scrivere un programma che, dati i redditi lordi, calcola i redditi al netto della tassa.

Sol.   Chiamiamo “r” il reddito lordo. Per calcolare il reddito al netto della tassa, dovremo sottrarre a r l'8% di r stesso, secondo la formula:

reddito_netto = r - (8/100)r

La traduzione in Scheme della espressione sopra costituirà il corpo della procedura. Ecco il programma completo

    (define calcola_tassa
      (lambda (r)
        (- r (* (/ 8 100) r )) ) )


Verso programmi più complessi


Programmi che contengono programmi     È possibile e sovente utile richiamare programmi già scritti all'interno dei programmi che stiamo scrivendo. Questa possibilità è illustrata nel prossimo esercizio.


Esercizio 3.1: Si hanno un triangolo di base b1 e altezza h1, un trapezio di base maggiore B2, base minore b2 e altezza h2, e infine un cerchio di raggio R. Scrivere un programma che calcola l'area complessiva occupata dalle tre figure.

Sol.   Se, nella finestra delle definizioni di DrScheme, abbiamo già a disposizione i programmi precedenti “area_triangolo” “area_trapezio” e “area_cerchio”, (unitamente alla definizione di π), possiamo abbreviare la scrittura del nostro programma, utilizzando al suo interno i suddetti programmi, e facendo quindi uno sforzo di elaborazione minore, in quanto non dovremo calcolare la formula dettagliata che somma le varie aree (vedi sotto). Infatti l'area del triangolo la potremo calcolare scrivendo (area_triangolo b1 h1), quella del trapezio scrivendo (area_trapezio B2 b2 h2) e l'area del cerchio scrivendo (area_cerchio R). Si dovrà poi sommare queste aree. Procediamo: Il corpo dalla procedura, costituito da una espressione abbastanza lunga, verrà spezzato su tre righe, in modo da rendere agevole la lettura del programma. Ecco il programma completo:

    (define calcola_somma_aree
      (lambda (b1 h1 B2 b2 h2 R)
        (+ (area_triangolo b1 h1)
              (area_trapezio B2 b2 h2)
              (area_cerchio R) )))

Una breve parentesi: come dovrebbe essere ormai chiaro, se nella Interaction Window scriviamo l'espressione

(calcola_somma_aree 6 4 8 5 3 9)

e premiamo INVIO, otterremo l'area complessiva ottenuta sommando le aree di un triangolo di base 6 e altezza 4, di un trapezio di base maggiore 8, base minore 5 e altezza 3, e di un cerchio di raggio 9.
Torniamo al discorso principale sui programmi contenenti altri programmi. Se, a differnza di quanto visto sopra, non avessimo a disposizione o non volessimo usare i 3 sottoprogrammi, saremmo costretti a scrivere un programma più lungo. A parte questo difetto, che può essere in certi casi marginale, è la comprensione del corpo della procedura che viene inficiata (quasi sempre). Ecco il programama riscritto non facendo uso dei 3 sottoprogrammi:

    (define calcola_somma_aree2
      (lambda (b1 h1 B2 b2 h2 R)
        (+ (/ (* b1 h1) 2) (/ (* (+ B2 b2) h) 2) (* (acos -1) R R))))

Potremmo forse migliorare la comprensione del corpo della procedura spezzando su più righe la sua scrittura, ma in ogni caso si otterrebbe una espressione più oscura rispetto a quella del programma precedente.


Test ed espressioni condizionali     Oltre ai numeri (interi, reali, complessi), un altro tipo di dato è costituito dai valori booleani, true (vero) e false (falso), che in Scheme vengono talora scritti rispettivamente come #t e #f. Chiameremo test una qualunque espressione il cui processo di valutazione condurrà ad un valore booleano. Semplificando (e banalizzando) il discorso, i test sono espressioni che presuppongono una domanda evidenziata dalla presenza di un operatore di confronto. Iniziamo a presentare i test fra numeri. Gli operatori di confronto che useremo sono i seguenti: I test vengono scritti, come d'uso per le espressioni in Scheme, ponendo in testa alla espressione l'operatore di confronto. Ad esempio, i test x = 2, (1+4) >= (2+8), 4 < 30/7, vengono scritti in Scheme rispettivamente come segue:

(=   x   2)     (>=   (+ 1 4)   (+ 2 8))     (<   4   (/ 30 7))

I test precedenti sono destinati a dare come risultato true oppure false. Sul primo test non possiamo dire nulla (è un test il cui esito dipende dal valore del parametro x: test di questo tipo compariranno molto spesso nel corpo di procedure). Del secondo e terzo test possiamo invece scrivere il risultato finale: false per il secondo test, true per il terzo. A questi risultati si perviene anche scrivendo i due test nella Interaction Window di DrScheme e premendo INVIO. Scrivere invece il primo test, isolato, nella Interaction Window (e non all'interno di una procedura) produrrà probabilmente un messaggio di errore simile al seguente: “ ...x unundefined identifier...”, indicativo del fatto che il nome x non è stato precedentemente introdotto e quindi è impossibile darne una valutazione.

I test possono essere fra loro combinati attraverso i connettivi logici: La congiunzione “and” può essere applicata ad un numero arbitrario di test, secondo la sintassi

(and   <test-1>   <test-2> ...   <test-n>)

e produce true come risultato se e solo se TUTTI i test a cui viene applicata danno, ciascuno, true come risultato, altrimenti il risultato è false. Ad esempio, il test

(and   (< 1 (+ -1 3))   (= 5 (sqrt 25))   (>= 100 (* 9 9)) )

dà risultato true, poiché tutti e 3 i test interni sono veri. Viceversa, il test

(and   (< 0 2)   (= 7 (/ 72 8)) )

dà risultato false, poiché il secondo test interno dà false come risposta.


La disgiunzione “or” è anch'essa applicabile ad un numero arbitratio di test, secondo la sintassi

(or   <test-1>   <test-2> ...   <test-n>)

e produce come risultato true se e solo se ALMENO un test a cui viene applicata dà true come risultato, altrimenti il risutlato è false. Ad esempio, il test

(or   (> 1 (+ -1 3))   (= 5 (sqrt 26))   (>= 100 (* 9 9)) )

dà true come risultato, poiché l'ultimo test ha come risultato true, e questo basta per concludere che true è il risultato del test complessivo. Viceversa, il test

(and   (>= 0 2)   (= 7 (/ 72 8)) )   (< 20 (* 4 4) )   (< 0 (- 1 1)) )

dà risultato false, poiché tutti i test interni danno false come risultato.


La negazione “not” si applica ad un unico argomento, secondo la sintassi

(not   <test>)

e produce come risultato il valore opposto al valore di verità del test a cui è applicata. Ad esempio, i seguenti test

(not (< 0 4) )     (not (and (< 5 3) (> 8 (+ 1 7)) ) )

producono rispettivamente false e true come risposta. Nel primo test, dopo il “not” segue un test vero, per cui la risposta complessiva sarà false. Nel secondo test, la congiunzione interna è resa falsa dalla presenza del test falso (> 8 (+ 1 7)); pertanto il valore complessivo dell'espressione è true.


Esercizio 3.2: Scrivere un programma “pari?” che seleziona i numeri pari: risponde true se un intero n è pari, false altrimenti.

Sol.   Da pari? ci aspettiamo il seguente comportamento:

(pari? 14)   →   true
(pari? 22)   →   true
(pari? 19)   →   false

Il programma pari? si basa su un test che farà uso del parametro n. Il test deputato a stabilire se n è pari o dispari è

(= 0 (remainder n 2) )

(un numero è pari se e solo se dà resto 0 quando è diviso per 2). Ecco i dati relativi al nostro programma: Pertanto il programma completo ha questo codice:

    (define pari?
      (lambda (n)
        (= 0 (remainder n 2) ) ))


Esercizio 3.3: Scrivere un programma p_divide_n? che, presi come argomenti due interi n e p, stabilisce se n è divisibile per p.

Sol.   Questo esercizio è molto simile al precedente. Passiamo direttamente alla soluzione senza commenti: Pertanto il programma completo ha questo codice:

    (define p_divide_n?
      (lambda (n p)
        (= 0 (remainder n p) ) ))

Ecco qualche esempio di sua applicazione:

(p_divide_n? 10 5)   →   true
(p_divide_n? 11 4)   →   false
(p_divide_n? 42 7)   →   true


Esercizio 3.4 Scrivere un programma PROG che seleziona tutti i numeri divisibili per 7 compresi nell'intervallo [0,50] (estremi compresi).

Sol.   Esempi di applicazione:

(PROG 14)   →   true
(PROG 23)   →   false
(PROG 70)   →   false

Il test su cui PROG si basa è composto da 3 sottotest a cui si applica la congiunzione. Infatti un numero n supera il test del programma se e solo se Le traduzioni in Scheme dei tre sottotest sono rispettivamente:

(<= n 50)
(>= n 0)
(= 0 (remainder n 7) )

Pertanto il test utilizzato dal programma è

(and   (<= n 50)   (>= n 0)   (= 0 (remainder n 7)) )

Ecco quindi il programma completo:

    (define PR0G
      (lambda (n)
        (and (<= n 50)
                (>= n 0)
                (= 0 (remainder n 7)) ) ) )

Esercizio 3.5: Sia A un insieme di numeri interi così definito: un numero n appartiene ad A se è pari e compreso nell'intervallo [40,100] (estremi compresi) oppure se è maggiore di 1000. Scrivere un programma che risponde true se n appartiene ad A, altrimenti risponde false.

Sol.   A l'insieme (infinito) dei numeri selezionati è:

A = {40, 42, 44, .... ,96, 98, 100, 1001, 1002, 1003, 1004 ....}

Dal programma cercato, che chiameremo “Seleziona_A”, ci aspettiamo, ad esempio, il comportamento seguente:

(seleziona_A 52)   →   true
(seleziona_A 104)   →   false
(seleziona_A 3000)   →   true

Il programma Seleziona_A si basa su un test che farà uso del parametro n e che stabilirà, rispondendo true o false, se n appartiene o meno ad A. Per questo fine notiamo che A è definito attraverso una disgiunzione (numeri pari dell'intervallo [40,100], oppure numeri maggiori di 1000). Per quanto riguarda i numeri n maggiori di 1000, questi vengono selezionati dal test

(> n 1000)

Chiamiamo, per il momento, T1 il test che seleziona i numeri pari dell'intervallo [40,100]. Possiamo pertanto scrivere una prima approssimazione del test finale che verrà usato dal programma:

(or   T1   (> n 1000) )

Dobbiamo ora scrivere esplicitamente T1. T1 deve selezionare gli interi n tali che: T1 è quindi composto da una congiunzione dei tre sottotest scritti sopra. Le traduzioni in Scheme dei tre sottotest sono rispettivamente: Possiamo a questo punto scrivere T1:

(and   (<= n 100)   (>= n 40)   (= 0 (remainder n 2)) )

Siamo ora in grado di scrivere il test completo del nostro programma:

(or (and (<= n 100) (>= n 40) (= 0 (remainder n 2)) )   (> n 1000) )

La riga scritta sopra (che nella stesura del programma spezzeremo per comodità di lettura in più righe, incolonnando opportunamente i test) costituirà il corpo della procedura del programma. Ecco il programma completo:

    (define seleziona_A
      (lambda (n)
        (or (and   (<= n 100)
                        (>= n 40)
                        (= 0 (remainder n 2)) )
              (> n 1000) )))


Esercizio 3.6: Scrivere un programma che seleziona tutti i numeri dell'insieme B, definito come il complementare dell'insieme A dell'esercizio precedente (ossia: a B appartengono tutti e soli i numeri che non appartengono ad A).

Sol.   Possiamo scrivere l'insieme B come segue (anche se non è rilevante ai fini della soluzione dell'esercizio):

B = {..... -10, -9, -8, .... , 37, 38, 39, 41, 43, 45, 47, .... 95, 97, 99, 101, 102, 103, 104, .... , 997, 998, 999, 1000}

La soluzione dell'esercizio è molto semplice, avendo a disposizione il programma dell'esercizio precedente. È infatti sufficiente prendere il test di Seleziona_A e farne la negazione. Il nuovo test darà come risposte valori di verità opposti al test precedente: false, se n appartiene ad A (ossia se n non appartiene a B); true, se n non appartiene ad A (ossia se n appartiene a B). Il programma completo è pertanto:

    (define seleziona_B
      (lambda (n)
        (not (or (and (<= n 100)
                              (>= n 40)
                              (= 0 (remainder n 2)) )
                     (> n 1000) ))))


Avendo a disposizione seleziona_A, possiamo naturalmente abbreviare il codice di seleziona_B:

    (define seleziona_B
      (lambda (n)
        (not (seleziona_A   n))))


Espressioni condizionali     Le espressioni condizionali, nel contesto di altri linguaggi di programmazione chiamate talvolta espressioni “if-then-else”, danno la possibilità di operare delle scelte. In Scheme sono possibili due tipi differenti di sintassi per le espressioni condizionali. Ci soffermeremo solo su una di queste, la sintassi delle cosiddette “espressioni-cond”. Le espressioni-cond consistono di una serie di test e di conseguenze (una per ciascun test), e di una alternativa finale. La sintassi è la seguente:

(cond   (<test_1>   <conseguenza_1>)
            (<test_2>   <conseguenza_2>)
            .....
            (<test_n>   <conseguenza_n>)
        (else   <alternativa_finale>) )

La valutazione dell'intera espressione avviene come segue: viene prima valutato il primo test, <test_1>: se questo è vero, si valuta <conseguenza_1>, mentre tutto il resto della espressione non viene considerato. Se invece <test_1> è falso, si passa a valutare <test_2>: se questo è vero, si valuta la sua conseguenza <conseguenza_2>, e le righe successive dell'espressione-cond non vengono considerate. Se anche <test_2> dà false come risultato, si passa al test successivo, e così via, fino a che non si trova il primo test che dà esito true, che consentirà di valutare la relativa conseguenza. Se, cosa possibile, nessun test dà esito true, si passerà a valutare l'alternativa finale, scritta nell'ultima riga della espressione e preceduta dalla parola chiave “else”.


Esercizio 3.7: Scrivere un programma “quoto_2” che, applicato ad un intero n, scrive il quoto della divisione di n con 2, nel caso in cui n sia pari. Se invece n è dispari, il programma restituisce il quoto della divisione di n+1 con 2 (ricordiamo che si ha quoto in una divisione intera, quando il resto della divisione è 0, altrimenti il risultato viene chiamato quoziente; la procedura utilizzata per calcolare quoto o quoziente, come noto, è “remainder”).

Sol.   Il corpo della procedura è costituito da una espressione condizionale che fa uso di un unico test (con relativa alternativa). Ecco il programma completo:

    (define quoto_2
      (lambda (n)
        (cond ((= 0 (remainder n 2)) (quotient n 2) )
                  (else (quotient (+ n 1) 2)) ) ))


Esercizio 3.8: Nel paese X è entrato in vigore un nuovo regime di tassazione: un reddito viene tassato del 8% se è uguale o superiore ai 50000 euro. Se invece è inferiore, subisce una tassazione del 3%.

Sol.   Questo esercizio è simile all'Esercizio 8, con la complicazione di dovere operare una scelta a seconda che il reddito sia inferiore o meno ai 50000 euro. Se chiamiamo r il reddito da tassare, avremo due formule differenti, a seconda di dove si situa il reddito. Se r < 50000, calcoleremo il reddito netto con la formula (in Scheme)

(- r (* (/ 3 100) r))

Altrimenti, se r>= 50000, calcoleremo il reddito netto con la formula

(- r (* (/ 8 100) r))

Ecco l'espressione condizionale che utilizzeremo:

(cond     ( (< r 50000)   (- r (* (/ 3 100) r)) )
( else   (- r (* (/ 8 100) r)) )

Chiamiamo il programma finale tassa_2. Ecco il codice:

    (define tassa_2
      (lambda (r)
        (cond ((< r 50000)   (- r (* (/ 3 100) r)) )
                  (else (- r (* (/ 8 100) r)) ))))


Esercizio 3.9: (variazione dell'esercizio precedente) Nel paese X viene proposta una modifica al regime di tassazione secondo il seguente schema: Scrivere un programma che, dato un reddito lordo, calcola il reddito netto.

Sol.   Siccome il calcolo del reddito netto, in tutti i casi, fa uso della stessa formula, (cambia solo la tassa applicata), potremmo preliminarmente scrivere un programma ausiliario “applica_tassa” che, presi come argomento un reddito lordo r e una tassa percentuale t, applica la tassa t ad r e calcola il reddito netto. La formula per il calcolo del reddito netto è

reddito_netto = r - (t/100)*r

Ecco il codice di questo programma:

    (define applica_tassa
      (lambda (r t)
        (- r (* (/ t 100) r))))

Ciò che ora faremo è tradurre in Scheme, attraverso una espressione-cond, la tabella di tassazione. Nello scrivere i test, terremo conto del fatto che, per passare a valutare un test successivo, è necessario che il test precedente non sia stato superato. Ad esempio, quando scriveremo il secondo test (reddito compreso fra 100000 e 199999 euro) non servirà chiedere se r è maggiore o uguale di 100000: se si arriva al secondo test, vuol dire che il primo ha già dato esito false, per cui sarà necessariamente r >= 100000. Ecco la traduzione della tabella (si noti il richiamo ad applica_tassa)

(cond ( (< r 100000) (applica_tassa r 3) )
          ( (< r 200000) (applica_tassa r 8) )
            ( (< r 300000) (applica_tassa r 13) )
            ( (< r 400000) (applica_tassa r 18) )
( else (applica_tassa r 23) ) )

Chiamiamo tassa_3 il programma finale. Eccone il codice:

    (define tassa_3
      (lambda (r)
        (cond ((< r 100000) (applica_tassa r 3) )
                  ((< r 200000) (applica_tassa r 8))
                  ((< r 300000) (applica_tassa r 13))
                  ((< r 400000) (applica_tassa r 18))
                  (else (applica_tassa r 23) ) ) ))



Programmi ricorsivi


Abbiamo visto nella precedente sezione che è possibile, all'interno di un programma, richiamare altri programmi, al fine di ottimizzare la scrittura del codice, evitare possibili errori, e rendere il programma di più agevole lettura. Una ulteriore possibilità offerta da Scheme (e da altri li nguaggi di programmazione), di grande interesse teorico, è la facoltà di richiamare ricorsivamente, all'interno di un programma, lo stesso programma che si sta definendo. Queste definizioni “circolari” richiedono particolari attenzioni, in quanto possono generare i cosiddetti “loop” infiniti. Se usate propriamente, conferiscono grande potenza espressiva al linguaggio. Le definizioni ricorsive di programmi emergono in modo naturale quando, eccezion fatta per uno o più casi base (a cui la computazione dovrà prima o poi essere ricondotta), un dato processo di computazione è scomponibile in sottoprocessi “simili” al processo stesso. Illustriamo con un esercizio questa situazione.

Esercizio 4.1: Si scriva un programma in Scheme, chiamato “fattoriale”, che, assegnato un numero intero positivo n (per il momento strettamente maggiore di 0), produce come risultato il prodotto di tutti i numeri compresi fra 1 ed n (con il nome “fatt” indicheremo la funzione matematica corrispondente: fatt(n) = 1*2*...*n).

Sol.   Dal programma fattoriale ci attendiamo ad esempio questi risultati:

(fattoriale 1)   →   1
(fattoriale 2)   →   2   (= 1*2)
(fattoriale 3)   →   6   (= 1*2*3)
(fattoriale 4)   →   24   (= 1*2*3*4) etc

Ragionando sul processo di calcolo che consente di calcolare la funzione fattoriale di un qualunque numero n, osserviamo che Ad esempio:

fatt(2) = 1*2 = fatt(1)*2
fatt(3) = 1*2*3 = (1*2)*3 = fatt(2)*3
fatt(4) = 1*2*3*4 = (1*2*3)*4 = fatt(3)*4
fatt(5) = 1*2*3*4*5 = (1*2*3*4)*5 = fatt(4)*5
...etc...

In sintesi, scrivendo in Scheme caso base e formula ricorsiva, abbiamo, per la funzione fatt, il seguente schema: Si osservi che lo schema sopra contiene tutta l'informazione necessaria per il calcolo del fattoriale di un numero. La formula relativa al caso baso è esplicita: a secondo membro si trova un risultato perfettamente definito. Invece, la formula relativa al caso n>1 è implicita, poiché il secondo membro contiene nuovamente un riferimento alla funzione fatt che dobbiamo calcolare. Ciò costringe (come accade ai programmi ricorsivi di Scheme) a effettuare la cosiddetta chiamata ricorsiva quando si procede alla computazione. Lo schema che definisce la funzione fatt richiama se stesso un numero di volte sufficiente fino a raggiungere il caso base, dove, finalmente, la computazione risultante potrà essere svolta senza un ulteriore chiamata ricorsiva. Ad esemplificare quanto detto, procediamo a calcolare (fattoriale 4) utilizzando lo schema. In quanto segue sotto, solo nell'ultima riga l'espressione sarà stata resa esplicita; nelle righe precedenti si renderà necessaria la chiamata ricorsiva:

fatt(4)   =
=   fatt(3) * 4
=   (fatt(2) * 3) * 4
=   (fatt(1) * 2) * 3 * 4
=   1*2*3*4   =   24

Sintetizzando, abbiamo a disposizione due definizioni della funzione fatt, che portano a calcolare gli stessi risultati (una avvertenza: nella definizione ricorsiva abbiamo usato una notazione spuria, che mescola espressioni scritte nell'usuale formato matematico con le espressioni-cond di Scheme):

Prima definizione (esplicita):

fatt(n) = 1*2*...*n


Seconda definizione (ricorsiva):

fatt(n) =
                        (cond ((n = 1)   1)
                                                (else   fatt(n-1) * n) )


Abbiamo visto che la definizione ricorsiva, esplicitando via via le espressioni ottenute, consente di arrivare al risultato che la finizione esplicita porge immediatamente. La definizione ricorsiva ha quindi l'evidente svantaggio di essere meno immediata di quella esplicita. D'altra parte, almeno a livello di scrittura delle formule, presenta il vantaggio di coinvolgere, nella formula, UNA sola operazione di moltiplicazione, anziché parecchie (n - 1 moltiplicazioni, se l'argomento è n, nel caso della definizione esplicita). Questa economia di mezzi si riflette in programmi brevi e comprensibili, mentre lo svantaggio sopra menzionato viene totalmente mascherato dal fatto che è la macchina, e non l'uomo, deputata a esplicitare le espressioni attraverso le chiamate ricorsive (il difetto può in realtà avere conseguenze in termini di efficienza dei programmi; non tratteremo tuttavia questo argomento).
Possiamo ora scrivere il programma fattoriale completo. Il corpo della procedura consiste nella traduzione in Scheme dello schema ricorsivo riportato sopra per la funzione fatt: Ecco il programma completo:

    (define fattoriale
      (lambda (n)
        (cond (( = n 1) 1)
                  (else (* (fattoriale (- n 1)) n) )) ))


Esercizio 4.2: Si scriva un programma “pot” che, assegnate una base B ed un esponente intero positivo e, calcola la potenza Be.

Sol.   Come noto, Be corrisponde al prodotto B*B*....*B, dove i fattori B compaiono e volte (se e=0, si pone B0=1. Tuttavia, come nel caso della funzione fattoriale vista nel precedente esempio, possiamo calcolare Be in modo differente, rendendo minime le operazioni di moltiplicazione, attraverso la formula (for-pot) introdotta sotto (usiamo la notazione con formato misto matematico/espressioni-cond di Scheme):
(for-pot)         Be   =   (cond ((= e 0) 1)
                        (else   B(e-1) * B))

Testiamo la correttezza di (for-pot), provando a calcolare attraverso essa B4 e verificando che il risultato viene effettivamente B*B*B*B. Avremo:

B4   =
=   B3  *  B
=   (B2  *  B) * B
=   (B1  *  B) * B * B
=   (B0  *  B) * B * B * B
=   1*B*B*B*B
=   B*B*B*B


(for-pot), come si può osservare, è una formula ricorsiva: il calcolo della potenza, relativa all'esponente e, è ricondotto, ogniqualvolta e>0, al calcolo della potenza con esponente e-1, che a sua volta richiamerà il calcolo della potenza con esponente e-2, e così via fino a che non si arriverà ad esponente 0, che segnerà il termine della chiamata ricorsiva. Prepariamo lo schema che precede la stesura del programma. Si osservi che il corpo della procedura consiste in (for-pot) integralmente tradotta in Scheme: Ecco infine il programma:

    (define pot
      (lambda (B e)
        (cond (( = e 0) 1)
                  (else (* (pot B (- e 1)) B) )) ))


Esercizio 4.3: Indichiamo con σ(n) la somma dei numeri che vanno da 0 fino a n (esempi: σ(3) = 0 + 1 + 2 + 3 = 6; σ(0) = 0; σ(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15). Si scriva un programma ricorsivo SOMMATORIA che calcoli la funzione σ.

Sol.   Premettiamo che è possibile risolvere questo esercizio attraverso la formula

σ(n) = n*(n+1)/2

Non consideriamo tuttavia questa possibilità e procediamo a dare una soluzione ricorsiva. Osserviamo che σ(n), per n>0, è riconducibile al calcolo di σ(n-1). Abbiamo ad esempio.

σ(4)   =   0 + 1 + 2 + 3 + 4
    =   (0 + 1 + 2 + 3) + 4
    =   σ(3) + 4

In generale, vale la formula (per n>0):

σ(n)   =   &sigma(n-1) + n

La formula sopra, unitamente al caso base, σ(0) = 0, consente di scrivere il programma, che presentiamo senza ulteriori commenti:

    (define SOMMATORIA
      (lambda (n)
        (cond ((= n 0) 0)
                  (else (+ (SOMMATORIA (- n 1)) n)))))


Esercizio 4.4: Dato n>0, chiamiamo δ(n) la somma dei numeri dispari da 1 fino al più grande numero dispari minore o uguale a n (esempi: δ(5) = 1 + 3 + 5 = 9; δ(6) = 1 + 3 + 5 = 9; δ(1) = 1). Scrivere un programma DELTA che calcola la funzione δ.

Sol.   Il problema è simile a quello del precedente esercizio, ma richiede di analizzare più casi. Per prima cosa prendiamo in considerazione alcuni esempi, che ci consentiranno di arrivare alla formula ricorsiva per δ.

δ(7)   =   1 + 3 + 5 + 7
    =   (1 + 3 + 5) + 7
    =   δ(5) + 7

δ(8)     =   1 + 3 + 5 + 7
    =   δ(7)

δ(11)   =   1 + 3 + 5 + 7 + 9 + 11
    =   (1 + 3 + 5 + 7 + 9) + 11
    =   δ(9) + 11

δ(12)   =   1 = 3 + 5 + 7 + 9 + 11
    =   δ(11)

Avremo in generale: I tre casi sopra, tradotti in Scheme, costituiscono il corpo della procedura del nostro programma

    (define DELTA
      (lambda (n)
        (cond ((= n 1) 1)
                  ((= 1 (remainder n 2)) (+ (DELTA (- n 2)) n))
                  (else (DELTA (- n 1))))))



La “costruzione” delle operazioni aritmetiche


Avvertenza per chi ha seguito il corso: la presente sezione è sviluppata in modo leggermente semplificato rispetto a quanto visto a lezione, dove i “mattoni” su cui costruire i programmi sono la funzione successore e la funzione predecessore

Sull'insieme dei numeri naturali Nat={0, 1, 2, ...} siamo abituati a pensare che le operazioni più semplici siano le cosiddette 4 operazioni, i cui calcoli vengono svolti attraverso opportune computazioni sulle rappresentazioni decimali dei numeri. In ordine di difficoltà crescente (e quindi di apprendimento): somma, differenza, prodotto, divisione intera, resto. Differenza e divisione intera sono soggette alle usuali restrizioni: siccome non abbiamo a disposizione i numeri negativi, si suppone che in una sottrazione il diminuendo sia sempre maggiore o uguale al sottraendo, mentre nel caso della divisione il divisore non potrà mai essere pari a 0.
Questa sezione ha due obbiettivi: Si tratta di una sezione dove il lettore, oltre a elementi di novità, incontrerà proprietà delle operazioni che ben conosce e che potrà vedere all'opera nella costruzione dei programmi.
Fissiamo ora il punto di partenza da cui muoveremo.
Partiamo dall'ipotesi che:
Il nostro scopo sarà recuperare tutte le operazioni aritmetiche che conosciamo: desideriamo, a partire da + e -

Costruzione della moltiplicazione

Come sopra delineato, vogliamo un programma MUL che calcola la moltiplicazione. La strada attraverso cui determineremo MUL, non potendo utilizzare la procedura *, farà riferimento direttamente alla definizione di moltiplicazione, vista come somma di un numero di addendi, tutti uguali al primo fattore, pari al secondo fattore: n * m = n + n + n + ... + n + n (m addendi). Questa somma si presta subito a essere scritta ricorsivamente. Separando infatti i primi m-1 addenti dall'ultimo addendo, otteniamo:

n + n + n + .... + n + n   (m addendi)
= (n + n + n + ... + n) + n   (in parentesi m-1 addendi)
= (n * (m-1)) + n


Il caso base, ottenuto per m=0, (ossia: n*0 = 0), unitamente a quanto visto sopra, ci consente di determinare una formula ricorsiva attraverso cui definire la moltiplicazione. Esprimiamo tale formula direttamente in Scheme:

(for-mul)         (MUL n m)   =   (cond ((= m 0) 0)
                                        (else   (+ (MUL n (- m 1))   n)


Siamo ora in grado di scrivere integralmente in programma MUL; il corpo della procedura consisterà nel secondo membro della uguaglianza (for-mul).

    (define MUL
      (lambda (n m)
        (cond ((= m 0)   0)
                  (else (+ (MUL n (- m 1))   n)))))


Costruzione del resto
A lezione, oltre a quello qua presentato, è stato spiegato un secondo programma per il calcolo del resto, basato sulle funzioni successore e predecessore.   Cerchiamo ora un programma RESTO che calcoli il resto della divisione intera fra n ed m (con m diverso da 0). Ancora una volta, la scrittura del programma si baserà su note proprietà della divisione intera (e del resto). Dati n ed m numeri naturali, con m diverso da 0, procediamo alla divisione intera di n con m, e chiamiamo q il quoziente ed r il resto. Avremo allora

n   =   m*q + r


r deve esattamente essere il risultato dato da (RESTO n m). Come noto, il resto r è un valore maggiore o uguale a 0 e strettamente minore del divisore m. Se n è un numero minore di m, r è banalmente uguale a n medesimo, mentre il quoziente q vale 0. In questo caso vale infatti l'uguaglianza

n   =   m*0 + n


Supponiamo ora n maggiore o uguale a m. In questo caso r viene (in genere) calcolato congiuntamente a q: q è il più grande numero tale che il prodotto m*q si mantiene minore o uguale al dividendo n (pertanto: m*(q+1) sarà maggiore di n), mentre r è la differenza fra n e m*q. Tuttavia noi non procederemo seguendo questo schema. Piuttosto, osserviamo la seguente proprietà:

il resto della divisione fra n ed m è uguale al resto della divisione fra (n-m) ed m


Infatti, partendo dall'ipotesi n = m*q + r, abbiamo

n - m   =   m*q + r - m
= m*q - m + r
= m*(q-1) + r

Come si vede, il resto della divisione fra n-m ed m non è variato rispetto alla divisione fra n ed m (mentre è variato il quoziente, ora uguale a q-1). Possiamo raccogliere quanto ora vist nella seguente formula:

(for-resto)         (resto n m)   =   (cond ((< n m)   n)
                                      (else   (resto (- n m) m))

Prima di scrivere il programma RESTO completo, vediamo un esempio di applicazione di (for-resto) al calcolo del resto della divisione intera fra 40 (divisore) e 7 (dividendo).

(resto 40 7)   =
=   (resto 33 7)
=   (resto 26 7)
=   (resto 19 7)
=   (resto 12 7)
=   (resto 5 7)
=   5

Procediamo ora alla scrittura del programma completo, di cui (for-resto) costituisce il corpo della procedura:

    (define RESTO
      (lambda (n m)
        (cond ((< n m)   m)
                  (else   (resto (- n m) m)))))


Costruzione del quoziente
A lezione, oltre a quello qua presentato, è stato spiegato un secondo programma per il calcolo del quoziente, basato sulle funzioni successore e predecessore.   Cerchiamo ora un programma QUOZIENTE che calcoli il quoziente della divisione intera fra n ed m (con m diverso da 0). Possiamo sfruttare le considerazioni viste nel punto precedente, relative al programma RESTO: quando n è minore di m, il quoziente della divisione vale 0. Altrimenti, come osservato precedentemente, sappiamo che il quoziente della divisione fra n ed m è uguale a 1 più il quoziente della divisione fra n-m ed m. Sintetizzando

(for-quoz)         (quoziente n m)   =   (cond ((< n m)   0)
                                                (else   (+ 1 (quoziente (- n m) m)))

Prima di scrivere il programma QUOZIENTE completo, vediamo un esempio di applicazione di (for-quoz) al calcolo del resto della divisione intera fra 40 e 7.

(quoziente 40 7)   =
=   1 + (quoziente 33 7)
=   1 + (1 + (quoziente 26 7))
=   1 + (1 + (1 + (quoziente 19 7)))
=   1 + (1 + (1 + (1 + (quoziente 12 7))))
=   1 + (1 + (1 + (1 + (1 + (quoziente 5 7)))))
=   1 + (1 + (1 + (1 + (1 + 0))))
=   5

Procediamo ora alla scrittura del programma QUOZIENTE completo, di cui (for-quoz) costituirà il corpo della procedura:

    (define QUOZIENTE
      (lambda (n m)
        (cond ((< n m)   0)
                  (else (+ 1 (QUOZIENTE (- n m) m))))))


Costruzione dell'elevamento a potenza
Questo programma è già stato visto. Riportiamo solo il codice senza commenti, sostituendo, per coerenza con le restrizioni della presente sezione, la procedura Scheme * con il programma MUL.

    (define POT
      (lambda (B e)
        (cond (( = e 0) 1)
                  (else (MUL (POT B (- e 1)) B) )) ))


Costruzione del Massimo Comun Divisore
Il prossimo programma, che chiameremo MCD, calcola il massimo comun divisore di due numeri n ed m, che chiamiamo mcd(n,m). Un metodo per calcolare mcd(n,m) consiste nello scomporre in fattori primi n ed m, e calcolare il prodotto dei fattori comuni, presi con l'esponente minore con cui compaiono nelle due scomposizioni. Esiste tuttavia un altro algoritmo, che è fra l'altro legato a quanto visto nei punti precedenti relativi ai programmi RESTO e QUOZIENTE. mcd(n,m), per definizione, è il più grande dei divisori comuni di n ed m. Consideriamo due coppie di numeri: (n,m) e (a,b). Se accade che l'insieme dei divisori comuni di n ed m coincide con l'insieme dei divisori comuni di a e b, allora dovrà essere mcd(n,m) = mcd(a,b). Ad esempio: se abbiamo n=30, m=24, a=60, b=78, si ha che l'insieme dei divisori comuni di 30 e 24 è

A = {1, 2, 3, 6}

Similmente, A è anche l'insieme dei divisori comuni di 60 e 78. È pertanto ovvio che mcd(30,24) = mcd(60,78) = 6. Ora, si osservi che, dati n ed m, con n maggiore di m, l'insieme dei divisori comuni di n ed m è esattamente lo stesso dell'insieme dei divisori comuni di n-m ed m. Vediamo un esempio di questa proprietè: sia n=105, m=75. L'insieme dei divisori comuni di n ed m è in questo caso

B = {1, 2, 3, 5, 15}

D'altra parte, come si può facilmente verificare, 30 (= n-m) e 75 continuano ad avere lo stesso insieme B di divisori, e pertanto dovrà essere mcd(105,75) = mcd(30,75) (= 15).
La giustificazione di questa proprietà è in sostanza equivalente alle seguente semplice osservazione: se un numero p divide sia n che m, allora divide anche la loro differenza; d'altra parte, se un numero p divide sia n-m che m, allora divide anche n (provate a dimostrare entrambi i fatti!). In conclusione si avrà (sempre nell'ipotesi n > m)

mcd(n,m) = mcd(n-m,m)



Le stringhe


Con il termine “stringa” intendiamo una successione di caratteri alfa-numerici, racchiusi fra doppio apice. Ecco alcuni esempi di stringhe:

"a12-bc"   "asdf_+=lksa"   "Anna"   "Benvenuti al corso di IAD"   ""   " "

La penultima stringa scritta "", che non contiene alcun carattere, (neanche la spaziatura), si chiama stringa vuota, ed è differente dall'ultima stringa scritta, " ", che contiene un carattere (la spaziatura).

Nel prosieguo della discussione, le sequenze “nude” di caratteri (non racchiuse fra doppi apici) verranno spesso indicate con lettere greche: σ, τ etc. La convenzione ora introdotta (che riguarda NON la sintassi del linguaggio Scheme, ma solo la presente esposizione) consente di riferirsi a generiche successioni di caratteri in modo compatto, attraverso un unico simbolo. Vediamo una applicazione di questa convenzione. Se associamo α alla sequenza di caratteri Anna, "α" sarà un modo sintetico per riferirsi alla stringa "Anna". Analogamente, per una qualunque sequenza di caratteri σ, "σ" sarà la stringa costituita da quella sequenza di caratteri. Sequenze nude di caratteri e stringhe sono concetti che non vanno confusi: le sequenze nude costituiscono gli identificatori, ossia quei nomi che, nelle definizioni, vengono assegnati a espressioni (costanti, programmi), e nelle procedure, ai parametri (ad esempio, si ricordi la definizione (define pi_greco 3.14); gli identificatori assumono il significato che a loro attribuisce la relativa definizione, o che possono, introdotti da un lambda, essere impiegati come parametri all'interno delle procedure. Viceversa, le stringhe sono oggetti definiti e non hanno lo scopo di venire associate ad altro. Passiamo a qualche esempio che illustra ulteriormente la differenza fra stringhe ed identificatori. Supponiamo di non avere definito nulla nella finestra delle definizioni di Dr. Scheme. Se nella Interaction Window digitiamo "Anna" e clicchiamo Invio, il risultato sarà "Anna". Se digitiamo Anna e clicchiamo Invio, il risultato sarà un messaggio di errore, in quanto Anna è un identificatore a cui non è stato associato nessun oggetto (attraverso una definizione). Se nella finestra delle definizioni diamo la definizione seguente

(define Anna (+ 3 4))

clicchiamo Run (o Execute) e poi, dopo avere digitato nella finestra delle interazioni Anna, clicchiamo Invio, il risultato che otterremo sarà il numero 7, poichè la nostra definzione attribuisce all'identificatore Anna (il risultato del)la espressione (+ 3 4). Se viceversa digitiamo "Anna" e clicchiamo Invio, il risultato continuerà a essere la stringa "Anna". Infine, se nella finestra delle definizioni diamo questa definizione

(define "Anna" (+ 1 2))

e clicchiamo Run, otterremo subito un messaggio di errore, poichè "Anna", munita del doppio apice, è una stringa, non un identificatore, e quindi non può essere utilizzata in una definizione come nome da associarsi ad una espressione.

Alle stringhe si applicheremo 4 procedure predefinite: La procedura string-length calcola la lunghezza di una stringa. Esempi:

(string-length "Anna") -> 4
(string-length "") -> 0
(string-length "CiaoPaola") -> 9
(string-length "Ciao Paola") -> 10
(string-length "Ciao Paola") -> 11   (le spaziature contano)
(string-length " ") -> 1

L'unica stringa ad avere lunghezza 0 è la stringa vuota "". Di lunghezza pari a 1 sono tutte le stringhe costituite da un solo carattere, che chiameremo singoletti (esempi: "a" "1" "x" etc, ma non "a ", " 1 " etc).

La procedura string-append prende come argomenti un numero arbitrario di stringhe e ne fa la concatenazione (non creando spaziature ulteriori fra le stringhe). Ecco qualche esempio:

(string-append "Ciao" "Anna!") -> "CiaoAnna!"
(string-append "Ciao " "Anna!") -> "Ciao Anna!"
(string-append "Ci" "ao" " An" "na" "come " "va?") -> "Ciao Annacome va?")
(string-append "Anna" " " "Paola") -> "Anna Paola"
(string-append "Anna" "") -> "Anna"
(string-append "casa") -> "casa"
(string-append "12" "34") -> "1234"
(string-append 12 34) -> messaggio di errore

Si osservino in particolare gli ultimi due esempi. L'operazione di concatenare le stringhe "12" e "34" (si ricordi: nonostante l'apparenza, questi non sono numeri!!) è perfettamente lecita, mentre la concatenazione dei due numeri 12 e 34 non ha senso (ai numeri applichiamo un altro set di operazioni: +, -, quotient, * etc etc)

La procedura substring estrae una sottostringa da una stringa data s. Oltre alla stringa s, occorre specificare due indici, che segnano, rispettivamente l'inizio (leggendo da sinistra a destra) della stringa da estrarre e il primo indice a destra oltre la stringa (pertanto il carattere che avrà questo indice risulterà essere al di fuori della stringa estratta).

Si ricordi che gli indici si iniziano a contare a partire dal numero 0, e come valore massimo (è importante ricordarlo) possono assumere la lunghezza della stringa, che corrisponde alla posizione che decreta il termine della stringa. Vediamo un esempio. Si consideri la stringa "violino". Ecco la corrispondenza indici/caratteri:
    - indice 0 -> v
    - indice 1 -> i
    - indice 2 -> o
    - indice 3 -> l
    - indice 4 -> i
    - indice 5 -> n
    - indice 6 -> o
    - indice 7 -> fine della stringa

Il primo carattere di una stringa corrisponderà sempre all'indice 0 (qualunque sia la stringa). Nell'esempio riportato, all'ultima "o" di "violino" corrisponde l'indice 6, che è uguale alla lunghezza della stringa "violino" (pari a 7) meno 1. In generale, data una qualunque stringa s non vuota, l'ultimo carattere della stringa in questione si otterrà in corrispondenza dell'indice (- (string-length s) 1), ossia lunghezza della stringa s meno 1. Vediamo ora come estrarre sottostringhe dalla stringa "violino". Se desideriamo estrarre la sottostringa "iolin", dovremo selezionare l'indice 1, che corrisponde alla prima "i", e l'indice 6, che corrisponde al primo indice a destra oltre la sottostringa da estrarre:

(substring "violino" 1 6) -> "iolin"

Se desideriamo estrarre la sottostringa finale "lino", dovremo selezionare l'indice corrispondente alla "l" (3), e l'indice immediatamente oltre la fine della stringa (7, che corrisponde alla lunghezza della stringa, e, come scritto sopra, segna la fine della stringa).

(substring "violino" 3 7) -> "lino"

Se desideriamo estrarre la sottostringa singoletto costituita unicamente dal primo carattere di "violino", la "v", dovremo selezionare l'indice corrispondente al primo (e unico) carattere della sottostringa (il carattere iniziale, quindi indice 0), e l'indice successivo (l'indice 1, collocato immediatamente a destra del termine della stringa da estrarre):

(substring "violino" 0 1) -> "v"

Se desideriamo estrarre la sottostringa singoletto costituita unicamente dall'ultimo carattere di "violino", la "o" finale, dovremo selezionare l'indice corrispondente al primo (e unico) carattere della sottostringa (il carattere finale, quindi indice 6 = (- (string-length "violino") 1) ), e l'indice successivo (l'indice 7 = (string-length "violino"), che segna come detto il termine della stringa):

(substring "violino" 6 7) -> "o"

Infine, osserviamo che la sottostringa estratta da "violino" impiegando gli indici 0 e 7, coincide esattamente con la stringa di partenza:

(substring "violino" 0 7) -> "violino"


La procedura string=? costituisce il test di uguaglianza fra stringhe: prese due stringhe come argomento, restituisce come risultato un valore di verità, true oppure false, a seconda che i due argomenti siano esattamente uguali o meno (per quanto riguarda le lettere, le maiuscole sono distinte dalle minuscole):

(string=? "Anna" "anna") -> false
(string=? "Anna" "Anna") -> true
(string=? "pane" " pane") -> false
(string=? "" " ") -> false

Il test string=? non può essere sostituito dal test di uguaglianza fra numeri =: il test di uguaglianza fra stringhe va tassativamente fatto utilizzando string=?. Pertanto un test del tipo

(= "Anna" "pane")

produrrà un messaggio di errore.
Nonostante il test string=? possa al momento sembrare destinato ad un utilizzo poco più che banale, se ne coglierà fra poco l'importanza, allorché verrà impiegato utilizzando un argomento parametrico.

Passiamo ora a qualche semplice programma sulle stringhe.


Esericizio 6.1: Il programma CIAO, applicato a nomi (di persona), produce risultati come da seguenti esempi:

(CIAO "Anna") -> "Ciao Anna! Come va?"
(CIAO "Giovanni) -> "Ciao Giovanni! Come va?"
(CIAO "Laura") -> "Ciao Laura! Come va?"

Scrivere un possibile codice Scheme del programma CIAO.

Sol.   Il programma CIAO dovrà prendere in ingresso una stringa generica "σ", e produrre come risultato "Ciao σ! Come va?", che possiamo comporre utilizzando la procedura string-append:

"Ciao σ! Come va?" ≡ (string-append "Ciao "   "σ"   "! Come va?")


Quanto ora visto ci consente di scrivere il programma:

    (define CIAO
      (lambda (s)
        (string-append "Ciao "   s   "! Come va?")))

Si osservi che il parametro s verrà sostituito da una stringa generica "σ" (ad esempio, negli esempi del testo dell'esercizio, l'argomento σ assume come valori le sequenze Anna, Giovanni e Laura). Pertanto, essendo l'argomento s una stringa a tutti gli effetti, già munita di doppio apice, non è corretta, ad esempio, questa versione del programma:

    (define CIAO-2
      (lambda (s)
        (string-append "Ciao "   "s"   "! Come va?")))

(si osservi in proposito che (CIAO-2 "Anna") -> "Ciao s, come va?").


Esercizio 6.2: Si scriva un programma PRIMO che, data una stringa non vuota s, estrae la sottostringa singoletto costituita unicamente dal primo carattere di s.

Sol.   Ecco alcuni esempi di applicazioni di PRIMO:

(PRIMO "Anna") -> "A"
(PRIMO "fuoco") -> "f"
(PRIMO " Ciao!") -> " "

Il programma PRIMO si scrive utilizzando la procedura predefinita substring, tenendo conto che il primo carattere della stringa corrisponde all'indice 0, e che il primo indice al di fuori della sottostringa, a destra, è l'indice 1. Ecco pertanto il programma:

    (define PRIMO
      (lambda (s)
        (substring s 0 1)))


Esercizio 6.3 Si scriva un programma ULTIMO che, data una stringa non vuota s, estrae la sottostringa singoletto costituita unicamente dall'ultimo carattere di s.

Sol.   Ecco alcuni esempi di applicazioni di ULTIMO:

(ULTIMO "Anna") -> "a"
(ULTIMO "fuoco") -> "o"
(ULTIMO " Ciao!") -> "!"

Il programma ULTIMO si scrive utilizzando di nuovo substring, tenendo conto che l'ultimo carattere della stringa corrisponde all'indice (- (string-length s) 1), e che il primo indice al di fuori della sottostringa, a destra, è (string-length s). Ecco il programma:

    (define ULTIMO
      (lambda (s)
        (substring s (- (string-length s) 1) (string-length s))))


Esercizio 6.4 Si scriva un programma C-PRIMO (abbreviazione per "cancella primo"), che, data una stringa non vuota s, estrae la sottostringa ottenuta da s cancellando il primo carattere.

Sol.   Ecco alcuni esempi di applicazioni di C-PRIMO:

(C-PRIMO "Anna") -> "nna"
(C-PRIMO "fuoco") -> "uoco"
(C-PRIMO " Ciao!") -> "Ciao!"

Il programma C-PRIMO si scrive usando substring, tenendo conto che la sottostringa estratta inizia dal secondo carattere di s, associato all'indice 1, mentre il primo indice al di fuori della sottostringa, a destra, è (string-length s). Ecco il programma:

    (define C-PRIMO
      (lambda (s)
        (substring s 1 (string-length s))))


Esercizio 6.5 Si scriva un programma C-ULTIMO (abbreviazione per "cancella ultimo"), che, data una stringa non vuota s, estrae la sottostringa ottenuta da s cancellando l'ultimo carattere.

Sol.   Ecco alcuni esempi di applicazioni di C-ULTIMO:

(C-PRIMO "Anna") -> "Ana"
(C-PRIMO "fuoco") -> "fuoc"
(C-PRIMO " Ciao!") -> " Ciao"

Il programma C-ULTIMO si scrive usando substring, tenendo conto che la sottostringa estratta inizia dal primo carattere di s, associato all'indice 0, mentre il primo indice al di fuori della sottostringa, a destra, è (- (string-length s) 1), indice che è in corrispondenza dell'ultimo carattere della stringa. Ecco il programma:

    (define C-PRIMO
      (lambda (s)
        (substring s 0 (- (string-length s) 1))))


Esercizio 6.6 Si scriva un programma FEMMINILE? che, data una stringa, stabilisce, se questa è associata ad un nome femminile: per questo fine si utilizzi il seguente algoritmo: un nome è classicifato femminile se termina con la lettera "a", altrimenti viene classificato come maschile (naturalmente questo algoritmo, pur funzionando correttamente in un gran numero di casi, quando le stringhe sono esprimono nomi italiani di persone, non dà risposte corrette sempre, come si può evincere dagli ultimi esempi sotto). Si desidera infine che il programma dia come risposta, in caso affermativo, la stringa "sì, il nome è femminile", mentre in caso negativo dia come risposta "no, il nome non è femminile".

Sol.   Ecco alcuni esempi di applicazioni a stringhe specifiche di FEMMINILE?:

(FEMMINILE? "Paola") -> "sì, il nome è femminile"
(FEMMINILE? "Giacomo") -> "no, il nome non è femminile"
(FEMMINILE? "Alessandra") -> sì, il nome è femminile"
(FEMMINILE? "Beatrice") -> "no, il nome non è femminile"
(FEMMINILE? "Luca") -> "sì, il nome è femminile"
(FEMMINILE? "123_sdfkja") -> "sì, il nome è femminile"

Il programma sarà basato su un testo che controlla se l'ultimo carattere della stringa s è uguale ad "a", e a seconda dei casi darà la conseguente risposta. Possiamo utilmente utilizzare il programma ULTIMO all'interno di FEMMINILE?

    (define FEMMINILE?
      (lambda (s)
        (cond ((string=? "a" (ULTIMO s))   "sì il nome è femminile")
                  (else "no, il nome non è femminile"))))


Esercizio 6.7 Si scriva un programma FEMMINILE2? che, data una stringa stabilisce, con i criteri dell'esercizio precendente, se è associata ad un nome femminile. A differenza del programma precedente, si richiede che la risposta sia un valore di verità true oppure false.

So.   Ecco alcuni esempi di applicazioni a stringhe specifiche di FEMMINILE2?:

(FEMMINILE2? "Paola") -> true
(FEMMINILE2? "Giacomo") -> false
(FEMMINILE2? "Alessandra") -> true
(FEMMINILE2? "Beatrice") -> false
(FEMMINILE2? "Luca") -> true
(FEMMINILE2? "123_sdfkja") -> true

Rispetto al caso precedente cambia solo la risposta da dare. Modificando leggermente il programma precedente, possiamo ottenere la prima versione del programma FEMMINILE2?

    (define FEMMINILE2?
      (lambda (s)
        (cond ((string=? "a" (ULTIMO s))   true)
                  (else false))))

Si osservi però che il test stesso utilizzato nella procedura fornisce già la risposta corretta. Il programma può pertanto essere semplificato come segue:

    (define FEMMINILE2?
      (lambda (s)
        (string=? "a" (ULTIMO s))))


Esercizio 6.8 Diciamo che due nomi sono affini se iniziano con le stesse due lettere. Ad esempio i nomi "Agostino" ed "Agata" sono affini secondo questa definizione, e così sono i nomi "Alberto" ed "Alessandra", mentre non lo sono i nomi "Stefano" e "Susanna". Scrivere un programma NOMI-AFFINI? che stabilisce se due nomi sono affini, dando, in caso affermativo risposta "nomi affini", in caso negativo "nomi non affini".

Sol.   Si tratta di confrontare le due sottostringhe iniziali costituite dai primi due caratteri dei nomi, e verificare che queste sono uguali. Se chiamiamo s e t le due stringhe che dobbiamo verificare essere affini, le due sottostringhe in questione le otteniamo con (substring s 0 2) e (subsrtring t 0 2). Ecco il codice del programma:

    (define NOMI-AFFINI?
      (lambda (s t)
        (cond ((string=? (substring s 0 2) (substring t 0 2)) "nomi affini")
                  (else "nomi non affini") )))


Esercizio 6.9 Scrivere un programma DIMINUTIVO, che data una stringa s associata ad un nome, restituisce come il risultato il diminutivo di quel nome. Si vuole che il programma crei un diminutivo secondo il seguente schema: se il nome termina con "o", il suffisso per creare il diminutivo sarà "ino"; se il nome termina con "a", il suffisso sarà "ina". In tutti gli altri casi il programma risponderà "non so fare il diminutivo".

Sol.   Ecco alcuni esempi di applicazione di DIMINUTIVO:

(DIMINUTIVO "Paolo") -> "Paolino"
(DIMINUTIVO "palla") -> "pallina"
(DIMINUTIVO "scuola") -> "scuolina"
(DIMINUTIVO "Ester") -> "non so fare il diminutivo"
(DIMINUTIVO "Luca") -> "Lucina"

(come si vede dall'ultimo esempio, anche questo programma non produrrà sempre risposte corrette). Per scrivere diminutivo dovremo verificare se il nome s termina con "a", con "o", oppure con un'altra lettera. In quest'ultimo caso produrremo il messaggio "non so fare il diminutivo" come risposta. Negli altri due casi, occorrerà togliere dal nome l'ultimo carattere (ad esempio: da "Paolo", ricavare "Paol") utilizzando il programma già introdotto C-ULTIMO, e successivamente concatenare il suffisso corretto (nel caso del nome "Paolo", concatenare "Paol" con "ino"). Ecco il codice del programma:

    (define DIMINUTIVO
      (lambda (s)
        (cond ((string=? (ULTIMO s) "a")     (string-append (C-ULTIMO s) "ina"))
                  ((string=? (ULTIMO s) "o")     (string-append (C-ULTIMO s) "ino"))
                  (else "non so fare il dimunitivo"))))



Costruzione della somma

In questa sezione vogliamo scrivere un programma che sommi due numeri, immaginando di NON avere a disposizione alcuno strumento di calcolo sui numeri naturali. Per questo scopo non lavoreremo direttamente sui numeri naturali 1, 2, 3, etc, ma sulle loro rappresentazioni decimali, che supporremo essere date dalle corrispondenti stringhe "1", "2", "3", etc. Operativamente, la differenza fra i numeri di Scheme e le loro rappresentazioni decimali è la seguente: ai numeri è possibile applicare il set di operazioni predefinite visto all'inizio, quali il test di uguaglianza =, di “essere minore di” <, “essere maggiore di” >, e poi +, -, *, remainder etc. Di queste operazioni, nessuna è applicabile alle rappresentazioni. Essendo stringhe, potremo usare quelle procedure che si applicano a quel tipo di dato: string-length, string-append, substring, string=?, più i programmi che abbiamo già introdotto sulle stringhe. In particolare useremo i programmi PRIMO, C-PRIMO, ULTIMO e C-ULTIMO. Lavorando con le rappresentazioni numeriche, nessuna usuale operazioni aritmetica ci è al momento consentita: come visto in precedenza, non è possibile calcolare ad esempio (+ "1" "2"). Il nostro obbiettivo sarà costruire un programma che chiameremo SOMMA che, date le rappresentazioni decimali di due numeri, produce la rappresentazione decimale del numero somma dei due. Ad esempio, desideriamo che

(SOMMA "89" "168") -> "257"

Il programma SOMMA verrà costruito attraverso l'algoritmo che conosciamo per sommare due numeri: mettere le cifre in colonna, e procedere alle somme delle unità, delle decine, e così via, tenendo conto dei riporti. Per prima cosa scriviamo un programma elementare, TABELLINA, che servirà a calcolare la cifra delle unità in una somma qualunque. Tale programma prenderà come argomenti la rappresentazione di due numeri, ciascuno costituito da una cifra, variabile quindi da 0 a 9, e produrrà come risultato non la somma dei numeri, ma semplicemente la cifra delle unità di tale somma. Vediamo su qualche esempio il funzionamento di TABELLINA:

(TABELLINA "1" "4") -> "5"
(TABELLINA "3" "5") -> "8"
(TABELLINA "8" "9") -> "7"
(TABELLINA "2" "8") -> "0"

TABELLINA è un programma piuttosto noioso da scrivere, dove occorre contemplare tutte le possibili combinazioni di cifre. Gli unici casi in cui possiamo compattare i risultati sono i primi due, nel codice sotto, corrispondenti ai casi in cui una delle due cifre da sommare sia "0". In questo caso la cifra della somma coinciderà con l'altra cifra da sommare.

    (define TABELLINA
      (lambda (s t)
        (cond ((string=? s "0") t)
                  ((string=? t "0") s)
                  ((and (string=? s "1") (string=? t "1")) "2")
                  ((and (string=? s "1") (string=? t "2")) "3")
                  ((and (string=? s "1") (string=? t "3")) "4")
                  ((and (string=? s "1") (string=? t "4")) "5")
                  ((and (string=? s "1") (string=? t "5")) "6")
                  ((and (string=? s "1") (string=? t "6")) "7")
                  ((and (string=? s "1") (string=? t "7")) "8")
                  ((and (string=? s "1") (string=? t "8")) "9")
                  ((and (string=? s "1") (string=? t "9")) "0")
                  ((and (string=? s "2") (string=? t "1")) "3")
                  ((and (string=? s "2") (string=? t "2")) "4")
                  ((and (string=? s "2") (string=? t "3")) "5")
                  ((and (string=? s "2") (string=? t "4")) "6")
                  ((and (string=? s "2") (string=? t "5")) "7")
                  ((and (string=? s "2") (string=? t "6")) "8")
                  ((and (string=? s "2") (string=? t "7")) "9")
                  ((and (string=? s "2") (string=? t "8")) "0")
                  ((and (string=? s "2") (string=? t "9")) "1")
                  ((and (string=? s "3") (string=? t "1")) "4")
                  ((and (string=? s "3") (string=? t "2")) "5")
                  ((and (string=? s "3") (string=? t "3")) "6")
                  ((and (string=? s "3") (string=? t "4")) "7")
                  ((and (string=? s "3") (string=? t "5")) "8")
                  ((and (string=? s "3") (string=? t "6")) "9")
                  ((and (string=? s "3") (string=? t "7")) "0")
                  ((and (string=? s "3") (string=? t "8")) "1")
                  ((and (string=? s "3") (string=? t "9")) "2")
                  ((and (string=? s "4") (string=? t "1")) "5")
                  ((and (string=? s "4") (string=? t "2")) "6")
                  ((and (string=? s "4") (string=? t "3")) "7")
                  ((and (string=? s "4") (string=? t "4")) "8")
                  ((and (string=? s "4") (string=? t "5")) "9")
                  ((and (string=? s "4") (string=? t "6")) "0")
                  ((and (string=? s "4") (string=? t "7")) "1")
                  ((and (string=? s "4") (string=? t "8")) "2")
                  ((and (string=? s "4") (string=? t "9")) "3")
                  ((and (string=? s "5") (string=? t "1")) "6")
                  ((and (string=? s "5") (string=? t "2")) "7")
                  ((and (string=? s "5") (string=? t "3")) "8")
                  ((and (string=? s "5") (string=? t "4")) "9")
                  ((and (string=? s "5") (string=? t "5")) "0")
                  ((and (string=? s "5") (string=? t "6")) "1")
                  ((and (string=? s "5") (string=? t "7")) "2")
                  ((and (string=? s "5") (string=? t "8")) "3")
                  ((and (string=? s "5") (string=? t "9")) "4")
                  ((and (string=? s "6") (string=? t "1")) "7")
                  ((and (string=? s "6") (string=? t "2")) "8")
                  ((and (string=? s "6") (string=? t "3")) "9")
                  ((and (string=? s "6") (string=? t "4")) "0")
                  ((and (string=? s "6") (string=? t "5")) "1")
                  ((and (string=? s "6") (string=? t "6")) "2")
                  ((and (string=? s "6") (string=? t "7")) "3")
                  ((and (string=? s "6") (string=? t "8")) "4")
                  ((and (string=? s "6") (string=? t "9")) "5")
                  ((and (string=? s "7") (string=? t "1")) "8")
                  ((and (string=? s "7") (string=? t "2")) "9")
                  ((and (string=? s "7") (string=? t "3")) "0")
                  ((and (string=? s "7") (string=? t "4")) "1")
                  ((and (string=? s "7") (string=? t "5")) "2")
                  ((and (string=? s "7") (string=? t "6")) "3")
                  ((and (string=? s "7") (string=? t "7")) "4")
                  ((and (string=? s "7") (string=? t "8")) "5")
                  ((and (string=? s "7") (string=? t "9")) "6")
                  ((and (string=? s "8") (string=? t "1")) "9")
                  ((and (string=? s "8") (string=? t "2")) "0")
                  ((and (string=? s "8") (string=? t "3")) "1")
                  ((and (string=? s "8") (string=? t "4")) "2")
                  ((and (string=? s "8") (string=? t "5")) "3")
                  ((and (string=? s "8") (string=? t "6")) "4")
                  ((and (string=? s "8") (string=? t "7")) "5")
                  ((and (string=? s "8") (string=? t "8")) "6")
                  ((and (string=? s "8") (string=? t "9")) "7")
                  ((and (string=? s "9") (string=? t "1")) "0")
                  ((and (string=? s "9") (string=? t "2")) "1")
                  ((and (string=? s "9") (string=? t "3")) "2")
                  ((and (string=? s "9") (string=? t "4")) "3")
                  ((and (string=? s "9") (string=? t "5")) "4")
                  ((and (string=? s "9") (string=? t "6")) "5")
                  ((and (string=? s "9") (string=? t "7")) "6")
                  ((and (string=? s "9") (string=? t "8")) "7")
                  (else "8"))))

Il programma TABELLINA, come si vede, contribuisce a scrivere correttamente la prima cifra di una somma, ma nulla dice circa gli eventuali riporti di una somma. Ad esempio (TABELLINA "5" "8") e (TABELLINA "1" "2") danno lo stesso risultato, "3". Per effettuare correttamente le somma, occorre l'informazione se due cifre sommate generano o meno un riporto (come accade nelle somme di "5" e "8", ma non di "1" e "2"). Allo scopo creiamo un programma dal nome RIPORTO?, che, prese come argomento due cifre, produrrà come risultato un valore di verità: true, se le cifre da sommare danno riporto, false altrimenti. Ad esempio:

(RIPORTO? "5" "8") -> true
(RIPORTO? "1" "2") -> false
(RIPORTO? "0" "9") -> false
(RIPORTO? "3" "7") -> true

Come il programma TABELLINA, anche RIPORTO? è un programma noioso da scrivere (per quanto semplice), dovendo nuovamente contemplare le combinazioni possibili di somme di due cifre. Siccome noi supponiamo di non disporre né dell'operazione di somma, né di un test di "minore uguale", che consentirebbe di abbreviare il programma, saremo costretti a usare un lungo test, introdotto da un or iniziale che consentirà di avere risposta true per tutte le combinazioni (date dagli and interni), per cui la somma delle due cifre sarà maggiore o uguale a 10. Ecco il codice di RIPORTO?.

    (define RIPORTO?
      (lambda (s t)
        (or (and (string=? s "9") (string=? t "1"))
              (and (string=? s "9") (string=? t "2"))
              (and (string=? s "9") (string=? t "3"))
              (and (string=? s "9") (string=? t "4"))
              (and (string=? s "9") (string=? t "5"))
              (and (string=? s "9") (string=? t "6"))
              (and (string=? s "9") (string=? t "7"))
              (and (string=? s "9") (string=? t "8"))
              (and (string=? s "9") (string=? t "9"))
              (and (string=? s "8") (string=? t "2"))
              (and (string=? s "8") (string=? t "3"))
              (and (string=? s "8") (string=? t "4"))
              (and (string=? s "8") (string=? t "5"))
              (and (string=? s "8") (string=? t "6"))
              (and (string=? s "8") (string=? t "7"))
              (and (string=? s "8") (string=? t "8"))
              (and (string=? s "8") (string=? t "9"))
              (and (string=? s "7") (string=? t "3"))
              (and (string=? s "7") (string=? t "4"))
              (and (string=? s "7") (string=? t "5"))
              (and (string=? s "7") (string=? t "6"))
              (and (string=? s "7") (string=? t "7"))
              (and (string=? s "7") (string=? t "8"))
              (and (string=? s "7") (string=? t "9"))
              (and (string=? s "6") (string=? t "4"))
              (and (string=? s "6") (string=? t "5"))
              (and (string=? s "6") (string=? t "6"))
              (and (string=? s "6") (string=? t "7"))
              (and (string=? s "6") (string=? t "8"))
              (and (string=? s "6") (string=? t "9"))
              (and (string=? s "5") (string=? t "5"))
              (and (string=? s "5") (string=? t "6"))
              (and (string=? s "5") (string=? t "7"))
              (and (string=? s "5") (string=? t "8"))
              (and (string=? s "5") (string=? t "9"))
              (and (string=? s "4") (string=? t "6"))
              (and (string=? s "4") (string=? t "7"))
              (and (string=? s "4") (string=? t "8"))
              (and (string=? s "4") (string=? t "9"))
              (and (string=? s "3") (string=? t "7"))
              (and (string=? s "3") (string=? t "8"))
              (and (string=? s "3") (string=? t "9"))
              (and (string=? s "2") (string=? t "8"))
              (and (string=? s "2") (string=? t "9"))
              (and (string=? s "1") (string=? t "9")))))

Possiamo a questo punto entrare nel cuore dell'algoritmo che consentirà di sommare le rappresentazioni di due numeri decimali. Cominciamo ad analizzare qualche esempio. Partiamo da alcuni casi molto semplici, dove, per il momento, non ci sono casi di riporto. Come sommare ad esempio "3" e "4"? Sappiamo che in questo caso il risulato corretto della somma deve essere "7", ossia vorremo che il programma finale SOMMA lavori nel modo seguente:

(SOMMA "3" "4") -> "7"

Per il momento osserviamo che

(TABELLINA "3" "4") -> "7"

Proviamo ora un'altra somma: ci aspettiamo

(SOMMA "15" "23") -> "38"

Osserviamo che

(TABELLINA "5" "3") -> "8"
(TABELLINA "1" "2") -> "3"

Ancora un ulteriore esempio: ci aspettiamo

(SOMMA "152" "236") -> "388"

Osserviamo (l'osservazione è ora meno banale):

(TABELLINA "2" "6") -> "8"
(SOMMA "15" "23") -> "38"   (vedi esempio precedente)
(SOMMA "152" "236") = (string-append (SOMMA "15" "23") (TABELLINA "2" "6"))

Si osservi che

"2" = (ULTIMO "152")
"6" = (ULTIMO "236")
"15" = (C-ULTIMO "152")
"23" = (C-ULTIMO "236")

Raccogliendo quanto visto sopra arriviamo a questa osservazione, valida a patto che non ci siano riporti: ogni qualvolta dobbiamo sommare due rappresentazioni di numeri decimali, s e t, composte da diverse cifre, possiamo procedere alla concatenazione:

(string-append (SOMMA (C-ULTIMO s) (C-ULTIMO t)) (TABELLINA (ULTIMO s) (ULTIMO t)))

Cosa accade se le cifre generano riporti? Osserviamo il seguente esempio, simile a quello precedente. Dal nostro programma SOMMA ci aspettiamo:

(SOMMA "152" "239") -> "391"

Si osservi che

(TABELLINA "2" "9") -> "1"
(RIPORTO? "2" "9") -> true
(SOMMA-con-riporto "15" "23") = (SOMMA "16" "23") -> "39"
"16" = il successore di "15"

Come si può osservare, sopra è comparso un nuovo elemento, la nozione di successore, che consente di effettuare la somma nei casi in cui ci sia riporto nella somma delle cifre delle unità. Al momento, nonostante sembri utile, non disponiamo di un programma SUCC che calcoli la rappresentazione del successore di un numero n, data la rappresentazione di n. Il programma SUCC dovrebbe lavorare ad esempio come segue:

(SUCC "13") -> "14"
(SUCC "19") -> "20"
(SUCC "2199") -> "2200"

Al fine di non spezzare il filo del discorso, si supponga di disporre del programma SUCC (sul cui codice torneremo dopo). A questo punto, facendo l'ipotesi che le cifre delle unità di s e t producano un riporto (segnalato dal risultato true effettuando il test RIPORTO? su (ULTIMO s) e (ULTIMO t)) potremo applicare la seguente formula per calcolare la somma:

(SOMMA s t)   =
(string-append (SOMMA (SUCC (C-ULTIMO s)) (C-ULTIMO t)) (TABELLINA (ULTIMO s) (ULTIMO t)))

Possiamo a questo punto scrivere il codice di SOMMA. Al suo interno utilizzeremo, oltre ai programmi RIPORTO?, TABELLINA, ULTIMO e C-ULTIMO, anche il programma SUCC che verrà scritto in seguito. Il programma SOMMA comprende due test iniziali per stabilire se una delle due stringhe è vuota, nel qual caso il risultato della somma sarà pari all'altra stringa. Questo caso deve essere considerato poiché ha luogo quando si sommano rappresentazioni con numeri differenti di cifre (se ad esempio si sommano "13" e "4", dopo la somma delle unità fra "3" e "4", resterà da sommare "1" con la stringa vuota "", che corrisponde a (C-ULTIMO "4")). Se entrambe le stringhe hanno almeno una cifra, si procederà, con i test successivi, a verificare se le due stringhe s e t hanno cifre delle unità che producono o meno riporto, e ci si regolerà conseguentemente, come sopra spiegato, per calcolare la somma complessiva.

    (define SOMMA
      (lambda (s t)
        (cond ((string=? s "") t)
                  ((string=? t "")   s)
                  ((RIPORTO? (ULTIMO s) (ULTIMO t))
                          (string-append (SOMMA (SUCC (C-ULTIMO s)) (C-ULTIMO t))
                                                  (TABELLINA (ULTIMO s) (ULTIMO t)) ))
                  (else   (string-append (SOMMA (C-ULTIMO s) (C-ULTIMO t))
                                                    (TABELLINA (ULTIMO s) (ULTIMO t)) )))))


Resta infine da scrivere il codice del programma SUCC. Lo riportiamo qua senza commenti. I lettori provino a comprendere da soli l'algoritmo che è alla base della sua stesura.

    (define SUCC
      (lambda (s)
                  (cond ((string=? s "") "1")
                  ((string=? (ULTIMO s) "0") (string-append (C-ULTIMO s) "1"))
                  ((string=? (ULTIMO s) "1") (string-append (C-ULTIMO s) "2"))
                  ((string=? (ULTIMO s) "2") (string-append (C-ULTIMO s) "3"))
                  ((string=? (ULTIMO s) "3") (string-append (C-ULTIMO s) "4"))
                  ((string=? (ULTIMO s) "4") (string-append (C-ULTIMO s) "5"))
                  ((string=? (ULTIMO s) "5") (string-append (C-ULTIMO s) "6"))
                  ((string=? (ULTIMO s) "6") (string-append (C-ULTIMO s) "7"))
                  ((string=? (ULTIMO s) "7") (string-append (C-ULTIMO s) "8"))
                  ((string=? (ULTIMO s) "8") (string-append (C-ULTIMO s) "9"))
                  (else (string-append (SUCC (C-ULTIMO s)) "0")))))



Esercizi proposti

I prossimi esercizi costituiscono un piccolo test per coloro che vogliono testare la preparazione raggiunta. Vanno quindi svolti prima di leggerne la soluzione. L'ordine di difficoltà è casuale.

Esercizio 8.1: Scrivere un programma CONTA-a che, data una stringa, conta quante "a" sono presenti in essa.

Sol.  

    (define CONTA-a
      (lambda (s)
        (cond ((string=? s "") 0)
                  ((string=? (PRIMO s) "a") (+ 1 (CONTA-a (C-PRIMO s))) )
                  (else (CONTA-a (C-PRIMO s))) )))


Esercizio 8.2: Scrivere un programma IPOTENUSA che, dati i lati di un triangolo rettangolo, calcola l'ipotenusa.

Sol.  

    (define IPOTENUSA
      (lambda (a b)
        (sqrt (+ (* a a) (* b b)))))


Esercizio 8.3: Scrivere un programma DIAGONALE che, dato il lato del quadrato, ne calcola la diagonale.

Sol.  

    (define DIAGONALE
      (lambda (lato)
        (* (sqrt 2) lato)))


Esercizio 8.4: Scrivere un programma PREFISSO-COMUNE che, date due stringhe s e t, calcola il prefisso più lungo comune ad entrambe le stringhe. Ad esempio:

(PREFISSO-COMUNE "fumo" "fuoco") → "fu"
(PREFISSO-COMUNE "casa" "base") → ""
(PREFISSO-COMUNE "casa" "cena") → "c"
(PREFISSO-COMUNE "panettiere" "panegirico") → "pane


Sol.  

    (define PREFISSO-COMUNE
      (lambda (s t)
        (cond ((or (string=? s "") (string=? t "")) "")
                  ((string=? (PRIMO s) (PRIMO t))
                    (string-append (PRIMO s) (PREFISSO-COMUNE (C-PRIMO s) (C-PRIMO t))) )
                  (else ""))))



...