Précédent Index Suivant

7   Continuations



De la poursuite, interruption et reprise de calculs variés.

Échappement

Exercice 60 : Écrire une fonction prenant un arbre de nombres et retournant leur produit. Utiliser un échappement dès qu'un des facteurs est nul.

Solution de l'exercice 60 :
;;; Continuations: echappement
(define (multiplier-arbre n*)
  (call/cc 
   (lambda (exit)
     (define (iterer n*)
       (if (pair? n*)
           (* (iterer (car n*))
              (iterer (cdr n*)) )
           (if (null? n*) 1
               (if (= 0 n*)
                   (exit 0)
                   n* ) ) ) )
     (iterer n*) ) ) )

Exercice 61 : Écrire une fonction prenant un symbole, une liste de symboles et otant la première occurrence de ce premier de cette seconde. Le partage entre le résultat et le second argument doit être assuré. Le résultat doit être calculé en un seul balayage du second argument.

Solution de l'exercice 61 :
(define (oter-symbole s original-s*)
 (call/cc
  (lambda (k)
    (define (oter s*)
      (if (pair? s*)
          (if (eq? (car s*) s)
              (cdr s*)
              (cons (car s*) (oter (cdr s*))) )
          (k original-s*) ) )
    (oter original-s*) ) ) )

Exercice 62 : Modifier la fonction précédente de manière à ce qu'elle ôte toutes les occurrences du symbole dans la liste de symboles. Le partage doit toujours être maximal et le résultat acquis en un seul balayage.

Solution de l'exercice 62 :
(define (oter-completement-symbole s s*)
  (define (oter s* k)
    (if (pair? s*)
        (if (eq? (car s*) s)
            (oter-tout (cdr s*))
            (cons (car s*) (oter (cdr s*) k)) )
        (k) ) )
  (define (oter-tout s*)
    (call/cc
     (lambda (k)
       (oter s* (lambda () (k s*))) ) ) )
  (oter-tout s*) )

Passage de continuations

Exercice 63 : Écrire la fonction factorielle en usant de continuations explicites. Voici un exemple de mise en oeuvre du résultat:
? (KFACT 6 (LAMBDA (X) X))
= 720  

Solution de l'exercice 63 :
(define (kfact n k)
  (if (> n 1)
      (kfact (- n 1) 
             (lambda (r)
               (k (* n r)) ) )
      (k 1) ) )

Exercice 64 : Réécrire, en usant de continuations explicites, la fonction suivante:
(define (flatten e)
  (if (pair? e)
      (append (flatten (car e))
              (flatten (cdr e)) )
      (if (null? e) e (list e)) ) )

Solution de l'exercice 64 :
(define (kflatten e k)
  (if (pair? e)
      (kflatten (car e) 
                (lambda (ra)
                  (kflatten (cdr e)
                            (lambda (rb)
                              (k (append ra rb)) ) ) ) )
      (if (null? e) (k e) (k (list e))) ) )

Exercice 65 : Réécrire, en usant de continuations explicites, la fonction précédente légèrement modifiée. Prendre garde à l'ordre des calculs.
(define (flatten2 e)
  (define (flat l r)
    (if (pair? l)
        (flat (car l) (flat (cdr l) r))
        (if (null? l) r (cons l r)) ) )
  (flat e '()) )

Solution de l'exercice 65 :
(define (kflatten2 e k)
  (define (kflat l r k)
    (if (pair? l)
        ;; Le cdr est traité en premier.
        (kflat (cdr l) r (lambda (result)
                           (kflat (car l) result k) ) )
        (if (null? l) (k r) (k (cons l r))) ) )
  (kflat e '() k) )

Continuations à arguments multiples

Exercice 66 : Linéariser un arbre représentant une expression arithmétique (avec - unaire, + et - binaire). Voici quelques exemples:
? (LINEARISER '(+ (- 3) (* (- 2 3) 5)))
= (+ -- 3 * - 2 3 5)  

Solution de l'exercice 66 :
(define (lineariser e)
  (cond ((pair? e)
         (case (car e)
           ((+ *)
            (cons (car e) (apply append (map lineariser (cdr e)))) )
           ((-)
            ;; Distinguer les - unaires ou binaires.
            (case (length (cdr e))
              ((1) (cons '-- (lineariser (cadr e))))
              ((2) (cons '- (apply append (map lineariser (cdr e))))) ) ) ) )
        (else (list e)) ) )

Exercice 67 : Écrire maintenant une fonction inversant lineariser c'est-à-dire construisant l'expression initiale à partir de sa forme linéarisée.

Solution de l'exercice 67 :
(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) ) ) ) ) )
          ((--)
           (analyser (cdr l)
                     (lambda (e1 l1)
                       (k `(- ,e1) l1) ) ) )
          (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) ) )) )

Exercice 68 : L'identité de Bezout stipule que si n et p sont premiers entre eux, alors il existe des nombres u et v tels que un+vp = 1. Écrire une fonction calculant ces nombres u et v et les retournant à sa continuation. On pourra tester la fonction bezout grâce à:
(define (verifier-bezout n p)
  (bezout n p (lambda (u v)
                (+ (* u n) (* v p)) )) )

Solution de l'exercice 68 :
(define (bezout n p k)    ; assume n>p
  (divide
   n p (lambda (q r)
         (if (= r 0)
             (if (= p 1)
                 (k 0 1)  ; since 0 × 1 - 1 × 0 = 1
                 (error "not relatively prime" n p) )
             (bezout
              p r (lambda (u v)
                    (k v (- u (* v q))) ) ) ) ) ) )

Filtrage avec variables

On souhaite raffiner la fonction filtrer3 précédemment vue à l'exercice 20 et ci-dessous rappelée, pour lui ajouter un environnement, une A-liste permettant de mémoriser des expressions filtrées. Voir exemples plus bas.
;;; filtre ::= atome | ?- | ... | ( filtre . filtre )
(define (filtrer3 expression filtre)
  (define (filtrer3-liste expressions filtres)
    (if (pair? filtres)
        (if (equal? (car filtres) '...)
            (or (filtrer3-liste expressions (cdr filtres))
                (and (pair? expressions)
                     (filtrer3-liste (cdr expressions) filtres) ) )
            (and (pair? expressions)
                 (filtrer3 (car expressions) (car filtres))
                 (filtrer3-liste (cdr expressions) (cdr filtres)) ) )
        (equal? expressions filtres) ) )
  (or (equal? filtre '?-) 
      (if (equal? filtre '...)
          (error 'filtrer3 "... ne peut survenir ici")
          (if (pair? filtre) 
              (filtrer3-liste expression filtre)
              (equal? expression filtre) ) ) ) )

Exercice 69 : Réécrire tout d'abord la fonction filtrer3 avec des continuations. La continuation normale (de succès) représentera ce qu'il reste à effectuer si le filtrage marche. La continuation d'échec matérialise ce qu'il faut faire si le filtrage échoue. La continuation d'échec ne prend pas d'argument, la continuation de succès sera invoquée sur l'environnement (attendre l'exercice suivant pour qu'elle prenne son utilité) et la continuation courante d'échec. La fonction filtrer6 retournera en fin de calcul l'environnement que l'on prendra égal à () (dont on rappelle qu'en Scheme r4rs, il vaut Vrai).

Solution de l'exercice 69 :
(define (filtrer6 expression filtre)
  (define (filtrer6-liste expressions filtres env succes echec)
    (if (pair? filtres)
        (if (equal? (car filtres) '...)
            (filtrer6-liste expressions (cdr filtres) env succes 
                            (lambda ()
                              (if (pair? expressions)
                                  (filtrer6-liste (cdr expressions) filtres
                                                  env succes echec )
                                  (echec) ) ) )
            (if (pair? expressions)
                (filtrer6-expression
                 (car expressions) (car filtres) env
                 (lambda (env echec)
                   (filtrer6-liste (cdr expressions) (cdr filtres) env
                                   succes echec ) )
                 echec )
                (echec) ) )
        (if (equal? expressions filtres) (succes env echec) (echec)) ) )
  (define (filtrer6-expression expression filtre env succes echec)
    (if (equal? filtre '?-)
        (succes env echec)
        (if (equal? filtre '...)
            (error 'filtrer6 "... ne peut survenir ici")
            (if (pair? filtre)
                (filtrer6-liste expression filtre env succes echec)
                (if (equal? filtre expression)
                    (succes env echec)
                    (echec) ) ) ) ) )
  (filtrer6-liste expression filtre '() (lambda (env echec) env) (lambda () #f)) )

Exercice 70 : Les variables seront nommées par des symboles dont le nom commence par un point d'interrogation. Lorsqu'une variable est rencontrée la première fois, elle est liée à la valeur qu'elle filtre et, lorsque rencontrée les fois suivantes, elle devra être égale aux expressions filtrées. Voici quelques exemples, le premier filtre des listes de deux termes égaux (au sens de equal?), le second filtre des listes de deux termes contenant une même sous-expression.
? (FILTRER7 '(A A) '(?X ?X))
= ((?X . A)) 
? (FILTRER7
  '((A B C) (R G B))
  '((... ?X ...) (... ?X ...)))
= ((?X . B))  

Solution de l'exercice 70 :
(define (filtrer-variable? s)
  (and (symbol? s)
       (let ((str (symbol->string s)))
         (and (> (string-length str) 0)
              (char=? (string-ref str 0) #\?) ) ) ) ) 
(define (filtrer7 expression filtre)
  (define (filtrer7-liste expressions filtres env succes echec)
    (if (pair? filtres)
        (if (equal? (car filtres) '...)
            (filtrer7-liste expressions (cdr filtres) env succes 
                            (lambda ()
                              (if (pair? expressions)
                                  (filtrer7-liste (cdr expressions) filtres
                                                  env succes echec )
                                  (echec) ) ) )
            (if (pair? expressions)
                (filtrer7-expression (car expressions) 
                                     (car filtres) 
                                     env
                                     (lambda (env echec)
                                       (filtrer7-liste (cdr expressions) 
                                                       (cdr filtres) 
                                                       env
                                                       succes
                                                       echec ))
                                     echec )
                (echec) ) )
        (if (equal? expressions filtres) (succes env echec) (echec)) ) )
  (define (filtrer7-expression expression filtre env succes echec)
    (cond 
     ((equal? filtre '?-) (succes env echec))
     ((equal? filtre '...) (error 'filtrer7 "... ne peut survenir ici"))
     ((filtrer-variable? filtre)
      (let ((p (assq filtre env)))
        (if (pair? p)
            (if (equal? expression (cdr p))
                (succes env echec)
                (echec) )
            (succes (cons (cons filtre expression) env) echec) ) ) )
     ((pair? filtre) (filtrer7-liste expression filtre env succes echec))
     (else (if (equal? filtre expression)
               (succes env echec)
               (echec) ) ) ) )
  (filtrer7-expression expression filtre '() 
                       (lambda (env echec) env)
                       (lambda () #f) ) )


Précédent Index Suivant