IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Scheme Discussion :

continuation call/cc


Sujet :

Scheme

  1. #1
    Membre du Club
    Inscrit en
    Novembre 2009
    Messages
    96
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 96
    Points : 51
    Points
    51
    Par défaut continuation call/cc
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  2. #2
    Membre du Club
    Profil pro
    Inscrit en
    Août 2009
    Messages
    38
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Août 2009
    Messages : 38
    Points : 57
    Points
    57
    Par défaut
    À 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    (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.

    Citation Envoyé par bazoga Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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))))))
    Est-ce que ça t'aide ?

  3. #3
    Membre du Club
    Inscrit en
    Novembre 2009
    Messages
    96
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 96
    Points : 51
    Points
    51
    Par défaut
    Citation Envoyé par ceciestunpseudo Voir le message

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  4. #4
    Membre du Club
    Profil pro
    Inscrit en
    Août 2009
    Messages
    38
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Août 2009
    Messages : 38
    Points : 57
    Points
    57
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  5. #5
    Membre du Club
    Inscrit en
    Novembre 2009
    Messages
    96
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 96
    Points : 51
    Points
    51
    Par défaut
    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 .

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Août 2009
    Messages
    38
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Août 2009
    Messages : 38
    Points : 57
    Points
    57
    Par défaut
    Citation Envoyé par bazoga Voir le message
    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.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Call CC et continuation
    Par JB122 dans le forum Scheme
    Réponses: 1
    Dernier message: 24/02/2015, 14h59
  2. [BASM] Comment faire un "Far Call" ?
    Par - Robby - dans le forum Langage
    Réponses: 3
    Dernier message: 03/09/2003, 09h56
  3. L'instruction continue ?
    Par Patrick PETIT dans le forum C
    Réponses: 11
    Dernier message: 10/03/2003, 09h05
  4. [VB6] attendre un événement pour continuer l'exécution
    Par Argonz dans le forum VB 6 et antérieur
    Réponses: 21
    Dernier message: 12/11/2002, 14h08
  5. [langage] Continuer a parser une ligne
    Par D[r]eadLock dans le forum Langage
    Réponses: 5
    Dernier message: 30/09/2002, 19h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo