Le avventure di un Pythonista in Schemeland/7

Alcuni lettori mi hanno chiesto se c’è qualche libro
per imparare Scheme che io consiglio particolarmente. In effetti
esistono molti buoni testi, ma nessuno che mi soddisfa al cento per cento
e che io raccomanderei senza riserve ai lettori di Stacktrace.
Questo è il motivo per cui finora sono stato restio a
parlare di bibliografia. C’è anche da dire che io sono uno di quelli che impara
dai manuali e dai newsgroup più che dai libri, quindi non sono ferratissimo
sulla letteratura esistente. Io qui citerò soltanto risorse disponibili in rete.
I lettori che ne sanno più di me in materia di letteratura sono caldamente
invitati a postare le loro raccomandazioni come commenti a questa puntata.


Mini-rassegna bibliografica

books.jpg

Ciò detto, la referenza principale su cui io ho imparato Scheme
è Teach Yourself Scheme in Fixnum Days di Dorai Sitaram, di cui si
possono dire molte cose buone. Si tratta di un report autoconsistente
e molto ben scritto, soprattutto nella prima parte. È ricco di informazioni,
ma nello stesso tempo conciso e con un numero di pagine
limitato, tale da essere leggibile da programmatori Scheme della
domenica, ovverossia persone che di lavoro usano un altro linguaggio
e non hanno troppo tempo da dedicare a Scheme (suppongo che questo
descriva la maggior parte dei lettori di Stacktrace).
D’altra parte Teach Yourself Scheme in Fixnum Days è un testo un pò
vecchiotto ed ignora completamente la macrologia moderna di Scheme, basata
sul pattern matching. Descrive soltanto le macro tradizionali
di tipo define-macro, che molti nel mondo Scheme non amano. Il mio
scopo in questo serie è
di dare una descrizione moderna di Scheme, aggiornata all’R6RS; inoltre
voglio discutere in dettaglio la moderna macrologia di Scheme.
Un testo più moderno (ma che comunque non copre l’R6RS) è
The Scheme Programming Language (Third Edition)
di R. Kent Dybvig, che descrive molto bene le macro di tipo syntax-case,
ma è un libro di molte centinaia di pagine molto dense, un pò troppo da leggere per
dei programmatori della domenica. Forse il libro più recente su Scheme è
Programming Languages Application and Interpretation di
Shriram Krishnamurthi che è ottimo, soprattutto la parte sulle continuazioni,
ma anche questo è molto impegnativo, nasce come libro di testo per l’università e
non copre l’R6RS (a mia conoscenza non ci sono testi che coprono
l’R6RS, è uno standard troppo recente).
È invalsa la consuetudine di indicare i libri su Scheme con acronimi, quindi
i due libri precedenti sono spesso indicati come TSPL3 e PLAI; non c’è dubbio
però che l’acronimo più famoso sia SICP, ovverossia
Structure and Interpretation of Computer Programs
di Harold Abelson e Gerald Jay Sussman. Questo libro ha insegnato Scheme
a generazioni di studenti ed è considerato un cult, ma io personalmente
lo conosco pochissimo, quindi non posso commentare su di esso.

Come vedete i libri non mancano, essendo Scheme un linguaggio con una
grande tradizione didattica; quello che manca è il tempo per leggerli!
Questo è uno dei motivi per cui sto scrivendo le mie “Avventure” sotto
forma di articoli e non sotto forma di libro: un articolo di 5-6 pagine ha molti
più lettori di un libro di 500-600 pagine. Inoltre la forma di articolo mi permette
di mantenere uno stile informale con cui mi trovo più a mio agio.

Quoting

Chiusa la mini-rassegna bibliografica, torniamo al tema centrale di
questa puntata, ovverossia al concetto di code is data.
Una delle carattestiche distintive del Lisp e linguaggi derivati è
l’esistenza di un operatore di quoting denotato con un apice
– l’apice è un’abbreviazione per quote, scrivere
'expr è lo stesso che scrivere (quote expr) – e
definito come segue:

  1. su oggetti primitivi come numeri, stringhe letterali, simboli, eccetera
    corrisponde all’identità
> '1
1
> '"hello"
"hello"
> ''a
'a
  1. su oggetti composti (espressioni) l’operazione di quoting trasforma
    un frammento di codice in una lista; per esempio '(display
    "hello")
    corrisponde alla lista
> (list 'display '"hello")
(display "hello")

mentre '(let ((x 1)) (* 2 x)) corrisponde alla lista

> (list 'let (list (list 'x '1)) (list '* '2 'x))
(let ((x 1)) (* 2 x))

