continuation call/cc [Résolu]

[bazoga]

Bonsoir,

je suis débutant en programmation fonctionnelle et j'ai du mal à comprendre la notion de continuation mis en œuvre par la fonction call/cc, voici un exemple d'utilisation de la notion de mémorisation de continuations:

Code :

1
2
3
4
5
6
7
8
9
10
11
(define saved'*dammyvalue*) ;; pour mémoriser la continuation

(define (strange-sum l)  ;; la somme des nombre d'une liste
  (if (null? l)
      0
      (+ (car l) (if (null? (cdr l))
		     (call/cc (lambda (f)
				(set! saved f)
				(strange-sum (cdr l))))
		     (strange-sum (cdr l))))))

une deuxieme version

Code :

1
2
3
4
5
6
7
(define (strange-sum-0 l) 
  (cond ((null? l) 0)
	((zero? (car l)) (call/cc (lambda (f)
				    (set! saved f)
				    (strange-sum-0 (cdr l)))))
	(else (+ (car l) (strange-sum-0 (cdr l))))))

une troisiemme version

Code :

1
2
3
4
5
6
7
(define (strange-sum-1 l) 
  (if (null? l)
      0
      (begin
	(cond ((zero? (car l)) (call/cc (lambda (f) (set! saved f)))))
	(+ (car l) (strange-sum-1 (cdr l))))))

pouvez vous m'expliquer svp ce que représentent ces continuations ?

pour la premiere version il me semble que la continuation liée à la variable saved est : (lambda(trou) (s + trou) ou s est la somme des nombres de la liste.

pour la deuxième et la troisième version, j'attends vos explications.

E. Bazaoga
Cordialement

[ceciestunpseudo]

À défaut de mention contraire, je prend pour principe que tu suis un cours de Scheme et que tu t'interroges sur ce que tu as vu en cours. Mes réponses vont donc en ce sens.

Il faut que tu comprennes la continuation obtenue par call/cc comme simplement : les calculs qu'ils restent à faire. Ainsi donc lorsque tu as une expression comme par exemple

Code :

1
2
3
(define (process n L)
  (display (cons n (call/cc {lambda (k) (set! saved k) L}))) )

Tu peux simplement retirer la partie call/cc (peu ou proue) pour obtenir la continuation

Code :

(saved r) = (display (cons n r))

La continuation ici est simplement l'ajout de n —*qui est fixe dans la continuation car c'est la valeur enfermée dans la fermeture lors de l'appel à process — puis l'affichage. J'ai mis le code concerné en vert pour t'aider à le visualiser.

Utilisé tel quel, il n'y a à peu près pas d'intérêt à utiliser call/cc. C'est par contre fort pratique pour s'échapper d'un calcul complexe dans un style par passage de continuation (CPS pour Continuation Passing Style). C'est utilisé pour des échappements de calcul récursif dont on connait le résultat sans avoir à continuer le calcul ou à effectuer du traitement d'exception par exemple.

Dans ce qui suit je te met la continuation en vert. Ça devrait t'aider à voir que tu t'es trompé pour ton premier guess.

Envoyé par bazoga

Code :

une deuxieme version

Code :

une troisiemme version

Code :

Est-ce que ça t'aide ?

[bazoga]

Envoyé par ceciestunpseudo

Est-ce que ça t'aide ?

Oui

j'ai une autre question a vous demander:

Soient x une donnée quelconque et l une liste linéaire, définir une fonction remove/erase,
telle que l’évaluation de l’expression (remove/erase x l) retourne :
— dans le cas où x possède zéro ou une occurrence dans l :
* une liste linéaire composée des éléments de l et apparaissant dans le
même ordre, excepté la première occurrence de x qui a été retirée ;

— dans le cas où x possède plusieurs occurrences dans l :
* la valeur #f.

NB: la liste est parcourue une seule fois

voici une solution une version "brute" :

Code :

1
2
3
4
5
6
7
8
9
10
(define (remove/erase x l)
  (call/cc
   (lambda(exit)
       (define (rec-remove/erase l)
         (let and-next ((l0 l) (flag #t))
           (cond ((null? l0) '())
                 ((equal? (car l0) x)(if flag (and-next (cdr l0) #f) (exit #f))) 
                 (else (cons (car l0)(and-next (cdr l0) flag) )))))
     (rec-remove/erase l))))

y' a t-il encore une version plus améliorée ?

Cordialement
E. Bazoga

[ceciestunpseudo]

Ta réponse me semble très correcte à peu de chose près.
Je suppose que c'est une question de devoir. Ce faisant, en faisant abnégation du contexte que je ne connais pas, je ne pourrais que te dire que tu peux légèrement rendre le code plus « esthétique » dans un sens fonctionnel mais que l'essentiel est là. Personnellement je me débarrasserais de ce flag qui rappelle trop les sentinelles utilisées en code impératif. De plus flag n'est que peu significatif. À mon sens, manipuler trop explicitement les booléens est souvent preuve d'un manque de structure au niveau logique. Ce n'est pas toujours vrai, mais cela peut être un symptôme de cette maladie terrible des développeurs en manque de rigueur mathématique.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (remove/erase x l)
  (call/cc
   {lambda(exit)
     ;; remove/erase avant de rencontrer le premier l0
     (define (remove/erase-before l0)
         (cond ([null? l0] '())
               ([equal? (car l0) x] (remove/erase-after (cdr l0))) 
               (else (cons (car l0) (remove/erase-before (cdr l0)))) ))
     ;; remove/erase après avoir rencontré le premier l0
     (define (remove/erase-after l0)
         (cond ([null? l0] '())
               ([equal? (car l0) x] (exit #f)) 
               (else (cons (car l0) (remove/erase-after (cdr l0)))) ))
     (remove/erase-before l) }))

On peut rendre ça tail-recursive avec une continuation après par exemple.

[bazoga]

Bonsoir,

Merci pour la réponse , certainement j'avoue qu'il me manque de la logique , j'espère qu'elle viendra avec l’expérience .

[ceciestunpseudo]

Envoyé par bazoga

Bonsoir,

Merci pour la réponse , certainement j'avoue qu'il me manque de la logique , j'espère qu'elle viendra avec l’expérience .

Attention cependant à ne pas me faire dire ce que je n'ai pas dit... ta solution était bien correcte. Si mes étudiants me donnent ce genre de réponse lorsque je leur pose ce genre de question, j'estime que c'est réussi. Lors d'un apprentissage il faut être pointilleux mais pas au point de sombrer dans l'orthodoxie fanatique.