[REBOL] Re: CPS transformations on func tion! values
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!