[Prev][Next][Index][Thread]

Re: Dylan Features

In article <c1Wi5.106299$1h3.1647179@news20.bellglobal.com>, "Maury 
Markowitz" <maury_markowitz@hotmail.com> wrote:

> > something like Scheme's call-with-current-continuation? Thanks!
> 
>   Newbie Q, what is this?

Do you know "continuation-passing style"?  It's a way of thinking about 
programs (and implementing them) that does not use the normal CPU return 
address stack to implement function return -- or put alternatiely, that 
makes function return explicit instead of implicit.

Take the standard factorial function:

  define method fact(n)
     if (n = 0)
        1
     else
        n * fact(n - 1)
     end
  end;

You can convert this (manally or automatically) into 
"continuation-passing style":

  define method fact(n, return)
     if (n = 0)
       return(1)
     else
        fact(n - 1, method (val) return(n * val) end)
     end
  end;

Now, instead of calling this as...

  format-out("factorial 5 is %=\n", fact(5));

 ... you'd call it as ...

  fact(5, method (val) format-out("factorial 5 is %=\n", val) end);


In fact, in true CPS, all the built-ins such as =, *, -, and format-out
will expect to be used in CPS as well:

  define method fact(n, return)
     \=(n, 0, method (bool)
       if (bool)
          return(1)
       else
          \-(n, 1, method (subresult)
            fact(subresult, method (factresult)
              \*(n, factresult, method (timesresult)
                return (timesresult)
              end)
            end)
          end)
       end
     end)
  end;

  method testfact(donext)
    fact(5, method (factresult)
      format-out("factorial 5 is %=\n", factresult, donext)
    end)
  end;


There are all sorts of interesting properties of CPS.  It makes certain 
sorts of compiler optomisations easier (and others harder).

The most striking property is that no function *EVER* falls off the end 
and returns.  You *always* end up with a tail-call to a function that 
itself never returns.  This in effect turns function call into a simple 
"goto".  And of course makes tail-call optomization mandatory if you 
want to actually program this way on real hardware.

Another interesting property is that it makes passing arguments and 
passing back function results symmetrical.  Why can you pass multiple 
arguments but not multiple results in most languages?  Because that's 
the way the historical function call ABI is set up.  Well, with CPS you 
never actually return, you just call the guy who is going to use your 
results -- and if there is more than one of them then it's just a normal 
function call with more than one argument.  No problem.

When you look at how CPS programs end up in machine code it's very 
interesting.  What you find is that firstly a whole bunch of different 
functions end up in memory next to each other with good old 
spaghetti-code goto's between them and no use of the hardware function 
call/return instructions.

The second thing you find is that the "branch and link" instructions 
found in such CPUs as the PowerPC (and several other RISCs) and even in 
older designs such as the PDP-11 are actually *ideal* for implementing 
CPS.

To really understand this stuff I suggest that you find the 1977 paper 
by Steele et al "Lambda: The Ultimate Declarative".  It's extremely 
interesting and well-written and is relevant to Dylan in that it 
describes a lot of the thinking that lead to Scheme, and on which Dylan 
in based.


Back to your question: what is call-with-current-continuation?

call-with-current-continuation is something that lets you mix CPS and 
ordinary style in the same program.  It's basically the high-level 
equivalent to "JSR" or "branch-and-link" at the machine level, in that 
those low-level instructions are themethod by which a program can gain 
access to the address o the next instruction to be executed and save it.

If Dylan had call-with-current-continuation then you could write this:

  define method fact(n, return)
     if (n = 0)
       return(1)
     else
       fact(n - 1, method (val) return(n * val) end)
     end
  end;


  format-out(
    "factorial 5 is %=\n",
    call-with-current-continuation( method(continuation)
       fact(n, continuation)
    end)
  )


In fact, you *can* write this in Dylan, and it looks like this:

  format-out(
    "factorial 5 is %=\n",
    block (continuation)
       fact(n, continuation)
    end
  )

Everything I showed above and -- as far as I recall -- nearly everything 
in the Steele paper can actually be done in Dylan using "block".

The diffeence between Scheme and Dylan is that in Dylan the function 
bound to the name "continuation" is valid only until you exit from the 
block() ... end construct.  In Scheme you can take this value and store 
it somewhere and use it later -- maybe even several times.  it's very 
much like the idea of a "closure", but applied to flow-of-control 
instead of to data.

C doesn't have closures.  The fact that Dylan has closures implies that 
some data that looks as if it could be stored on the stack (and could be 
in C) in fact has to be stored on the heap.  Closures in effect create 
"objects".

Continuations do the same thing for flow-of-control.  The fact that 
Dylan doesn't have full call-with-current-continuation means that 
function call/return can happen on a stack.  In Scheme there are some 
function invocations that actually need to be stored on the heap.  
call-with-current-continuation with unlimited extent in effect creates 
"threads".


A good example of a program written in CPS is the old "Thomas" compiler, 
which implements prefix-syntax Dylan on top of Scheme.  You can still 
find it on the net and reading the code is very interesting.

-- Bruce
Follow-Ups: References: