Planche : 1




Le langage Scheme

Revision: 1.6





  Macros et continuations





Christian Queinnec   UPMC--LIP6


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)
  ; (list e1 e2 ... en)
  ; º (cons e1 (list e2 ... en))
  ; Cas de base: (list) º '()
  (if (pair? terms)
      (cons 'cons
      (cons (car terms)
      (cons (cons 'list (cdr terms))
            '() ) ) )
      ''() ) ) 

Second exemple:
(define-macro (cond . clauses)
  ; (cond (p1 e11 ... e1n1) (p2 e21 ... e2n2) ...)
  ; º (if p1 (begin e11 ... e1n1) (cond (p2 e21 ... e2n2) ...))
  ; Cas de base: (cond) º #f
  (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:
  1. read: Des caractères sont lus, les macro-caractères sont traités et une Sexpression est construite.
  2. La Sexpression est expansée et doit mener à un programme.
  3. 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.
  4. 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))      ; ® 6
(* (letcc k (+ (k 1) 2)) (/ 6 3))  ; ® 2

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 (varbody))

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))  ; ® (+ * 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                          ; <- /voir début
  (letcc k1                     
    (show coursA k1) )          ; -> /invoke/k1 montrer page cours
  (analyze                      ; analyser solution
   (letcc k2
     (propose exoB k2) ) ) )    ; -> /invoke/k2 proposer exercice


Ce document a été traduit de LATEX par HEVEA.