call/cc evaluation 
Author Message
 call/cc evaluation

I'm trying to get a handle on call/cc, and I was wondering how you can
trace out by hand what a program using call/cc does. For example,
without set!, the "substitution model" can be applied to evaluate
expressions, but after that you need to add in the "environment model,"
with rules like these:

1. To create a fuction, create a pair with one element set to the list
of arguments and the body of the function, and the other the environment
in which it was defined.

2. To apply a function to arguments, create a new frame, with a parent
the environment from the function, and the arguments bound to their
values. Evaluate the body of the function in this new environment.

3. To evaluate an expression which is a list, evaluate all of it's
elements and apply the first item to the rest.

4 to n. Lots of special cases for special forms like set!, define,
lambda, let, etc.

How can these be modified to include continuations?



Sun, 20 Apr 2003 15:51:47 GMT  
 call/cc evaluation

Quote:

> How can these be modified to include continuations?

I won't answer your question directly, but I suggest you look for
books on denotational semantics.  Continuations were originally
invented as a tool for giving the semantics of languages that don't
provide first class continuations.

--
         Mark Seaborn

          ``If it stays as it is I can't see it altering''
                  -- Graham Taylor



Mon, 21 Apr 2003 21:40:38 GMT  
 call/cc evaluation

Quote:


> > How can these be modified to include continuations?

> I won't answer your question directly, but I suggest you look for
> books on denotational semantics.  Continuations were originally
> invented as a tool for giving the semantics of languages that don't
> provide first class continuations.

Bzzt.... continuations were invented for lots of reasons... if I remember
correctly the main motivation was to provided a semantics for "goto" as well
as for other purely implementation related details of compiling non-stack
based langauges to something like Algol...


Tue, 22 Apr 2003 00:12:50 GMT  
 call/cc evaluation

+---------------
| I'm trying to get a handle on call/cc...
+---------------

I strongly suggest you buy & read this book (which, despite the title,
is really about Scheme [mostly]):

        "Lisp in Small Pieces", by Christian Queinnec
        [Originally in French as "Les Langages Lisp".]
        <URL:http://youpou.lip6.fr/queinnec/WWW/LiSP.html>
        <URL:http://shop.barnesandnoble.com/booksearch/
             isbnInquiry.asp?isbn=0521562473>

The book presents a series of interpreters and compilers for Scheme,
each one handling additional details and/or refinements of the previous.
Issues of how full continuations interact with various parts of the
implementations are visited several times.

He also goes into extensive detail in presenting various options
for representing environments & lexical variables, code (at various
levels of interpretation and compilation), closures, stacks, etc.

Absolutely essential reading IMHO for anyone who wants to get
"under the covers" of the semantics & implementation of Scheme.

-Rob

p.s. The chapter on denotational semantics may seem daunting at first.
Fortunately, you can skim it or even skip it on first reading without
losing all that much. (Though if you do, it *is* well worth going back
and reading it more closely later.)

-----

Network Engineering             http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.          Phone: 650-933-1673
1600 Amphitheatre Pkwy.         PP-ASEL-IA
Mountain View, CA  94043



Wed, 23 Apr 2003 12:26:00 GMT  
 call/cc evaluation

Quote:

>p.s. The chapter on denotational semantics may seem daunting at first.
>Fortunately, you can skim it or even skip it on first reading without
>losing all that much. (Though if you do, it *is* well worth going back
>and reading it more closely later.)

I found it very accessible. It's the first introduction into that
matter that I could read from the beginning to the end without
totally losing my way! ;-)

felix



Wed, 23 Apr 2003 03:00:00 GMT  
 call/cc evaluation

Quote:

> I'm trying to get a handle on call/cc, and I was wondering how you can
> trace out by hand what a program using call/cc does. For example,
> without set!, the "substitution model" can be applied to evaluate
> expressions, but after that you need to add in the "environment model,"
> with rules like these:

> 1. To create a fuction, create a pair with one element set to the list
> of arguments and the body of the function, and the other the environment
> in which it was defined.

> 2. To apply a function to arguments, create a new frame, with a parent
> the environment from the function, and the arguments bound to their
> values. Evaluate the body of the function in this new environment.

> 3. To evaluate an expression which is a list, evaluate all of it's
> elements and apply the first item to the rest.

> 4 to n. Lots of special cases for special forms like set!, define,
> lambda, let, etc.

> How can these be modified to include continuations?

The `environment model' doesn't include any model of the control flow,
so it would be hard to modify it to include continuations.

The easiest way (at least it was easiest for me) to understand
continuations is to use the `machine' model.  This model is developed
in Chapter 5 of S&ICP, and it uses a `machine' with `registers' and a
`stack' to evaluate Scheme expressions.

In this model, the `continuation' is the *entire* state of the machine
(registers and stack) that is available at the point where the machine
is about to do a return.

The primitive function CALL-WITH-CURRENT-CONTINUATION will be taking a
function as an argument.  What it needs to do is `reify' its
continuation (make a copy of the entire state of the machine and wrap
it up in an object), and then apply the receiver to that reified
continuation by putting the receiver in the function register, the
reified continuation into the argument list, and jumping to apply.

When you invoke (apply) one of these reified continuations, you simply
unwrap the whole thing and replace the current machine state with the
old copy, put the argument you are invoking it on wherever return
values go, and jump to return.

-----= 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! =-----



Fri, 25 Apr 2003 03:00:00 GMT  
 call/cc evaluation

Quote:

> I won't answer your question directly, but I suggest you look for
> books on denotational semantics.  Continuations were originally
> invented as a tool for giving the semantics of languages that don't
> provide first class continuations.

True.  For a more complete discussion see the proceedings of the 2nd
ACM SIGPLAN Workshop on Continuations, especially the invited talk
by John Reynolds, "The Discoveries of Continuations", which is online
at

    http://www.brics.dk/~cw97/

Will



Fri, 25 Apr 2003 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. call-with-values & call/cc

2. The expense of call/cc (was R4RS)

3. references on call/cc

4. call/cc in Forth?

5. call for papers: ESOP, CC, CAAP

6. call/cc possible in Dylan?

7. Trouble with CALL/CC

8. call/cc

9. catch/throw implemented with call/cc

10. desperate call/cc question

11. Help requested for call/cc

12. R4RS interpretation of interaction of MAP and CALL/CC

 

 
Powered by phpBB® Forum Software