This post, and Pepe's last night, interest me. Can I suggest you write them up as Wiki essays?
-Dan Please excuse typos; composed l on a handheld device. On Feb 21, 2013, at 3:42 PM, Raul Miller <[email protected]> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
