Xref: utzoo comp.object:517 comp.lang.c++:5694
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!brutus.cs.uiuc.edu!apple!oliveb!mipos3!orc!Ozona!chase
From: chase@Ozona.orc.olivetti.com (David Chase)
Newsgroups: comp.object,comp.lang.c++
Subject: Re: Re^2: Continuations
Summary: I think we're having a terminology problem
Message-ID: <48742@ricerca.UUCP>
Date: 28 Nov 89 23:06:52 GMT
References: <2664@bingvaxu.cc.binghamton.edu> <9624@pyr.gatech.EDU> <1623@odin.SGI.COM> <1989Nov28.183816.15252@odi.com> <9964@june.cs.washington.edu> <34657@cornell.UUCP>
Sender: news@orc.Olivetti.Com
Reply-To: chase@Ozona.UUCP (David Chase)
Followup-To: comp.object
Organization: Olivetti Research California, Menlo Park, CA
Lines: 91

In article <34657@cornell.UUCP> Chet Murthy writes:
>peterd@cs.washington.edu (Peter C. Damron) writes:

>>I just had to reply when I saw this.  C and C++ are definitely "lexically
>>scoped" (I would prefer to call it statically scoped).

>Yes, they are, but they don't provide support for closures as
>first-class objects (the funarg problem).  So they don't provide
>"full" support for lexical scoping.  Scheme/ML do.

Try "lexical scope with nested procedures" for "lexical scope", and I
think you'll fix your misunderstanding.  (I got this from the Dragon
Book, 2nd ed., and I once abused the terminology in the same way).  C,
Pascal, Modula-3, and Scheme all have lexical scope -- the bindings
can be determined by examining the program text.  In addition, all
four use the "most-closely-nested rule" for resolving bindings.

However, the languages listed differ in their treatment of nested
procedures:

C         forbids them  (no closures).

Pascal    allows them, but (in Pascal Classic, at least) forbids
          their assignment to variables, use as parameters to
	  procedures, or use in a RETURN.  (no closures, because it
	  turns out that a display can be used).

Modula-3  allows them, but forbids their assignment to variables or
          their use in a RETURN.  (closures needed, but must obey
	  stack lifetime rules).  (I hope this example isn't too
	  obscure -- I'm rather familiar with it at the moment).

Scheme    allows them (garbage-collected closures, except where
          optimized away).

Now (returning to continuations [pun unintended]), it happens that
many many things can be defined in terms of continuations, including
exception handling.  With closures, it is possible to implement some
really interesting exception handlers, but liberal use of closures and
continuations can (read will, with current technology) interfere with
optimization (in particular, it interferes with register allocation --
if you don't map the same variables to the same registers at the
appropriate program points, it gets very very messy, much like setjmp
and longjmp).

One limited use of continuations is actually very much like
setjmp/longjmp (though the syntax is different).  In C, it might go
something like (ignore the type-checking, and pretend we have nested
procedures):

typedef any_type (*continuation)();

f(...)
  {
  int key, x;
  tree t;

  int search(t,K) tree t; continuation K;
  {
  /* RETURN immediately via K if found */

    if (match(key, t)) K(t);
    search(left(t),K);
    search(right(t),K);

  /* Normal return for failure */
  }

  tree g(K) continuation K;
     {
       /* Find key in tree t, returning quickly if found. */
       search(t,K);

       /* If search returns at all, then it failed to find anything,
          so we return NULL */
       return NULL;
     }
  ...
  x = call_with_curr_continuation(g);
  ...
  }

This should illustrate the (ab)use of continuations in a simple,
quick-return fashion.  More sophisticated use of continuations will
store them in global variables and/or return them.  This allows the
program to "return to" (a second time) an "inactive" call frame.  The
implementation of these is a little more heavyweight, but it does
allow easy descriptions of backtracking algorithms and iterators.
Note the usefulness of lexical scope in this example.

David


Brought to you by Super Global Mega Corp .com