implementing dynamic-wind
Marijn
nicely. In fact I am so far with it that I feel up to the challenge of
implementing some of the weirder parts of the R5RS - hygienic macros
and dynamic-wind.
I'll bother you all about hygienic macros later, what has me stunned
right now is dynamic-wind. The main question I had is: Can
dynamic-wind be implemented without complicating the basic evaluation
system?
I've got a system that first compiles code to a bytecode
representation, and then runs it. I do not care much about increasing
the complexity of the compile stage a little, and call/cc could get
somewhat bigger if necessary, but I do not want to add stuff to the
basic continuation data structure. - Yet it seems that dynamic-wind
requires a way to store stuff in my continuations. The 'normal'
execution of the before and after thunks can be done simply by the
dynamic-wind function itself, but when continuations get swapped in
and out by call/cc the evaluator has to know about the functions it
needs to execute. A table on the side associating continuations with
functions as seen in the more ad-hoc dynamic-wind hacks does not look
very scalable, it seems to me that there is no way to remove entries
in this table once a continuation is no longer reachable.
I hope I'm missing some nice elegant way of doing this...
Marijn Haverbeke
David Rush
> what has me stunned
> right now is dynamic-wind. The main question I had is: Can
> dynamic-wind be implemented without complicating the basic evaluation
> system?
Oh good. Another opportunity for endless trolling and flames ;)
dynamic-wind is a much discussed construct (the first google
references date back to the early 90s) For the sake of
discussion, I'll use the following names:
call/cc - R4RS call-with-current-continuation (no dyn-wind)
call/wc - R5RS call-with-current-continuation
It turns out that call/wc can be implemented entirely in terms of
call/cc. The controversial part is that I think that both call/cc and
call/wc should be available.
> I've got a system that first compiles code to a bytecode
> representation, and then runs it. I do not care much about increasing
> the complexity of the compile stage a little, and call/cc could get
> somewhat bigger if necessary, but I do not want to add stuff to the
> basic continuation data structure. - Yet it seems that dynamic-wind
> requires a way to store stuff in my continuations.
...
> I hope I'm missing some nice elegant way of doing this...
Matthias Blume's 1998 implementation is appended to this
message.
david rush
--
I am not here because of what lies ahead of me, but because of
what lies behind me
-- Morpheus, _The Matrix: Reloaded_
; from http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=izvhr5y4jy.fsf%40ux01.CS.Princeton.EDU&rnum=5
(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)))
Marcin 'Qrczak' Kowalczyk
> I'll bother you all about hygienic macros later, what has me stunned
> right now is dynamic-wind. The main question I had is: Can
> dynamic-wind be implemented without complicating the basic evaluation
> system?
Yes. Only call/cc must be changed a bit.
http://www.cs.hmc.edu/~fleck/envision/scheme48/meeting/node7.html
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Michael Sperber
Marijn> I'll bother you all about hygienic macros later, what has me stunned
Marijn> right now is dynamic-wind. The main question I had is: Can
Marijn> dynamic-wind be implemented without complicating the basic evaluation
Marijn> system?
Yes. You merely need to have a slightly fancier implementation of
call/cc. Jonathan Rees's '92 Scheme of Things column shows how to do
it using pointer reversal
http://mumble.net/~jar/pubs/scheme-of-things/june-92-meeting.ps
The TABA-style implementation in Scheme 48 (in scheme/rts/wind.scm) is
even simpler.
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
Marijn
like that. The code from the june 92 meeting paper is quite weird, but
it works. And after staring at it for half an hour I also managed to
grasp why it works. Dynamic-wind down, only bignums and hygienic
macro's left to do...
Jens Axel Søgaard
In case you want to make the same stunt twice and implement
bignums in Scheme, here is some ideas:
<http://www.mactech.com/articles/mactech/Vol.08/08.03/BigNums/>
--
Jens Axel Søgaard
Marijn
> bignums in Scheme, here is some ideas:
>
> <http://www.mactech.com/articles/mactech/Vol.08/08.03/BigNums/>
Nice article, too late though... I just finished implementing bignums
with C++ code this morning. I'm still open to any articles that
explain the exact scoping rules of macro expansion in simple terms
though.
Display Name
"Marijn" <mari...@hotmail.com> wrote in message
> I'm still open to any articles that
> explain the exact scoping rules of macro expansion in simple terms
> though.
This may help as a first step:
http://groups.google.com/groups?selm=87it8db0um.fsf%40radish.petrofsky.org
Andre
David Rush
The current canonical text is Al* Petrofsky's _A Syntax Rules Primer
for the Mildly Insane_. Google groups for it. It's an excellent text.
And if you have a running Scheme interpreter Al has also written a
syntax-rules expander that is completely independent of eval (which
most of the rest of the extant expanders do use).
david rush
--
If you're stuck at the level of wanting to point at a picture and
click, you've got to understand that you're basically at the same
level as a preverbal child...
-- bear (on comp.lang.scheme)
Algebraic Petrofsky
> The current canonical text is Al* Petrofsky's _A Syntax Rules Primer
> for the Mildly Insane_. Google groups for it.
Here's a version with an important typo fixed:
http://petrofsky.org/src/primer.txt
Note that, unless you have a referral from your primary care
physician, it's likely that your health plan will only pay for Joe
Marshall's "Syntax-rules Primer for the Merely Eccentric":
http://home.comcast.net/~prunesquallor/macro.txt
-al
Marijn
> for the Mildly Insane_. Google groups for it. It's an excellent text.
> And if you have a running Scheme interpreter Al has also written a
> syntax-rules expander that is completely independent of eval (which
> most of the rest of the extant expanders do use).
I've read Petrofsky's article a few times and I think I understand
most of it. Still mostly in the dark on how I would implement it
though. My system does a separate compilation step in which identifier
are transformed to either a handle to a pair in the top environment if
they refer to top bindings, or a pair of numbers representing the
'distance' in the current environment (a list of vectors with the
values of the variables, the distance indicates that the variable
refers to the x-th element of the y-th vector). Now with a working
macro system I'd have to preprocess expressions that are lists
starting with a macro value to transform them. In this transformed
expression I'd have to represent the identifiers that are inserted
from the macro template differently from those that were part of the
original expression. Which opens a whole new can of worms because
set!, define, define-syntax, let-syntax and normal identifier
dereferencing all work with identifiers, and all in different ways.
Not to mention the problem of these 'identifiers from macro templates'
occuring inside a macro definition.
Where can I find this portable macro-expander? I googles but while
some people are talking about it, no one is linking to it. I'd like to
take a look at it and maybe, if the licence allows, cheap out and use
it as the macro expander for my own system.
Jens Axel Søgaard
> I've read Petrofsky's article a few times and I think I understand
> most of it. Still mostly in the dark on how I would implement it
> though.
Dybvig's article "Syntactic abstraction in Scheme" might
give you some ideas.
<http://www.cs.indiana.edu/chezscheme/syntax-case/>
Al*'s alexpander.scm can be found at <http://www.petrofsky.org/src/>.
--
Jens Axel Søgaard
David Rush
> I've read Petrofsky's article a few times and I think I understand
> most of it. Still mostly in the dark on how I would implement it
> though. My system does a separate compilation step in which identifier
> are transformed to either a handle to a pair in the top environment if
> they refer to top bindings, or a pair of numbers representing the
> 'distance' in the current environment
yes, I know the drill. Ideally, macro-expansion should be done
*before* any of those representations are instantiated. This is
actually why I've started on a second version of S2. I represented
syntax trees too naively to be able to easily implement
macro-expansion.
My point is that I have become convinced that one should to design your
datastructures to accomodate syntactic manipulations from the start,
which almost certainly means a fully-abstract identifier type.
david rush
--
It's not what you've got that matters, it's how you've got it.
-- Esmerelda Weatherwax in _Lords and Ladies_
Andre
> Where can I find this portable macro-expander?
Here :
http://www.cs.indiana.edu/chezscheme/syntax-case/
see also SLIB:
http://swissnet.ai.mit.edu/~jaffer/SLIB.html
Andre
felix
>
> Where can I find this portable macro-expander? I googles but while
> some people are talking about it, no one is linking to it. I'd like to
> take a look at it and maybe, if the licence allows, cheap out and use
> it as the macro expander for my own system.
http://www.petrofsky.org/src/alexpander.scm
cheers,
felix
Marijn
> *before* any of those representations are instantiated.
But if you transform the expression as a first step, how do you keep
scoping information intact? When two identifiers that are equal to
each other are inserted in the pre-compile step (which is how my
system currently works), the compiler has no way of knowing where they
came from. I suppose I should make a special 'macro inserted variable'
type, which contains an expression (either an identifier or another
macro inserted variable) and reference to a macro or the environment
associated with that macro. Icky.
I realized yesterday when looking through the documentation of
mzscheme that I do a bunch of stuff in a really backward way in my
implementation, so I'll probably drop this awful macro stuff for a
while to work on other stuff (error handling, better garbage
collection). It usually helps to get away from a hairy problem for a
while and then attack it with a fresh mind...
David Rush
> David Rush <ku...@gofree.indigo.ie> wrote in message
> > yes, I know the drill. Ideally, macro-expansion should be done
> > *before* any of those representations are instantiated.
>
> But if you transform the expression as a first step, how do you keep
> scoping information intact?
This is precisely the point. Initially you only know about the scope
of syntactic bindings. You don't really know *anything* about value
bindings until after you have completed syntactic expansions.
> When two identifiers that are equal to
> each other are inserted in the pre-compile step (which is how my
> system currently works), the compiler has no way of knowing where they
> came from.
This is why I have concluded that identifiers need to be a fully
abstract type. There's a lot of annotations that need to get attached
to them in a lexically-scoped system that provides macrotic
transformations of syntax-trees.
> I realized yesterday when looking through the documentation of
> mzscheme that I do a bunch of stuff in a really backward way in my
> implementation, so I'll probably drop this awful macro stuff for a
> while to work on other stuff (error handling, better garbage
> collection). It usually helps to get away from a hairy problem for a
> while and then attack it with a fresh mind...
Yup. Unfortunately, this path also easily leads to refactorings that
are more expensive than rewrites. Of course, you learn a lot on the
way and you have a system that is broken in ways that may be
acceptable to some audience. A lot depends on your goals.
david rush
--
Remember: There is no Scheme underground
Marijn
days, so I guess I could pollute it further by putting some other tiny
questions here instead of making a whole new thread.
First about begin, from my reading of the R5RS this:
(lambda ()
(begin
(define x 2)
2))
is not really valid. The point is the define inside the begin block. I
put it in a lambda because if the begin is top level it gets even more
confusing. Anyway, all interpreters I tried (mzscheme, scheme48,
guile) accept this without problem. I was thinking of inlining begin
blocks instread of macro-ing them into a lambda expression, but this
would make the above example invalid. Did I miss something in the R5RS
or do those interpreters just enhance the language a little? (or is it
yet another totally grey area where the standard is not clear?)
Another thing... Is it correct that from all the primitives defined in
the R5RS only set-car!, set-cdr! and vector-set! >>> modify 'pointers'
in existing scheme data structures <<< ? I guess depending on the
implementation of environments set! can usually be reduced to one of
these (it can in my implementation). I need to know because I am
trying to implement a simple (two-generation) generational garbage
collector, and when tracing the reachable cells of the young
generation I must know of any pointers that point from the old
generation into the new generation. If I can pull this off by only
modifying the three primitives mentioned it is not that hard, but I
have a feeling I am missing something here...
Marijn Haverbeke
Marcin 'Qrczak' Kowalczyk
> First about begin, from my reading of the R5RS this:
>
> (lambda ()
> (begin
> (define x 2)
> 2))
>
> is not really valid.
You are right.
My Scheme interpreter interprets it as a call to a function called
'define' (because it's indeed not an internal definition) but it
should be an error. I will fix this.
> Another thing... Is it correct that from all the primitives defined in
> the R5RS only set-car!, set-cdr! and vector-set! >>> modify 'pointers'
> in existing scheme data structures <<< ?
Also vector-fill!, and possibly other things depending on the
implementation, e.g. force, dynamic-wind, and as you said - set!,
and thus letrec and define.