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 abstrac-tion
(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, not-purely-lexical way.)
The definition for abstracted-fact looks like the following.
(* 2 *)
(define abstracted-fact
(lambda (fact)
(lambda (n)
(if (zero? n)
1
(* n (fact (1- n)))))))
The free variable is gone, but we are not home and dry be-cause 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 pass-fact
(lambda (f n)
(if (zero? n)
1
(* n (f f (1- n))))))
pass-fact
>>> (pass-fact pass-fact 5)
120
Notice what happened to the original definition of fact: it was changed! In
abstracted-fact, we did not change the definition at all - we merely wrapped a lambda
form around the untampered-with-definition 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: abstracted-fact gets rid of the free
variable yet keeps the definition intact; pass-fact seems to have captured a recursive
mechanism without using recursion.
Theoretically, it should be possible to start from pass-fact and massage it into
two parts; a “recursionless recursion mechanism” (the Y combinator), and
abstracted-fact.
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 ((three-plus-two (+ 3 2)))
(* three-plus-two three-plus-two))
While the main motivation behind let is to avoid recomp-utations, 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 (three-plus-two)
(* three-plus-two three-plus-two))
(+ 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 pass-fact 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 l-calculus, we are compelled to curry (a requirement of
l-calculus). 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 pass-fact
(lambda (f)
(lambda (n)
(if (zero? n)
1
(* n ((f f) (1- n)))))))
pass-fact
>>>
((pass-fact pass-fact) 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