Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

CPS transformations on func tion! values

 [1/9] from: maarten:koopmans:surfnet:nl at: 25-Feb-2003 21:49


Hi, Now here is a puzzle.... Has anybody given any thought to CPS transformation on function! values ( a function! translator)? I did, but I can't figure out how to get all that dynamic code in tail-form :( Why? I'd like to be able to suspend my REBOL at any time, serialize it and the resume at some other time. Perhaps on another REBOL somewhere in the wild wild REB. Why? Think parallelized computations. Think GRID computing. Think Information World (yes Gabriele, I haven't forgotten). Storing the state of a REBOL is easy if you mark some types (port! native! as volatile) and do dome tricks on others (most notably those use values). Storing bindings is harder, but you can get pretty far. Storing control flow is a challenge. --Maarteb

 [2/9] from: greggirwin:mindspring at: 25-Feb-2003 15:24


Hi Maarten, MK> I'd like to be able to suspend my REBOL at any time, serialize it and MK> the resume at some other time. Perhaps on another REBOL somewhere in the MK> wild wild REB. I remember thinking about this when you brought it up before. If I were to tackle it, I'd start by defining some constraints on exactly what is supported and when it can be halted/resumed. That should make it doable as a starting point. I might even devise a specific architecture for apps that need to do this - perhaps even a dialect to define them. Being able to halt and resume any arbitrary REBOL at any time will be quite a challenge. The question, for me, is whether you need that amount of flexibility. -- Gregg

 [3/9] from: maarten:koopmans:surfnet:nl at: 26-Feb-2003 10:29


Hi Gregg, When I did Rugby I tried to support REBOL as is, which gives great benefits. So the challenge will be to have as little constraints as possible, as my experience is that any implementation adds some constraints on the fly (even if you're not aware). Still waiting for any suggestions... --Maarten

 [4/9] from: joel:neely:fedex at: 27-Feb-2003 14:07


Hi, Maarten, I had thought about this, but hit the wall except for thoughts to would be the subject of further articles in the series of articles on REBOLforces (Recursion->Iteration->Objects->Tasks). Maarten Koopmans wrote:
> I'd like to be able to suspend my REBOL at any time, serialize it > and the resume at some other time. Perhaps on another REBOL > somewhere in the wild wild REB. >... > Storing the state of a REBOL is easy ... > > Storing control flow is a challenge. >
But to me, storing control flow is part of the state. For some simple cases, such as the example below (forgive me for the definition of VOWELS, speakers of something other than English, I'm just trying to make a small example ;-) vowels: charset "AEIOUaeiou" count-vowels: func [s [string!] /local count] [ count: 0 parse s [ any [ vowels (count: count + 1) | skip ] ] count ] foreach message [ "Eat at Joe's!" "Hello, world!" "My dog has fleas." ][ yield reduce [count-vowels message tab message] ] Let's imagine that the word YIELD somehow saves state in a place/way that it can be RESUMEd later, and returns the value of the following expression. I can understand how to transform all of this into an object with a STEP method, which returns for each call a single YIELDed result: my-obj: make object! [ vowels: charset "AEIOUaeiou" count-vowels: func [s [string!] /local count] [ count: 0 parse s [ any [ vowels (count: count + 1) | skip ] ] count ] messages: [] start: func [b [block!]] [messages: copy/deep b] step: func [/local message] [ if not tail? messages [ message: first messages messages: next messages return reduce [ count-vowels message tab message ] ] ] ] my-obj/start [ "Eat at Joe's!" "Hello, world!" "My dog has fleas." ] print my-obj/step ; ... arbitrary other unrelated stuff occurs print my-obj/step ; ... more unrelated stuff while [found? answer: my-obj/step] [print answer] but if the YIELD had been placed inside the PARSE, as in vowels: charset "AEIOUaeiou" yield-vowels: func [s [string!] /local vowel] [ parse s [ any [ vowel: vowels (yield first vowel) | skip ] ] none ] foreach message [ "Eat at Joe's!" "Hello, world!" "My dog has fleas." ][ yield reduce [count-vowels message tab message] ] then implementing this would require substantial rewriting of the use of PARSE (assuming that we don't have a way to get/set the state of an in-process PARSE evaluation). My conclusion was that if I were going to be able to model a yield/resume scenario (within my lifetime, at least ;-), I'd be better off writing each one individually rather than trying to come up with an automatic rewriting mechanism. Of course, there are folks who can probably do more with this idea than I... -jn- -- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446 Counting lines of code is to software development as counting bricks is to urban development.

 [5/9] from: brian::hawley::net at: 28-Feb-2003 13:52


At 09:49 PM 2/25/03 +0100, Maarten wrote:
>Now here is a puzzle.... >Has anybody given any thought to CPS transformation on function! values (
<<quoted lines omitted: 4>>
>resume at some other time. Perhaps on another REBOL somewhere in the wild >wild REB.
Sounds great, but you can't do this to a regular REBOL process. REBOL is stack-based rather than continuation- based since 1.9, so saving a continuation would require reading the stack (how do you do this?) and resuming one would require writing to the stack directly, with an as- yet nonexistent native. Basically it would be easier to write your own continuation-based interpreter. On the other hand, I have written continuation-passing code in REBOL in a previous project, in a section that provided facilities similar to Rugby. This was before Rugby came out, not nearly as good and not published, but it worked well enough. The relevant function consumed a list of blocks, each block a statement of REBOL code that I referred to as an event, usually a function call. Each event function did a part of a task then returned the next event to be done in the task, which the event handler appended on to the event list. When an event completed a task it returned none. The point of this was to implement cooperative multitasking, but I could have easily saved the event list and loaded it later if I needed to (I didn't). Because the current state of a task needed to be stored in a single event block (no stack, no history), events were written in a continuation-passing style. What I didn't do is write code that CPS-transformed the REBOL code for me. That would have required a semantic model for REBOL in continuation form, and I didn't have time to make one. It was quicker to break up the code by hand. YMMV.
>Why? > >Think parallelized computations. Think GRID computing. Think Information >World (yes Gabriele, I haven't forgotten).
If you use your existing Rugby facilities you should be able to rig up a Linda-style event server. Clients would then post events to the server, nodes would then grab and handle events, posting subsequent events if necessary. Kinda old-school compared to the grid model but it could still work.
>Storing the state of a REBOL is easy if you mark some types (port! native! >as volatile) and do dome tricks on others (most notably those use values).
Aaack. Most of the work I do with REBOL is on those volatile types, making it quite unsuitable for this kind of distributed computing. The closest I come is with applications similar to BitTorrent. - Brian

 [6/9] from: maarten:koopmans:surfnet:nl at: 1-Mar-2003 13:10


> Sounds great, but you can't do this to a regular REBOL > process. REBOL is stack-based rather than continuation-
<<quoted lines omitted: 3>>
> yet nonexistent native. Basically it would be easier to > write your own continuation-based interpreter.
You can to a certain degree if you intercept the evaluation within a function call (a stack frame) and create functions in tail-form. The problem is all the dynamic code like reduce [ .. ] and do [ .. ] How do you transform that?
> On the other hand, I have written continuation-passing > code in REBOL in a previous project, in a section that
<<quoted lines omitted: 13>>
> in a single event block (no stack, no history), events > were written in a continuation-passing style.
This sounds a bit like the Rugby task engine. But I'd like to move beyond that.
> What I didn't do is write code that CPS-transformed the > REBOL code for me. That would have required a semantic > model for REBOL in continuation form, and I didn't have > time to make one. It was quicker to break up the code > by hand. YMMV. >
I have difficulty creating that model (hence my post).
>> Why? >>
<<quoted lines omitted: 6>>
> necessary. Kinda old-school compared to the grid model > but it could still work.
You can even do better than that, but it requires significant work from the programmer. With a fully reflexive language we should be able to do better. Rugby has features like "chaining" where a call on a server is redirected to another node (the idea was to easily allow P2P searches and stuff), but, but....
>> Storing the state of a REBOL is easy if you mark some types (port! >> native! as volatile) and do dome tricks on others (most notably those
<<quoted lines omitted: 3>>
> kind of distributed computing. The closest I come is > with applications similar to BitTorrent.
But you can override all the I/O functions and add you own IO virtualization layer then. Sigh. Lots of thinking to do. Thanks anyway.... --Maarten

 [7/9] from: maarten:koopmans:surfnet:nl at: 1-Mar-2003 13:14


Hey Joel,
> I had thought about this, but hit the wall except for thoughts to > would be the subject of further articles in the series of articles > on REBOLforces (Recursion->Iteration->Objects->Tasks). >
I don't want to limit myself to tasks only. Migratable processes! I know stackless python was there and will be there soon (again).
> But to me, storing control flow is part of the state. > For some simple cases, such as the example below (forgive me for the
<<quoted lines omitted: 86>>
> come up with an automatic rewriting mechanism. Of course, there > are folks who can probably do more with this idea than I...
Yes, but your mindset is yield/resume. In a CPS transformation you pass in a continuation and never return (as a function). You simply call the continuation (which basically is what-to-do-next). To do that you'll need to transform a function body to tail-form, and there lies my problem. How do you deal with do/reduce/compose and the likes? Where is that Guru (Carl) when you need him ;-) --Maarten

 [8/9] from: joel:neely:fedex at: 1-Mar-2003 9:29


Hi, Maarten, I think we're talking about the same thing (and we are saying that we don't have an automated way to get there yet! ;-) What follows is my (unfortunately lengthy) explanation of why I think so. -jn- Maarten Koopmans wrote:
> I don't want to limit myself to tasks only. Migratable > processes! I know stackless python was there and will be > there soon (again). >
Perhaps I was using too much mental shorthand. Let me use the word "agenda" (in the sense of "to-do list", including both the specification of the action(s) to take and the context in which the action(s) will be taken). To my mind, an "agenda" represents a possible future sequence of evaluations that: - can exist simultaneously with other agendas, - whose progress can be incrementally realized, and - whose progress can occur independently of other agendas. All of that is independent of "where" the agenda is located (or may be performed). As far as I care, the "next" event/action of an agenda could occur: - on the same box at the next moment, - on the same box some arbitrary point in the future, - on some other box, etc...
> Yes, but your mindset is yield/resume. ...the continuation > (which basically is what-to-do-next)... >
I see no difference between calling a continuation and continuing/resuming an agenda. Both are just realizing a bit more of the future.
> In a CPS transformation you pass in a continuation and never > return (as a function). You simply call the continuation... > To do that you'll need to transform a function body to > tail-form, and there lies my problem. > >From my perspective that is one way to create an agenda, but
not the only way. See below for examples...
> How do you deal with do/reduce/compose and the likes? >
Short answer: I don't. Longer/better answer: This all reminds me of proving programs; I don't know, in general, how to take an arbitrary, already-written piece of code and prove that it possesses some arbitrary property (such as termination! ;-). But what I *can* do is start with a specification for the property I want to obtain (at least for some properties) and design a piece of code so that I can prove it possesses those properties. I don't know how to take an arbitrary piece of REBOL and use a fixed set of rules or procedures to transform it into one of the representations we're talking about (e.g. one or more tail- recursive functions, one or more objects with STEP methods, etc.) But what I *can* do (have done) is take specifications for future behaviors I want to enable and create objects that can be incrementally stimulated to realize that future. Below are a bunch of different "recipes" for computing the product of a block of numbers: a recursive function, a tail- recursive function, two iterative functions, and an object representing an agenda. The functions are "atomic" in the sense that once I ask REBOL to evaluate one of them, nothing else happens until that evaluation has finished. But with the object, we have the properties I described at the top of this note. 8<---------------------------------------------------------- recprod: func [b [block!]] [ either empty? b [ 1 ][ (first b) * recprod next b ] ] trecprod: func [b [block!] /local .trecprod] [ do .trecprod: func [.p [number!] .b [block!]] [ either empty? .b [ .p ][ .trecprod .p * first .b next .b ] ] 1 b ] iterprod: func [b [block!] /local p] [ p: 1 while [not empty? b] [ p: p * first b b: next b ] p ] foreachprod: func [b [block!] /local p] [ p: 1 foreach n b [p: p * n] p ] agendaprod: make object! [ b: [] p: 1 nextaction: none taction: [if not empty? b [paction]] paction: [p: p * first b baction ] baction: [b: next b taction ] init: func [bb [block!]] [ b: bb p: 1 nextaction: taction self ] new: func [bb [block!]] [ do in make self [] 'init bb ] step: func [] [ either none? nextaction [ p ][ nextaction: do nextaction none ] ] ] 8<---------------------------------------------------------- Here's a transcript exercising them:
>> nums: [2 5 3 6 11] ;; == [2 5 3 6 11] >> recprod nums ;; == 1980 >> trecprod nums ;; == 1980 >> iterprod nums ;; == 1980 >> foreachprod nums ;; == 1980
(big fat yawn thusfar... ;-)
>> agenda: agendaprod/new nums >> until [found? foo: agenda/step] foo ;; == 1980
or, for more visual impact,
>> agenda: agendaprod/new nums >> while [none? foo: agenda/step] [prin "."] print foo
................1980 Instead of evaluating STEP repeatedly for one agenda object until it completed its work, we could have made several of them and let them take turns, or (with a suitable form of representation) could have sent them to various other boxen for evaluation, etc... If you still think I'm missing the point, I'll be happy to hear about it, of course!

 [9/9] from: maarten:koopmans:surfnet:nl at: 1-Mar-2003 18:56


Hey Joel, You're not missing the point, but this I did a year ago in Rugby already and am not satisfied with it. I'd like to make this easier to do, hence my question. In a task/object framework you'd translate that to pre-emptive scheduling. Or do it continuation-based, which I was thinking about. The challenge IMHO is to do it automated, which means re-implementing a part of REBOL (slightly changed) in REBOL, which should be possible. All those Scheme guys are also doing the same thing with their favourite language ;-) softREBOl, there it is again. Oh well, while I hit my head some more against the wall I'll just do something easy like implementing a P2P network or so ;-) --Maarten

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted