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

Reply via email to