From: Kristof Bastiaensen Date: 2004-08-21T21:25:56+09:00 Subject: Re: ruby, actors, continuations, Kernel#callcc On Sat, 21 Aug 2004 11:30:50 +0900, zuzu wrote: > On Sat, 21 Aug 2004 10:26:08 +0900, Kristof Bastiaensen > 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. > > Yes, that's right. A 'continuation point' would be a special kind of object/actor, which receives an environment and a value. It could also take more values, but in the pure lambda-calculus it can take only one. >> 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? > If I understand correctly, a coroutine restores it's environment when it resumes control. A function doesn't do that. It doesn't have an environment. It accepts the environment that the caller gives it. This may be the current environment, or a saved one in the case of a closure. Also note that it doesn't really "return" a value. It passes the value to the given continuation. >> 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? > Exactly! A closure is just a continuation. It's a continuation that takes another continuation (a return adress) that it must pass the end result to. you can express that in Ruby: #return a closure that adds i to its argument def sum(i) params = callcc do |cc| return cc #exit from the method with the current-continuation end #params contains the arguments passed to the continuation ret = params.shift # the first argument is the return continuation retval = i + params.shift # add i to the second argument ret.call(retval) #send the result to the return continuation end a = sum(2) callcc{ |cc| a.call(cc, 3) } => 5 > >> 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. Well, see the continuation-point as an actor which takes a value and an environment. If you pack the environment and the continuation-point together you get a continuation like it is returned by call/cc. > >> 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. Nice! I didn't know this kind of computing already exists. These cpu's from starbridgesystems are chips with a lot of fpga's packed in them. I am a bit worried they say they patented this technology, and have patents pending. They shouldn't patent universal technology! > perhaps the hardware will seem more relevant once the software for it > actually exists. It would be nice to have a Ruby translater for them. You could then take a Ruby-program, and it would be wired into the FPGA, and as a result be very fast. For example each class/object could have it's own method lookup (which is one of the bottlenecks of Ruby). Dynamicly adding or changing methods is no problem. Ruby on speed! > >> Regards, >> KB > > peace, > -z Thanks, KB