Scheme
Lo Scheme è un linguaggio di programmazione funzionale, un dialetto del Lisp di cui mantiene tutte le caratteristiche, che è stato sviluppato negli anni settanta da Guy L. Steele e Gerald Jay Sussman, che lo introdussero nel mondo accademico con una serie di articoli noti come le Lambda Papers e nel libro Structure and Interpretation of Computer Programs, usato per decenni come testo in alcuni esami di Scienze dell'Informazione.
In ambiente Gnu/Linux, il desktop manager GNOME implementa l'interprete Scheme Guile.
Programmi di esempio
Il seguente esempio visualizza il testo «Hello world».
(display "Hello World")
(newline)
Alcuni esempi più complessi
Il seguente esempio calcola il massimo comune divisore tra gli argomenti numerici x e y.
(define (mcd x y)
(cond ((= x y) x)
((> x y) (mcd (- x y) x))
(else (mcd x (- y x)))))
Il seguente esempio serve a girare una stringa, ad esempio da "abcdef" si ottiene "fedcba".
(define (sl w) (substring w (sub1 (string-length w)) (string-length w)))
(define (dl w) (substring w 0 (sub1 (string-length w))))
(define (reversem s w)
(if (= (string-length s) 0) w
(reversem (dl s) (string-append w (sl s)))))
Questo invece fa la stessa cosa dell'esempio di sopra, solo usando alcune funzioni di scheme.
(define (reverse s) (reversem s "")) ;tail recursion
(define (reverse2 w)
(list->string(reverse (string->list w))));standard
Questa funzione serve a sapere se un certo numero è primo:
(define (primo?m n s)
(if (= (sub1 n) s) "e' primo"
(if (= 0 (remainder n (add1 s))) (string-append "non e' primo, e' divisibile per: " (number->string (add1 s)))
(primo?m n (add1 s)))))
(define (primo? n) (primo?m n 1))
Accenni alla programmazione in Scheme
A differenza della maggior parte degli altri linguaggi di programmazione, Scheme utilizza una notazione prefissa, ovvero una notazione in cui al posto di scrivere (2 + 3) si scrive (+ 2 3). Questa notazione si propaga a tutte le funzioni, sicché se abbiamo una funzione N-aria f, la sua rappresentazione sarà (f argomento1 argomento2... argomentoN).
Tipi di dato
Lo Scheme implementa tutti i tipi di dato fondamentale: booleani, numeri, caratteri, stringhe, vettori. Ma anche dei tipi speciali, tra cui troviamo le liste (coppie), le porte (flussi di dati) i simboli e le procedure.
Per riconoscere questi tipi di dato, Scheme ci mette a disposizione delle particolari funzioni che praticamente sono nel formato "tipoDiDato?" che restituiscono il booleano TRUE se l'argomento passato è nel formato tipoDiDato, ma ecco la tabella riassuntiva:
| Funzione | Spiegazione |
|---|---|
(boolean? argomento) |
l'argomento è un booleano? |
(number? argomento) |
l'argomento è un numero? |
(char? argomento) |
l'argomento è un carattere? |
(string? argomento) |
l'argomento è una stringa? |
(vector? argomento) |
l'argomento è un vettore? |
(list? argomento) |
l'argomento è una lista? |
(port? argomento) |
l'argomento è una porta? |
(symbol? argomento) |
l'argomento è un simbolo? |
(procedure? argomento) |
l'argomento è una procedura? |
Vediamo ora alcuni dettagli su questi tipi di dati
Booleani
Si indicano tramite il carattere cancelletto e la lettera T (TRUE) per vero e F (FALSE) per falso. Quindi #T è vero, mentre #F e falso.
Le funzioni sui booleani sono quelle classiche della letteratura:
| Funzione | Risultato restituito |
|---|---|
(not arg) |
nega arg. falso-> vero e vero->falso |
(and arg1 arg2 ...) |
falso,falso->falso falso,vero->falso vero,vero->vero |
(or arg1 arg2 ....) |
falso,falso->falso falso,vero->vero vero,vero->vero |
Numerici
Si indicano scrivendo semplicemente il numero che si vuole descrivere, tuttavia si possono esprimere vari tipi di dato numerico: numeri positivi e negativi, numeri con la virgola e numeri in notazione esponenziale. Per riconoscere in che classe di numeri ci troviamo, è possibile usare una delle seguenti funzioni, che come quelle viste prima (con il punto interrogativo) restituisce un booleano:
| Funzione | Risultato restituito |
|---|---|
(integer? argomento) |
l'argomento è un intero |
(rational? argomento) |
l'argomento è un numero razionale |
(real? argomento) |
l'argomento è un reale |
(complex? argomento) |
l'argomento è un numero complesso |
È inoltre possibile specificare la base di numerazione tramite #fN, dove f è la base ed N un numero:
| Basi possibili | Tipo di base |
|---|---|
#bN |
N è binario |
#oN |
N è ottale |
#dN |
N è decimale |
#xN |
N è esadecimale |
#dN non si usa praticamente mai, visto che la base è di default quella decimale.
Esistono poi le seguenti funzioni booleane e di conversione:
| Funzioni | funzionalità |
|---|---|
(exact? espressione) |
L'espressione restituisce un numero esatto? |
(inexact? espressione) |
L'espressione restituisce un numero approssimato? |
(exact->inexact espressione) |
Approssima il valore dell'espressione |
(inexact->exact espressione) |
Converte un valore approssimato in un valore esatto. |
Per classificare ulteriormente i numeri, ad esempio tra positivi e negativi, o pari e dispari, Scheme mette a disposizione le seguenti primitive:
| Funzioni | funzionalità |
|---|---|
(zero? numero) |
Il numero è uno zero? |
(positive? numero) |
Il numero è positivo? |
(negative? numero) |
Il numero è negativo? |
(odd? numero) |
Il numero è dispari? |
(even? numero) |
Il numero è pari? |
Ovviamente poi si hanno le comuni funzioni matematiche presenti in tutti i linguaggi.
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(+ arg1 arg2 ... argN) |
arg1+arg2+...+argN | numerico |
(- arg1 arg2 ... argN) |
arg1-arg2-...-argN | numerico |
(* arg1 arg2 ... argN) |
arg1*arg2*...*argN | numerico |
(/ arg1 arg2 arg3... argN) |
(..(arg1/arg2)/arg3).../argN | numerico |
(log arg) |
log naturale di arg | numerico |
(exp arg) |
esponenziale di arg | numerico |
(sin arg) |
seno di arg | numerico |
(cos arg) |
coseno di arg | numerico |
(tan arg) |
tangente di arg | numerico |
(asin arg) |
arcoseno di arg | numerico |
(acos arg) |
arcocoseno di arg | numerico |
(atan arg) |
arcotangente di arg | numerico |
(sqrt arg) |
radice quadrata arg | numerico |
(expt base potenza) |
base^potenza | numerico |
(abs arg) |
valore assoluto di arg | numerico |
(quotient arg1 arg2) |
arg2 | numerico |
(remainder arg1 arg2) |
resto (positivo) della divisione | numerico |
(modulo arg1 arg2) |
resto della divisione | numerico |
(ceiling arg) |
tetto di arg (approssimazione della parte intera per eccesso) | numerico |
(floor arg) |
pavimento di arg (approssimazione della parte intera per difetto) | numerico |
(round arg) |
approssimazione generica di arg | numerico |
(truncate arg) |
troncamento di arg | numerico |
(max arg1 ... argN) |
valore massimo tra arg1 e argN | numerico |
(min arg1 ... argN) |
valore minimo tra arg1 e argN | numerico |
(gcd arg1 ... argN) |
massimo comune divisore tra arg1..e.. argN | numerico |
(lcm arg1 ... argN) |
minimo comune multiplo tra arg1.. e.. argN | numerico |
(numerator arg) |
numeratore di arg | numerico |
(denominator arg) |
denominatore di arg | numerico |
(= arg1 arg2 ... argN) |
arg1=arg2=...=argN? | booleano |
(< arg1 arg2 ... argN) |
arg1<arg2<...<argN? | booleano |
(> arg1 arg2 ... argN) |
arg1>arg2>...>argN? | booleano |
(>= arg1 arg2 ... argN) |
arg1>=arg2>=...>=argN? | booleano |
(<= arg1 arg2 ... argN) |
arg1<=arg2<=...<=argN? | booleano |
Caratteri
In Scheme i caratteri si indicano con un cancelletto, seguito da un backslash ed il carattere che si vuole esprimere (senza il backslash, si confonderebbero i caratteri T e F ed i booleani TRUE e FALSE).
Tra le funzioni rilevanti troviamo:
| Funzioni | Risultato restituito |
|---|---|
(char=? char1 char2) |
char1 è uguale a char2? |
(char<? char1 char2) |
char1 è lessicograficamente inferiore a char2? |
(char>? char1 char2) |
char1 è lessicograficamente superiore a char2? |
(char<=? char1 char2) |
char1 è lessicograficamente non superiore a char2? |
(char<=? char1 char2) |
char1 è lessicograficamente non inferiore a char2? |
Di queste funzioni esiste anche la versione ci, case insensitive, si ha quindi char-ci=?, char-ci<?, char-ci<=?..ecc.
Altre funzioni sui caratteri sono le seguenti:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(char? arg) |
arg è un carattere? | booleano |
(char-alphabetic? arg) |
arg è un carattere alfabetico? | booleano |
(char-numeric? arg) |
arg è un carattere rappresentante un numero? | booleano |
(char-whitespace? arg) |
arg è un carattere rappresentante uno spazio bianco? | booleano |
(char-upper-case? arg) |
arg è un carattere alfabetico maiuscolo? | booleano |
(char-lower-case? arg) |
arg è un carattere alfabetico minuscolo? | booleano |
(char->integer arg) |
il carattere viene trasformato in numero | numerico |
(integer->char arg) |
il numero viene trasformato in carattere | carattere |
(char-upcase arg) |
il carattere alfabetico diventa maiuscolo | carattere |
(char-downcase arg) |
il carattere alfabetico diventa minuscolo | carattere |
Stringhe
Le stringhe in scheme si rappresentano tra doppi apici, un esempio di stringa potrebbe ad esempio essere "stringa". Alcune funzioni per la gestione delle stringhe, sono le seguenti:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(make-string n) |
crea una stringa lunga n | stringa |
(make-string n ch) |
crea una stringa lunga n, formata dal solo caratte ch | stringa |
(string char1 char2 ..charN) |
crea una stringa formata dai caratteri char1, char2,... charN | stringa |
(string-length str) |
restituisce la dimensione di str | numerico |
(string-ref str idx) |
restituisce il carattere alla posizione idx, della stringa str | carattere |
(substring str beg end) |
restituisce la porzione di stringa contenuta tra i due indici beg ed end | stringa |
(string-set! str idx ch) |
sostituisce con ch, il carattere alla posizione idx nella stringa str | stringa |
(string-append str1 str2...strN) |
concatena le stringhe str1, str2, ..., strN | stringa |
(string-copy str) |
restituisce una copia della stringa str | stringa |
(string->list str) |
restituisce una lista formata dai caratteri della stringa str | lista |
(list->string lst) |
restituisce una stringa formata dai caratteri della lista lst | stringa |
Come per i caratteri abbiamo degli operatori di controllo per il confronto tra stringhe, che sono uguali a quelli per i caratteri, cambia solo il nome, i principali sono elencati in seguito, ed esistono anche nella versione string-ci (case insensitive):
| Funzioni | Risultato restituito |
|---|---|
(string=? str1 str2) |
str1 è uguale a str2? |
(string<? str1 str2) |
str1 è lessicograficamente inferiore a str2? |
(string>? str1 str2) |
str1 è lessicograficamente superiore a str2? |
(string<=? str1 str2) |
str1 è lessicograficamente non superiore a str2? |
(string<=? str1 str2) |
str1 è lessicograficamente non inferiore a str2? |
Liste
Le liste come specificato prima, sono un particolare tipo di dato, a prima vista assomigliano a degli array, ma tale visione è errata (anche perché gli array sono implementati tramite il tipo di dato vector). La vera natura delle liste è quella di coppie, un esempio potrebbe essere (2 3), ma anche (2 3 4) è una coppia, formata dal primo elemento (2) e da tutti gli altri (3 4). Ma le liste non contengono solo numeri, possono contenere caratteri, stringhe, booleani, altre liste (esempio:"(2 3 (4 5))"), ma anche tipi di dato misti (esempio:"(#\T 4 (4 #F ("stringa")))"). Essendo delle coppie, le funzioni principali per agire sopra sono car che restituisce il primo elemento e cdr, che restituisce il secondo elemento. Le funzioni classiche che Scheme fornisce, sono le seguenti:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(list arg1 arg2 ... argN) |
costruisce una lista formata dagli argomenti arg1,arg2,...,argN | lista |
(pair? lst) |
la lista lst è non vuota? | booleano |
(car lst) |
restituisce il primo elemento della lista lst | misto |
(cdr lst) |
restituisce la lista formata dagli elementi dal secondo all'ultimo elemento della lista lst | lista |
(cadr lst) |
restituisce il primo elemento della lista che si otterebbe invocando (cdr lst) |
misto |
(cons arg lst) |
restituisce una lista in cui al primo posto c'e' arg | lista |
(append lst1 lst2) |
concatena le due liste lst1 e lst2 | lista |
(length lst) |
restituisce il numero di elementi della lista | numerico |
(reverse lst) |
inverte gli elementi della lista | lista |
Da notare che le funzioni car e cdr, si possono comporre insieme nel senso che se vogliamo fare (cdr(cdr lst)), possiamo usare direttamente la funzione cddr. Stessa cosa per (car (cdr lst)), che si può sintetizzare con cadr.
Scheme presenta poi altre funzioni composte, alcune delle quali simulano le funzioni sui vettori, ed altre piuttosto di conversione lista a vettore e viceversa:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(null? lst) |
la lista lst è vuota? | booleano |
(set-car! lst arg) |
setta la prima posizione al valore arg | lista |
(set-cdr! lst arg) |
setta la seconda posizione al valore arg | lista |
(list-ref lst k) |
restituisce l'elemento nella posizione k della lista lst | misto |
(list->vector lst) |
restituisce un vettore formato dagli elementi della lista lst | vettore |
(vector->list vctr) |
restituisce una lista formata dagli elementi vel vettore vctr | vettore |
Funzioni particolari che agiscono sulle liste sono la funzione apply, map e for-each:
| Funzioni | Risultato restituito |
|---|---|
(apply f lst) |
esegue la funzione f usando come elementi quelli presenti nella lista |
(map f lst1...lstN) |
esegue la funzione f sugli elementi allo stesso indice della lista |
(for-each f lst1...lstN) |
esegue la funzione f sugli elementi delle liste |
Per spiegare meglio, facciamo un esempio:
> (define lst1 (list 2 3 4 5 6)) > (apply + lst1) > > 20 > (define lst2 (list 1 2 3 4 5)) > (map + lst1 lst2) > > (3 5 7 9 11)
Vettori
I vettori sono degli array standard, ovvero sono una struttura che contiene un solo tipo di dato, si rappresentano come una lista anticipata da un cancelletto, ovvero #(arg1 arg2... argN). Dove arg1 ha indice 0, ed argN ha indice N-1.
Le funzioni che Scheme fornisce per la gestione dei vettori, sono le seguenti:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(vector arg1 arg2 ... argN) |
costruisce un vettore formato dagli elementi arg1, arg2,..., argN | vettore |
(make-vector n) |
costruisce un vettore formato da n elementi vuoti | vettore |
(make-vector n arg) |
costruisce un vettore formato da n elementi di tipo arg | vettore |
(vector-length vctr) |
restituisce il numero di elementi del vettore vctr | numerico |
(vector-ref vctr idx) |
restituisce l'elemento nella posizione idx del vettore vctr | vettore |
(vector-set! vctr idx arg) |
imposta l'elemento del vettore vctr, all'indice idx al valore arg | vettore |
Porte
Le porte dette in breve sono dei flussi di dati che possono essere in ingresso o in uscita, hanno numerose funzioni tra le quali troviamo la lettura/scrittura dallo standard input/output (lettura/scrittura di caratteri da/nel terminale, un po' come il printf e lo scanf di C) e la gestione di files. Le porte si possono aprire in input (lettura di dati) ed in output (scrittura di dati).
Alcune delle funzioni particolari che suggerisce lo Scheme sono le seguenti:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(input-port? arg) |
arg è una porta in input? | booleano |
(output-port? arg) |
arg è una porta in output? | booleano |
(open-input-file str) |
apre un file il cui nome è la stringa str come porta in input | porta |
(open-output-file str) |
apre un file il cui nome è la stringa str come porta in output | porta |
(close-input-file str) |
chiude un file il cui nome è la stringa str, aperto in input | niente |
(close-output-file str) |
chiude un file il cui nome è la stringa str, aperto in output | niente |
Lettura dei dati
Le letture di dati, soprannominate in Scheme come "operazioni di input", avvengono tramite le seguenti funzioni:
| Funzioni | Risultato restituito | tipo |
|---|---|---|
(read-char port) |
legge il carattere successivo dalla porta port | carattere |
(peek-char port) |
da una copia del carattere successivo dalla porta port (non viene spostato il puntatore) | carattere |
(read port) |
legge dalla porta port | misto |
(eof-object port) |
siamo alla fine del file? | booleano |
Nota: se su read-char e read, non si specifica la porta port, la lettura avviene dallo standard input (lettura da console).
Scrittura dei dati
Le scritture di dati, soprannominate in Scheme come "operazioni di output", avvengono tramite le seguenti funzioni:
| Funzioni | Risultato restituito |
|---|---|
(write-char char port) |
scrive il carattere char sulla porta port |
(write obj port) |
scrive l'oggetto obj sulla porta port |
(display obj port) |
mostra l'oggetto obj attraverso la porta port |
(newline port) |
scrive una linea vuota sulla porta port |
Nota: se su write-char e write, non si specifica la porta port, la scrittura avviene sullo standard output (scrittura su console).
Definizione di procedure
Definizione di un dato
In Scheme la definizione di un qualsiasi tipo di dato avviene tramite define
Definizione di un valore numerico: > (define mio_numero 3)
Definizione di una stringa: > (define mia_stringa "Ciao Mondo")
Definizione di una lista: > (define mia_lista (list #T 6 2 #/G))
Quindi anche per le procedure, si usa define. Il metodo più semplice per creare una procedura che prenda un certo numero di argomenti, avviene sempre tramite define:
Definizione di una procedura: > (define (mia_procedura arg1 arg2... argN) ...)
Ma visto che in Scheme le procedure possono essere considerate come speciali variabili che contengono un riferimento ad il codice della procedura stessa, la definizione spesso avviene tramite la funzione lambda:
Definizione di una procedura, tramite la funzione lambda: > (define mia_procedura (lambda (arg1 arg2... argN) ...))
Lambda permette anche la definizione di procedure interne ad una stessa procedura, ovvero di procedure locali che non vengono eseguite, ma rimangono solo porzioni di codice, finché non vengono eseguite.
Costrutti fondamentali
Condizione semplice (if)
Dopo aver visto i tipi di dato e le funzioni per gestirli, ed aver finalmente capito come si definisce una procedura, passiamo ai costrutti fondamentali. In Scheme il costrutto fondamentale utilizzato è l'if, l'if si presenta nel seguente modo
> (if condizione espressione_nel_caso_la_condizione_sia_vera
eventuale_espressione_nel_caso_la_condizione_sia_falsa)
;dice se l'argomento fornito e' uguale o diverso da 5
(define (prova_if arg1)
(if (= arg1 5) "l'argomento fornito e' 5"
"l'argomento fornito e' diverso da 5"))
Si potrebbe cioè dire che l'if di Scheme contiene in sè anche l'else degli altri linguaggi di programmazione.
Condizione composta (cond)
È praticamente un if multiplo si presenta nel seguente modo:
> (cond (prima_condizione espressione) (seconda_condizione espressione) ... (else espressione))
Ci sono un paio di cose da notare:
- l'else non è obbligatorio, si può omettere nel caso in cui non ce ne sia la necessità (cioè solo quando almeno un caso è verificato, altrimenti genererà un errore di Run-time).
- Si tratta di una funzione derivata, implementabile tramite l'if ed il costrutto begin.
Condizione basata sul valore restituito da un'espressione (case)
Si tratta di un if con una singola espressione, che una volta che è stata valutata, può assumere uno dei valori specificati nella struttura come val1, val2, val3:
> (case espressione_che_viene_valutata ((val1) espressione) ((val2) espressione) ... (else espressione))
Come nel caso del costrutto cond, l'else è opzionale.
Blocchi di espressioni (begin)
Come specificato prima, per esprimere un blocco di espressioni in scheme è necessario usare la funzione begin:
> (begin prima_espressione
seconda_espressione
...
n-esima_espressione
)
Questo permette ad esempio in un if di poter specificare come espressione, molte espressioni tutte racchiuse dal begin.
Un costrutto non fondamentale (do)
Essendo un linguaggio funzionale, in Scheme sarebbe bello poter usare sempre l'if e la ricorsione ma visto che ciò risulta a volte più complicato del previsto, Scheme mette a disposizione degli utenti il costrutto do. do permette di fare dei cicli, simili ai for/while di altri linguaggi di programmazione, si presenta sotto diverse forme:
La prima che assomiglia al costrutto do-until di java, è il seguente:
> (do ()
(condizione_di_uscita eventuale_espressione_da_eseguire_prima_dell_uscita)
prima_espressione_del_ciclo
seconda_espressione_del_ciclo
...
n-esima_espressione_del_ciclo
)
Si guarda la condizione di uscita, se è vera vengono valutate le espressioni successive ovvero: prima_espressione_del_ciclo, seconda_espressione_del_ciclo... n-esima_espressione_del_ciclo, e tutto questo viene fatto finché la condizione_di_uscita non fallisce.
La seconda forma, assomiglia molto ai generici costrutti for:
> (do ((variabile valore_iniziale_della_variabile passo))
(condizione_di_uscita eventuale_espressione_da_eseguire_prima_dell_uscita)
prima_espressione_del_ciclo
seconda_espressione_del_ciclo
...
n-esima_espressione_del_ciclo
)
Praticamente il ciclo si basa sui valori che assume la variabile, questa viene inizializzata ad un certo valore ed incrementata/diminuita (sono possibili anche diverse operazioni) finché non raggiunge un certo valore, ovvero rispetta la condizione_di_uscita.
;esempio che visualizza i numeri naturali inferiori alla variabile numero
(define (prova_do numero)
(do ((indice 0 (+ indice 1)))
((>= indice numero))
(display indice)
(newline)
))
Programmare in Scheme
Scheme per sua definizione prevede la programmazione tramite ricorsione, detta brutalmente si usano costrutti come if e cond, in cui viene richiamata la funzione stessa con particolari parametri.
La ricorsione semplice si ottiene richiamando un'unica volta la procedura stessa, supponiamo ad esempio di non avere a disposizione il costrutto *, e di voler definire una moltiplicazione tramite l'addizione. visto che k*n equivale a k+k+...+k con k ripetuto n volte, allora potremo scrivere il seguente codice:
(define (molt a b)
(if (= a 0) 0
(+ b (molt (- a 1) b))))
In questo esempio si a molt ripetuto all'interno di se stesso. Come funziona questa ricorsione? Supponiamo di avere (molt 3 4), il risultato atteso è quello di 3*4=12. Ma vediamo da vicino il flusso di esecuzione:
> (molt 3 4) [prima iterazione: ricorsione] (+ 4 (molt (- 3 1) 4)) [seconda iterazione: ricorsione] (+ 4 (+ 4 (molt (- 2 1) 4))) [terza iterazione: ricorsione] (+ 4 (+ 4 (+ 4 (molt (- 1 1) 4)))) [quarta iterazione: si è nella condizione in cui a è uguale a 0, si sostituisce (molt 0 4) con 0] (+ 4 (+ 4 (+ 4 0))) [prima risoluzione] (+ 4 (+ 4 4)) [seconda risoluzione] (+ 4 8) [restituzione del risultato] 12
Un secondo tipo di ricorsione prevede una ricorsione che si dirama, ad ogni iterazione. Vediamone un esempio tramite fibonacci.
(define (fibonacci n)
(cond ((= n 1) 1)
((= n 2) 2)
(else (+ (fibonacci (- n 1)) (fibonacci (- n 2))))))
Anche se è possibile descrivere il flusso d'esecuzione come sopra, questo cresce molto in fretta (vedere la Teoria della complessità computazionale), e quindi non verrà riportato.
Esempi vari di programmazione in Scheme
Un esempio di programma che interagisce con l'utente:
(define (maxpot b n k) (if (not (>= n (expt b k))) (sub1 k) (maxpot b n (add1 k))))
(define b 0)
(define n 0)
(quote "Ora sara' calcolata la massima potenza per b^k <= n")
(quote "Inserisci ora b:")
(set! b (read))
(quote "Inserisci ora n:")
(set! n (read))
(if (and (> b 1) (> n 0))
(string-append "La massima potenza che soddisfa b^k <= n e: " (number->string (maxpot b n 0)))
(quote "E' subentrato un errore: devi aver imposto b<=1 e/o n<=0"))
Implementazione del problema del tavolo rotondo (o di Cesare):
(define (aski s);position in A.S.C.I.I.
(char->integer (string-ref s 0)))
(define (retro s);from A.S.C.I.I. to string
(list->string (list (integer->char s))))
(define (dl s) ;delete last "char"
(substring s 0 (- (string-length s) 1)))
(define (sl s) ;select last "char"
(substring s (- (string-length s) 1) (string-length s)))
(define (lwc? s) (and (> (aski s) 96) (< (aski s) 123))) ;lower-case?
(define (upc? s) (and (> (aski s) 64) (< (aski s) 91))) ;upper-case?
(define (modGC old n new) ;modulo gcesare
(define (h s) (modGC (dl old) n (string-append (retro s) new)));applicazione principale tail-recursion
; (aski (sl old)) e' l'unita' carattere in numero, sarebbe un bene rinominarla!,con un let ch ad esempio, ma dove? cosi' come (sl old)...
; la seconda e la terza condizione andrebbero riunite in una sola a cui vanno cambiati due caratteri..min (65 o 97) e max (90 o 122)
(cond ((string=? "" old) new) ;condizione di uscita
((and (lwc? (sl old)) (> (+ n (aski (sl old))) 122)) (h (+ 97 (- (sub1 n) (- 122 (aski (sl old)))))));gestione del riporto
((and (upc? (sl old)) (> (+ n (aski (sl old))) 90)) (h (+ 65 (- (sub1 n) (- 90 (aski (sl old)))))))
((not (or (lwc? (sl old)) (upc? (sl old)))) (h (aski (sl old))));eccezioni:numeri, spazi bianchi ecc.
(else (h (+ n (aski (sl old))))))); siamo nella normalita', l'alfabeto non deve nemmeno cominciare dall'inizio
(define (gcesare old n w) (if (and (< n 26) (> n 0))
(cond ((string=? w "cod") (modGC old n "")) ((string=? w "dec") (modGC old (- 26 n) "")) (else "opzione non valida, riprovare con dec o cod"))
"n deve essere un numero, compreso tra 0 e 26, estremi esclusi!"))
Un esempio più complesso, il gioco Tic Tac Toe (semplice implementazione ASCII):
(define n 0) ;input
(define (slst? l) (if (null? l) #t (if (number? (car l)) #f (slst? (cdr l))))) ;symbolic list?
(define (view l) (begin (display "La situazione attuale e' la seguente: \n") ;Visualizzatore ^_^
(display (cons (car l) (cons (cadr l) (list (caddr l))))) (newline)
(display (cons (cadddr l) (cons (cadddr (cdr l)) (list(cadddr (cddr l)))))) (newline)
(display (cdddr(cdddr l))) (newline)))
(define (free? l e) (if (null? l) #f (if (not (equal? (car l) e)) (free? (cdr l) e) #t)))
(define (tr l e s) ;trova e rimpiazza
(if (equal? (car l) e) (cons s (cdr l))
(cons (car l) (tr (cdr l) e s))))
(define (win l wpos) (cond ((null? wpos) #f) ; posizione vincente? ->vai a win?..
((eqc? (car wpos) l) #t)
(else (win l (cdr wpos)))))
(define (win? l)(win l '((1 2 3) (4 5 6) (7 8 9) (1 4 7) (2 5 8) (3 6 9) (1 5 9) (7 5 3)))) ;posizioni vincenti
(define (eqc? l1 l2) (if (null? l1) #t (if (cc l2 (car l1)) (eqc? (cdr l1) l2) #f))) ;gli elementi della lista <l1> compaiono nella lista <l2>?
(define (cc l e) (if (null? l) #f (if (equal? (car l) e) #t (cc (cdr l) e)))) ;<e> e' contenuto nella lista <l>?
(define (wplay genlst plslst mnslst turn)
(let ((wis '(display "Ha vinto il giocatore: ")))
(view genlst)
(cond ((win? plslst) (eval wis) (display "+"))
((win? mnslst) (eval wis) (display "-"))
((slst? genlst) (display "Parita', non ha vinto nessuno!"))
(else (begin (display "Inserisci un numero,da 1 a 9, e' il tuo turno ") (display turn) (newline)
(set! n (read)) (display "Hai inserito: ") (display n) (newline)
(if (number? n)
(if (< n 10)
(if (free? genlst n)
[if (equal? turn '+) (wplay (tr genlst n '+) (append plslst (list n)) mnslst '-)
(wplay (tr genlst n '-) plslst (append mnslst (list n)) '+)]
(begin (display "Il posto inserito e' occupato\n") (wplay genlst plslst mnslst turn)))
(begin (display "Il posto inserito e' inesistente\n")(wplay genlst plslst mnslst turn)))
(begin (display "Il posto e' indicato tramite un numero da 1 a 9\n")(wplay genlst plslst mnslst turn))))))))
(define play (begin (display "Inizio del gioco, comincia + .\n")(wplay (list 1 2 3 4 5 6 7 8 9) (list '+) (list '-) '+)))
Altri progetti
Wikimedia Commons contiene immagini o altri file su Scheme
Collegamenti esterni
Implementazioni
- (EN) Drscheme interprete Open Source per tutti i sistemi operativi
- (EN) Chez Scheme interprete freeware per Microsoft Windows e Unix
- (EN) Chicken compilatore Scheme-to-C
- (EN) Bigloo compilatore Scheme-to-C e Scheme-to-Java compiler
- (EN) Kawa ambiente Scheme scritto in Java, che compila codice Scheme in bytecode Java
Altre risorse
- (EN) A large collection of Scheme resources
- (EN) Scheme Requests for Implementation (SRFI)
- (EN) How to Design Programs
- (EN) Una bibliografia sulla ricerca correlata a Scheme, con link a molti articoli accademici, comprese le originali Lambda Papers
