R5RS call/cc & dynamic-wind in terms of r4rs
Michael Klein
A while ago, this thread was active, and I was curious as to how one
would go about
implementing dynamic-wind & call/cc (r5rs semantics) using only a
function with
r4rs call/cc semantics. Let's call said function
r4rs-call-with-current-continuation.
-- Mike Klein
Below is the last message DejaNews had on the thread:
Subject: Re: R5RS is available
From: William D Clinger <wi...@ccs.neu.edu>
Date: 1998/03/20
Message-ID: <3512FA...@ccs.neu.edu>
Oops again. I think this inconsistency in the R5RS resulted from
inconsistent answers to the question "Is DYNAMIC-WIND a library
procedure?".
It is true that the semantic equation for callcc didn't get updated
in the R5RS. The reason for that, I think, is that the simplest
description I know of for the semantics of DYNAMIC-WIND is by means
of the Scheme code that implements the new-style call/cc using the
old-style call/cc. Hence I usually think of DYNAMIC-WIND as a
library procedure, at least when I'm thinking about its semantics.
It is not described as a library procedure in the R5RS because this
implementation of the new-style call/cc using the old-style call/cc
cannot be done safely except by the implementor, who must arrange
for the new-style call/cc to become defined, and the old-style
call/cc to disappear, before any library procedures or user code
ever calls CALL-WITH-CURRENT-CONTINUATION.
So the intention was that there would be only one call/cc, with
the new-style semantics. As Keith Wright pointed out, however,
the old-style semantics is still useful, at least as a conceptual
device, when thinking about the semantics of DYNAMIC-WIND.
Will
Matthias Blume
In article <355C20E5...@alumni.caltech.edu.nospam> Michael Klein <mkl...@alumni.caltech.edu.nospam> writes:
A while ago, this thread was active, and I was curious as to how one
would go about
implementing dynamic-wind & call/cc (r5rs semantics) using only a
function with
r4rs call/cc semantics. Let's call said function
r4rs-call-with-current-continuation.
The code for that is in J. Rees' "The Scheme of Things" report on "The
June 1992 Meeting". See the Scheme repository.
Subject: Re: R5RS is available
From: William D Clinger <wi...@ccs.neu.edu>
Date: 1998/03/20
Message-ID: <3512FA...@ccs.neu.edu>
Oops again. I think this inconsistency in the R5RS resulted from
inconsistent answers to the question "Is DYNAMIC-WIND a library
procedure?".
It is true that the semantic equation for callcc didn't get updated
in the R5RS. The reason for that, I think, is that the simplest
description I know of for the semantics of DYNAMIC-WIND is by means
of the Scheme code that implements the new-style call/cc using the
old-style call/cc. Hence I usually think of DYNAMIC-WIND as a
library procedure, at least when I'm thinking about its semantics.
It is not described as a library procedure in the R5RS because this
implementation of the new-style call/cc using the old-style call/cc
cannot be done safely except by the implementor, who must arrange
for the new-style call/cc to become defined, and the old-style
call/cc to disappear, before any library procedures or user code
ever calls CALL-WITH-CURRENT-CONTINUATION.
So the intention was that there would be only one call/cc, with
the new-style semantics. As Keith Wright pointed out, however,
the old-style semantics is still useful, at least as a conceptual
device, when thinking about the semantics of DYNAMIC-WIND.
This whole hoopla could have been completely avoided if "old-style"
call/cc would have been retained and a "new-style" call/cc would have
been added UNDER A DIFFERENT NAME. Since the new-style call/cc does
not actually call the given argument "with the current continuation",
this would be only logical. I propose something like
CALL-WITH-WINDING-CONTINUATION or CALL/WC.
With this one would be able to relegate both DYNAMIC-WIND and CALL/WC
to library status, and people (such as myself) who do not care about
DYNAMIC-WIND could safely ignore it there.
In my opinion, DYNAMIC-WIND is a new (additional) wart on the
language. The complications of properly defining it in the semantics
section are witness to that.
--
-Matthias
Keith Wright
bl...@ux03.cs.princeton.edu (Matthias Blume) writes:
> In article <355C20E5...@alumni.caltech.edu.nospam> Michael Klein
> <mkl...@alumni.caltech.edu.nospam> writes:
>
> A while ago, this thread was active, and I was curious as to how one
> would go about implementing dynamic-wind & call/cc (r5rs semantics)
> using only a function with r4rs call/cc semantics. Let's call said
> function r4rs-call-with-current-continuation.
Oh, please, let's not. But it's nice to see a thread where people
are taking some time to think---not just reacting.
>> The code for that is in J. Rees' "The Scheme of Things" report on "The
>> June 1992 Meeting". See the Scheme repository.
which is at http://www.cs.indiana.edu/scheme-repository/home.html
or http://www.cs.cmu.edu/Web/Groups/AI/html/repository.html .
it's just a little too long to post.
From: William D Clinger <wi...@ccs.neu.edu>
It is not described as a library procedure in the R5RS because this
implementation of the new-style call/cc using the old-style call/cc
cannot be done safely except by the implementor, who must arrange
for the new-style call/cc to become defined, and the old-style
call/cc to disappear, before any library procedures or user code
ever calls CALL-WITH-CURRENT-CONTINUATION.
So the intention was that there would be only one call/cc, with
the new-style semantics. As Keith Wright pointed out, however,
the old-style semantics is still useful, at least as a conceptual
device, when thinking about the semantics of DYNAMIC-WIND.
>> This whole hoopla could have been completely avoided if "old-style"
>> call/cc would have been retained and a "new-style" call/cc would have
>> been added UNDER A DIFFERENT NAME. Since the new-style call/cc does
>> not actually call the given argument "with the current continuation",
>> this would be only logical. I propose something like
>> CALL-WITH-WINDING-CONTINUATION or CALL/WC.
>>
I already proposed keeping both, with different names. I withdraw my
proposed names, I like these better.
>> With this one would be able to relegate both DYNAMIC-WIND and CALL/WC
>> to library status, and people (such as myself) who do not care about
>> DYNAMIC-WIND could safely ignore it there.
>>
I don't see why ignorability should depend on whether it is primitive
or defined in Scheme.
> In my opinion, DYNAMIC-WIND is a new (additional) wart on the
> language. The complications of properly defining it in the semantics
> section are witness to that.
>
So the question boils down to one wart or two? I can sympathize with
the desire to keep the number down, call/cc already makes my brain
feel a bit loose in my head. Now we can imagine duelling
continuations where one programmer wraps code in dynamic-wind to
ensure the exit procedures get called, while another one uses call/cc
instead of call/cw and screws up the whole plan.
But suppose we know what we are doing, is it reasonable to want to use
both? Suppose we have a big procedure called, say, think-hard. This
uses dynamic-wind and call/wc to build some fancy co-routine structure
where the entry proc in dynamic-wind sets up some hypothetical
situation, the middle proc reasons in that situation, and the exit
proc un-does the hypotheses. The whole thing is deeply recursive and
keeps lists of winding continuations to juggle various parts of the
tree search.
Now suppose that the computation can reach a point where it discovers
that the whole think-hard procedure is irrelevant, because something
has caught fire. Would it make sense to call
(call/cc (lambda(abort) (think-hard abort situation)))
where think-hard does a lot of complicated stuff, but may call
(if (on-fire) (abort "run for your life"))
to trash the whole computation (without pausing to unwind)?
I even imagine that this could pass through several levels. Perhaps
the "call/cc think-hard" expression is enclosed in a dynamic-wind that
ensures files are closed before terminating all computations and
turning on the sprinklers. But does this work right? The global
winding context (the *here* variable) still says we are in the
middle of think-hard, and there is a lot of unwinding to do before
we are out. So the call to abort did not really abort everything,
any call to a winding continuation will unwind think-hard before
continuing. Bug or feature?
Perhaps the wise Knights of the Lambda Calculus hid the old call/cc
to prevent us from breaking everything by trying to use incompatible
versions together.
But here's a scary thought:
(define call/cc (eval 'call/cc (scheme-report-environment 4)))
--
--Keith
This mail message sent by GNU emacs and Linux.
Food, Shelter, Source code.
Matthias Blume
>> With this one would be able to relegate both DYNAMIC-WIND and CALL/WC
>> to library status, and people (such as myself) who do not care about
>> DYNAMIC-WIND could safely ignore it there.
>>
I don't see why ignorability should depend on whether it is primitive
or defined in Scheme.
Agreed. I just want my good old call/cc without the winding stuff.
That's all.
> In my opinion, DYNAMIC-WIND is a new (additional) wart on the
> language. The complications of properly defining it in the semantics
> section are witness to that.
>
So the question boils down to one wart or two? I can sympathize with
the desire to keep the number down, call/cc already makes my brain
feel a bit loose in my head. Now we can imagine duelling
continuations where one programmer wraps code in dynamic-wind to
ensure the exit procedures get called, while another one uses call/cc
instead of call/cw and screws up the whole plan.
[ ... long example snipped ... ]
Of course, that danger is always there. It's just like someone using
lists as immutable tuples and someone else comes along, uses set-car!
and set-cdr!, and screws up the whole plan...
Personally, I don't want to have dynamic-wind AT ALL -- so I wouldn't
screw anything up. My CALL/WC is just a concession to people who
can't do without. IMNSHO, it is the programmer's responsibility to
use call/cc or call/wc consistently.
Dynamic-wind is for managing global state, and he who mixes global
state with coroutines is asking for trouble. In your example (which I
snipped), wouldn't it be better to pass the hypotheses (that
supposedly needed to be unwound and re-wound) as an argument to
THINK-HARD? No winding would be necessary then. I am not religious
about it -- side effects have their place -- but there is also
something to be said in favor of the functional paradigm...
--
-Matthias
Matthias Blume
At the risk of stealing my own thunder...
Here is an alternative implementation of CALL/WC and DYNAMIC-WIND that
I find more appealing. At the first glance it may look less elegant
than then one suggested by the 1992 meeting paper. However...
The main advantage is that it manages the data structure necessary for
remembering unwinding- and rewinding-thunks in a functional manner and
does not rely on side-effects. The code below still contains
assignments to global variables (*current-wc* and *current-i*), but
those can also be eliminated by making these variables into
arguments that are passed to every procedure.
This naturally leads to a straightforward explanation of DYNAMIC-WIND
and CALL/WC in denotational semantics. More importantly, the
explanation does not have to rely on the store.
Fortunately, up to a constant (and probably small) factor, the given
implementation is as fast as the one in the meeting paper.
-------------
The idea is completely straightforward: A "winding context" is a list
of before-after thunks. To go from "here" to "there" we need to find
the longest common tail of the two lists. We unwind the "here" list
up to that point and rewind the "there" list beginning from that
point. To find the longest common tail efficiently, we also
explicitly keep the length of each context (that's the ominous
*current-i*).
-Matthias
Here is the code... (Warning! This is barely tested!)
----------------------
(define (nothing) '())
(define *current-wc* (list (cons nothing nothing)))
(define *current-i* 0)
(define (wind-to! there-wc there-i)
(let ((here-wc *current-wc*)
(here-i *current-i*))
(define (unwind-rewind from to from-i)
(if (eq? from to)
'()
(begin (set! *current-wc* (cdr from))
(set! *current-i* (- from-i 1))
((cdar from))
(unwind-rewind (cdr from) (cdr to) (- from-i 1))
((caar to))
(set! *current-wc* to)
(set! *current-i* from-i))))
(define (unwind-more diff from to from-i)
(if (zero? diff)
(unwind-rewind from to from-i)
(begin (set! *current-wc* (cdr from))
(set! *current-i* (- from-i 1))
((cdar from))
(unwind-more (+ diff 1) (cdr from) to (- from-i 1)))))
(define (rewind-more diff from to from-i)
(if (zero? diff)
(unwind-rewind from to from-i)
(begin (rewind-more (- diff 1) from (cdr to) from-i)
((caar to))
(set! *current-wc* to)
(set! *current-i* (+ from-i diff)))))
(let ((diff (- there-i here-i)))
(cond ((< diff 0) (unwind-more diff here-wc there-wc here-i))
((> diff 0) (rewind-more diff here-wc there-wc here-i))
(else (unwind-rewind from to here-i))))))
(define (call-with-winding-continuation f)
(let ((here-wc *current-wc*)
(here-i *current-i*))
(call-with-current-continuation
(lambda (k)
(f (lambda args
(wind-to! here-wc here-i)
(apply k args)))))))
(define (dynamic-wind before middle after)
(let ((cur-wc *current-wc*)
(cur-i *current-i*))
(before)
(set! *current-wc* (cons (cons before after) cur-wc))
(set! *current-i* (+ cur-i 1))
(let ((result (middle)))
(set! *current-wc* cur-wc)
(set! *current-i* cur-i)
(after)
result)))
--
-Matthias
Matthias Blume
Here is an implementation/explanation if dynamic-wind and
call-with-winding-continuation that does not rely on destructive
update. I have alluded to that in my previous article.
Of course, the implementation below is not meant to be a serious
proposal for *implementing* call/wc and dynamic-wind _at the language
surface_. But it shows how these "features" could be explained in
denotational semantics. Furthermore, Scheme compilers could use this
"winder-passing-style" as their intermediate representation (along the
lines of the familiar continuation- and closure-passing styles).
In the implementation, all functions have an additional argument that
represents the current winding context together with its depth
(length). A winding context is simply a list of pairs of before/after
thunks. (I need to be able to detect the case where two contexts are
identical. In Scheme I use eq? for that. In denotational semantics one
would have to use some kind of explicit unique tags.)
Most functions simply pass the winding context around unchanged.
DYNAMIC-WIND creates new winding contexts, and the escape procedures
created by call-with-winding-continuation use the auxiliary function
"wind" to run the appropriate set of before/after thunks.
An implementation based on this proposal has the advantage that it is
well-defined what happens if someone uses call/cc instead of call/wc
in a program that also uses dynamic-wind: An escape-procedure created
by call/cc (in my code this is called CALL-WITH-CURRENT-CONTINUATION-WPS)
will not run any of the before/after thunks between "there" and
"here", but it _will_ restore the correct winding context. This is
in contrast to the code shown in the "meeting paper" where using (the
original) call/cc would leave the global data structure used for
winding in an incorrect state because no rerooting of the winder tree
would take place.
Also, the lack of destructive updates counts as a definite plus in my
book... (... which, of course, is not unrelated to those previously
mentioned advantages).
-Matthias
Here is the code. An example of "factorial" in winder-passing style
is added at the bottom.
;------------------------------------SNIP--------------------------
;; winding arg: (<wc> . <i>)
;; where <wc> is a list of pairs of the form ((<before> . <after>) ...)
;; and where <i> = (length <wc>)
;; we need a call/cc in "winder-passing style":
(define (call-with-current-continuation-wps here f)
(call-with-current-continuation
(lambda (k)
(f here
(lambda (ignore x)
(k x))))))
;; auxiliary function to do the unwinding/rewinding:
(define (wind from to)
;; if both winding contexts are equally long:
(define (unwind-rewind from-wc i to-wc)
(if (eq? from-wc to-wc)
'()
(let ((after-from (cdar from-wc))
(before-to (caar to-wc))
(from-wc (cdr from-wc))
(to-wc (cdr to-wc))
(i (- i 1)))
(after-from (cons from-wc i))
(unwind-rewind from-wc i to-wc)
(before-to (cons to-wc i)))))
;; if the "from" context is longer than the "to" context:
(define (unwind-more diff from-wc from-i to-wc)
(if (zero? diff)
(unwind-rewind from-wc from-i to-wc)
(let ((after-from (cdar from-wc))
(from-wc (cdr from-wc))
(from-i (- from-i 1))
(diff (- diff 1)))
(after-from (cons from-wc from-i))
(unwind-more diff from-wc from-i to-wc))))
;; if the "from" context is shorter than the "to"-context:
(define (rewind-more diff from-wc to-wc to-i)
(if (zero? diff)
(unwind-rewind from-wc to-i to-wc)
(let ((before-to (caar to-wc))
(to-wc (cdr to-wc))
(to-i (- to-i 1))
(diff (+ diff 1)))
(rewind-more diff from-wc to-wc to-i)
(before-to (cons to-wc to-i)))))
(let* ((from-wc (car from))
(from-i (cdr from))
(to-wc (car to))
(to-i (cdr to))
(diff (- from-i to-i)))
;; do simple case analysis and call appropriate function
(cond ((< diff 0) (rewind-more diff from-wc to-wc to-i))
((> diff 0) (unwind-more diff from-wc from-i to-wc))
(else (unwind-rewind from-wc from-i to-wc)))))
;; here is where it's at...
(define (call-with-winding-continuation here f)
(call-with-current-continuation-wps
here
(lambda (here k)
(f here
(lambda (there x)
(wind there here)
;; alternative fast-path shortcut for the previous line:
;; (if (not (eq? (car there) (car here))) (wind there here))
(k here x))))))
(define (dynamic-wind here before middle after)
(before here)
(let* ((new-here (cons (cons (cons before after) (car here))
(+ (cdr here) 1)))
(result (middle new-here)))
(after here)
result))
;------------------------------------SNIP-----------------------
;; Example: Fibonacci test code (with some bells and whistles to
;; demonstrate winding/unwinding):
;; make initial winding context
(define (nothing here) '())
(define here (cons (List (cons nothing nothing)) 0))
;; global variable for storing continuation
(define global-k #f)
;; global flag to control whether factorial should bail out
(define escape #f)
;; exit continuation; after bailing out, the value of exit will be: ESCAPED!
(define exit
(call-with-winding-continuation
here
(lambda (here k) k)))
;; factorial (+ winding test code) in winder-passing style
(define (fac-wps here n)
(if (zero? n)
(call-with-winding-continuation
here
(lambda (here k)
(set! global-k k)
(if escape
(exit here 'escaped!)
1)))
(dynamic-wind
here
(lambda (here) (write (list 'Enter: n)) (newline))
(lambda (here) (* n (fac-wps here (- n 1))))
(lambda (here) (write (list 'Enter: n)) (newline)))))
--
-Matthias
William D Clinger
Matthias Blume wrote:
> Personally, I don't want to have dynamic-wind AT ALL -- so I wouldn't
> screw anything up.
If you are the only programmer on a project, and you don't use any libraries
that were written by anyone else, and no one else will ever use your code
after you have written it, then you won't screw anything up by using R4RS
CALL-WITH-CURRENT-CONTINUATION in place of the R5RS version that interacts
properly with DYNAMIC-WIND.
In the real world, using R4RS CALL-WITH-CURRENT-CONTINUATION in R5RS Scheme
would be asking for trouble. That's why R5RS CALL-WITH-CURRENT-CONTINUATION
must know about DYNAMIC-WIND, and that's why the R5RS doesn't describe a
second version of CALL-WITH-CURRENT-CONTINUATION with the R4RS semantics.
(As I explained in a previous message, the denotational semantics of call/cc
in the appendix of the R5RS is just wrong, because we forgot to change it.)
I appreciate Blume's code, and I look forward to reading it carefully.
Will
Keith Wright
William D Clinger <wi...@ccs.neu.edu> writes:
> Matthias Blume wrote:
>
> In the real world, using R4RS CALL-WITH-CURRENT-CONTINUATION in R5RS Scheme
> would be asking for trouble. That's why R5RS CALL-WITH-CURRENT-CONTINUATION
> must know about DYNAMIC-WIND, and that's why the R5RS doesn't describe a
> second version of CALL-WITH-CURRENT-CONTINUATION with the R4RS semantics.
>
Can you explain the nature of the trouble I am asking for? If there were
a call-with-current-continuation, and call-with-winding-continuation there
would be two kinds of continuation, direct and winding. If you call a
direct continuation you just go directly, if call a winding continuation
the winding gets done. The semantics is clear enough, since call/wc is
defined in terms of call/cc. Of course you can write a bug if you call
the wrong kind of continuation, but is there no way they can co-exist?
> I appreciate Blume's code, and I look forward to reading it carefully.
>
I am a little uncertain on the point. Is this code meant to have the
same semantics as the "zipper tree" code in the June meeting document,
but implemented better, or is it meant to implement "better"
semantics?
William D Clinger
Keith Wright wrote:
> Can you explain the nature of the trouble I am asking for? If there were
> a call-with-current-continuation, and call-with-winding-continuation there
> would be two kinds of continuation, direct and winding. If you call a
> direct continuation you just go directly, if call a winding continuation
> the winding gets done. The semantics is clear enough, since call/wc is
> defined in terms of call/cc. Of course you can write a bug if you call
> the wrong kind of continuation, but is there no way they can co-exist?
They can co-exist in some sense, but I don't think they can co-exist very
well. In particular, I don't see how any R5RS-conforming implementation
of Scheme can support a procedure that has the R4RS semantics for call/cc.
The main reason for having DYNAMIC-WIND in the language is to provide a
guarantee that
(dynamic-wind thunk1 thunk2 thunk3)
can't return a value unless both thunk1 and thunk3 have been evaluated,
in that order. (They might be evaluated several times, in fact, but
always in that order, and these evaluations are never nested.)
A use of R4RS CALL-WITH-CURRENT-CONTINUATION would destroy this guarantee,
which is part of the R5RS specification of DYNAMIC-WIND. It would also
break most code that uses DYNAMIC-WIND.
Matthias Blume dismissed this problem by writing:
> Of course, that danger is always there. It's just like someone using
> lists as immutable tuples and someone else comes along, uses set-car!
> and set-cdr!, and screws up the whole plan...
>
> Personally, I don't want to have dynamic-wind AT ALL -- so I wouldn't
> screw anything up. My CALL/WC is just a concession to people who
> can't do without. IMNSHO, it is the programmer's responsibility to
> use call/cc or call/wc consistently.
In my message, I tried to point out that this is not a realistic
attitude for multi-programmer projects, or for projects that use code
libraries written by other people, or for software that will be used,
maintained, and extended by other people.
Blume's analogy with mutable pairs has some validity, but there are
some important differences. Mutable pairs are redundant in Scheme,
because we could use two-element vectors instead. It is sometimes
convenient that MEMQ etc work on mutable as well as immutable pairs,
but we could probably design vector versions of MEMQ etc in a couple
of hours or less so that isn't a very compelling argument. In my
opinion, Scheme would be a better language without SET-CAR! and SET-CDR!,
because immutable pairs would allow us to express things that we can't
express now: compound data that can't be mutated.
Unlike mutable pairs, DYNAMIC-WIND is not redundant. Nothing else
interacts with CALL-WITH-CURRENT-CONTINUATION so as to guarantee
sequencing of actions.
So if we're going to get rid of something, let's get rid of SET-CAR!
and SET-CDR!, not DYNAMIC-WIND.
> I am a little uncertain on the point. Is [Blume's] code meant to have the
> same semantics as the "zipper tree" code in the June meeting document,
> but implemented better, or is it meant to implement "better"
> semantics?
I believe it was meant to have the same semantics (when R4RS call/cc is
not available), but to be a more elegant specification of that semantics
because it does not use side effects. This makes it a more suitable
addition to the denotational semantics of Scheme. That is why I am very
pleased that Matthias Blume has made it available.
It may also have been intended to have a better semantics when R4RS call/cc
is available. For reasons explained above, I don't think this is a good
idea, and I don't believe any R5RS-conforming implementation can do this.
Will
Matthias Blume
William D Clinger <wi...@ccs.neu.edu> writes:
> Matthias Blume wrote:
>
> In the real world, using R4RS CALL-WITH-CURRENT-CONTINUATION in R5RS Scheme
> would be asking for trouble. That's why R5RS CALL-WITH-CURRENT-CONTINUATION
> must know about DYNAMIC-WIND, and that's why the R5RS doesn't describe a
> second version of CALL-WITH-CURRENT-CONTINUATION with the R4RS semantics.
>
Can you explain the nature of the trouble I am asking for?
Dynamic-wind is typically used to maintain certain dynamic invariants
of the global state. If someone gives you a library that internally
uses dynamic-wind, and you pass it a higher-order function of your own
that bails out bypassing the winders, then the library is likely to
get confused.
Of course, the blame is not so much with call/cc but with the very
fact that the library is using global state...
If there were
a call-with-current-continuation, and call-with-winding-continuation there
would be two kinds of continuation, direct and winding. If you call a
direct continuation you just go directly, if call a winding continuation
the winding gets done. The semantics is clear enough, since call/wc is
defined in terms of call/cc. Of course you can write a bug if you call
the wrong kind of continuation, but is there no way they can co-exist?
> I appreciate Blume's code, and I look forward to reading it carefully.
>
I am a little uncertain on the point. Is this code meant to have the
same semantics as the "zipper tree" code in the June meeting document,
but implemented better, or is it meant to implement "better"
semantics?
Both (to the degree that that's possible :).
1. If you only have my call/wc and my dynamic wind, then it should
behave exactly like the ones described in the June meeting paper.
2. My implementation does not rely on side-effects. IMO, that's good
all by itself, but it also means that one can easily take it as a
guideline for coding up denotational semantics. This will be a lot
more straightforward because there needs to be no mention of the
store.
3. If you allow both call/wc _and_ call/cc, then my code gives better
semantics (namely the ones that you assumed above). The zipper-tree
implementation breaks if you use r4rs call/cc directly because it
relies on an important invariant: The state tree must always be rooted
at the current state.
--
-Matthias
Dorai Sitaram
In article <iziun1t...@ux02.CS.Princeton.EDU>,
Matthias Blume <bl...@ux02.cs.princeton.edu> wrote:
>
>Dynamic-wind is typically used to maintain certain dynamic invariants
>of the global state. If someone gives you a library that internally
>uses dynamic-wind, and you pass it a higher-order function of your own
>that bails out bypassing the winders, then the library is likely to
>get confused.
>
>Of course, the blame is not so much with call/cc but with the very
>fact that the library is using global state...
But it may not be realistic to expect a library to
perform no file/port manipulation whatsoever...
Matthias Blume
>Of course, the blame is not so much with call/cc but with the very
>fact that the library is using global state...
But it may not be realistic to expect a library to
perform no file/port manipulation whatsoever...
If IO were done using functional streams, this would not be an issue.
Also, I would call it unrealistic to require files to be
opened/closed/rewound/... on every context switch in a concurrent
system that happens to be implemented using continuations.
--
-Matthias
Keith Wright
bl...@ux02.cs.princeton.edu (Matthias Blume) writes:
> In article <yk90nxl...@tiac.net> Keith Wright <kwr...@tiac.net> writes:
> Can you explain the nature of the trouble I am asking for?
>
> Dynamic-wind is typically used to maintain certain dynamic invariants
> of the global state. If someone gives you a library that internally
> uses dynamic-wind, and you pass it a higher-order function of your own
> that bails out bypassing the winders, then the library is likely to
> get confused.
How could the library get confused if it is _gone_? If you get back
into it by calling a continuation it has produced, then presumably
that is a winding continuation, and all necessary winding will be done
when you call that. Maybe a better metaphor is to say that the
library has messed up some global state, intending to put it right on
exit, but you have killed it before it can make things right.
But maybe you _wanted_ to do that. Maybe that's why you used a
non-winding continuation.
What if we call them CALL-WITH-CURRENT-CONTINUATION (which does the
winding), and CALL-WITH-NONWINDING-CONTINUATION (which does not).
That way having both becomes an extention rather than a variation.
(In fact this is an extention of both R4RS and R5RS, since R4 did not
contain DYNAMIC-WIND both procedures were equivalent at that time).
Matthias Blume
> Dynamic-wind is typically used to maintain certain dynamic invariants
> of the global state. If someone gives you a library that internally
> uses dynamic-wind, and you pass it a higher-order function of your own
> that bails out bypassing the winders, then the library is likely to
> get confused.
How could the library get confused if it is _gone_?
If it is gone -- fine. (C++ folks would disagree, because they
typically want to call all those stu^H^H^Hwonderful deconstructors
before something goes for good. Same problem -- too much global
state.)
If you get back
into it by calling a continuation it has produced, then presumably
that is a winding continuation, and all necessary winding will be done
when you call that.
But what if you don't get back via a winding continuation? (Actually,
if you left via some non-winding continuation, you better also get
back in via a non-winding continuation. The reason is that the
library still "thinks" that you never left, and it may get confused if
you "enter" it for a "second time".)
Maybe a better metaphor is to say that the
library has messed up some global state, intending to put it right on
exit, but you have killed it before it can make things right.
But maybe you _wanted_ to do that. Maybe that's why you used a
non-winding continuation.
Well, that's my point. I am also in favor of having non-winding
continuations. But I acknowledge that one has to be very careful if
one mixes both kinds (i.e., one needs to know what one is doing).
One typical scenario where R4RS call/cc is exactly The Right Thing
(winders or no winders) is the scheduler in a system that implements
concurrency. Ideally, a context switch should not be observable
through the semantics of the concurrent system because it is only
there to simulate multiple hardware CPUs. If all you have is
R5RS-style call/wc, then you cannot make context-switches unobservable
because the user program can always use dynamic-wind to find out.
(Not to mention the danger of an arbitrary slowdown of context
switches. I find that intolerable.)
What if we call them CALL-WITH-CURRENT-CONTINUATION (which does the
winding), and CALL-WITH-NONWINDING-CONTINUATION (which does not).
That way having both becomes an extention rather than a variation.
(In fact this is an extention of both R4RS and R5RS, since R4 did not
contain DYNAMIC-WIND both procedures were equivalent at that time).
I like the CALL-WITH-CURRENT-CONTINUATION (R4RS)/
CALL-WITH-WINDING-CONTINUATION (R5RS) naming scheme better, because
despite its name, R5RS call/cc does not actually call its argument
with the _current_ continuation.
--
-Matthias
Keith Wright
bl...@ux01.cs.princeton.edu (Matthias Blume) writes:
> In article <ykyavva...@tiac.net> Keith Wright <kwr...@tiac.net> writes:
>
> If you get back
> into it by calling a continuation it has produced, then presumably
> that is a winding continuation, and all necessary winding will be done
> when you call that.
>
> But what if you don't get back via a winding continuation?
You can't get back via a non-winding continuation, because the library
does not produce any (unless the library author wants you to do this).
I suppose you could mess up by calling it again, is that what you mean?
> (Actually,
> if you left via some non-winding continuation, you better also get
> back in via a non-winding continuation. The reason is that the
> library still "thinks" that you never left, and it may get confused if
> you "enter" it for a "second time".)
Using "zipper tree" semantics, I think it works out exactly right, because
the non-winding continuation is "unobservable". You are out and back
without changing the winding context, and nobody the wiser. (I have to
admit that I haven't yet absorbed your "winding passing style" semantics.)
Maybe I should take a vow of silence until I think I understand both of
them.
> Well, that's my point. I am also in favor of having non-winding
> continuations. But I acknowledge that one has to be very careful if
> one mixes both kinds (i.e., one needs to know what one is doing).
Careful!? I'm scared witless.
> One typical scenario where R4RS call/cc is exactly The Right Thing
> (winders or no winders) is the scheduler in a system that implements
> concurrency. Ideally, a context switch should not be observable
^^^^^^^^^^
What you don't know can't hurt you (until you find out too late).
> I like the CALL-WITH-CURRENT-CONTINUATION (R4RS)/
> CALL-WITH-WINDING-CONTINUATION (R5RS) naming scheme better, because
> despite its name, R5RS call/cc does not actually call its argument
> with the _current_ continuation.
>
Well, I like it too, but we may have to give it up for compatibility.
Matthias Blume
bl...@ux01.cs.princeton.edu (Matthias Blume) writes:
> In article <ykyavva...@tiac.net> Keith Wright <kwr...@tiac.net> writes:
>
> If you get back
> into it by calling a continuation it has produced, then presumably
> that is a winding continuation, and all necessary winding will be done
> when you call that.
>
> But what if you don't get back via a winding continuation?
You can't get back via a non-winding continuation, because the library
does not produce any (unless the library author wants you to do this).
I suppose you could mess up by calling it again, is that what you mean?
No, that's not what I mean. If the library has higher-order
functions, then I as a user can pass in anything I like and produce a
non-winding continuation that lets me get back there.
> (Actually,
> if you left via some non-winding continuation, you better also get
> back in via a non-winding continuation. The reason is that the
> library still "thinks" that you never left, and it may get confused if
> you "enter" it for a "second time".)
Using "zipper tree" semantics, I think it works out exactly right, because
the non-winding continuation is "unobservable". You are out and back
without changing the winding context, and nobody the wiser. (I have to
admit that I haven't yet absorbed your "winding passing style" semantics.)
Maybe I should take a vow of silence until I think I understand both of
them.
If nothing goes "wrong", then the two are equivalent. But with
winder-passing style nothing can go wrong even if you have r4rs- and
r5rs-call/cc. That's in contrast to zipper-trees which do get
confused if you jump from here to there using r4rs-call/cc and then
try to go back using r5rs-call/cc.
> I like the CALL-WITH-CURRENT-CONTINUATION (R4RS)/
> CALL-WITH-WINDING-CONTINUATION (R5RS) naming scheme better, because
> despite its name, R5RS call/cc does not actually call its argument
> with the _current_ continuation.
>
Well, I like it too, but we may have to give it up for compatibility.
Compatibility with WHAT? R5RS didn't even exist until a few weeks ago...
--
-Matthias
be...@damek.kth.se
In article <izk97da...@ux01.CS.Princeton.EDU>,
bl...@ux01.cs.princeton.edu (Matthias Blume) wrote:
> In article <ykn2ca6...@tiac.net> Keith Wright <kwr...@tiac.net> writes:
...deleted
> Well, I like it too, but we may have to give it up for compatibility.
>
> Compatibility with WHAT? R5RS didn't even exist until a few weeks ago...
There is a pre-R6RS workshop announced. Perhaps a knowledgeable person
could send in a suggestion that both call-with-current-continuation and
call-with-winding-continuation should be in R6RS?
BTW, what are the chances that something could be _removed_ from R5RS?
I.e. why not try and clean up Scheme?
I belive that Shriram Krishnamurthi has posted that multiple return values
are a performance bottle neck, and adds complexity, for all the cases
where they are not needed. Other people have suggested that the
performance gain in the (few?) cases where multiple values are used could
be had from a better compiler, instead. So why not remove them?
Other things (with-input-from-file comes to mind) have also been mentioned
as trouble makers.
Andi Kleen
be...@damek.kth.se writes:
> In article <izk97da...@ux01.CS.Princeton.EDU>,
> bl...@ux01.cs.princeton.edu (Matthias Blume) wrote:
>
> > In article <ykn2ca6...@tiac.net> Keith Wright <kwr...@tiac.net> writes:
> ...deleted
> > Well, I like it too, but we may have to give it up for compatibility.
> >
> > Compatibility with WHAT? R5RS didn't even exist until a few weeks ago...
>
> There is a pre-R6RS workshop announced. Perhaps a knowledgeable person
> could send in a suggestion that both call-with-current-continuation and
> call-with-winding-continuation should be in R6RS?
How about a _standard_ defstruct macro ?
-Andi