Le avventure di un Pythonista in Schemeland/7

Mini-rassegna bibliografica

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

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!