From: carroll@ori.cis.udel.edu (Mark C. Carroll)
Subject: Re: A challenge to the anti-goto
Organization: University of Delaware, Newark
Date: Thu, 5 Nov 1992 16:57:16 GMT

In article <Bx6z1J.57r@mentor.cc.purdue.edu> hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
>In article <BEVAN.92Nov3211454@hippo.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
>>In article <1992Nov3.165005.18037@midway.uchicago.edu> dave@alex.uchicago.edu (Dave Griffith) writes:
>>   >   If we've known about this problem for twenty years, why don't we
>>   >   have more powerful `break' instructions in our existing languages??
>
>>   >Code the inner loops as a function, and use 'return' as your
>>   >powerful 'break'. 
>
>>   Well, no.  The idea is to be able to break out of multiple loops.  Making
>>   functions out of your inner loops does nothing to help this.  You would have
>>   to use setjmp/longjmp, with all the hideousness that entails.  
>
>>   It should be noted that Ada and CLU have named loops and named breaks.  They
>>   are indeed quite nice for many control flow problems.
>
>>You could always use a variant of the function approach and have
>>explicit continuations i.e. don't "return" from functions, just call
>>the next function with the "result" of the current one.  I don't know
>>what a C compiler would make of this, but a number of Scheme (and at
>>least one Prolog) compiler transforms everything into this sort of
>>code and consequently deals efficiently with it.  Of course, whether
>>a continuation based program is easier to understand than one which
>>uses explicit gotos is something I'll leave others to decide.
>
>There are two major problems with this.  For one, the stack grows with
>the non-returns, and taking care of this would be at least as bad as
>garbage collection, if not worse, as stack locations are, for extremely
>good reasons, not globally known.  For another, this does not handle
>procedures which continue the resource use of the current procedure.
>

Wrong... (You know, I _really_ hate it when people criticize something
out of ignorance. Why must you post a criticism of something that you
know nothing about?)

First, compilation by continuations does _not_ necessarily incur stack
growth. Calling a continuation is not quite a traditional function call -
continuations NEVER RETURN. 

The idea of continuations is that at any point, the rest of the computation
being conducted can be thought of as a function which takes as arguments
the value computed by the current statement.

So, consider the following:

   A := B + C
   D := A * B
   E := D + 2

This can be rewritten as follows:

function step1() {
   return step2(B+C)
}

function step2(A:integer) {
   return step3(A*B)
}

function step3(D : integer) {
   return D+2;
}
   
These are all tail calls, so no stack growth is necessary. 

Compilation by using continuation passing does _not_ have any problem
with procedures which continue the resource use of the current
procedure.  The continuation function is the _entire_ rest of the
computation, so it includes all resources that are needed by the rest
of the computation.

There's a lot more to it than this; if you're really interested in it,
try getting a copy of Appel's book.

	<MC>
-- 
|| Mark Craig Carroll: <MC>     ||"I prize the cloudy, tearing sky,
|| Univ of Delaware, Dept of CIS|| for the thoughts that flap and fly.
|| Grad Student/Labstaff Hacker || For staying in and reading by.
|| carroll@udel.edu             || For sitting under" -Karen Peris
Newsgroups: comp.lang.misc