e così via. Questo significa che qualunque programma Scheme/Lisp ammette una
rappresentazione naturale come lista (nidificata) di simboli e valori primitivi:
code is data. D’altra parte, qualunque lista nidificata di simboli e valori
primitivi che corrisponde ad un programma Scheme/Lisp sintatticamente valido
può essere valutata, sia a runtime con eval che a compilation time
con il meccanismo delle macro. Le conseguenze sono affascinanti: visto
che ogni programma non è altro che una lista, diventa pensabile scrivere
programmi che costruendo liste, scrivono altri programmi
e cose del genere. Tutto questo si può fare anche in altri linguaggi: per
esempio in Python potete generare delle stringhe corrispondenti al
codice sorgente di funzioni e classi e valutarle con vari meccanismi
(eval, exec, __import__, compile, etc) oppure in C/C++
avete il meccanismo delle macro offerto dal preprocessore; tuttavia
in nessun linguaggio
la generazioni di codice è così conveniente come in Scheme/Lisp dove
è builtin, grazie alle -expressioni o, se volete, grazie alle parentesi.

Quasi-quoting

In tutti i linguaggi di scripting esiste una qualche forma di string interpolation;
per esempio in Python potete scrivere

def say_hello(user):
return "hello, %(user)s" % locals()

In Scheme/Lisp, esiste anche una forma di list interpolation:

