Continuation + Static scope environment

**mathk** · 11/03/2008, 23h11

Bonjour,

J'essaye d'implementer l'algo d'un producteur avec les continuatuions

Voila mon code:

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
16
(define producer (local [(define resume (box false))]
                           (lambda (real-send)
                             (local [(define real-sendb (box real-send))
                                     (define send (lambda (value-to-send)
                                                   (let/cc k
                                                      (begin
                                                        (set-box! resume k)
                                                        ((unbox real-sendb) value-to-send)))))]
                               (if (unbox resume)
                                   (begin
                                     (set-box! real-sendb real-send)
                                     ((unbox resume) 'dummy))
                                   (begin
                                     (send 'providence)
                                     (send 'houston)
                                     (send 'bangalroe)))))))

Pour utiliser le producteur voici le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 (printf "Get 1 ~a" (let/cc k (route-producer k)))
 (printf "Get 2 ~a" (let/cc k (route-producer k)))

Mais voila le problem c'est que real-sendb utilse la premiere continuation passe en parametre

real-sendb est donc toujours egale, et ce malgres mon (set-box! real-sendb real-send) a:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(lambda (k-value)
(prinf "Get 1 ~a" value))

La solution est donc:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define route-producer (local [(define resume (box false))]
                           (lambda (real-send)
                             (local [(define real-sendb (box real-send))
                                     (define send (lambda (value-to-send)
                                                   (set-box! real-sendb (let/cc k
                                                      (begin
                                                        (set-box! resume k)
                                                        ((unbox real-sendb) value-to-send))))))]
                               (if (unbox resume)
                                     ((unbox resume) real-send)
                                   (begin
                                     (send 'providence)
                                     (send 'houston)
                                     (send 'bangalroe)))))))

Mais voila je ne comprend pas pourquoi ma premiere solution ne marche pas.

Merci

**Garulfo** · 12/03/2008, 00h32

Avant de chercher plus loin... j'aimerais te demander :
0) quel langage utilises-tu ? mzscheme ?
1) pourquoi utilises-tu local ? est-ce bien celui de "etc.ss" ?
2) pourquoi utilises-tu box ?
3) que produit ton producer ?
4) pourquoi veux tu des continuations dans ton code ?

Bon je pense comprendre que c'est un problème de devoir, mais j'aimerais être sûr. Sinon c'est très compliqué pour pas grand chose.

**mathk** · 12/03/2008, 01h24

A vrai dir je lis le livre
http://www.cs.brown.edu/~sk/Publicat...gs/2007-04-26/
Chapitre 19.6

Et j'utilise donc le language fourni.
Pretty Big PLAI Scheme

http://www.cs.brown.edu/~sk/Publicat...s/plai-371.plt

**mathk** · 12/03/2008, 01h24

Envoyé par Garulfo

Bon je pense comprendre que c'est un problème de devoir, mais j'aimerais être sûr. Sinon c'est très compliqué pour pas grand chose.

As-tu une idee en tete?

**Garulfo** · 12/03/2008, 03h43

Envoyé par mathk

As-tu une idee en tete?

Oui. J'ai même mieux, j'ai la réponse

Ça demande un peu de travail de compréhension de ma part et — sans vouloir jouer le vantard — cela veut dire que c'est un problème bien compliqué.

Je vais essayer de t'expliquer, mais ce n'est pas évident. Si tu n'as pas bien saisi profondément les principes de fermeture et de capture des continuations courantes c'est pas du tout aisé.

En plus, si j'étais devant toi je te ferais un dessin — ce n'est pas une métaphore — mais là, c'est moins facile à décrire.

Dans ton premier exemple, lorsque le premier send est appelé, i.e. (send 'providence), il lie syntaxiquement une valeur pour real-sendb. Lorsque tu crois modifier real-sendb lors d'un deuxième passage, tu ne modifies pas le bon (celui capturé dans le premier send) mais un autre que tu viens de définir par un nouvel appel à route-producer.
J'ai réécris un peu ta première fonction pour le mettre en évidence

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
16
17
18
19
20
21
22
23
24
25
(require (lib "trace.ss"))
(define route-producer (local [(define resume (box false))]
                         (lambda (real-send n)
                           (local [(define real-sendb (box real-send))
                                   (define compteur n)
                                   (define send (lambda (value-to-send)
                                                  (let/cc k
                                                    (begin
                                                      (printf "compteur : ~a\n" compteur)
                                                      (set-box! resume k)
                                                      ((unbox real-sendb) value-to-send)))))]
                             (trace send)
                             (if (unbox resume)
                                 (begin
                                   (set-box! real-sendb real-send)
                                   ((unbox resume) 'dummy))
                                 (begin
                                   (send 'providence)
                                   (send 'houston)
                                   (send 'bangalroe)))))))


(printf "Get 1 ~a \n" (let/cc k (route-producer k 0)))
(printf "Get 2 ~a \n" (let/cc k (route-producer k 1)))

J'ai mis en bleu ce qui est changé. L'un des avantages de local c'est qu'on peut tracer les fonctions internes. Profitons en donc.
L'exécution de ça produit l'affichage

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
|(send providence)
compteur : 0
Get 1 providence 
|dummy
|(send houston)
compteur : 0
Get 1 houston

On voit que c'est deux fois « compteur : 0 » qui apparaît. En effet, dans resume, lors du deuxième appelle de route-producer se trouve la continuation du premier send. Celui ci capture dans sa fermeture les valeurs des premiers real-sendb et compteur.

Est ce que tu comprends pourquoi ça ne marchait pas ?

Alors, pourquoi ça fonctionne dans le deuxième ? Car c'est bien toujours le send qui est capturé avec toujours dans sa fermeture le premier real-sendb. Et oui, mais justement. Lors de l'appel de ce « premier » send, la variable real-sendb qui va être modifiée ne va pas être la nouvelle mais l'ancienne. Pour le voir, on peut constater que si on fait les même modification que tantôt à ton deuxième code, compteur ne change toujours pas.

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
16
17
18
19
20
21
(define route-producer2 (local [(define resume (box false))]
                          (lambda (real-send n)
                            (local [(define real-sendb (box real-send))
                                    (define compteur n)
                                    (define send (lambda (value-to-send)
                                                   (set-box! real-sendb (let/cc k
                                                                          (begin
                                                                            (printf "compteur : ~a\n" compteur)
                                                                            (set-box! resume k)
                                                                            ((unbox real-sendb) value-to-send))))))]
                              (trace send)
                              (if (unbox resume)
                                  ((unbox resume) real-send)
                                  (begin
                                    (send 'providence)
                                    (send 'houston)
                                    (send 'bangalroe)))))))


(printf "Get 1 ~a \n" (let/cc k (route-producer2 k 0)))
(printf "Get 2 ~a \n" (let/cc k (route-producer2 k 1)))

ce qui donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
|(send providence)
compteur : 0
Get 1 providence 
|#<void>
|(send houston)
compteur : 0
Get 2 houston

C'est un problème difficile ce que tu demandes ici.
Mais j'espère t'avoir éclairé.

**mathk** · 12/03/2008, 23h50

Envoyé par Garulfo

Est ce que tu comprends pourquoi ça ne marchait pas ?

Oui

merci bcp.
Permet moi donc dereformuler ce que tu m'as expliquer pour voir si j'ai bien compris.

Les differents appele a la closure route-produceur capture bien plusieur send et il en est de meme pour real-send et real-sendb.

En revanche la continuation stocker dans resume continue toujours selon la premiere capture du send etand donner que la fermeture de resume ce passe lors de l'evaluation de route-produceur (cad lorsque (define route-produceur ...) est evalue).

C'est pourquoi il faut que se soit la premiere capture de real-sendb qui change. Le real-sendb qui est fermer avec se fameux premier send.

Il me s'emble que j'ai parfaitement compris mais il me semble aussi que je suis tres confus.

En tous cas merci

OT: Je suis bien daccord avec Bertrand Russell

j'ajouterais meme qu'a la fin on ne sais toujours pas qui a tord ou raison. (Bien sur pour eviter toute interpretation fausse d'un corrolaire)

**mathk** · 13/03/2008, 00h08

Envoyé par Garulfo

Sinon c'est très compliqué pour pas grand chose.

Je pensais que tu avais une idee de solution plus simple pour faire un producteur.

**Garulfo** · 13/03/2008, 02h30

Envoyé par mathk

[...]
Il me s'emble que j'ai parfaitement compris mais il me semble aussi que je suis tres confus.

[...]

TU me sembles effectivement bien comprendre. Bravo c'est pas simple.

Envoyé par mathk

[...]
OT: Je suis bien daccord avec Bertrand Russell

j'ajouterais meme qu'a la fin on ne sais toujours pas qui a tord ou raison. (Bien sur pour eviter toute interpretation fausse d'un corrolaire)

Mais comme tout bon logicien je te dirais que : tous le monde a tord ou raison

En tout cas, Russell est mon maître à penser dans les philosophes contemporains.

**Garulfo** · 13/03/2008, 03h11

Envoyé par mathk

Je pensais que tu avais une idee de solution plus simple pour faire un producteur.

Oui, je n'avais pas compris que tu me demandais si j'avais un idée pour ça.

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
16
17
18
19
20
21
22
23
24
25
(define (create-producer list-elements) 
  (let* [(elements list-elements)
         (producer-k (lambda (k) (if (pair? list-elements)
                                     (let [(head (car list-elements))
                                           (tail (cdr list-elements))
                                           ]
                                       (set! list-elements tail)
                                       (k head)
                                       )
                                     'error:no-more-elements
                                     )
                       )
                     )
         ]
    producer-k
    )
  )

(define producer-cities (create-producer '(providence houston bangalroe)))

(printf "Get 1 ~a \n" (let/cc k (producer-cities k)))
(printf "Get 2 ~a \n" (let/cc k (producer-cities k)))
(printf "Get 3 ~a \n" (let/cc k (producer-cities k)))
(printf "Get 4 ~a \n" (let/cc k (producer-cities k)))

La seule différence est le comportement pour les éléments surnuméraires. Mais je suppose que l'exercice prenait place dans un contexte. Cette solution n'est donc pas pertinente aux acquis de l'exercice.

**mathk** · 13/03/2008, 15h07

Envoyé par Garulfo

Mais comme tout bon logicien je te dirais que : tous le monde a tord ou raison

En tout cas, Russell est mon maître à penser dans les philosophes contemporains.

Cool je vais l'ajouter dans ma list des auteurs a lire

**mathk** · 13/03/2008, 15h09

Envoyé par Garulfo

Oui, je n'avais pas compris que tu me demandais si j'avais un idée pour ça.

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
16
17
18
19
20
21
22
23
24
25
(define (create-producer list-elements) 
  (let* [(elements list-elements)
         (producer-k (lambda (k) (if (pair? list-elements)
                                     (let [(head (car list-elements))
                                           (tail (cdr list-elements))
                                           ]
                                       (set! list-elements tail)
                                       (k head)
                                       )
                                     'error:no-more-elements
                                     )
                       )
                     )
         ]
    producer-k
    )
  )

(define producer-cities (create-producer '(providence houston bangalroe)))

(printf "Get 1 ~a \n" (let/cc k (producer-cities k)))
(printf "Get 2 ~a \n" (let/cc k (producer-cities k)))
(printf "Get 3 ~a \n" (let/cc k (producer-cities k)))
(printf "Get 4 ~a \n" (let/cc k (producer-cities k)))

La seule différence est le comportement pour les éléments surnuméraires. Mais je suppose que l'exercice prenait place dans un contexte. Cette solution n'est donc pas pertinente aux acquis de l'exercice.

Oui c'est effectivement plus simple.
Les elements surnumeraires sont les elements qui n'appartiennent pas a la liste?

Autre question est-ce que local et let ont la meme semantique?

**Garulfo** · 13/03/2008, 20h02

Envoyé par mathk

Oui c'est effectivement plus simple.
Les elements surnumeraires sont les elements qui n'appartiennent pas a la liste?

Je parlais effectivement des appels qui suivent l'appel ayant travaillé sur le dernier élément.

Envoyé par mathk

Autre question est-ce que local et let ont la meme semantique?

Non. local est une macro qui fait une définition au top-level avec un nom unique. Le nom des variables liées par le local dans l'expression de ce dernier sont modifiées en conséquence. Personnellement, je n'y vois que peu d'intérêt en général. Cela permet d'appeler à l'interne des procédures ou des macros qui ne pourrait être appliquées que sur des éléments du top-level. Le seul véritable intérêt c'est pour le trace

**mathk** · 14/03/2008, 00h50

Envoyé par Garulfo

Je parlais effectivement des appels qui suivent l'appel ayant travaillé sur le dernier élément.

Non. local est une macro qui fait une définition au top-level avec un nom unique. Le nom des variables liées par le local dans l'expression de ce dernier sont modifiées en conséquence. Personnellement, je n'y vois que peu d'intérêt en général. Cela permet d'appeler à l'interne des procédures ou des macros qui ne pourrait être appliquées que sur des éléments du top-level. Le seul véritable intérêt c'est pour le trace

Ok merci bcp

Continuation + Static scope environment

Scheme

Discussions similaires

Partager

Partager