Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!zephyr.ens.tek.com!tekcrl!tekchips!kend
From: kend@tekchips.LABS.TEK.COM (Ken Dickey)
Newsgroups: comp.object
Subject: Re: Continuations
Message-ID: <5135@tekcrl.LABS.TEK.COM>
Date: 29 Nov 89 20:31:35 GMT
References: <2664@bingvaxu.cc.binghamton.edu> <9624@pyr.gatech.EDU> <1623@odin.SGI.COM> <128489@sun.Eng.Sun.COM> <31794@news.Think.COM>
Sender: ftp@tekcrl.LABS.TEK.COM
Reply-To: kend@mrloog.WR.TEK.COM (Ken Dickey)
Organization: Tektronix, Inc., Beaverton,  OR.
Lines: 32

In article <31794@news.Think.COM> barmar@think.com writes:
>...  It's the very existence of first-class
>continuations in Scheme-like languages that causes them not to be
>stack-based. ...

[I saw this and could not help but respond... 8^]

People interested in this discussion might want to look at R. Kent
Dybvig's thesis "Three implementation models for Scheme", U of North
Carolina at Chappel Hill, 1987.  It describes heap and *stack* based
scheme implementation techniques.  Many (most?) compiled Scheme
implementations do use (possibly segmented) stacks.  A good discussion
of implementation techniques can be found in "Implementation
Strategies for Continuations" by Clinger, Hartheimer and Ost in the
'88 ACM Lisp & FP Conference Proceedings.  

I guess the gist of the above is that you can use a stack strategy
until a continuation is captured, at which time the used part of the
stack is `captured', marked immutable, and may be shared.  If indeed
shared, then it must be copied to be reexecuted--otherwise it could
not be reexecuted multiple times.  How the capture occurs depends on
your storage recycling (gc) strategy and may involve copying to the
heap, playing with page tables, etc.  There are some technical
wrinkles, but stack strategies are certainly widely used.  

Some people now believe that stacks are no longer required (e.g.
Appel, "Garbage Collection can be Faster than Stack Allocation",
Information Processing Letters, v25 #4, 1987), but that is another
question.


-Ken Dickey		kend@mrloog.WR.TEK.COM


Brought to you by Super Global Mega Corp .com