Re: CPS in Parrot

[Matthias Felleisen <address@hidden>]

On Wednesday, August 6, 2003, at 02:29 AM, Michael Sperber wrote:

>>>>>> "Michael" == Michael Vanier <mvanier@cs.caltech.edu> writes:
>
> Michael> "And, just to top it off, someone (no, I don't know who, so 
> this might be
> Michael>  CS Legend) once proved that you can build any control 
> structure you can
> Michael>  think of with continuations."
>
> @INPROCEEDINGS{Filinski1994-popl,
>         CROSSREF = {POPL1994},
>         AUTHOR = {Andrzej Filinski},
>         TITLE = {Representing Monads},  YEAR = 1994,
>         PAGES = {446-457}
> }
>

It depends on what you mean with "build". It is certainly not true that 
FunctionalScheme + callcc
can express F (my good old friend that produces composable 
continuations, which eventually
made it into Mach 4). I also don't see how FunctionalScheme + callcc 
can express prompt.

I am also willing to throw in set! and challenge you again to define 
"build" in a way that excludes
at least thing.

My own definition of "build" was published as On the expressive power 
of programming languages.

The small stack slices that Michael mentions were first around in MIT 
Scheme and Chez Scheme.
But Mike's reference to Clinger's paper is appropriate.

-- Matthias


> I'm sure it's on Andrzej's homepage or on Citeseer.
>
> Michael> Also, Dan doesn't mention segmented stack architectures that 
> are
> Michael> essentially a linked list of stacklets of finite size.  With 
> this you can
> Michael> avoid most of the overhead of both stack copying (on the one 
> hand) and
> Michael> heap-allocated individual frames (on the other hand).  PLT 
> scheme uses this
> Michael> system.  There is a paper on this, but I can't find it right 
> now.
>
> PLT's implementation of CALL/CC (and threads) is still pretty
> expensive.  The paper to look at is
>
> @Article{Clinger:1999:ISF,
>   author =       "William D. Clinger and Anne H. Hartheimer and Eric M.
>                  Ost",
>   title =        "Implementation Strategies for First-Class
>                  Continuations",
>   journal =      "Higher-Order and Symbolic Computation",
>   volume =       "12",
>   number =       "1",
>   pages =        "7--45",
>   month =        apr,
>   year =         "1999"
> }
>
> -- 
> Cheers =8-} Mike
> Friede, Völkerverständigung und überhaupt blabla