> Note that while this definition is correct, it's also rather slow, The above finding does not surprise me; as far as I can see and remember your implementation is based on gerunds. The gerundial (or atomic) representation seems to be the natural J way to encode verbs into nouns; however, in my experience, it often leads to space and time inefficiencies relative to a straightforward linear representation and I definitely favor the latter, bugs notwithstanding (e.g., http://www.jsoftware.com/pipermail/programming/2012-October/029548.html ) for production purposes.
This is a slight (fully tacit) variation of my Rosetta Code implementation ( http://rosettacode.org/wiki/Y_combinator#J ) based on linear representation: u=. [ NB. Function (left) n=. ] NB. Argument (right) sr=. ([ apply ,&<) f. NB. Self referring (yc=. ((((&>)/)((((^:_1)b.)(`(<'0';_1)))(`:6)))(&(sr f.)))f.) ((((&>)/)((((^:_1)b.)(`_1))(`:6)))(&([ 128!:2 ,&<)))f. NB. A tacit Y combinator (fac=. (1:`(n * u sr n - 1:)) @. (0: < n)) f. 1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0: < ]) (Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1: < n)) f. (([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1: < ]) This is a comparison of the two implementations: st=. 7!:2@:] , 6!:2 100 st '(Y Ev almost_factorial)Ev 9' 712128 0.00461468 10 st '(Y Ev almost_fibonacci)Ev"0 i. 10' 775104 0.12754 100 st 'fac f. yc 9' 97024 0.000340252 10 st 'Fib f. yc ("0) i.10' 62336 0.00417713 Nevertheless, I do appreciate your lambda calculus style implementation of the Y combinator. On Tue, Oct 9, 2012 at 12:25 PM, Raul Miller <[email protected]> wrote: > In http://www.jsoftware.com/pipermail/programming/2012-June/028338.html > (and http://www.jsoftware.com/pipermail/programming/2012-June/028339.html) > I presented what I was thinking of as a J implementation of the Y > combinator. > > But I overlooked a key detail -- my "implementation" of Y named itself > in its body, and the whole point of the Y combinator is to implement > recursion without any function having a name for itself. > > Here's an implementation without that self reference: > > lambda=:3 :0 > if. 1=#;:y do. > 3 :((y,'=.y');<;._2]0 :0)`'' > else. > (,<#;:y) Defer (3 :(('''',y,'''=.y');<;._2]0 :0))`'' > end. > ) > > Defer=:2 :0 > if. (_1 {:: m) <: #m do. > v |. y;_1 }. m > else. > (y;m) Defer v`'' > end. > ) > > M=: lambda 'f h x' > (f`:6 h`:6 h)`:6 x > ) > > N=: lambda 'f h' > (M`:6 f)`:6 h > ) > > Y=: lambda 'f' > g=. N`:6 f > g`:6 g > ) > > Also posted at > http://rosettacode.org/wiki/Y_combinator#alternate_implementation > and here are the examples currently posted there: > > (Y Ev almost_factorial)Ev 9 > 362880 > (Y Ev almost_fibonacci)Ev 9 > 34 > (Y Ev almost_fibonacci)Ev"0 i. 10 > 0 1 1 2 3 5 8 13 21 34 > > Note that while this definition is correct, it's also rather slow, and > seems to allow an effective stack depth of 2000 stack frames before it > errors out, when used like this: > > stack_depth=: lambda 'f n' > f Ev ([ smoutput) n+1 > ) > > (Y Ev stack_depth)Ev 0 > > Hopefully, that's the last of my mistakes on my treatment of this issue... > > Here's how it works: > > in M: > > f will be the application function body (such as almost_factorial) > deferred where it needs an additional argument. > > h will be the deferred function body of N associated with f and > waiting for a single additional argument > > x will be the recursive parameter (this will be an integer, when > evaluating almost_factorial). > > And, these definitions are consistent with the values associated with > those names in N and Y. > > The trick is that we're always building a new h every time before we > evaluate f, which gives us a self reference mechanism. The h result > here always has the same structure, but it's always computed afresh, > which allows us to have recursion while evading any requirement for a > name for the recursive function. > > Y just initializes the process. > > FYI, > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
