Planche : 1
Planche : 2
Abstractions syntaxiques
Elles permettent d'introduire et d'user d'abréviations qui sont
spécifiées comme des règles de réécriture. On peut toujours se passer
de macros!
Un appel à une macro ressemble à une application fonctionnelle (mais
n'en est pas une):
(macro paramètres...)
L'expansion revient à réécrire cette abréviation en une forme
équivalente qui sera alors substituée en lieu et place de
l'abréviation originale. Les formes spéciales
let, letrec, cond sont, entre autres, des
macros.
Premier exemple:
(define-macro (list . terms)
;
;
;
(if (pair? terms)
(cons 'cons
(cons (car terms)
(cons (cons 'list (cdr terms))
'() ) ) )
''() ) )
Second exemple:
(define-macro (cond . clauses)
;
;
;
(if (pair? clauses)
(list 'if (caar clauses)
(cons 'begin (cdar clauses))
(cons 'cond (cdr clauses)) )
'#f ) )
Planche : 3
La notation backquote
Dans une expression à évaluer, tout est à évaluer sauf ce qui est sous
quote. Dans la synthèse d'une expression par
backquote, rien n'est à évaluer sauf ce qui est précédé par
, ou ,@
`(a b) º '(a b)
`(a ,b) º (cons 'a (cons b '()))
º (list 'a b)
º (append '(a) (list b))
`(a ,@b c) º (cons 'a (append b '(c))
Ainsi peut-on réécrire la définition de cond en:
(define-macro (cond . clauses)
(if (pair? clauses)
`(if ,(caar clauses)
(begin ,@(cdar clauses))
(cond ,@(cdr clauses)) )
`#f ) )
En fait, ces notations sont des abréviations semblables à celle
portant sur quote. Bien sûr, quasiquote et les
autres sont des macros.
`expression est lu comme (quasiquote expression)
,expression est lu comme (unquote expression)
,@expression est lu comme (unquote-splicing expression)
Planche : 4
Le mécanisme d'expansion
En fait la boucle d'interaction ressemble à:
(define (toplevel)
(display (evaluate (check-syntax (expand (read))) global-env))
(toplevel) )
(define (expand e)
(if (pair? e)
(let ((p (assoc (car e) macro-env)))
(if (pair? p)
(expand (apply (cdr p) (cdr e)))
(expandlis e) ) )
e ) )
(define (expandlis e*)
(if (pair? e*)
(cons (expand (car e*))
(expandlis (cdr e*)) )
e* ) )
(define macro-env
(list (cons 'quote (lambda (data) `',data))
(cons 'lambda (lambda (vars . body)
`(lambda ,vars . ,(expandlis body)) ))
(cons 'quasiquote (lambda (e) ...))
(cons 'define-macro
(lambda (call . body)
(set! macro-env
(cons (cons ',(car call)
(evaluate `(lambda ,(cdr call)
,@body )
predefined-env ) )
macro-env ) ) ) ) ) )
Planche : 5
Le let nommé
(let name ((var1 form1)
...
(varN formN) )
corps )
(let ()
(define (name var1 ... varN)
corps )
(name form1 ... formN) )
(letrec ((name (lambda (var1 ... varN)
corps )))
(name form1 ... formN) )
(define (fact n)
(let iterate ((n n)
(r 1) )
(if (= n 1)
r
(iterate (- n 1) (* r n)) ) ) )
º
(define (fact n)
(define (iterate n r)
(if (= n 1)
r
(iterate (- n 1) (* r n)) ) )
(iterate n 1) )
Planche : 6
Le grand tableau
Comment est traité un programme:
-
read: Des caractères sont lus, les
macro-caractères sont traités et une Sexpression est
construite.
- La Sexpression est expansée et doit mener à un programme.
- Quelquefois (et notamment en DrScheme) la syntaxe est vérifiée
et notamment la présence des define pour les variables
globales de l'utilisateur.
- le programme est évalué.
Planche : 7
La notion de continuation
Il n'y a pas que l'expression à évaluer et l'environnement lexical où
l'évaluer, il y a aussi une entité mystérieuse, la
continuation, qui est celle à qui l'on devra retourner le résultat de
l'évaluation (l'appelant dans le cas d'une fonction).
Dans l'expression (* (+ 1 2) (/ 6 3)), lorsque l'on calcule
(+ 1 2), le contexte est (* [] (/ 6 3)). Ce contexte
peut être représenté par une fonction unaire
(lambda (u) (* u (/ 6 3))).
En Scheme on peut capturer les continuations et les utiliser comme des
fonctions unaires.
(* (letcc k (+ 1 2)) (/ 6 3)) ;
(* (letcc k (+ (k 1) 2)) (/ 6 3)) ;
letcc existe en DrScheme.
On peut ainsi réaliser aisément des échappements.
(define (times-list l)
(letcc exit
(define (scan l)
(if (pair? l)
(let ((n (car l)))
(if (= 0 n)
(exit 0)
(* n (scan (cdr l))) ) )
1 ) )
(scan l) ) )
En fait, letcc n'est qu'une macro au-dessus de la fonction
très spéciale call/cc.
(letcc var body) º (call/cc (lambda (var) body))
call/cc est une fonction unaire qui prend en argument une
fonction unaire qui sera invoquée avec la continuation courante
(encore une autre fonction unaire). Les règles sont:
(call/cc j)k º (j k)k
(k value)k' º valuek
Planche : 8
Un exemple
Écrire un semi-prédicat heading qui prend une liste et
retourne le préfixe de cette liste conduisant au symbole qui y
apparaît au moins deux fois et dont la seconde occurrence est la plus
proche du début de la liste. Ainsi:
(heading '(a b c d c a)) ® (a b)
(define (heading l)
(letcc exit
(define (scan l seen)
(if (pair? l)
(let ((p (assq (car l) seen)))
(if (pair? p)
((cdr p) '())
(letcc k
(cons (car l)
(scan (cdr l)
(cons (cons (car l) k)
seen ) ) ) ) ) )
(exit #f) ) )
(scan l '()) ) )
Détails de l'évaluation et des échappements:
(heading '(a b c d c a))k0
(scan '(a b c d c a) '())k0
(cons 'a (scan '(b c d c a) '((a . k0)))k1)k0
(cons 'a (cons 'b (scan '(c d c a) '((b . k1)(a . k0)))k2)k1)k0
(cons 'a (cons 'b (cons 'c (scan '(d c a)
'((c . k2)(b . k1)(a . k0)))k3)k2)k1)k0
(cons 'a (cons 'b (cons 'c (cons 'd (scan '(c a)
'((d . k3)(c . k2)(b . k1)(a . k0)))k4)k3)k2)k1)k0
(cons 'a (cons 'b (cons 'c (cons 'd (k2 '())k4)k3)k2)k1)k0
(cons 'a (cons 'b '())k1)k0
'(a b)
Planche : 9
Continuations
Toutes les formes de contrôle séquentielles peuvent être réalisées
avec les continuations: échappements, coroutines, moteurs, futurs,
multi-tâche non-préemptifs ...
La continuation représente à tout instant le contexte de calcul
c'est-à-dire ce qu'il reste à faire. Il n'y a pas de restriction sur
son emploi: c'est strictement plus puissant que
setjmp/longjmp de C ou le
try/finally de Java.
Pourtant, il existe une transformation de programme qui prend un
programme avec des call/cc et le transforme en un programme
sans call/cc. On la nomme « transformation CPS » pour
Continuation Passing Style, elle fait apparaître explicitement
les continuations que call/cc fabriquait.
Cette transformation consiste à demander à chaque fonction de prendre
un argument supplémentaire: la continuation et à ne plus jamais
retourner de valeur mais plutôt la fournir à la continuation. Voici la
factorielle en style CPS:
(define (fact n k)
(if (= n 1)
(k 1)
(fact (- n 1) (lambda (r) (k (* n r)))) ) )
(fact 5 (lambda (x) x))
(fact 5 (lambda (x) (* x x)))
Ce style qui consiste à donner en argument(s) le(s) receveur(s) des
calculs se nomme le style par continuation. Il est par exemple utile
lorsque l'on retourne plusieurs résultats (cf. values et
call-with-values) ou que l'on manipule explicitement
plusieurs continuations (comme un moteur Prolog) ou que l'on veut
écrire un interprète d'un langage procurant des primitives manipulant
les continuations.
(define (lineariser e)
(if (pair? e)
(case (car e)
((+ - * /)
(cons (car e) (apply append (map lineariser (cdr e)))) )
(else (error 'lineariser 'operateur-inconnu (car e))) )
(list e) ) )
(lineariser '(+ (* 2 3) 4)) ;
(define (elever l)
(define (analyser l k)
(if (pair? l)
(case (car l)
((+ - * /)
(analyser (cdr l)
(lambda (e1 l1)
(analyser l1
(lambda (e2 l2)
(k `(,(car l) ,e1 ,e2)
l2 ) ) ) ) ) )
(else (k (car l) (cdr l))) )
(error 'elever 'termes-manquant l) ) )
(analyser l (lambda (e ll)
(if (null? ll)
e
(error 'elever 'termes-en-trop ll) ) )) )
Un autre exemple relatif à un moteur de cédérom qui mémorise des
continuations sous forme d'URL:
<-URL HTML->
(begin ;
(letcc k1
(show coursA k1) ) ;
(analyze ;
(letcc k2
(propose exoB k2) ) ) ) ;
Ce document a été traduit de LATEX par
HEVEA.
Macros et continuations