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