Ora che conosciamo tutte le basi di Scheme dobbiamo iniziare la parte più difficile, abituare la nostra testa a ragionare secondo il modello funzionale. Per fare questo non possiamo prescindere dall’uso di un linguaggio un po più matematico ma che, vi assicuro, dopo l’impatto iniziale si rivelerà piuttosto automatico (e se avete dubbi potete sempre chiedere su LQH).

La base di scheme, come sapete, è funzionale. In quanto linguaggio funzionale esso va programmato secondo i canoni della teoria delle funzioni ricorsive. Le funzioni ricorsive sono un argomento molto esteso ma di importanza fondamentale nella teoria della calcolabilità. In questa lezione non ci occuperemo della totalità delle funzioni ricorsive ma ci limiteremo a trattare il sottoinsieme delle funzioni ricorsive primitive. Queste funzioni ricorsive hanno, fra le tante, la non trascurabile proprietà di terminare sempre. Ovvero data una qualunque funzione ricorsiva primitiva e un qualsiasi input la funzione cesserà la propria esecuzione restituendoci un risultato.

Senza addentrarci troppo nella teoria sappiate che una funzione ricorsiva è una funzione nella quale esiste un caso in cui la soluzione è diretta e nel caso generale il risultato è ricavabile passando ad un’altra funzione tutti gli argomenti della funzione ricorsiva più il risultato della stessa calcolato su un insieme più piccolo degli argomenti originali. Ovvero:

Detto così sembra enormemente complicato. In realtà nella maggior parte dei casi una funzione ricorsiva può essere riportata alla ricorsione di una funzione ad un argomento e quindi.

Se anche così la cosa vi crea problemi cercherò di risolverli con il più semplice degli esempi: il fattoriale. Ricordate inoltre che la funzione g(y,x) solitamente è implicita.

Il fattoriale espresso ricorsivamente apparirà come:

Che penso sia di facile interpretazione.

I casi in cui risaliamo direttamente al risultato si chiamano casi base, i casi in cui è necessario usare la ricorsione sono detti casi ricorsivi.

Poiché questo è un corso di Scheme vediamo come trasportare questa funzione matematica in una funzione di Scheme. Il passo è semplice.

1
2
3
4
5
(define (fattoriale y)

    (cond ((= y 0) 1)

    (else (* y (fattoriale (- y 1))))

    )

)

Come vedete ci basta inserire in un COND tutti i casi base e tutti i casi ricorsivi. Il caso base, in questo esempio, equivale a y=0, in questo caso infatti il fattoriale è semplicemente 1. Se y non è nulla allora dobbiamo eseguire il passo ricorsivo. Notate che in questo caso la funzione g(y,x) è semplicemente la funzione prodotto.

Il meccanismo di funzionamento è semplice. Le chiamate ricorsive hanno sempre due stati:

• Uno stato di crescita in cui si fanno le chiamate ricorsive inserendo tutto sullo stack.
• Uno stato di calcolo in cui partendo dalla cima dello stack si effettuano i calcoli ripercorrendo le varie chiamate ricorsive a ritroso.

Nel caso di funzioni ricorsive semplici questi stati sono raggruppati in due fasi distinte. Lo stato di crescita continua fino al raggiungimento di un caso base dopo il quale tutte le chiamate sullo stack terminano a cascata.

Facciamo un esempio. Riprendiamo la nostra funzione fattoriale e vediamo come si comporta nel fare il fattoriale di 4.

La prima chiamata sarà

(fattoriale 4)

A questo punto si entra nel COND. Y è chiaramente diverso da zero, quindi viene eseguito il ramo else. La funzione esegue:

(* 4 (fattoriale 3) )

A questo punto viene invocato nuovamente fattoriale. L’esecuzione corrente viene quindi sospesa mentre viene avviata una nuova esecuzione di fattoriale. A questo punto i passi vengono rieseguiti nella nuova chiamata. Y è ancora diverso da zero quindi viene eseguito ancora il ramo else.

( * 4 ( * 3 (fattoriale 2) ) )

Viene aggiunta una nuova chiamata in pila. E così via.

( * 4 ( * 3 ( * 2 ( * 1 (fattoriale 0) ) ) ) )

A questo punto però ci troviamo nella situazione in cui la nuova chiamata di fattoriale è esattamente il caso base. A questo punto la chiamata termina restituendo 1 senza eseguire una nuova chiamata a fattoriale.

( * 4 ( * 3 ( * 2 ( * 1 1 ) ) ) )

Inizia così la fase di calcolo e distruzione. Terminata l’ultima chiamata di fattoriale si riprende dalla chiamata precedente che non fa altro che calcolare 1 x 1 e terminare. E così via a cascata fino alla chiamata originale che termina con il risultato complessivo. Ovvero 24.

Questo è il meccanismo generale di una funzione ricorsiva.

RICAPITOLANDO

• Una funzione ricorsiva è una funzione che richiama se stessa su una porzione più piccola degli argomenti.
• Una funzione ricorsiva primitiva termina sempre.
• Una funzione ricorsiva primitiva è sempre composta da uno o più casi base e uno o più casi ricorsivi.
• Una funzione ricorsiva senza casi ricorsivi non è ricorsiva. Una funzione senza casi base non termina mai.
• Una funzione ricorsiva presenta nella sua esecuzione due stati: uno stato di crescita e uno stato di calcolo e distruzione.

RISORSE

Allego di seguito un file Scheme che contiene alcune piccole funzioni ricorsive numeriche. Potete dargli un occhiata, prima però potete provare a farle da voi. Le funzioni sono:

• Fattoriale (fatto)
• Serie di Fibonacci
• Moltiplicazione
• Somma
• Elevazione a potenza

Il file lo trovate QUI.

Nella prossima lezione continueremo questo argomento cercando di chiarire molti altri aspetti pratici di una funzione ricorsiva e vedremo come applicarla a compiti più complessi del semplice calcolo delfattoriale di un numero.

Ora che conosciamo tutte le basi di Scheme dobbiamo iniziare la parte più difficile, abituare la nostra testa a ragionare secondo il modello funzionale. Per fare questo non possiamo prescindere...

Come in ogni linguaggio di programmazione, una delle cose essenziali per scrivere un qualunque programma è la  gestione delle condizioni. Una condizione consiste, come penso sappiate, nell’eseguire un blocco di comandi a seconda se sia rispettata o meno una data condizione.

In Scheme la gestione delle condizioni è molto completa. Iniziamo quindi a vedere uno dei costrutti più famosi anche se in Scheme non viene molto usato: l’if.

IF

1
2
3
(if condizione

    espressione_nel_caso_la_condizione_sia_vera

    eventuale_espressione_nel_caso_la_condizione_sia_falsa)

Questa è la struttura dell’if. Viene valutata condizione e a seconda se sia vera o falsa viene eseguito rispettivamente il primo o il secondo blocco di espressioni. Guardiamo un piccolo esempio:

1
2
3
4
5
6
7
; TESTIF: Verifica se A è uguale a Zero.

(define (testif a)

 (if (= a 0) (display "Il valore inserito è uguale a zero.")

         (display "Il valore inserito NON è uguale a zero.")

 )

 (newline)

)

Questa funzione non fa altro che dire se il valore passato per parametro è zero oppure no. Potete subito constatare che questo costrutto è del tutto simile agli if presenti negli altri linguaggi.

COND

COND è il costrutto condizionale più utilizzato a causa della sua versatilità. Esso è infatti in grado di simulare abilmente sia un IF sia un CASE. Vediamo come è strutturato.

1
2
3
4
5
(cond

(prima_condizione espressione)

(seconda_condizione espressione)

...

(else espressione))

Ad ogni sua applicazione vengono valutate le condizioni a partire dalla prima fino all’ultima e viene eseguito il blocco di istruzioni corrispondente alla condizione vera. Se nessuna condizione è vera viene eseguito il ramo else. Vediamo un esempio:

1
2
3
4
5
6
7
8
; TESTCOND: Verifica se B è uguale a 0 o a 1.

(define (testcond b)

    (cond ((= b 0) (display "B = 0"))

        ((= b 1) (display "B = 1"))

        (else (display "NONE"))

    )

    (newline)

)

Questa funzione verifica se il parametro è 0 oppure 1 e in caso contrario risponde con NONE.

CASE

Questo è l’ultimo costrutto decisionale in Scheme. Si comporta in modo molto simile allo switch…case presente in molti altri linguaggi.

1
2
3
4
5
(case espressione_che_viene_valutata

   ((val1) espressione)

   ((val2) espressione)

   ...

   (else espressione))

Viene innanzitutto valutata l’espressione. Dopodichè il valore risultante viene confrontato con la lista di valori val1, se il valore è contenuto in val1 viene eseguita l’espressione corrispondente altrimenti si passa a val2. Così via fino a else che viene eseguita in ogni caso.

1
2
3
4
5
6
7
8
9
; TESTCASE: Verifica se C è pari o dispari compreso fra 0 e 10.

(define (testcase c)

 (case c

     ((1 3 5 7 9) (display "C = DISPARI"))

     ((2 4 6 8 10) (display "C = PARI"))

     (else (display "NONE"))

 )

 (newline)

)

RICAPITOLANDO:

• IF esegue un espressione se la condizione è vera, ne esegue un altra se è falsa.
• COND esegue l’espressione corrispondente alla condizione vera o a else se nessuna è vera.
• CASE calcola un espressione ed esegue i comandi associati alla lista che contiene tale valore.

Come in ogni linguaggio di programmazione, una delle cose essenziali per scrivere un qualunque programma è la  gestione delle condizioni. Una condizione consiste, come penso sappiate, nell’eseguire un blocco di...

