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
