faking dynamic-wind ?
Brian Denheyer
Is there a way to "fake" dynamic-wind in a scheme which does not
support it.
It's not obvious to me that it can be done without low-level support
of some sort.
Of course, if you could do it without low level support, then what's
the point of it being in R5RS, right ?
Brian
Martin Rodgers
> Is there a way to "fake" dynamic-wind in a scheme which does not
> support it.
See how SLIB does it:
http://www-swiss.ai.mit.edu/~jaffer/SLIB.html
> It's not obvious to me that it can be done without low-level support
> of some sort.
Yeah, you need call-with-current-continuation, and that's not low-
level. It's high-level. ;)
--
Email address intentially munged | You can never browse enough
will write code that writes code that writes code for food
<URL:http://www.wildcard.demon.co.uk>
Rob Warnock
+---------------
| Is there a way to "fake" dynamic-wind in a scheme which does not
| support it. It's not obvious to me that it can be done without
| low-level support of some sort.
The minutes of the legendary "June 1992" meeting at Xerox PARC
<URL:ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/standards/
june-92-meeting.ps.gz> included a "user-mode" reference implementation
of dynamic-wind, but noted:
Since dynamic-wind interacts with call-with-current-continuation,
this implementation must replace the usual definition of the latter.
That is, *all* calls to call/cc must be to the one defined in the
dynamic-wind code (which saves away the original function value and
replaces it with its own, by set!-ing the global variable). This can
only work if no built-in route uses call/cc, and if the dynamic-wind
code appears lexical *before* any code that uses call/cc.
+---------------
| Of course, if you could do it without low level support, then what's
| the point of it being in R5RS, right ?
+---------------
Efficiency.
-Rob
-----
Rob Warnock, 31-2-510 rp...@sgi.com
Network Engineering http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
Matthias Blume
> Brian Denheyer <bri...@zipcon.net> wrote:
> +---------------
> | Is there a way to "fake" dynamic-wind in a scheme which does not
> | support it. It's not obvious to me that it can be done without
> | low-level support of some sort.
> +---------------
>
> The minutes of the legendary "June 1992" meeting at Xerox PARC
> <URL:ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/standards/
> june-92-meeting.ps.gz> included a "user-mode" reference implementation
> of dynamic-wind, but noted:
>
> Since dynamic-wind interacts with call-with-current-continuation,
> this implementation must replace the usual definition of the latter.
>
> That is, *all* calls to call/cc must be to the one defined in the
> dynamic-wind code (which saves away the original function value and
> replaces it with its own, by set!-ing the global variable). This can
> only work if no built-in route uses call/cc, and if the dynamic-wind
> code appears lexical *before* any code that uses call/cc.
>
> +---------------
> | Of course, if you could do it without low level support, then what's
> | the point of it being in R5RS, right ?
> +---------------
Look up my old "call/wc" ("call-with-winding-continuation") proposal for an
alternative user-mode implementation that does not interfere with call/cc.
(Actually, it does interfere and you still have to replace every call/cc
with a version that is aware of dynamic-wind, but the new version is
still O(1) for capture and invocation provided the old one was.)
The need for replacing _every_ call/cc with a winding one is a
terrible thing, IMO, because it essentially renders call/cc useless
for implementing concurrency.
Matthias
--
Matthias Blume <blume@k_u_r_i_m_s.k_y_o_t_o-u.a_c.j_p>
Kyoto University, Research Institute for Mathematical Sciences
(remove those spam-preventing underscores from mail address)
felix
Matthias Blume wrote in message ...
>The need for replacing _every_ call/cc with a winding one is a
>terrible thing, IMO, because it essentially renders call/cc useless
>for implementing concurrency.
Why that? I haven't seen your "call/wc", but with the normal
(SLIB-style) "dynamic-wind" on top of old "call/cc" it's certainly possible.
As long as your scheduler uses the previous (native) "call/cc",
and as long as you take care to preserve all live winds for each
thread, there is no problem with concurrency.
felix
Michael Livshin
> Is there a way to "fake" dynamic-wind in a scheme which does not
> support it.
yes, by wrapping `call/cc'. look at SLIB for an implementation of
this.
note that if your Scheme has some other constructs for non-local
control flow (like catch/throw etc.) that are not implemented using
call/cc, then you'll have to wrap them too.
--
(only legal replies to this address are accepted)
The software isn't finished until the last user is dead.
Alexandria Petrofsky
> rp...@rigden.engr.sgi.com (Rob Warnock) writes:
> >
> > The minutes of the legendary "June 1992" meeting at Xerox PARC
> > <URL:ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/standards/
> > june-92-meeting.ps.gz> included a "user-mode" reference implementation
> > of dynamic-wind, ...
> Look up my old "call/wc" ("call-with-winding-continuation") proposal for an
> alternative user-mode implementation that does not interfere with call/cc.
> (Actually, it does interfere and you still have to replace every call/cc
> with a version that is aware of dynamic-wind, but the new version is
> still O(1) for capture and invocation provided the old one was.)
The implementation referenced by Warnock also adds only O(1) overhead
to continuation capture and invocation if there is no winding to be
done. The slib implementation is not O(1) because it calls length to
count how deep we are in the tree of winding states. The 1992
implementation avoids this by keeping the tree rooted at the current
state. Below is an implementation using this algorithm.
-al
(define dynamic-wind
(let ((old-call/cc call-with-current-continuation)
(root (cons #f #f)))
(define (new-call/cc proc)
(let ((saved-place root))
(old-call/cc (lambda (cont)
(proc (lambda results
(reroot! saved-place)
(apply cont results)))))))
(define (dynamic-wind before during after)
(let ((saved-place root))
(reroot! (cons (cons before after) root))
(call-with-values during
(lambda results
(reroot! saved-place)
(apply values results)))))
(define (reroot! new-root)
(define (reverse-pair p) (cons (cdr p) (car p)))
(if (not (eq? root new-root))
(begin (reroot! (cdr new-root))
((caar new-root))
(set-car! root (reverse-pair (car new-root)))
(set-cdr! root new-root)
(set! root new-root))))
(cons new-call/cc dynamic-wind)))
(define call-with-current-continuation (car dynamic-wind))
(define dynamic-wind (cdr dynamic-wind))
Matthias Blume
> Matthias Blume wrote in message ...
>
> >The need for replacing _every_ call/cc with a winding one is a
> >terrible thing, IMO, because it essentially renders call/cc useless
> >for implementing concurrency.
>
>
> Why that? I haven't seen your "call/wc", but with the normal
> (SLIB-style) "dynamic-wind" on top of old "call/cc" it's certainly possible.
> As long as your scheduler uses the previous (native) "call/cc",
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
That's the point. With the new R5RS dynamic-wind, you don't have (portable)
access to the previous native call/cc.
> and as long as you take care to preserve all live winds for each
> thread, there is no problem with concurrency.
By the way, I just had a look at how slib does dynamic-wind, and it turns
out that it is quite similar to my call/wc. So no wonder that there is
no problem.
(In my proposal there is the native call/cc (the old one) -- augmented
to preserve winds, and the new call/wc (which is like the new R5RS call/cc).
The point that I made there was that it can be done in a purely functional way
if you do it in a CPS-based compiler using something that I called
"winder-passing-style". I also used a list representation that that gives you
a constant-time length operation which makes it truly O(1) in case no winding
has to be done. Since you have a CPS-style compiler, you should perhaps look
it up!)
Matthias Blume
> Matthias Blume <s...@my.sig> writes:
>
> > rp...@rigden.engr.sgi.com (Rob Warnock) writes:
> > >
> > > The minutes of the legendary "June 1992" meeting at Xerox PARC
> > > <URL:ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/standards/
> > > june-92-meeting.ps.gz> included a "user-mode" reference implementation
> > > of dynamic-wind, ...
>
> > Look up my old "call/wc" ("call-with-winding-continuation") proposal for an
> > alternative user-mode implementation that does not interfere with call/cc.
> > (Actually, it does interfere and you still have to replace every call/cc
> > with a version that is aware of dynamic-wind, but the new version is
> > still O(1) for capture and invocation provided the old one was.)
>
> The implementation referenced by Warnock also adds only O(1) overhead
> to continuation capture and invocation if there is no winding to be
> done.
I know. But it is inherently imperative and will break badly if someone
uses a mix of old (non-winding) call/cc and new call/cc. Since for things
like schedulers the old call/cc is needed, this is not good.
> The slib implementation is not O(1) because it calls length to
> count how deep we are in the tree of winding states.
The slib implementation is similar to my call/wc proposal. Like the
latter, it could easily recover the O(1) property by keeping track of
the list lengths separately. (To put it differently: by using a list
representation with an O(1) length operation.)
> The 1992 implementation avoids this by keeping the tree rooted at
> the current state.
I know that algorithm. See above for why it is not ideal. My call/cc
was designed precisely with overcoming its problems in mind.
Joe Marshall
> Brian Denheyer <bri...@zipcon.net> wrote:
>
> +---------------
> | Of course, if you could do it without low level support, then what's
> | the point of it being in R5RS, right ?
> +---------------
>
> Efficiency.
And interaction with other things like interrupts.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
felix
>"felix" <fe...@anu.ie> writes:
>
>> Matthias Blume wrote in message ...
>>
>> >The need for replacing _every_ call/cc with a winding one is a
>> >terrible thing, IMO, because it essentially renders call/cc useless
>> >for implementing concurrency.
>>
>>
>> Why that? I haven't seen your "call/wc", but with the normal
>> (SLIB-style) "dynamic-wind" on top of old "call/cc" it's certainly
possible.
>> As long as your scheduler uses the previous (native) "call/cc",
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>That's the point. With the new R5RS dynamic-wind, you don't have
(portable)
>access to the previous native call/cc.
>
That's not the problem. If we can implement dynamic-wind in user-mode
(that's what
we are talking about, remember?) then we *have* access to the native
call/cc.
Otherwise the implementation wouldn't be possible at all. And if a
Scheme-system
*already* provides dynamic-wind (natively) it can still support concurrency,
if
implemented correctly. So I still don't see your point.
felix
David Rush
> Matthias Blume wrote in message ...
> >"felix" <fe...@anu.ie> writes:
> >> Matthias Blume wrote in message ...
> >> (SLIB-style) "dynamic-wind" on top of old "call/cc" it's certainly
> >> possible.
> >> As long as your scheduler uses the previous (native) "call/cc",
> >(portable) access to the previous native call/cc.
> That's not the problem. If we can implement dynamic-wind in user-mode
> (that's what we are talking about, remember?) then we *have* access
<meta>
Hmmm... starting to sound a lot like c.l.l in here
</meta>
david rush
--
From the start...the flute has been associated with pure (some might
say impure) energy. Its sound releases something naturally untamed, as
if a squirrel were let loose in a church." --Seamus Heaney
David Rush
> rp...@rigden.engr.sgi.com (Rob Warnock) writes:
> > Brian Denheyer <bri...@zipcon.net> wrote:
> > Of course, if you could do it without low level support, then what's
> > the point of it being in R5RS, right ?
> And interaction with other things like interrupts.
Which aren't in R5RS.
david rush
--
If you give someone Fortran, he has Fortran.
If you give someone Lisp, he has any language he pleases.
-- Guy L. Steele Jr.
Matthias Blume
> Matthias Blume wrote in message ...
> >"felix" <fe...@anu.ie> writes:
> >
> >> Matthias Blume wrote in message ...
> >>
> >> >The need for replacing _every_ call/cc with a winding one is a
> >> >terrible thing, IMO, because it essentially renders call/cc useless
> >> >for implementing concurrency.
> >>
> >>
> >> Why that? I haven't seen your "call/wc", but with the normal
> >> (SLIB-style) "dynamic-wind" on top of old "call/cc" it's certainly
> possible.
> >> As long as your scheduler uses the previous (native) "call/cc",
> > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >That's the point. With the new R5RS dynamic-wind, you don't have
> (portable)
> >access to the previous native call/cc.
> >
>
>
> That's not the problem. If we can implement dynamic-wind in user-mode
> (that's what
> we are talking about, remember?) then we *have* access to the native
> call/cc.
That's not what I was talking about. In R5RS, there is no native
call/cc. Period. (The user-level implementation is just a way of
faking R5RS-compliance.)
> Otherwise the implementation wouldn't be possible at all. And if a
> Scheme-system *already* provides dynamic-wind (natively) it can
> still support concurrency, if implemented correctly. So I still
> don't see your point.
Sure, it can provide anything it likes. But if it has only R5RS
call/cc and *no* concurrency, then you are out of luck. And according
to R5RS, a compliant implementation is perfectly entitled to do so.
(This is an old discussion which, as you said yourself, you did not
see. In this discussion I was criticizing R5RS, not its potential
user-level implementations. In fact, my call/wc proposal was
precisely about fixing the problems by *doing* a (different)
user-level implementation.)
felix
Matthias Blume wrote in message ...
>
>call/cc. Period. (The user-level implementation is just a way of
>faking R5RS-compliance.)
Of course. But this is about a non-R5RS situation in which we
want to "fake dynamic-wind" (because it doesn't provide it,
because it isn't R5RS). In R5RS I don't have to fake it, because
it's already there.
>Sure, it can provide anything it likes. But if it has only R5RS
>call/cc and *no* concurrency, then you are out of luck. And according
>to R5RS, a compliant implementation is perfectly entitled to do so.
Yes, you're right. I didn't think of that.
felix
Joe Marshall
> Joe Marshall <j...@content-integrity.com> writes:
> > rp...@rigden.engr.sgi.com (Rob Warnock) writes:
> > > Brian Denheyer <bri...@zipcon.net> wrote:
> > > Of course, if you could do it without low level support, then what's
> > > the point of it being in R5RS, right ?
> > > Efficiency.
> > And interaction with other things like interrupts.
>
> Which aren't in R5RS.
Nor is efficiency.
Rob Warnock
+---------------
| "felix" <fe...@anu.ie> writes:
| > That's not the problem. If we can implement dynamic-wind in user-mode
| > (that's what we are talking about, remember?) then we *have* access
| > to the native call/cc.
|
| That's not what I was talking about. In R5RS, there is no native
| call/cc. Period. (The user-level implementation is just a way of
| faking R5RS-compliance.)
I think there are at least two typos here. R5RS *has* both call/cc and
dynamic-wind native [see section "6.4 Control features"], and even R4RS
had native call/cc as an "essential procedure". Is this what you meant
to say instead?
In R4RS, there is no native dynamic-wind. Period. (The user-level
implementation is just a way of faking R5RS-compliance.)
Algol Petrofsky
> This is an old discussion ...
I have tried but failed to look up your call/wc proposal. Google returns zero
hits for call-with-winding-continuation, and dejanews is, alas,
not the resource it once was.
If it's only a few kilobytes, could you post your call/wc proposal
again? I am increasingly curious to know what you're talking about.
One thing I don't understand is why you can't just refrain from using
dynamic-wind if you don't like it's interaction with call/cc. If you
start your r5rs program with:
(define dynamic-wind #f)
then call/cc will behave indistinguishably from the way it did in
r4rs, won't it?
I'm also confused about what you mean by concurrency. Are you talking
about non-standard extensions to the language to provide primitives
for concurrency, or are you talking about programs using standard
scheme call/cc to do cooperative multithreading?
If you're talking about a non-standard version of scheme, then what
does it matter what the semantics of standard dynamic-wind are?
If you're talking about standard scheme programs doing their own
pseudo-multithreading on top of call/cc, then I think I need to see
some example code before I will understand how dynamic-wind is getting
in your way (or how a different dynamic-wind would be much more useful
to you).
-al
Joe English
>Matthias Blume wrote:
>+---------------
>| That's not what I was talking about. In R5RS, there is no native
>| call/cc. Period. (The user-level implementation is just a way of
>| faking R5RS-compliance.)
>+---------------
>
>I think there are at least two typos here. R5RS *has* both call/cc and
>dynamic-wind native [see section "6.4 Control features"], and even R4RS
>had native call/cc as an "essential procedure". Is this what you meant
>to say instead?
But the R5RS "call-with-current-continuation" is not the same
as the R4RS "call-with-current-continuation". It's really a
"call-with-winding-continuation".
> In R4RS, there is no native dynamic-wind. Period. (The user-level
> implementation is just a way of faking R5RS-compliance.)
The trouble is, you can implement call/wc on top of call/cc,
but the reverse is not true. This is IMO a serious deficiency
in R5RS.
--Joe English
Joe Marshall
> The trouble is, you can implement call/wc on top of call/cc,
> but the reverse is not true. This is IMO a serious deficiency
> in R5RS.
If there were a mechanism by which you could invoke a continuation
without running the appropriate exit and entry elements of
dynamic-wind, then you have defeated the purpose (and poked a hole in
the semantics) of dynamic-wind, have you not?
Why do you consider the inability to evade a dynamic-wind (or
conversely, the ability to write cleanup code that cannot be
subverted) a serious deficiency?
Joe Marshall
> If you're talking about standard scheme programs doing their own
> pseudo-multithreading on top of call/cc, then I think I need to see
> some example code before I will understand how dynamic-wind is getting
> in your way (or how a different dynamic-wind would be much more useful
> to you).
There really are two forms of dynamic state, `global' dynamic state,
and `thread local' dynamic state. Dynamic-wind is good at handling
the `thread local' state, but it is good at handling the `global'
state only if you are running a single thread. If you attempt to use
dynamic-wind to handle multiple threads (and you are using
call-with-current-continuation to implement your threads), you will
have problems.
Consider these two situations: You want to cause printout to be in
base 8, and you want to control a drill press.
In the former case, you wish to dynamically bind *print-base* to 8,
and you most likely want this to occur on a per-thread basis. A
dynamic-wind solves the problem easily because it can restore the base
to normal every time you invoke a continuation to switch threads.
In the latter case, however, every time you switched a thread, you
would start and stop the drill press.
Call-with-current-continuation and dynamic-wind (as defined) are not a
suitable substrate for simulating multithreading in Scheme. Rather
than point the blame at one or the other definition, however,
extending the language to include multithreading might be a better idea.
Matthias Blume
> Matthias Blume <s...@my.sig> wrote:
> +---------------
> | "felix" <fe...@anu.ie> writes:
> | > That's not the problem. If we can implement dynamic-wind in user-mode
> | > (that's what we are talking about, remember?) then we *have* access
> | > to the native call/cc.
> |
> | That's not what I was talking about. In R5RS, there is no native
> | call/cc. Period. (The user-level implementation is just a way of
> | faking R5RS-compliance.)
> +---------------
>
> I think there are at least two typos here. R5RS *has* both call/cc and
> dynamic-wind native [see section "6.4 Control features"], and even R4RS
> had native call/cc as an "essential procedure". Is this what you meant
> to say instead?
No, by "native call/cc" we (felix and I) meant the *real* call/cc,
i.e., the one that calls its argument with the current continuation.
The one in R5RS runs various winders first, so it isn't technically
call/cc at all. (Hence my proposal to change the name of that
procedure to call/wc (call-with-winding-continuation).)
Matthias Blume
> jeng...@flightlab.com (Joe English) writes:
>
> > The trouble is, you can implement call/wc on top of call/cc,
> > but the reverse is not true. This is IMO a serious deficiency
> > in R5RS.
>
> If there were a mechanism by which you could invoke a continuation
> without running the appropriate exit and entry elements of
> dynamic-wind, then you have defeated the purpose (and poked a hole in
> the semantics) of dynamic-wind, have you not?
No, you have not (at least not necessarily) because you can define the
semantics of dynamic-wind that way. And "defeating" the purpose of
dynamic-wind is definitely something that one sometimes wants to do --
for example when implementing a scheduler for threads.
> Why do you consider the inability to evade a dynamic-wind (or
> conversely, the ability to write cleanup code that cannot be
> subverted) a serious deficiency?
See above.
Matthias Blume
> Matthias Blume <s...@my.sig> writes:
> > This is an old discussion ...
>
> I have tried but failed to look up your call/wc proposal. Google returns zero
> hits for call-with-winding-continuation, and dejanews is, alas,
> not the resource it once was.
>
> If it's only a few kilobytes, could you post your call/wc proposal
> again? I am increasingly curious to know what you're talking about.
I'll try to dig it up.
> One thing I don't understand is why you can't just refrain from using
> dynamic-wind if you don't like it's interaction with call/cc.
*I* can. But perhaps not the people whose code I want to link mine with.
> If you start your r5rs program with:
>
> (define dynamic-wind #f)
... then those people's code might not do what it was meant to do anymore.
> I'm also confused about what you mean by concurrency. Are you talking
> about non-standard extensions to the language to provide primitives
> for concurrency, or are you talking about programs using standard
> scheme call/cc to do cooperative multithreading?
I meant (for example) the latter. Some systems also provide timer
interrupts which then give you a way to do the former also.
> If you're talking about standard scheme programs doing their own
> pseudo-multithreading on top of call/cc, then I think I need to see
> some example code before I will understand how dynamic-wind is getting
> in your way (or how a different dynamic-wind would be much more useful
> to you).
Just think of two threads, each doing its own very deep recursion,
invoking mayn dynamic-wind's in between. Then imagine doing a context
switch and think about how much (and what) code runs during the
context switch...
ste...@pcrm.win.tue.nl
>Just think of two threads, each doing its own very deep recursion,
>invoking mayn dynamic-wind's in between. Then imagine doing a context
>switch and think about how much (and what) code runs during the
>context switch...
Indeed, the dynamic-wind only seems to make sense (to me) as
a clean-up mechanism similar to try..finally in some other
languages. This makes sense if you use call/cc to build
an exception system on, but it does not make sense
if you want to use call/cc to do cooperative multitasking.
Indeed, if you wants to mix both uses of call/cc, you soon
find out that this means that you cannot use dynamic-wind
for try..finally purposes.
(Since Scheme isn't clairvoyant and cannot guess in which of
the two meanings you want to use call/cc.)
Which means that you probably end up:
1. not using the real dynamic-wind
2. write your own call-with-winding-continuation + fake-dynamic-wind
3. do exceptions with the new call/wc and use the original call/cc
for threading
So it would be much more useful if we actually had both
call/wc and call/cc. Only having call/cc (actually call/wc) and
dynamic-wind is hardly more useful than only having call/cc, and is
implementation-wise just as complex as having both call/cc and
call/wc.
Stephan
--
ir. Stephan H.M.J. Houben
tel. +31-40-2474358 / +31-40-2743497
e-mail: step...@win.tue.nl
Joe English
>jeng...@flightlab.com (Joe English) writes:
>
>> The trouble is, you can implement call/wc on top of call/cc,
>> but the reverse is not true. This is IMO a serious deficiency
>> in R5RS.
>
>If there were a mechanism by which you could invoke a continuation
>without running the appropriate exit and entry elements of
>dynamic-wind, then you have defeated the purpose (and poked a hole in
>the semantics) of dynamic-wind, have you not?
Probably. But to be honest I'm not entirely sure
what the semantics of dynamic-wind really *are* --
I never could reconcile the prose description
in section 6.4 with the formal semantics in section 7.2.
>Why do you consider the inability to evade a dynamic-wind (or
>conversely, the ability to write cleanup code that cannot be
>subverted) a serious deficiency?
Is dynamic-wind appropriate for cleanup code though?
Most cases of cleanup code I can think of -- closing
open file descriptors, releasing COM handles, dismissing
dialog boxes, et cetera -- are things that need to
be called exactly once. With dynamic-wind, the 'after'
and 'before' thunks can be called multiple times.
It seems to me that dynamic-wind is better suited for
implementing things like coroutines or cooperative
multitasking; it doesn't seem to be useful for implementing
exception handlers or try-finally.
Anyway, call/wc is a more complicated construct than call/cc.
That R5RS provides the complicated one and not the simple one
as a primitive is what I consider the deficiency.
--Joe English
Marc Feeley
> > jeng...@flightlab.com (Joe English) writes:
> >
> > > The trouble is, you can implement call/wc on top of call/cc,
> > > but the reverse is not true. This is IMO a serious deficiency
> > > in R5RS.
> >
> > If there were a mechanism by which you could invoke a continuation
> > without running the appropriate exit and entry elements of
> > dynamic-wind, then you have defeated the purpose (and poked a hole in
> > the semantics) of dynamic-wind, have you not?
>
> No, you have not (at least not necessarily) because you can define the
> semantics of dynamic-wind that way. And "defeating" the purpose of
> dynamic-wind is definitely something that one sometimes wants to do --
> for example when implementing a scheduler for threads.
If you really want to have a "bare-bone" call/cc (i.e. no winding) in
an R5RS Scheme system, the trick is that you should redefine
both dynamic-wind and call-with-current-continuation. Something
along the lines:
(define call-with-current-continuation-no-winding
call-with-current-continuation) ; get the builtin call/cc
(define (call-with-current-continuation receiver)
... any of many implementations, but using call-with-current-continuation-no-winding ...)
(define (dynamic-wind before thunk after)
... any of many implementations, but using call-with-current-continuation-no-winding ...)
So even though the R5RS call/cc is being used, **it** never has any
winding to do, so you get the same semantics out of
call-with-current-continuation-no-winding as R4RS call/cc.
Of course I'm assuming the runtime library isn't using a builtin
dynamic-wind directly.
Marc
Matthias Blume
Sure. And of course this just admits: R5RS' dynamic-wind is
completely useless.
> Of course I'm assuming the runtime library isn't using a builtin
> dynamic-wind directly.
This, indeed, is the usual "gotcha" when you do any "roll-your-own" stuff.
Rob Warnock
+---------------
| Indeed, if you wants to mix both uses of call/cc, you soon
| find out that this means that you cannot use dynamic-wind
| for try..finally purposes.
You can't anyway, since you'd want the unwinding to *stop* when it hits
the "after" clause that was being used for the "finally" part. That is,
consider this naive/obvious implementation of CL's "unwind-protect",
which assumes that all system errors invoke a continuation captured
in the top-level REPL (which is the case in many implementations):
> (defmacro unwind-protect (protected-form . cleanup-forms)
`(begin
(call/cc
(lambda (break)
(dynamic-wind
(lambda () #t)
(lambda () ,protected-form)
(lambda () (break)))))
,@cleanup-forms))
> (unwind-protect (/ 1 0)
(print "This prints anyway")
17)
/: division by zero
This prints anyway
17
>
However, R5RS clearly says:
The effect of using a captured continuation to enter or exit
the dynamic extent of a call to "before" or "after" is undefined.
So you can't legally do that [even though it works in the particular
implementation I tried it in].
I ran into exactly this problem when implementing a private REPL inside
a script that was supposed to be portable between MzScheme and SCM. SCM
did what I had hoped for, but MzScheme barfed on a continuation being
invoked in the "after" thunk -- it called the "after" thunk again!!
[Hey, "undefined" behavior can be *anything*, right?] Thankfully, the
Rice guys fixed the problem in the next release.
+---------------
| (Since Scheme isn't clairvoyant and cannot guess in which of
| the two meanings you want to use call/cc.)
| Which means that you probably end up:
| 1. not using the real dynamic-wind
| 2. write your own call-with-winding-continuation + fake-dynamic-wind
| 3. do exceptions with the new call/wc and use the original call/cc
| for threading
+---------------
It's worse than that. The Scheme spec makes no guarantee that program
errors will invoke a [captured top-level] continuation, thus you have
no guarantee whatsoever that, say, "(/ 1 0)" or "(* 5 'foo)" will even
*do* an unwind!!
-Rob
p.s. Precisely because MzScheme *was* designed (or evolved) to support
instructional programming, with DrScheme (and its MrEd-based GUIs) allowing
execution of arbitrary student code yet wanting to catch all errors itself,
MzScheme exception-handling system *does* interact fairly nicely with both
call/cc & dynamic-wind. But that's just one implementation, not the standard.
Brian Denheyer
Joe> Is dynamic-wind appropriate for cleanup code though?
Actually that's what prompted my question.
I am porting some of the scsh code to gambit-c and I _thought_ I
needed dynamic wind, which is not in gambit-c 3.0.
scsh is using dynamic-wind exactly as you say. Get a file descriptor,
the call which uses the fd fails, the after thunk closes the fd.
I am doing a lot of thinking about exactly how to handle errors in
deeply nested code, and coming to the conclusion that passing up a
return value from 5+ levels deep just isn't the way to go (duh).
It does seem like dynamic-wind is a reasonable way to accomplish
clean-up after an "exception".
Joe> Most cases of cleanup code I can think of -- closing
Joe> open file descriptors, releasing COM handles, dismissing
Joe> dialog boxes, et cetera -- are things that need to
Joe> be called exactly once. With dynamic-wind, the 'after'
Joe> and 'before' thunks can be called multiple times.
Joe> It seems to me that dynamic-wind is better suited for
Joe> implementing things like coroutines or cooperative
Joe> multitasking; it doesn't seem to be useful for implementing
Joe> exception handlers or try-finally.
So this discussion is making me think that "hacking" dynamic wind into
gambit-c may not do what I would like it to do. Oh well, that's why I
stay up late and write test code :-) I'll know shortly ...
There is one other thing that I'm not clear on. There seems to be a
distinction between r4rs call/cc and r5rs call/cc. What I _think_ I
am reading is that implementing dynamic-wind in r4rs is not a problem,
where as in r5rs it is, because the operation of call/cc is
"different".
Is this right ?
Do I need to be wise in the ways of denotational semantics to really
understand the difference ? It appears to me it's something you would
only _truly_ understand if you had tried to implement a scheme.
Theory is nice, but it's practice that really you make sense of
things.
Brian
Joe Marshall
> Joe Marshall <j...@content-integrity.com> writes:
>
> > jeng...@flightlab.com (Joe English) writes:
> >
> > > The trouble is, you can implement call/wc on top of call/cc,
> > > but the reverse is not true. This is IMO a serious deficiency
> > > in R5RS.
> >
> > If there were a mechanism by which you could invoke a continuation
> > without running the appropriate exit and entry elements of
> > dynamic-wind, then you have defeated the purpose (and poked a hole in
> > the semantics) of dynamic-wind, have you not?
>
> No, you have not (at least not necessarily) because you can define the
> semantics of dynamic-wind that way.
Er, yes, but redefining the semantics of dynamic-wind doesn't close
the hole in the original semantics.
> And "defeating" the purpose of dynamic-wind is definitely something
> that one sometimes wants to do -- for example when implementing a
> scheduler for threads.
I understand the issues of multithreading, dynamic-wind, winding, etc.
I've come to the conclusion that CALL-WITH-CURRENT-CONTINUATION isn't
a suitable primitive for implementing multitasking. And since R5RS
doesn't address multitasking, I don't see that as a deficiency.
Joe Marshall
> Is dynamic-wind appropriate for cleanup code though?
> Most cases of cleanup code I can think of -- closing
> open file descriptors, releasing COM handles, dismissing
> dialog boxes, et cetera -- are things that need to
> be called exactly once.
I'm not sure there is a construct that will do `the right thing'
here. Presumably, though, the `before' thunk could attempt to re-open
the file descriptor, re-acquire a COM handle, re-display a dialog box,
etc.
> It seems to me that dynamic-wind is better suited for
> implementing things like coroutines or cooperative
> multitasking.
I disagree.
dynamic-wind started off as a `first-class continuation aware' version
of lisp's unwind-protect. Unwind-protect is used for cleaning things
up, never for multithreading. If dynamic-wind is unsuitable for
cleanup, I don't think that attempting to shoehorn it into a
multithreading role is appropriate.
> Anyway, call/wc is a more complicated construct than call/cc.
> That R5RS provides the complicated one and not the simple one
> as a primitive is what I consider the deficiency.
Maybe we should figure out two things:
1. How do you do `unwind-protect' in Scheme if not via
dynamic-wind?
2. How should multiple threads be addressed, and how should
they interact with cwcc and dynamic wind?
>
> --Joe English
>
> jeng...@flightlab.com
felix
Joe Marshall wrote in message <3dfgdw...@content-integrity.com>...
>
> 2. How should multiple threads be addressed, and how should
> they interact with cwcc and dynamic wind?
>
I think the approach Matthias gave is quite appropriate: provide two
versions of call/cc, a simple one that is not aware of dynamic-wind,
and a winding one.
(In CHICKEN I use this method: there is "%%call-with-current-continuation",
which is the basic one, it's actually just used by the scheduler [*], and
"call-with-current-continuation", which does winding (the SLIB way))
felix
--
[*] Well, you can use it anywhere you like (if you need dead fast
continuations). But then of course it's your own fault if you
use it together with dynamic-wind.
Matthias Blume
> Matthias Blume <s...@my.sig> writes:
>
> > Joe Marshall <j...@content-integrity.com> writes:
> >
> > > jeng...@flightlab.com (Joe English) writes:
> > >
> > > > The trouble is, you can implement call/wc on top of call/cc,
> > > > but the reverse is not true. This is IMO a serious deficiency
> > > > in R5RS.
> > >
> > > If there were a mechanism by which you could invoke a continuation
> > > without running the appropriate exit and entry elements of
> > > dynamic-wind, then you have defeated the purpose (and poked a hole in
> > > the semantics) of dynamic-wind, have you not?
> >
> > No, you have not (at least not necessarily) because you can define the
> > semantics of dynamic-wind that way.
>
> Er, yes, but redefining the semantics of dynamic-wind doesn't close
> the hole in the original semantics.
>
> > And "defeating" the purpose of dynamic-wind is definitely something
> > that one sometimes wants to do -- for example when implementing a
> > scheduler for threads.
>
> I understand the issues of multithreading, dynamic-wind, winding, etc.
> I've come to the conclusion that CALL-WITH-CURRENT-CONTINUATION isn't
> a suitable primitive for implementing multitasking. And since R5RS
> doesn't address multitasking, I don't see that as a deficiency.
Call/cc is often touted as the "one for all" primitive that lets you do
everything -- including multitasking. In fact, cooperative threads are
the prime textbook example. If you drop that, you may as well drop call/cc
altogether. (If the language had native threads and native exceptions,
that would not be such a bad choice, IMO.)
Rob Warnock
+---------------
| dynamic-wind started off as a `first-class continuation aware' version
| of lisp's unwind-protect. Unwind-protect is used for cleaning things
| up, never for multithreading. If dynamic-wind is unsuitable for
| cleanup, I don't think that attempting to shoehorn it into a
| multithreading role is appropriate.
And as I pointed out in <URL:news:91uk40$f165j$1...@fido.engr.sgi.com>,
dynamic-wind (at least, the R5RS version) is not suitable for cleanup
at all, since it doesn't allow you to stop the unwinding! [Result of
call/cc in "after" thunk is undefined.]
+---------------
| > Anyway, call/wc is a more complicated construct than call/cc.
| > That R5RS provides the complicated one and not the simple one
| > as a primitive is what I consider the deficiency.
|
| Maybe we should figure out two things:
| 1. How do you do `unwind-protect' in Scheme if not via
| dynamic-wind?
+---------------
You don't, at least not an conform to the standard. [My article ref'd
above showed a non-standard way that works in SCM & MzScheme, but...]
But even if you did, there's no guarantee in the standard that *system*
errors will unwind, so it's useless in any case. Whereas in Common Lisp,
there *is* a guarantee that an unwind-protect will catch exceptions:
<URL:http://www.xanalys.com/software_tools/reference/HyperSpec/
Body/speope_unwind-protect.html>
Unwind-protect protects against all attempts to exit from
"protected-form"...
-Rob
Joe Marshall
> Call/cc is often touted as the "one for all" primitive that lets you
> do everything -- including multitasking.
It shouldn't be. You can sort of simulate multitasking with it, but
you cannot build a robust multitasking system on top of it (on top of
*either* the r4rs or the r5rs version.)
> In fact, cooperative threads are the prime textbook example.
Cooperative threads or co-routines? If the threads are independent,
then this would be a poor example indeed for a textbook!
> If you drop that, you may as well drop call/cc altogether.
I wouldn't go that far. cwcc is plenty useful, even if you can't
base a multithreaded shared-image implementation on top of it.
felix
Joe Marshall wrote in message ...
>
>It shouldn't be. You can sort of simulate multitasking with it, but
>you cannot build a robust multitasking system on top of it (on top of
>*either* the r4rs or the r5rs version.)
>
Not without some way to preempt the current task. But if a Scheme
implementation provides that, then (R4RS) call/cc is the perfect
device for this kind of job. The next release of Gambit for example will
offer a pretty
powerful real-time multitasking system based on call/cc (a while ago
Marc Feeley posted a very interesting benchmark in comp.lang.scheme,
in which Gambit threads outperformed native threads by an couple of orders
of a magnitude).
felix
jbs
felix wrote:
>
> Joe Marshall wrote in message ...
> >
> >It shouldn't be. You can sort of simulate multitasking with it, but
> >you cannot build a robust multitasking system on top of it (on top of
> >*either* the r4rs or the r5rs version.)
> >
>
> Not without some way to preempt the current task.
To do cooperative multitasking, which is very useful for a lot of
applications[*], you don't need to preempt anything.
[*] The very successful (in its day) Novell Netware network operating
system is based on cooperative multitasking, as is the Macintosh.
Joe Marshall
> Joe Marshall wrote in message ...
> >
> >It shouldn't be. You can sort of simulate multitasking with it, but
> >you cannot build a robust multitasking system on top of it (on top of
> >*either* the r4rs or the r5rs version.)
> >
>
> Not without some way to preempt the current task.
That is a necessary, but not sufficient condition.
> But if a Scheme implementation provides that, then (R4RS) call/cc is
> the perfect device for this kind of job.
I disagree.
Consider what multitasking is: the running of multiple threads of
execution within a single heap image.
Now consider how to accomplish that. The most direct way of doing so
would be to simultaneously run multiple instances of the Scheme
interpreter. For instance, on a machine *with multiple processors*.
Time-division multiplexing of a single processor is one way of
*simulating* the effect of multiple (slower) processors, but how the
effect is achieved, via multiple pieces of hardware or via a software
illusion is *below* the abstraction barrier and you shouldn't have to
know about it.
So imagine you have a dual-processor computer, and each processor is
running a thread in your scheme image. What should happen when a
thread performs a cwcc? What should happen when a thread attempts to
invoke a continuation captured by a different thread? How should an
`unwind-protect' work under these circumstances?
Now you *might* decide that you want to create a multi-threaded Scheme
implementation that time-slices the processor to create the illusion
of multiple threads. And you *might* have an implementation for which
the underlying continuation management code can do this easily (as in
Felix's), but I think that identifying *that* particular mechanism
with the R4RS cwcc is a mistake. You may choose to implement R4RS
cwcc using that underlying code, but you shouldn't confuse the
implementation with the abstraction.
felix
Joe Marshall wrote in message <7l4mr9...@content-integrity.com>...
> [...multi-processor stuff...]
Yes, you are right, of course. I was just assuming this is about
(lightweight) threads on a single-processor system (the much more
likely scenario, IMHO).
>... but I think that identifying *that* particular mechanism
>with the R4RS cwcc is a mistake. You may choose to implement R4RS
>cwcc using that underlying code, but you shouldn't confuse the
>implementation with the abstraction.
This is not quite true (or I grossly misunderstand you). *That*
particular mechanism (of multitasking) is implemented *using* R4RS call/cc,
not the other way round. The underlying continuation management code
is nothing special, just (non-winding/R4RS) call/cc.
Have you read Mitchell Wand's paper on multiprocessing? (I guess you have)
felix
Jeffrey B. Siegal
> Now consider how to accomplish that. The most direct way of doing so
> would be to simultaneously run multiple instances of the Scheme
> interpreter. For instance, on a machine *with multiple processors*.
That's not necessarily true. One of the benefits of cooperative
multitasking is that programming is much easier if you don't have to
worry about arbitrary preemptions or, even worse, multiprocessor
coordination.
For preemptive threads, call/cc might be obviously the wrong tool, but
not for nonpreemptive threads.
Marc Feeley
> running a thread in your scheme image. What should happen when a
> thread performs a cwcc? What should happen when a thread attempts to
> invoke a continuation captured by a different thread?
This is not a problem. Just read SRFI-21. The basic idea is that
each thread is created with an initial continuation that is roughly:
(lambda (result)
(let ((ct (current-thread)))
(thread-result-set! ct result)
(thread-terminate! ct)))
This continuation is valid in any thread. So a thread captured in one
thread can be invoked in a different thread T, and causes the
termination of T.
> How should an
> `unwind-protect' work under these circumstances?
You mean dynamic-wind, right? Yes this is a problem. I do not like
dynamic-wind, I do not like things of that kind. [I apologize for
the Dr. Seuss fans!] But the problem is with dynamic-wind, not with call/cc.
You will see that in SRFI-21 dynamic-wind only works when the
destination continuation was captured in the current thread.
Marc
J. A. Durieux (reply from http://www.biep.org/)
news:91t9e4$rn7$1...@dragon.flightlab.com...
> Is dynamic-wind appropriate for cleanup code though?
> Most cases of cleanup code I can think of -- closing
> open file descriptors, releasing COM handles, dismissing
> dialog boxes, et cetera -- are things that need to
> be called exactly once. With dynamic-wind, the 'after'
> and 'before' thunks can be called multiple times.
But isn't that as it should be?
If I open a file in a before chunk, capture a continuation, close the file
in the after chunk, and then jump into the continuation, shouldn't the file
be re-opened (and eventually re-closed)? And likewise if I jump in the
other direction, shouldn't the file be closed?
I should think the continuation wouldn't make much sense otherwise.
--
Biep
http://www.biep.org/
(email to me can be sent from there)
Joe Marshall
> "Joe English" <jeng...@flightlab.com> wrote in message
> news:91t9e4$rn7$1...@dragon.flightlab.com...
> > Is dynamic-wind appropriate for cleanup code though?
> > Most cases of cleanup code I can think of -- closing
> > open file descriptors, releasing COM handles, dismissing
> > dialog boxes, et cetera -- are things that need to
> > be called exactly once. With dynamic-wind, the 'after'
> > and 'before' thunks can be called multiple times.
>
> But isn't that as it should be?
> If I open a file in a before chunk, capture a continuation, close the file
> in the after chunk, and then jump into the continuation, shouldn't the file
> be re-opened (and eventually re-closed)?
I would think that would an acceptable course of action, provided the
dynamic-state could be restored. Signalling an error is another
option.
> And likewise if I jump in the
> other direction, shouldn't the file be closed?
It should definitely be open within the context and closed outside.
> I should think the continuation wouldn't make much sense otherwise.
Agreed.