Scheme è uno dei principali dialetti del Lisp. E’ un linguaggio multi paradigma anche se incentrato sul paradigma funzionale per questioni ereditarie. Nonostante ciò con Scheme si può fare praticamente tutto, dalla programmazione a oggetti alla programmazione imperativa, dalla funzionale ricorsiva alla sua versione “logica”.

Ci tengo però a precisare che Scheme è e rimane un linguaggio un po particolare. Diverso concettualmente da tutti i linguaggi tradizionali. Scheme è indirizzato a:

• Persone che sanno programmare e che vogliono espandere i loro confini in modi che non avrebbero mai immaginato.
• Persone che non hanno mai programmato e che volgiono conoscere lo spirito intimo della programmazione.
• Persone a cui la programmazione classica non è mai piaciuta ma amano lo spirito “matematico” della stessa.
• Persone che amano la neuroingegneria in senso lato.

A chi NON è indirizzato:

• Persone che sanno programmare e che non sentono il bisogno di imparare altro.
• Persone che non hanno mai programmato e vogliono subito essere produttivi e fare qualche applicazione carina.
• Persone la cui idea di programmazione è costruire enormi gestionali in grado di mantenere informazioni su pescherie sul mar baltico, parrucchieri per donnole, palestre e altre cose noiose (per me ovviamente).

Chiariti questi punti spero di avere da ora in poi solo persone che rientrano nei primi tre punti e che non si spazientiscano se Scheme sembri strano, complicato, astratto e chi più ne ha più ne metta.

Iniziamo con il presentare alcuni aspetti essenziali. Lo studio di Scheme è IMPRESCINDIBILE da questi concetti.

NOTAZIONE PREFISSA

Scheme come in Lisp esprime tutto in notazione prefissa. In notazione prefissa bisogna prima specificare la funzione e poi tutti i suoi parametri a seguire.

Ad esempio 1+1 diventa:

(+ 1 1)

Mentre 2 + (3 * 2) + 1 diventa:

(+ 2 (* 3 2) 1)

Questo tipo di notazione può risultare a prima vista molto complessa e inutilmente dispendiosa. E’ vero e non è vero. Nelle semplici operazioni matematiche può effettivamente risultare poco intuitiva e poco chiara, tuttavia, in tutti gli altri casi questa forma permette un controllo del codice inqguagliabile. E’ molto facile, ad esempio, istruire un programma a creare ed eseguire codice proprio.

LISTE E ATOMI

Un altra cosa da tenere in considerazione è che in Scheme tutto è una lista. Anche lo stesso programma è una lista.

Una lista può contenere una lista o un atomo. Un atomo è semplicemente tutto ciò che non è una lista (ad esempio stringhe, numeri, caratteri e nomi di funzioni).

Per generare esplicitamente una lista si può usare il comando list.

1
2
3
4
5
6
7
8
; Lista di numeri.

(list 1 2 3)



; Lista di stringhe.

(list "a" "b" "c")



; Lista di liste.

(list (list 1 2) (list "a") (list))

E via discorrendo fino ad avere contortissimi costrutti di liste piene di liste di liste. E’ importante notare che data una lista (a b c d … z) Scheme interpreta sempre il primo elemento di una lista come un comando. Quindi quando vogliamo indicare una lista pura dobbiamo sempre usare come primo elemento il comando list.

DEFINIZIONI

In Scheme tutte le definizioni, siano esse di variabili intere, stringhe, ma anche funzioni e procedure sono definite grazie al comando define.

1
2
3
4
5
; Variabile numerica.

(define pippo 3)



; Stringa.

(define pluto "Ciao")

E come abbiamo detto anche le funzioni possono essere definite in questo modo.

(define (somma a b) (+ a b))

Ecco che abbiamo definito una semplice funzione somma che potrà essere richiamata così:

(somma 3 4)

Una funzione è quindi definita secondo il formato:

(define (nomefunzione parametro1 parametro2 .... parametroN) (corpo della funzione))

RICAPITOLANDO:

• Scheme è un dialetto del LISP.
• Scheme è un linguaggio multiparadigma incentrato però sul paradima funzionale.
• In Scheme ogni cosa racchiusa fra parentesi è un lista.
• In Scheme ogni cosa che non è una lista si chiama Atomo (numeri, stringhe e altro).
• In Scheme si utilizza esclusivamente la notazione prefissa anche per le operazioni aritmetiche.
• In Scheme tutto si definisce con il comando define. Sia variabili che costanti che funzioni.
• In Scheme il primo elemento di una lista è sempre visto come un comando.

Scheme è uno dei principali dialetti del Lisp. E’ un linguaggio multi paradigma anche se incentrato sul paradigma funzionale per questioni ereditarie. Nonostante ciò con Scheme si può fare praticamente...