Mailing List Archive: 49091 messages

## [REBOL] Re: Functional programming in REBOL

### From: larry:ecotope at: 12-Aug-2001 17:08

```
Hi Ladislav,

OK, I will stop teasing. The mystery function ??? is actually a very famous
function with the rather imposing name "the applicative-order Y-combinator".
Its derivation was a culminating point in the development of the lambda
calculus (the mathematical theory underlyling functional programming). It is
also known as the Paradoxical Combinator and the *dreaded* Y-combinator. I
must say that it is a truly mind-stretching function, even when you have
done a derivation of it, it still seems like black magic.

There have been recent discussions of the implementation of Y in Perl,
Scheme, Ruby, Java, and the lambda calculus on the web:

http://lambda.weblogs.com/discuss/msgReader\$838

And now we also have a version in REBOL.:-)

Although paradoxical, it is actually a useful function (especially in the
lambda calculus, because it is what allows recursion).

The applicative-order Y-combinator in REBOL:

Y: func [g][
do
func [h][h :h]
cfunc [f][g func [x][do f :f x]]
]

I found that it requires only one use of cfunc (the function that makes
functions that remember their args). My simple cfunc is included below for
those who wish to try this version. Ladislav's e-func will work just as
well. Alternatively, we can replace the single use of cfunc with an
equivalent USE block, thus making Y self-contained:

Y: func [g][
do
func [h][h :h]
func [f][use [h][h: :f g func [x][do h :h x]]]
]

We can define the "self-application"  U-combinator as:

U: func [f][f :f]

Then the second version of Y can be written as:

Y: func [g][
U func [f][use [h][h: :f g func [x][do h :h x]]]
]

The Y-combinator is a very special function because it generates the
fixed-point of its function argument. It satisifes the following equation:

(g (Y g)) = (Y g)       (g (g (Y g))) = (Y g)  and so on.

We will test this in a bit.

The Why of Y

We know that we can use a function without giving it a name, e.g.

>> do func [x][x + 12] 5
== 17

But consider a recursive function like the recursive version of factorial:

fact: func [n][
either zero? n [1][n * fact n - 1]
]

Here it seems, the name fact for the function is required in order to obtain
the recursion. But one can avoid naming the function and still get the
recursion. In a nutshell, this is what Y does. I will illustrate it's use on
the fact function.

Step 1) We want to use functional abstraction to remove the reference to
fact in the global context from the body. We can do this with a function
wrapper made like this:

fact*: func [fact][
func [n][
either zero? n [1][n * fact n - 1]
]
]

So the function to be applied in the body for the next recursion is passed
in as an argument. Notice the code in the body of fact has not been changed.
Making the wrapper just means creating a func with an arg of the same name
as the name of the function used in the body for the recursion step. Notice
that fact* is not recursive.

This is the kind of function which Y needs for its argument. Y will
instantly turn this kind of function into one that recurs as often as
needed. The inner func must have a termination condition or the application
of Y will create a function that loops forever.

Step 2)

Now we can define the recursive factorial we want as:

>>fact: Y :fact*

>> fact 12
== 479001600

>> source fact
fact: func [n][
either zero? n [1] [n * fact n - 1]
]

This is a bit misleading because the two occurences of fact are unrelated,
we could have named the outer function anything we wanted.

But we still seem to be using a variable name for one of our functions. This
is easily avoided by substituting the definition of fact* as the arg for Y:

fact: Y func [fact][
func [n][either zero? n [1][n * fact n - 1]]
]

Look Ma! No Names.

This is the final product, a recursive version of factorial which does not
require any external name resolution for the recursion function in the inner
body. It can be shown that Y is a universal recurser (i.e., it can be used
to recursively reduce any wrapped recursive function).

Now we can test the fixed-point property with respect to the fact* function.

>> do Y :fact* 5
== 120
>> do fact* Y :fact* 5
== 120
>> do fact* fact* Y :fact* 5
== 120
>>

So (Y fact*) is indeed a fixed-point of fact*.

The Y-combinator has been an object of fascination in computer science since
Church invented it in the 30's. It has also apparently struck fear in the
hearts of many students.

My own reaction is: Wow! Y is possibly the most clever and devious function
I have seen. It's fun stretching your mind and Y is guaranteed to do that.

There are some good references on the web with derivations of Y, mostly in
the Scheme language:

http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
http://www.mactech.com/articles/mactech/Vol.08/08.01/DazeY/
http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/index.ht
ml
http://www.mit.edu/afs/athena/project/adedev/elk/tst/Y

There is also a good derivation in Chapter 9 of "The Little Schemer" by
Friedman and Felleisen. This is repeated with extensive annotation by Jim
Weirich in the Scheme link of the URL at the top of this note. His final
comment:

;; I've walked through the entire thing, and can say I believe I
;; understand each step, but the wonder of the entire process leaves
;; my mind boggled.

Ladislav, could you please check all the functions I give above, and see if
I went too far in eliminating the use of cfunc. Let me know if you see a
better way to present the Y function.
Try applying it to your favorite recursive function.

Enjoy
-Larry

PS I am looking forward to your further comments on Y, especially with
regard to your comments below. BTW There is another way to produce recursive
anonymous functions using just the U combinator combined with a small change
in the original recursive function body.

---------code for cfunc --------------------

cfunc: func [spec body /local args][
args: copy []
repeat el spec [if word? :el [append args to-get-word :el]]
func spec compose/deep [
do append reduce [func [(spec)][(body)]][(args)]
]
]
```