Daze Y
Volume Number:   8

Issue Number:   1

Column Tag:   Lisp Listener

Deriving Miss Daze Y
Deriving the (applicative order) Y combinator in a concrete way via fact
By André van Meulebrouck, Chatsworth, California: Internet: vanMeule@cup.portal.com
“Deriving Miss Daze Y”
“The utmost abstractions are the true weapons with which to control our thought of concrete fact.”  Alfred North Whitehead
This article will seek to derive the (applicative order) Y combinator in a concrete way via fact.
Definition: The Y combinator is a function which, when applied to the abstracted version of a recursive function, is the equivalent of the (original) recursive function. [vanMeule May 1991]
Definition: fact is that pedagogical function of obsessive interest, the factorial function.
Abstracted fact
In [vanMeule May 1991], the Y combinator was motivated by a desire to convert everything into a combinator (a lambda expression which has no free variables). In “combinatorizing” everything we found the following definition in need of abstraction (the process whereby we get rid of free variables by making them bound in an outer lambda expression, then promising to pass in “the right thing” when invoking the outer lambda expression).
(* 1 *)
(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (1 n))))))
In the definition of fact above, the variable is a free variable. (Such recursive definitions rely on free variables being resolved in an odd, notpurelylexical way.) The definition for abstractedfact looks like the following.
(* 2 *)
(define abstractedfact
(lambda (fact)
(lambda (n)
(if (zero? n)
1
(* n (fact (1 n)))))))
The free variable is gone, but we are not home and dry because we now have to pass in the definition of fact. In fact, we have to have a mechanism that is capable of providing them on demand!
Recursionless fact
In [vanMeule Jun 1991], what is perhaps the simplest trick for getting rid of recursion was shown: passing the would be recursive function as an argument!
(* 3 *)
>>>
(define passfact
(lambda (f n)
(if (zero? n)
1
(* n (f f (1 n))))))
passfact
>>> (passfact passfact 5)
120
Notice what happened to the original definition of fact: it was changed! In abstractedfact, we did not change the definition at all  we merely wrapped a lambda form around the untamperedwithdefinition of fact.
Merging facts
What we really want is a way to get rid of recursion without modifying the definition of the function we’re ridding the recursion from. In other words, we want to have the best of the two different approaches: abstractedfact gets rid of the free variable yet keeps the definition intact; passfact seems to have captured a recursive mechanism without using recursion.
Theoretically, it should be possible to start from passfact and massage it into two parts; a “recursionless recursion mechanism” (the Y combinator), and abstractedfact.
To Be or to Let it Be
In the discussion that follows, we will use let, which hasn’t been “properly” introduced yet. So, let’s take a look at let via the following example.
(* 4 *)
(* (+ 3 2)
(+ 3 2))
The expression (+ 3 2) is being recomputed. Alternatively, we can compute the value of (+ 3 2) once, and hold onto the result via let.
(* 5 *)
(let ((threeplustwo (+ 3 2)))
(* threeplustwo threeplustwo))
While the main motivation behind let is to avoid recomputations, it can be used purely for the sake of readability (i.e. even if the value being leted will only be used once).
Our use of let herein will be purely syntactic sugar for a more (syntactically) cumbersome looking (but semantically equivalent) lambda expression. For instance, our example would look like the following if we were to use lambda instead of let.
(* 6 *)
(lambda (threeplustwo)
(* threeplustwo threeplustwo))
(+ 3 2))
[Rees et al. 1986] gives a more rigorous and precise Scheme definition for let.
Getting the facts straight
In the style of [Gabriel 1988], let’s start with passfact and try to massage it into what we want.
Since one of the rules of our “minimalist” game [vanMeule Jun 1991] was to stick to combinators and lcalculus, we are compelled to curry (a requirement of lcalculus). Also, since there are cases where currying gains expressive power that we would otherwise have to simulate, it seems natural to curry as the first step.
(* 7 *)
>>>
(define passfact
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (1 n)))))))
passfact
>>>
((passfact passfact) 5)
120
Notice how the invocation of the new version of fact is more complicated than the recursive
version. That can be fixed by tucking the invocation, which passes the function as an argument,
inside the new definition of fact.
(* 8 *)
>>>
(define fact
(let ((g (lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (1 n))))))))
(g g)))
fact
>>>
(fact 5)
120
(Note that we would have looked like the Department of Redundancy Department had we not curried  parameter n would have to be bound twice.)
(* 9 *)
(define redundantfact
(lambda (n)
(let ((g (lambda (f n)
(if (zero? n)
1
(* n (f f (1 n)))))))
(g g n))))
Recalling that our game plan was to separate out abstractedfact and Y from passfact, it would be interesting to see how close the definitional part of fact (the part that has the if) now is to abstractedfact.
(* 10 *)
(lambda (n)
(if (zero? n)
1
(* n ( (ff) (1n)))))
As can be seen above, we’re actually quite close already! If the (f f) part in the box were abstracted out we’d be there!
(* 11 *)
(lambda (F)
(lambda (n)
(if (zero? n)
1
(* n (F (1 n))))))
(Note: the name of the parameters in the above expression are not significant because there are no free variables in the expression. For instance, parameter F could be renamed to fact or any other name we want other than n.)
After abstracting out the (f f) part and invoking it on the argument it needs, we have the following.
(* 12 *)
>>>
(define fact
(let ((g (lambda (f)
(lambda (n)
((lambda (func)
(if (zero? n)
1
(* n (func (1 n)))))
(f f))))))
(g g)))
fact
>>> (fact 5)
120
(Question for the Überprogrammer: Why couldn’t we do the abstraction and invocation as in the following?)
(* 13 *)
(define donttrythisathomefact
(let ((g (lambda (f)
((lambda (func)
(lambda (n)
(if (zero? n)
1
(* n (func (1 n))))))
(f f)))))
(g g)))
Now, massage the definitional part of fact some more so that it looks just like abstractedfact.
(* 14 *)
>>>
(define fact
(let ((g (lambda (f)
(lambda (n)
(((lambda (func)
(lambda (n)
(if (zero? n)
1
(* n (func (1 n))))))
(f f))
n)))))
(g g)))
fact
>>> (fact 5)
120
Using a gratuitous let, we can pull out the definition of abstractedfact and name it locally.
(* 15 *)
>>>
(define fact
(let ((abstractedfact
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (1 n))))))))
(let ((g (lambda (f)
(lambda (n)
((abstractedfact (f f)) n)))))
(g g))))
fact
>>> (fact 5)
120
Notice that in doing the above, a free variable was introduced into g in the second let. (abstractedfact is free with respect to g and bound with respect to the outermost let.) We can fix this by abstracting out abstractedfact from the innermost let.
(* 16 *)
>>>
(define fact
(let ((abstractedfact
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (1 n))))))))
((lambda (abstractedfunction)
(let ((g (lambda (f)
(lambda (n)
((abstractedfunction (f f)) n)))))
(g g)))
abstractedfact)))
fact
>>> (fact 5)
120
Y is now ready to leave the nest and flY!
Notice that the last tweak to fact achieved our aim: we now have abstractedfact totally separated out from the recursionless recursion mechanism.
We can now name the recursion mechanism and make it a function in its own right.
(* 17 *)
>>>
(define y
(lambda (abstractedfunction)
(let ((g (lambda (f)
(lambda (arg)
((abstractedfunction (f f)) arg)))))
(g g))))
y
Question: Is Y a general purpose recursion removal function? (i.e., will it remove the recursion in any arbitrary function?) Herein, I will simply claim that it is and refer the reader to [Gabriel 1988] and/or any of the many other references that address this question (some of which are are listed in [vanMeule May 1991, Jun 1991]).
Now that we’ve got Y, we can clean up the definition of fact.
(* 18 *)
>>>
(define fact
(let ((abstractedfact
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (1 n))))))))
(y abstractedfact)))
fact
>>> (fact 5)
120
We can clean up further by getting rid of the gratuitous let.
(* 19 *)
>>>
(define fact
(y (lambda (f)
(lambda (n)
(if (zero? n)
1
(* n (f (1 n))))))))
fact
>>> (fact 5)
120
Looking ahead
There’s a type of recursion that our (applicative order) version of Y is not designed to handle. Consider the following functions.
!codeexamplestart!
(* 20 *)
>>>
(define myeven?
(lambda (n)
(if (zero? n)
#t
(myodd? (1 n)))))
myeven?
>>>
(define myodd?
(lambda (n)
(if (zero? n)
#f
(myeven? (1 n)))))
myodd?
>>> (myodd? 5)
#t
>>> (myeven? 5)
#f
These functions need to know about each other: they are mutually recursive.
We can handle this problem by coming up with a new version of Y (let’s call it Y2). Y wants one function as an argument. What happens if instead of a function, a list of functions is passed in? Such a list could contain all the functions which need to have (mutual) knowledge of each other. Accessing the different functions can then be done by using list accessing primitives. (This is the approach used to resolve the problem in lcalculus.)
Exercise for the Überprogrammer: Derive Y2. Hint for a possible game plan: starting with myeven? and myodd? expressed via a letrec, get rid of the letrec by converting to a let and making use of a dynamic list. Then, thrash out Y2 in a similar manner as was done for Y in this article. Does Y2 turn out to be the same as Y?
Question for the Überprogrammer: if evaluation were normal order rather than applicative order, could we use the same version of Y for mutually recursive functions that we used for “regular” recursive functions (thus making a Y2 function unnecessary)?
Another question: Let’s say we have 3 or more functions which are mutually recursive. What do we need to handle this situation when evaluation is applicative order? What about in normal order?
Note: [vanMeule Jun 1991] gave enough primitives to create dynamic lists. For example, the combinator equivalent of the Scheme expression: (list ’a ’b ’c) could be built like this:
(* 21 *)
(comcons ’a (comcons ’b (comcons ’c comnil))) ,
and this same idea could be used in conjuring up a combinator version of Scheme’s list function, which could be called comlist.
“Thanks” to:
The hummingbird nest in a nearby tree which afforded much enjoyment in watching two new pilots grow up and get their wings. Bugs/infelicities due to Spring in the air.
Bibliography and References
[Gabriel 1988] Richard P. Gabriel. "The Why of Y." LISP Pointers, vol. 2, no. 2 October/November/December, 1988.
[Rees et al. 1986] Jonathan Rees and William Clinger (editors). Revised3 Report on the Algorithmic Language Scheme; AI Memo 848a. MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, USA, September 1986.
[vanMuele May 1991] André van Meulebrouck. "A Calculus for the Algebraiclike Manipulation of Computer Code" (Lambda Calculus). MacTutor, May 1991.
[vanMuele Jun 1991] André van Meulebrouck. "Going Back to Church" (Church numerals). MacTutor, June 1991.
All examples in this article were implemented in MacScheme.