From: zuzu <sean.zuzu@...>
Date: 2004-08-21T11:30:50+09:00
Subject: Re: ruby, actors, continuations, Kernel#callcc

On Sat, 21 Aug 2004 10:26:08 +0900, Kristof Bastiaensen
<kristof@vleeuwen.org> wrote:
> 
> 
> On Sat, 21 Aug 2004 07:24:31 +0900, zuzu wrote:
> 
> > reading carl hewitt's seminal paper on the actor model:
> > http://www.lcs.mit.edu/publications/specpub.php?id=762 my current
> > impression is that actors are basically pure-OO objects using
> > continuations (coroutines?) instead of stack-frame methods/subroutines.
> > this way objects only require "promises" (in the form of the passing of
> > context) rather than the final value (as with method stack-frames).  (i
> > think this important towards breaking free from von neumann
> > architecture, ala bachus:
> > http://delivery.acm.org/10.1145/360000/359579/p613-backus.pdf?key1=359579&key2=7975779801&coll=portal&dl=ACM&CFID=11111111&CFTOKEN=2222222
> >
> > but i still can't quite seem to grok continuations, at least in terms of
> > interpreting it for ruby, w/r/t closures and Kernel#callcc.  this after
> > reading dan "parrot" sugalski's weblog
> > [http://www.sidhe.org/~dan/blog/], jim weirich's email
> > [http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/78288 ],
> > and rubygarden/c2.com/wikipedia articles on the subject:
> > http://www.rubygarden.org/ruby?action=history&id=Continuations
> > http://rubygarden.org/ruby?ContinuationExplanation
> > http://www.ruby-doc.org/docs/ProgrammingRuby/html/ref_c_continuation.html
> > http://c2.com/cgi/wiki?ContinuationExplanation
> > http://en.wikipedia.org/wiki/Subroutine
> > http://en.wikipedia.org/wiki/Coroutine
> >
> >
> > any futher help is much appreciated.
> >
> > thanks!
> >
> > -z
> 
> Hi,

hey.  let me see how well i follow what say here...

> Here is how I think continuations and actor theory work together. This is
> my interpretation, and it is possible I didn't get everything right, but I
> hope it may help you.
> 
> I think the main problem in understanding continuations is that normally a
> continuation is regarded as a function. However I think it is more the
> other way around.  A function is more a special form of a continuation.

yes, i've heard it described this way before; seems accurate.

> Let me try to explain a little.
> Instead of looking at a program as a sequens of statements,

aka "procedural programming"...

> you could
> consider a program as many independend points (or actors), each which
> takes a value, does something with it, and passes it to another point. You
> could then call each such point a contination-point. (That is how I call
> it, I don't really know if there is an official name). In the
> actor-theory, this point would be an actor.

or i believe one could say "object".  as described both by carl hewitt
[Carl Hewitt, Peter Bishop, Richard Stieger, "A Universal Modular 
Actor Formalism for Artificial Intelligence", Proceedings of the 1973
International Joint Conference on Artificial Intelligence, pp.
235-246.] and mark miller
[http://www.erights.org/elib/capability/ode/ode-submission.html] (and
in a previous thread here; Re: Functional Ruby):

Objects == Lambda Abstraction + Message Dispatch + Local Side Effects

however, objects define their inputs and outputs with _methods_
(functions/subroutines/whatever you wish to call them).  so from this
perspective the "continuation points" seem more concerned with lexical
scope, yes?  or "associates" as carl hewitt seemingly describes this
phenomenon.


> To be useful, the
> continuation-point must also be aware of the current environment, 

(context / scope)

> and the
> easiest way is to pass the environment from each point to another.  In the
> actor-theory this environment could be just another actor, which could
> respond to queries, for example to get a value.
> 
> A function would be a special kind of continuation-point, one that takes
> in addition to the other values a continuation. This continuation will be
> saved in the environment, and when the function has finished to do what it
> has to do, it will send it's return value to the saved continuation.

after re-reading that paragraph twice, ok, i think...  how is this not
a COroutine rather than a SUBroutine?  that it returns a _value_
rather than simply another context/environment?

> How do closures and call/cc fit in this model?  You could say a closure is
> a function and a saved environment.

ok, so how is this not just aka a continuation?
closures retain their lexical scope, and otherwise an anonymous/lambda
function/subroutine, no?


> To call a closure, you get the saved
> environment, and call the function with this environment, and any
> parameters.  As described above, the function is a continuation-point that
> accepts continuation, and calls this continuation will the final result.

so, this is to say, subroutines/functions/methods and coroutines are
_composed_ of continuations?  and a closure is composed of a function?
 again, when the topic returns to a matter of "saved
environment/context/scope" i am confused by a perceived redundancy.
 
> However you could also save the environment for a continuation-point,
> basicly creating a closure over the continuation-point.  This closure is
> what is normally called a continuation.

uh, right.  a closure is a continuation; but by saying this i seem to
be muddling this "continuation-point" concept i think.

> call/cc just captures the next continuation (with the environment, which
> includes any functions to return to), wraps it in an object, and calls the
> given block with that object.

for now i am thinking of this as not unlike the Proc object, as how
functions/blocks are defined, particularly without an object to "own"
them.

>The continuation is actually that part of
> the program that will receive the result from call/cc.  That result can be
> either the value of the block, or the value passed to the
> continuation-object (using "cont.call(value)").

i'm still not so swift on understanding this either...  for now it
feels like block/proc object design burp syntax.  maybe that's totally
wrong.

> I think the nice thing about actor theory is that it allows lambda
> calculus to be implemented using parallel objects. You could build a chip,
> where each continuation-point can be programmed in the chip, and would act
> on its own.  This chip could the perform all the computations in parallel,
> since each continuation point can act on it's own.  This would be
> radically different from the current cpu-design, where there is only a
> single point of controlflow.  A special sort of FPGA could be used for
> this kind a chip, since they allow reprogramming on the fly.

yes!  think of http://www.starbridgesystems.com/
though in the short to mid-term i am thinking more about the PPC970
architecture.
but an FPGA solution would certainly reach much closer to escaping von
neumann architecture.

> Because lambda calculus is very basic to programming, it could be possible
> to transform a traditional program into a form that makes maximum use of
> parallelism in such a chip, and therefor be very fast.  Also all processes
> that would fit into memory would run effectively parallel (not simulated
> using task-switching), and wouldn't slow down any other process. It would
> also support dynamic languages better, so that a ruby program wouldn't be
> any slower that a C/C++ program.

precisely!  this has very important ramifications for my mid to
long-term interests in cybernetics (norbert wiener) and systems theory
(which seems to now popularly referred to as "complexity").  frankly,
much like stephen wolfram and mathematica, my current research on
bringing actor model / flow-based programming to ruby is simply a tool
to do what i really want to do.  like graffiti at mit, "i would rather
write programs to help me write programs, then write programs".

> I don't know if the design of such a chip would be possible, but it would
> be a radically different aproach to computing.

i believe some work in this has already been done.  some old, such as
"real-time actor systems" by henry baker, and some new such as the
aforementioned starbridgesystems.  perhaps the hardware will seem more
relevant once the software for it actually exists.

> Regards,
> KB

peace,
-z