TweetFollow Us on Twitter

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

(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 redundant-fact
 (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 abstracted-fact and Y from pass-fact, it would be interesting to see how close the definitional part of fact (the part that has the if) now is to abstracted-fact.

(* 10 *)

(lambda (n)
 (if (zero? n)
 1
 (* n ( (ff) (1-n)))))

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 dont-try-this-at-home-fact
 (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 abstracted-fact.

(* 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 abstracted-fact and name it locally.

(*  15 *)

>>>
(define fact
 (let ((abstracted-fact
 (lambda (f)
 (lambda (n)
 (if (zero? n)
 1
 (* n (f (1- n))))))))
 (let ((g (lambda (f)
 (lambda (n)
 ((abstracted-fact (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. (abstracted-fact is free with respect to g and bound with respect to the outermost let.) We can fix this by abstracting out abstracted-fact from the innermost let.

(*  16 *)

>>>
(define fact
 (let ((abstracted-fact
 (lambda (f)
 (lambda (n)
 (if (zero? n)
 1
 (* n (f (1- n))))))))
 ((lambda (abstracted-function)
 (let ((g (lambda (f)
 (lambda (n)
 ((abstracted-function (f f)) n)))))
 (g g)))
 abstracted-fact)))
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 abstracted-fact 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 (abstracted-function)
 (let ((g (lambda (f)
 (lambda (arg)
 ((abstracted-function (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 ((abstracted-fact
 (lambda (f)
 (lambda (n)
 (if (zero? n)
 1
 (* n (f (1- n))))))))
 (y abstracted-fact)))
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 my-even?
 (lambda (n)
 (if (zero? n)
 #t
 (my-odd? (1- n)))))
my-even?
>>>
(define my-odd?
 (lambda (n)
 (if (zero? n)
 #f
 (my-even? (1- n)))))
my-odd?
>>> (my-odd? 5)
#t
>>> (my-even? 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 l-calculus.)

Exercise for the Überprogrammer: Derive Y2. Hint for a possible game plan: starting with my-even? and my-odd? 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 *)

(com-cons ’a (com-cons ’b (com-cons ’c com-nil))) ,

and this same idea could be used in conjuring up a combinator version of Scheme’s list function, which could be called com-list.

“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 Algebraic-like 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.

 
AAPL
$99.02
Apple Inc.
+1.35
MSFT
$43.97
Microsoft Corpora
-0.53
GOOG
$590.60
Google Inc.
+1.58

MacTech Search:
Community Search:

Software Updates via MacUpdate

Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more
Autopano Giga 3.6 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more

Latest Forum Discussions

See All

Traps n’ Gemstones Review
Traps n’ Gemstones Review By Campbell Bird on July 28th, 2014 Our Rating: :: CASTLEVANIA JONESUniversal App - Designed for iPhone and iPad Fight mummies, dig tunnels, and ride a runaway minecart to discover ancient secrets in this... | Read more »
The Phantom PI Mission Apparition Review
The Phantom PI Mission Apparition Review By Jordan Minor on July 28th, 2014 Our Rating: :: GHOSTS BUSTEDUniversal App - Designed for iPhone and iPad The Phantom PI is an exceedingly clever and well-crafted adventure game.   | Read more »
More Stubies Are Coming Your Way in a Ne...
More Stubies Are Coming Your Way in a New Update Posted by Jessica Fisher on July 28th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
The Great Prank War Review
The Great Prank War Review By Nadia Oxford on July 28th, 2014 Our Rating: :: PRANKING IS SERIOUS BUSINESSUniversal App - Designed for iPhone and iPad Though short, The Great Prank War offers an interesting and fun mix of action and... | Read more »
Marvel Contest of Champions Announced at...
Marvel Contest of Champions Announced at Comic-Con Posted by Jennifer Allen on July 28th, 2014 [ permalink ] Announced over the weekend at San Diego Comic-Con was the fairly exciting looking Marvel Contest of Champions. | Read more »
Teenage Mutant Ninja Turtles Review
Teenage Mutant Ninja Turtles Review By Jennifer Allen on July 28th, 2014 Our Rating: :: DULL SWIPINGUniversal App - Designed for iPhone and iPad The pizza power is weak when it comes to this Teenage Mutant Ninja Turtles game.   | Read more »
Exploration Focused Puzzle Game Beatbudd...
Exploration Focused Puzzle Game Beatbuddy Set to Make Transition from PC to iOS this September Posted by Jennifer Allen on July 28th, 2014 [ permalink ] | Read more »
PlanetHD
PlanetHD By Nadia Oxford on July 28th, 2014 Our Rating: :: SPACE MADNESSUniversal App - Designed for iPhone and iPad PlanetHD will keep players busy for a while, though its unpredictable physics are a handful to deal with.   | Read more »
This Week at 148Apps: July 21-25, 2014
Another Week of Expert App Reviews   At 148Apps, we help you sort through the great ocean of apps to find the ones we think you’ll like and the ones you’ll need. Our top picks become Editor’s Choice, our stamp of approval for apps with that little... | Read more »
Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more
Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
WW Sales Program Manager, *Apple* Online St...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.