NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/lang/misc/2771

Internet Message Format | 1992-08-23 | 6.1 KB

Path: sparky!uunet!mcsun!uknet!gdt!aber!aberfa!pcg
From: [e-mail] (Piercarlo Grandi)
Newsgroups: comp.lang.misc
Subject: Re: Call/CC (Was Re: PL/1 non-local goto versus setjmp/longjmp)
Message-ID: <[e-mail]>
Date: 23 Aug 92 17:43:19 GMT
References: <[e-mail]> <[e-mail]>
    <[e-mail]> <[e-mail]
    <[e-mail]>
    <[e-mail].>
Sender: [e-mail] (USENET news service)
Reply-To: [e-mail] (Piercarlo Grandi)
Followup-To: comp.lang.misc
Organization: Prifysgol Cymru, Aberystwyth
Lines: 113
In-Reply-To: [e-mail]'s message of 20 Aug 92 23: 27:27 GMT
Nntp-Posting-Host: aberdb

On 20 Aug 92 23:27:27 GMT, [e-mail] (Mel Walker) said:

mwalker> I'm reading the r4rs report on Scheme, and this "Call with
mwalker> current continuation" confuses the heck out of me. I can't
mwalker> figure out what it's good for. Is it just kind of a
mwalker> setjmp/longjmp? I guess I don't see the similarity people have
mwalker> been posting about. Can anybody straighten me out on this?

Here I have rack and hot irons, ready for use. :-)

First, two references: John Allen, "Anatomy of Lisp"; Abelrson &
Sussman, "Program structures".

Second, a small explanation:

All languages have implicit an environment graph and a control graph.
Nodes in the environment graph are token-value associations, and nodes
in the control graph are cpu-state frames.

  Low-level explanation:
    Given a procedure, it is instantiated by creating a new environment
    node, filling it out with the arguments, creating a new control node,
    setting the PC in itr to the beginning of the procedure, and then
    making it active instead of the one describing the currently running
    procedure instance.

A given procedure may have many instances, e.g.  for recursion, and
correspondingly many environment and control nodes may refer to it.

Procedure instances may be values that are passed around, or may not be.

Now, most languages have restrictions to ensure that the control and
environment graphs are really trees, and that such trees can only be
walked depth first. In other words that the control and environment
trees can be implemented as a stack, as no procedure instance outlives
the procedure instance that created it.

While the control and environment graphs are normally treated as
linearized trees, in a FIFO fashion, there are at least two cases where,
even in traditional languages, strict nesting must be violated. The two
cases are procedure parameters (downward furnargs) and non local gotos
(catch/throw or longjmp).

With procedure parameters, depending on the language, an environment
frame is passed downwards, skipping several intermediate levels of the
stack. With non local gotos, control is transferred upwards, skipping
several levels of the stack.

Both facilities however are restricted to stack operation; procedure
parameters cannot be passed upwards (except for particular cases) and
control cannot be transferred downwards. The reasons are that,  in stack
based implementations, if a reference to an environment node is passed
upwards, the environment node will have been deallocated, and if a
control transfer is done downwards, the control node will also have been
deallocated.

However if environment and control nodes are made to exist in a non
stack like fashion then environment nodes can be passed 'upwards' and
control transfers can happen 'downwards'. An environment node that
persists upwards is called a closure, and a control node that that
persists downwards is called a continuation point.

Once these two entities can be manipulated, an entity called a
continuation (or generator or coroutine, at times) can be assembled out
of a continuation point and a closure. A continuation is just a
procedure instance made persistent and resumable.

call/cc 'just' gives you a handle on the currently executing procedure
instance. Or rather a copy of that, usually -- most scheme systems
create procedure instances on the stack by default, and only in the
relatively rare case where one uses call/cc the procedure instance gets
copied to the heap; this is safe because procedure instance handles can
only be gotten via call/cc. In older, dynamically scoped lisps, the
function primitive could be used to obtain a closure, but that was all
(in scheme, which is lexically scoped, it's define that is mostly used
to create closures, statically that is).

Note that in scheme there is no direct way to get separate access to the
environment and control node components of a procedure instance.

Now, what is the similarity between setjmp and call/cc?

  That setjmp creates a continuation point that can be resumed by some other
  arbitrary procedure instance, as long as the resuming procedure instance
  is newer than the resumed one. In other words setjmp/longjmp are an
  escape, just like call/cc, from the strict nesting of procedure
  call/return.

And what is the difference?

  There are two of them: setjmp defines only a continuation point, not a
  closure (it even loses parts of the current closure, if 'volatile' is
  not used!), while call/cc does both, and the continuation point defined by
  setjmp cannot be passed upwards, while the continuation defined by
  call/cc can.


There is also another relationship of sorts between the two:

  In some implementations of call/cc there is some abuse of setjmp, where
  it is used to define the control node of a continuation, even in a
  downward sense, by second guessing setjmp's implementation and changing
  stacks behind its back. This works, but is hardly portable.


Finally, a small idea on what call/cc is good for. Well, to realize in
scheme a lot of nice tricks, or rather fundamental concepts, like
coroutines, streams, generators, classes, actors, exception handling,
... by letting you create arbitrary control and environment graphs.
--
Piercarlo Grandi                   | JNET: [e-mail]
Dept of CS, University of Wales    | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: [e-mail]