I believe Jose Quintana has already posted similar material, using apply. He might have even posted an implementation exactly like what I am posting here. But I am not sure how to find that.
Also, I am basing this off of my reading of http://mvanier.livejournal.com/2897.html -- I have some quibbles with how he has treated some subjects, but I will mostly refrain from expressing them here. Note however that the idea of a "combinator" is not something that has an exact syntactic equivalent in J. This is a slippery issue to discuss because of the terminology differences between people dealing with lambda expressions and people dealing with J. But I will try: First, a "lambda" roughly corresponds to a "gerund" in J. A lambda can take another lambda as an argument, and can produce another lambda as a result. Of course, gerunds are passive (which is somewhat like being lazy, though not quite the same), but we can activate them using `:6 (And, we can go the other way -- converting a verb into a gerund, with a `'' suffix next to the verb.) However, another issue is that a gerund only takes a single right argument (which of course might be an arbitrarily complex array). Traditionally when dealing with "lambdas" this single left argument is broken into named pieces. But these pieces might be other lambdas and they might be lists and they might be whatever else, while J's arrays are homogeneous. Anyways, rather than attempting to re-implement all the quirks of the syntax normally employed by people working with lambdas, I would prefer to re-express the concepts using J's native syntax -- the resulting code will be much simpler than if I also had to build an emulator. So I am "not really implementing the Y combinator" here, because I am not implementing a combinator. But what I am going to do here is conceptually similar... So, anyways... code: almost_fibonacci=:4 :0 f=. x`:6 if. 0 = y do. 0 elseif. 1 = y do. 1 elseif. do. ((f'')`:6 y-1) + ((f'')`:6 y-2) end. ) almost_factorial=:4 :0 f=. x`:6 if. 0 = y do. 1 else. y * (f'')`:6 y-1 end. ) Y=: 3 :0 (Y bind y`'')&(y`:6)`'' ) And, example use: (Y almost_fibonacci`'')`:6"0 ] i.9 0 1 1 2 3 5 8 13 21 (Y almost_factorial`'')`:6"0 ] i.9 1 1 2 6 24 120 720 5040 40320 In other words, this is a mechanism for implementing recursion. How deep can it go? almost_increment=:4 :0 f=. x`:6 try. (f'')`:6 y+1 catch. y end. ) (Y almost_increment`'')`:6 ] 0 9996 Compare this to $:@>: ::] 0 6666 So we are still limited by the C stack here, but it's a bit more generous than anonymous recursion. And what's happening is that when we get to the recursive case we run Y to unpack a verb which is capable of one more level of recursion. f'' gives us a gerund that can handle one more level of recursion, and (f'')`:6 is that same result expressed as an active verb. But maybe there's a way of using induction instead of recursion? To use induction, we would want to build our result up from an inductive start instead of working backwards. And, for something like fibonacci we need to retain at least two previous values. Perhaps something like this: resembles_fibonacci=:3 :0 'limit n x_prev x_prev_prev'=. y if. n >: limit do. y else. limit, (n+1), (x_prev+x_prev_prev), x_prev end. ) resembles_fibonacci^:_] 8 0 0 1 8 8 21 13 Compare this to (Y almost_fibonacci`'')`:6"0 ] 8 21 The result using Y is cleaner -- we do not have to extract our result from the midst of our intermediate results. Nor do we have to assemble our initial state. Y itself is generic. Meanwhile, Y requires extensive use of passive voice and it depends C's stack for recursion. The inductive example does not use the stack. And, of course, assembling our initial state need not be all that hard, and we can arrange for our desired result to be easier to extract: inductive_fibonacci=:3 :0 if. 0=#$y do. y,0 0 1 return. end. 'limit n x_prev_prev x_prev'=. y if. n >: limit do. y else. limit, (n+1), x_prev, x_prev+x_prev_prev end. ) ([:{: inductive_fibonacci^:_)"0 i. 9 0 1 1 2 3 5 8 13 21 And note that the Y version of fibonacci is doubly recursive, where the inductive implementation is not (though using fibonacci at rank 0, like I am doing here, introduces yet another form of inefficiency that could be better addressed in the body of the definition of a fibonacci verb). Anyways... from a J point of view the "Y combinator" seems to be less than enthralling. Combinators in J require extensive explicit treatment of passive voice (though perhaps not so much when implemented using apply instead of using gerunds?), and they have a few other issues when viewed from a J point of view. -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