> (define (say-hello user)
`("hello" ,user))

> (say-hello "Michele")
("hello" "Michele")

L’operatore ` (backquote o quasiquote) introduce una lista da interpolare
(template)
in cui è possibile sostituire delle variabili tramite l’operazione di unquoting,
denotata con una virgola (comma), nel nostro caso il nome dell’utente ,user.
La funzione say-hello prende una stringa nome utente e ritorna una lista
contenete la stringa "hello" e il nome dell’utente.
Oltre all’operatore unquote esiste anche l’operatore unquote-splice
(scritto ,@ e letto comma-at) che opera su delle liste come segue:

> (let ((ls '(a b c))) `(func ,@ls))
(func a b c)

In pratica ,@ls “scompatta” la lista nei sui componenti: senza la splice,
otterremmo

> (let ((ls '(a b c))) `(func ,ls))
(func (a b c))

La potenza della quasiquotation
sta nel fatto che siccome in Scheme/Lisp il codice non è altro che una lista,
è possibile facilmente eseguire del codice costruito a partire da dei template.
Per esempio, supponiamo di voler valutare un espressione Scheme in un
dato contesto, dove il contesto è definito in termini di una lista di nomi/valori:

(eval-with-context '((a 1)(b 2) (c 3))
'(* a (+ b c)))

Come possiamo definire la funzione eval-with-context? La risposta
è semplice, usando eval ed un template per un’espressione let:

(define (eval-with-context ctx expr)
(eval `(let ,ctx ,expr) (environment '(rnrs))))

Notate che eval richiede un secondo argomento, che specifica il linguaggio
conosciuto dall’interprete; nel nostro caso
abbiamo imposto che eval conosca tutte le procedure e macro
dello standard rnrs più recente (cioè l’R6RS). La specificazione dell’
environment ha la stessa sintassi di un import perché in pratica
si tratta dello stesso concetto ed è possibile importare nell’environment
di eval moduli definiti dall’utente.
eval è estremamente potente ed a volte è l’unica soluzione possibile,
in particolare quando si vuole poter eseguire codice generico a runtime,
ovverossia quando si sta scrivendo un interprete; molte altre volte però
si vuole eseguire codice conosciuto a tempo di compilazione e si
può far fare il lavoro di eval più elegantemente ad una macro.
Questo significa in pratica che si sta scrivendo un compilatore.

Programmi che scrivono programmi

writer.jpg

Una volta che si è capito che il codice non è altro che un tipo di
dato, diventa semplice scrivere programmi che prendono in input un
sorgente e generano in output un altro sorgente: in pratica, diventa
semplice scrivere un interprete od un compilatore. La differenza è
che nel primo caso il codice sorgente viene convertito ed eseguito
(interpretato) pezzo a pezzo, mentre nel secondo il codice originale
viene convertito (compilato) in blocco. Supponiamo per esempio di
voler scrivere un compilatore che converte il programma

(begin
(define n 3)
(display "begin program\n")
(for i from 1 to n (display i))
(display "\nend program\n"))

nel programma

(begin
(define n 3)
(display "begin program\n")
(let loop (( i 1))
(unless (>= i n) (display i) (loop (add1 i))))
(display "\nend program\n")))

e più in generale converte

(begin                                 (begin
(expr1 ...) (expr1' ...)
(expr2 ...) ==> (expr2' ...)
... ...
(exprN ...)) (exprN' ...))

dove le espressioni possono essere di tipo for o di qualunque altro tipo
non contenente una sotto-espressione di tipo for.
begin è la sintassi standard di Scheme per raggruppare
espressioni multiple in una espressione singola senza introdurre un
nuovo scope
(se volete introdurre un nuovo scope vi serve let)
e preservando l’ordine di valutazione (nei linguaggi funzionali
tipo Scheme l’ordine di valutazione tipicamente non è specificato
dallo standard).

Si può scrivere tale compilatore come segue:

(import (rnrs) (only (ikarus) pretty-print))

;; a very low-level approach
(define (convert-for-into-loop begin-list)
(assert (eq? 'begin (car begin-list)))
`(begin
,@(map (lambda (expr)
(if (eq? 'for (car expr)) (apply convert-for (cdr expr)) expr))
(cdr begin-list))))

(define (convert-for i from i0 to i1 . actions)
;; from must be 'from and to must be 'to
(assert (and (eq? 'from from) (eq? 'to to)))
`(let loop ((i ,i0))
(unless (>= i i1) ,@actions (loop (+ i 1)))))

(pretty-print
(convert-for-into-loop
'(begin
(define n 3)
(display "begin program\n")
(for i from 1 to n (display i))
(display "\nend program\n"))))

Eseguendo lo script non avrete difficoltà a verificare che
effettivamente transforma l’espressione for in un named let.
Non sarebbe difficile estendere il compilatore e renderlo in grado di
maneggiare sotto-espressioni (basta farlo diventare
ricorsivo) e strutture più generali del begin: ma questo lo lascio
per esercizio. Vedremo in una puntata futura, quando parleremo dei
code-walker, cosa si può fare per convertire codice sorgente
generico. In generale convert-for-into-loop può essere pensato
come un preprocessore che espande il codice sorgente in linguaggio di
alto livello che comprende l’espressione for come primitiva in
codice sorgente in un linguaggio di basso livello che non comprende la
primitiva for. Preprocessori di questo tipo possono essere
implementati esternamente al linguaggio, ma anche internamente, usando
il meccanismo builtin delle macro. Le macro sono l’argomento su cui
ci focalizzeremo nelle prossime puntate. La loro potenza
sta nel fatto che esse forniscono
delle potenti funzionalità di pattern matching al cui paragone
l’esempio appena dato che usa solo operazioni di base sulle liste quali
car/cdr/map appare assolutamente primitivo. Tanto per solleticare
l’appetito ed aumentare l’attesa della prossima puntata, vi faccio
vedere come appare convert-for scritto come una macro:

(define-syntax for
(syntax-rules (from to); literals
((for i from i0 to n do-action ...)
(let loop ((i i0))
(unless (>= i n) do-action ... (loop (+ i 1)))))))

Notate l’assenza di punteggiatura (niente backquote, niente virgole, niente
comma splice) a parte i tre puntini
che indicano semplicemente la ripetizione di zero o più elementi.
convert-for-into-loop diventa inutile perché tutti i cicli for
definiti nel codice verranno automaticamente convertiti dal compilatore
senza che voi facciate nulla.

La prossima puntata sarà dedicata interamente alle macro. Non mancate!

Comments

  1. Mi permetto io di fornire qualche informazione in più intorno a SICP (altrimenti noto come “Wizard Book”, a causa del disegno in copertina; qualcuno lo chiama anche “Purple Book”, per ragioni ovvie).

    “Structure and interpretation of computer programs” è stato usato per anni, al MIT, come testo per il corso introduttivo di informatica, ma non vuol dire che sia un libro dallo scarso respiro, anzi. È un libro sulla programmazione, prima ancora che un libro su Scheme: chi riesce a leggerlo da cima a fondo, risolvendo tutti gli esercizi, avrà affrontato tali e tanti temi da potersi ritenere un informatico più che esperto: programmazione funzionale (ovviamente), programmazione logica, programmazione con vincoli, compilatori.

    Tanto per dare un’idea, riporto il testo dell’ultimo esercizio proposto dal libro (5.52) “As a counterpoint to exercise 5.51, modify the compiler so that it compiles Scheme procedures into sequences of C instructions. Compile the metacircular evaluator of section 4.1 to produce a Scheme interpreter written in C.”

    Personalmente lo apprezzo poi per lo stile, per l’inclinazione matematica dei tanti problemi proposti per gli esempi, e per la ricchezza di riferimenti. Le note a piè pagina formano poi un sottotesto che è possibile e piacevole leggere a parte. Bello.

    SICP è disponibile in rete completamente, e ne esiste anche una declinazione in video: il ciclo di lezioni tenute nel 1986 per Hewlett-Packard da Hal Abelson e Gerald Jay Sussman sono liberamente scaricabili. I video sono molto curati e secondo me ben fatti. Direi anche molto divertenti.

  2. Grande Michele! Ottimo articolo! Ti seguo sempre, “silenziosamente”, ma attentamente. Bravo!

  3. Marco Benelli says:

    “How to Design Programs”
    Fellesein, Findler, Flatt, Krishnamurthi

    http://www.htdp.org/

    E’ considerato da molti l’erede del SICP, e, come questo, e’ piu’ un testo
    sulla programmazione che non su Scheme.

    Altri testi e tutorials si possono trovare su:

    http://www.schemers.org/

    Inoltre io ho sempre trovato interessante:

    http://library.readscheme.org/

  4. @Marco grazie, non lo conoscevo

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.