|
|
 |
 |
 |
 |
Scheme Programming Language
|
 |
 |
 |
 |
|
|
|
|
r5rs_pitfall and the yinyang puzzle have me puzzled
I am working on my own interpreter/compiler for scheme, and am having a
problem understanding the "yinyang" puzzle algorithm in the "r5rs_pitfall"
test program. I recreate this algorithm here:
;; Modification of the yin-yang puzzle so that it terminates and produces
;; a value as a result. (Scott G. Miller)
(define result
(let (
[x '()]
[y 0])
(call/cc
(lambda (escape)
(let* (
[yin
(
(lambda (foo)
(set! x (cons y x))
(cond
((= y 10)(escape x))
(else
(begin
(set! y 0)
foo))))
(call/cc (lambda (bar) bar)))]
[yang
(
(lambda (foo)
(set! y (+ y 1))
foo)
(call/cc (lambda (baz) baz)))])
(yin yang))))))
I run this is another interpreter, SXM, and it runs fine and produces the
correct result. I run this in my interpreter, and it gets stuck in an
infinite loop. The problem I have is this: Looking at the algorithm, I
believe it SHOULD get stuck in an infinite loop. Obviously there is
something about either let* or continuations or some other aspect of this
that I don't understand.
If there is someone that understands how this algorithm works, and would be
willing to explain it to me, I would be very grateful.
Brian C. Barnes
On Apr 12, 2:46 pm, "Brian C. Barnes" <bcbar@austin.rr.com> wrote:
> I am working on my own interpreter/compiler for scheme, and am having a > problem understanding the "yinyang" puzzle algorithm in the "r5rs_pitfall" > test program. I recreate this algorithm here: > ;; Modification of the yin-yang puzzle so that it terminates and produces
> ;; a value as a result. (Scott G. Miller)
> (define result
> (let (
> [x '()]
> [y 0])
> (call/cc
> (lambda (escape)
> (let* (
> [yin
> (
> (lambda (foo)
> (set! x (cons y x))
> (cond
> ((= y 10)(escape x))
> (else
> (begin
> (set! y 0)
> foo))))
> (call/cc (lambda (bar) bar)))]
> [yang
> (
> (lambda (foo)
> (set! y (+ y 1))
> foo)
> (call/cc (lambda (baz) baz)))])
> (yin yang))))))
> I run this is another interpreter, SXM, and it runs fine and produces the
> correct result. I run this in my interpreter, and it gets stuck in an
> infinite loop. The problem I have is this: Looking at the algorithm, I
> believe it SHOULD get stuck in an infinite loop. Obviously there is
> something about either let* or continuations or some other aspect of this
> that I don't understand.
functions and you will be enlightened.
> Try inserting some code at the beginning of the YIN and YANG internal
> functions and you will be enlightened.- Hide quoted text -
>
interesting. In the working version, using SXM, I see Yin called once,
then Yang called once, Then Yin called once, Then Yang called twice,
then Yin called once, and Yang called 3 times, etc., etc..
When I run it under my own interpreter, Yin is called once, Then Yang
is called once. After this point, both variables Yin and Yang are
bound to the same continuation, and only Yang gets called from there
on out - incrementing "y" infinitely.
It appears that the first application of the form (yin yang) returns
to the continuation that was evaluating a value for yin in the let*
expression. Originally, the continuation that was the one returned by
the call/cc in the yin initializaiton sequence. The application of
(yin yang) the first time, however, I believe re-enters that
continuation, now assigning the value "yang" to yin. Control then
flows normally into the "yang" evaluation portion of the let*, which
evaluates yang to be the continuation of the call/cc after it. At this
point both yin and yang have a continuation that points to the return
to the evaluation of yang - or at least they do in my interpreter. I
wish I could get SXM to single step. Is there a different scheme
interpreter that is free and can single step over code?
Brian C. Barnes skrev:
> I am working on my own interpreter/compiler for scheme, and am having a
> problem understanding the "yinyang" puzzle algorithm in the
> "r5rs_pitfall" test program. I recreate this algorithm here:
Have you tested simpler call/cc programs first?
Old threads on this puzzle contains various explanations:
<http://groups.google.com/group/comp.lang.scheme/browse_frm/thread/172...>
<http://groups.google.com/group/comp.lang.scheme/browse_frm/thread/a54...>
<http://groups.google.com/group/comp.lang.scheme/browse_frm/thread/f42...>
--
Jens Axel Sgaard
On Apr 13, 2:11 pm, Jens Axel Sgaard <use@soegaard.net> wrote:
Yes, I've tested several other call/cc tests and patterns and they
work fine. There is something different about this one that I'm not
getting, and it may be the way let* expressions are evaluated and then
bound in my interpreter.
At any rate, those are some great links with just the kind of
explanations I was looking for. Thanks very much. I don't know why my
own search didn't turn up any of those.
Brian.
> Yes, I've tested several other call/cc tests and patterns and they
> work fine. There is something different about this one that I'm not
> getting, and it may be the way let* expressions are evaluated and then
> bound in my interpreter.
Have you checked the call/cc related tests in the pitfall collection?
<http://sisc-scheme.org/r5rs_pitfall.scm>
<http://sisc-scheme.org/r5rspitresults.html>
--
Jens Axel Sgaard
Yes, I've run those tests. My interpreter passes them all except the "yin
yang" one, and 1.3, which fails with "incorrect number of arguments passed
to procedure". I'm debugging that one too.
Thanks.
brian
"Jens Axel Sgaard" <use@soegaard.net> wrote in message
news:461fe0a4$0$91714$edfadb0f@dread12.news.tele.dk...
>> Yes, I've tested several other call/cc tests and patterns and they >> work fine. There is something different about this one that I'm not >> getting, and it may be the way let* expressions are evaluated and then >> bound in my interpreter. > Have you checked the call/cc related tests in the pitfall collection?
> <http://sisc-scheme.org/r5rs_pitfall.scm>
> <http://sisc-scheme.org/r5rspitresults.html>
> --
> Jens Axel Sgaard
Brian C. Barnes skrev:
Maybe this explanation can give a hint:
<http://groups.google.com/group/comp.lang.scheme/msg/e12cf5f473d388b8?...>
--
Jens Axel Sgaard
Thanks. I'll study that. I'm sure it will help.
"Jens Axel Sgaard" <use@soegaard.net> wrote in message
news:46209461$0$903$edfadb0f@dread12.news.tele.dk...
Well, I've made an interesting discovery. If I re-write the test using
nested "let" expressions instead of a single "let*", it works as it should
(not that I understand WHY it works, but at least it works). I must have
something wrong in let* that is interacting with continuation captures.
Thanks to everyone who has helped.
"Brian C. Barnes" <bcbar@austin.rr.com> wrote in message
news:46210439$0$24710$4c368faf@roadrunner.com...
On Apr 14, 10:07 pm, "Brian C. Barnes" <bcbar@austin.rr.com> wrote:
> Well, I've made an interesting discovery. If I re-write the test using
> nested "let" expressions instead of a single "let*", it works as it should
> (not that I understand WHY it works, but at least it works). I must have
> something wrong in let* that is interacting with continuation captures.
But let* IS nested lets. How else did you implement let*?
Aziz,,,
That's true, but I didn't code let* exactly like that, because I wanted to
be able to take advantage of the knowledge that there wouldn't be any
intervening combinations between the binding forms to make it more
efficient. I must have messed that up somewhere along the line.
"Abdulaziz Ghuloum" <aghul @gmail.com> wrote in message
> On Apr 14, 10:07 pm, "Brian C. Barnes" <bcbar @austin.rr.com> wrote: >> Well, I've made an interesting discovery. If I re-write the test using >> nested "let" expressions instead of a single "let*", it works as it >> should >> (not that I understand WHY it works, but at least it works). I must have >> something wrong in let* that is interacting with continuation captures. > But let* IS nested lets. How else did you implement let*?
> Aziz,,,
Good news: Having looked over the my code, I realized that I was allocating
the binding environments for the let* variables too early - at a point
BEFORE the continuation was being created. This caused a problem if the
continuation got captured and then later reinstated (as with call/cc and the
yinyang puzzle). By modifying my code to wait to allocate the environment
until the init expression had been evaluated, I have resolved my problem and
the yinyang puzzle now runs correctly in my interpreter.
This is good news for me, since I can now debug through the execution and
try to better understand how it works.
Thanks to everyone who posted help and suggestions. I've been programming
imperative languages for 30 years (C, C++, BASIC, FORTRAN, COBOL, pascal,
etc., etc.). Scheme is my first "functional" language, and writing an
interpreter for it was my way of learning the language. I'm glad to have
gotten over this annoyance. I've got most of R5.92RS implemented, and it's
been a lot of fun and a challanging learning experience.
Brian.
"Brian C. Barnes" <bcbar@austin.rr.com> wrote in message
news:46228caa$0$8983$4c368faf@roadrunner.com...
> That's true, but I didn't code let* exactly like that, because I wanted to > be able to take advantage of the knowledge that there wouldn't be any > intervening combinations between the binding forms to make it more > efficient. I must have messed that up somewhere along the line. > "Abdulaziz Ghuloum" <aghul@gmail.com> wrote in message
> news:1176612698.585415.267980@n59g2000hsh.googlegroups.com...
>> On Apr 14, 10:07 pm, "Brian C. Barnes" <bcbar@austin.rr.com> wrote:
>>> Well, I've made an interesting discovery. If I re-write the test using
>>> nested "let" expressions instead of a single "let*", it works as it
>>> should
>>> (not that I understand WHY it works, but at least it works). I must have
>>> something wrong in let* that is interacting with continuation captures.
>> But let* IS nested lets. How else did you implement let*?
>> Aziz,,,
On Apr 15, 4:36 pm, "Brian C. Barnes" <bcbar@austin.rr.com> wrote:
> That's true, but I didn't code let* exactly like that, because I wanted to
> be able to take advantage of the knowledge that there wouldn't be any
> intervening combinations between the binding forms to make it more
> efficient. I must have messed that up somewhere along the line.
Look at the bright side. What you implemented is letrec* (though the
scope of your let* may be slightly different).
Aziz,,,
|
|
|
|
|
|
Add to del.icio.us |
Digg this |
Stumble it |
Powered by Megasolutions Inc