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 :
;;;
(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)
;;
(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)))) )
((-)
;;
(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) ;
(divide
n p (lambda (q r)
(if (= r 0)
(if (= p 1)
(k 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.
;;;
(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) ) )