Continuation Passing Style
(http://en.wikipedia.org/wiki/Continuation-passing_style) is a topic
relevant to web programming and compiler implementation.
Superficially, we might think that this style of programming is not a
very good fit for J, because no one has bothered to implement "tail
call optimization" for J.
In the context of web programming, a continuation represents the work
that a server would do when it receives a request from a client.
In the context of compiler design, a continuation represents a "unit
of work" that is being transformed to some other representation.
But, as is typical for constraints on symbolic topics, there's another
way to do it. One such way would be a gerund passing machine - a
machine which combines a gerund with a noun to produce a new gerund.
Once we have a system like this, we can describe an arbitrary sequence
of computations using ^: (probably ^: _).
When working with gerunds, it's useful to be able to see the atomic
representation of a verb, as this has the same structure as a gerund.
But we also should be able to easily distinguish between verbs and
gerunds. So, when working on this kind of code, we might want both
the atomic and linear representations of verbs:
9!:3]1 5
A variation on the above suggestion would be a gerund and an array
with an operation to combine them with a new noun to produce a new
pair paired gerund and array. Of course gerunds can already contain
multiple arrays, but it might be better to have a focus on a
particular array. A further variation, though, would be to use gerund
introspection to extract the array of interest. Here, we become
interested in the structure of the gerund. We also might want to pass
the gerund to the verb represented by the gerund. We would also want
to build up a small toolkit of helper verbs (and other grammatical
forms) to deal with common tasks.
Here's an example of a verb with an embedded array:
,&'abc'
Here's how extracting the array might look:
(0;1;1;1){::,&'abc'`''
abc
$(0;1;1;1){::,&'abc'`''
3
So, let's define:
Y=: (0;1;1;1)&{::
Here, given a gerund of the form u&y (or any similar structure), Y
will extract the original value of y.
If we want the body of the gerund for u, we might use (0;1;0)&{:: but
note that this will need to be boxed before it can be used as a gerund
again, and of course we may want to combine it with other things. If
we had used 'abc'&, we'd want (0;1;0;1)&{:: to extract the value x
value being passed to , but I'm not ready to go there, yet. Instead:
M=: (0;1;0)&{::
This name is in analogy to the 'm' argument for conjunctions. It's
not completely accurate, but it will do until I think of something
better. Here's what happens when we have M inspect the gerund of its
own definition.
M M f.`''
+-+-------+
|0|+-+-+-+|
| ||0|1|0||
| |+-+-+-+|
+-+-------+
This is the body of a gerund of a noun. Because gerunds themselves
are nouns, the ` mechanism is not useful (by itself) for constructing
the gerund of a noun. But we could build ourself something that does
the same thing:
n2bg=: (,'0') ; <
n2bg 0;1;0
+-+-------+
|0|+-+-+-+|
| ||0|1|0||
| |+-+-+-+|
+-+-------+
We can box this and pass the result to `:6 to extract the original noun:
(<n2g 'abc')`:6
abc
We can build up expressions this way and then evaluate them:
(<n2bg 'abc')`,`(<n2bg 'def')`:6
abcdef
In other words, we can use gerunds to represent a part of an
incomplete computation. In other words, a gerund can be thought of as
being analogous to a continuation. (But it's not quite the same. For
one thing, I am not employing "lexical context". But, also, if we
build the Y combinator to represent recursion we'll get a stack
overflow at modest stack depths, and my plan here is to use (^:_)
induction to avoid that issue.)
At this point, we have enough definition to build a crude gerund
passing machine:
gpm0=: 4 :0
((<n2bg x),(x`:6),<n2bg y)`:6
)
In other words, if the left argument is a dyadic gerund and the right
argument is a noun we can evaluate the verb represented by the gerund
with these arguments. That said, note that this could also work if
the gerund represents an adverb that produces a monadic verb, or if it
represents a conjunction. However, it cannot be a noun, because a
train of three nouns is not syntactically valid, in J.
Now, if we want to use this in the context of ^:_ we might want our
result to also be a gerund. And, so far, we only have n2bg in our
construction kit.
So let's tackle an easy, solved problem: finding the factorial of a
small integer. And, let's use the result of Y to represent our
intermediate (and final) result.
The inductive part of our process would retain the body of the M part
of our gerund along with a new intermediate result. Perhaps:
M@[ (,&< n2bg) Y@[ * ]
But, we also need to represent the new right argument (1 less than the
previous right argument, but never going lower than 1).
1 >. <:
Now, how do we make this work with ^:_?
To make this work with ^:_ we need to have the full train (the gerund
with the number we are taking the factorial of, and all intermediate
results) as a single value which we iterate on, and we need the final
result to be a fixed point in the calculation (fixed point being where
^:_ stops). We also need tools to wrap the intermediate results in
gerund form.
And, there's two kinds of states here, to represent -- there's the
fixed point, and there's the recursive steps. It might be simplest if
we can use the same representation for both cases. But gpm0 isn't
quite right for this - it wants only one of the arguments to be in the
gerund, not both.
So let's take a step away from "continuation passing style" (one
independent argument) and invent a "gerund passing style" (two
embedded arguments with a fixed point having the same structure).
Instead of M and Y, we need to be able to extract three bodies
corresponding to x, u and y. Perhaps:
X3=: (0;1) {:: ]
U3=: 1 {:: ]
Y3=: (2;1) {:: ]
Note that U3 is a gerund body, while X3 and Y3 assume that the gerund
body is a noun body and they extract the contained noun.
If we define words based on the above extractors, we could use them like this:
xVal=: Fx train
uBod=: Fu train
yVal=: Fy train
we can put them back together into a gerund for `:6, like this:
(n2gb xVal) ; uBod ,&< n2gb y
We need to define Fx and Fy. [Caution: I am going to swap the
arguments from the order I used above, to address an issue which I
will point out later.]
Fx=: 1 >. <:@X3
Fy=: Y3 * X3
We also need to define our initial state. If we characterize our
initial state as X0, U0 and Y0 then X0 will be the number we are
taking the factorial of, U0 will represent the code that does the
computations for (n2gb xVal) ; uBod ,&< n2gb y and Y0 will be 1.
So, how do we define Fu?
We could just bundle everything together:
start=: (n2bg 5); (n2bg@Fx; U3,&< n2bg@Fy)`'' ,&< n2bg 1
step=: verb def '(U3 y)`:6 y'
Y3 step^:_ start
120
But we probably want to be able to supply an argument to this
factorial function, otherwise all we've done is represent a complex
representation for the number 120.
A brute force approach here, might be:
factorial=: 13 :'Y3 step^:_ (n2bg y); (n2bg@Fx; U3,&< n2bg@Fy)`'''' ,&< n2bg 1'
factorial 5
120
factorial 4
24
factorial"0] 2 3 5 7
2 6 120 5040
That works. But we've buried our factorial code in with our gerund
mechanics, and it would be nice to be able to separate them out.
By "factorial code" I might mean:
* The initial value to be returned by Y3 (1)
* The body of Fy (which computes subsequent values to be returned by Y3)
* The body of Fx (which computes values to be returned by X3 after our
initial pass)
(The initial value for X3 was the right argument to the derived verb.)
But that's three "independent" things, is there any way to get rid of
one of them?
One approach here, is to note that the useful computation in Fx was a
monad and the useful computation in Fy was a dyad, and J's verbs
always have both a monadic and a dyadic definition. (And, while I am
at it, if I could somehow define the identity for the verb I would not
need it to be a separate parameter. Unfortunately, I do not know how
to do that.) So, I can write a conjunction which accepts a left
argument of Fx : Fy and a right argument which is the initial value
for what Fy will be returning in later stages. (The initial value for
what Fx will produce in later stages will be an argument to our
derived verb.)
gpm1=: conjunction define
[: Y3 [: step^:_ n2bg; ((n2bg@u@X3; U3,&< n2bg@(X3 u Y3))`'' ,&< n2bg n)"_
)
(1 >. <:) :* gpm1 1 ] 5
120
In other words, given an initial value for y (1) and a monadic verb
for finding the next value of y given the current value of y (1 >. <:)
and a dyadic verb for combining the current x and y to find the next
value for x we can build a machine which acts like a recursive
function.
But here we are still bundling everything together. We could rewrite
this to expose the internals, perhaps:
gpm1start=: conjunction define
n2bg; ((n2bg@u@X3; U3,&< n2bg@(X3 u Y3))`'' ,&< n2bg n)"_
)
Now, we can do stuff like:
Y3 step step step step (1 >. <:) :* gpm1start 1 ] 5
120
And, we can inspect intermediate results:
(X3,Y3) (1 >. <:) :* gpm1start 1 ] 5
5 1
(X3,Y3) step (1 >. <:) :* gpm1start 1 ] 5
4 5
(X3,Y3) step step (1 >. <:) :* gpm1start 1 ] 5
3 20
But we did not technically need to define gpm1start as an independent
word - if we take advantage of gerund structure we could have used
gpm1 itself:
(X3,Y3) step step (<(0;1;2;1;2) {:: (1 >. <:) :* gpm1 1`'')`:6]5
3 20
In other words, we have a rich set of tools, here, for representing
constrained computation, if we want to use them for that purpose.
FYI,
--
Raul
P.S. In the middle of writing this, I decided that I wanted my monadic
verb to be on the left and my dyadic verb to be on the right - this
matches the pattern used by : but is of course not the only option.
P.P.S. Notation like 0;1;1;1 might seem mysterious, but it's really no
worse (and no better) than things like cadddr in scheme, or more
verbose arrangements of words like 'first' and 'rest'.
Anyways here's a breakdown of the left arguments for (0;1;1;1) {:: ]
An initial 0 breaks the gerund out of its box, exposing the top level
of its internal structure. This structure is typically a type
identifier followed by a value. A subsequent 1 extracts that value.
In an expression like ,&'abc' the type identifier will be '&' and the
value will be a pair corresponding to , and 'abc' so another 1 gets us
the internals representing the 'abc', and a final 1 extracts the value
itself.
If we instead wanted the gerund body for the verb, we use (0;1;0) {::
] -- again, the leftmost 0 exposes the top level of the gerund
internals, the 1 gets us the pair which were combined using & and 0
gets us the gerund body corresponding to the left argument of the '&'
Note that we are ignoring '&' here because we are only using this in
contexts which we know were built using & at the top level - this
knowledge about context corresponds to what could be a static type
constraint, if we had a statically typed implementation of J.
In the case of X3, U3 and Y3 we were working with a gerund train, so
instead of always using 0 to expose the internals we had to pick which
member of the train we were exposing. An initial 0 got us the
leftmost member of the train, an initial 1 got us the second member of
the train and an initial 2 got us the final member of the train.
After that, for X3 and Y3, we used a 1 to get at the content - while
the computer needs the type information to represent a general case,
we were sufficiently constrained that we could ignore the type
information (the type was always a noun). For U3 we stopped after
extracting our initial body - we had no need to look any deeper.
Finally, there's
(<(0;1;2;1;2) {:: (1 >. <:) :* gpm1 1`'')`
Here, gpm1 was building us a train like this: ([: Y3 [: step^:_
goodies) and we wanted to extract the goodies. To do this, note that
a long train can be build up from shorter trains - in this case the
underlying structure would be ([: Y3 ([: step^:_ goodies))
So: 0 opens the gerund representing the result of gpm1, 1 extracts the
body of the top train ([: Y3 ([: step^:_ goodies))and 2 gets us the
righthand side of that train, then 1 extracts the body of the inner
train ([: step^:_ goodies) and 2 gets us the righthand side (goodies)
of this inner train. Since this was the body of a gerund, we can box
it, and then turn it back into a verb, and evaluate it with an
argument of 5, to build our starting state for finding the factorial
of 5.
P.P.P.S. In addition to the term "continuation", another word for a
code fragment (which has properties somewhat like our gerunds here) is
"thunk". As I understand it, a continuation is a suspended
computation which takes 1 argument and a thunk is a suspended
computation which takes 0 arguments. In other words in the sentence
(thunk`:6 y) the result of thunk`:6 is what I would be inclined to
think of as a continuation.
P.P.P.P.S. this is a bit long, but I think it's a relevant exposition
of some ideas used to describe recursive processes which was asked
about in another [long] thread.
P.P.P.P.P.S. I may have made mistakes in this exposition, if so please
let me know and I will attempt to understand and hopefully correct
those mistakes.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
