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.76
Apple Inc.
+2.09
MSFT
$44.08
Microsoft Corpora
+0.45
GOOG
$520.84
Google Inc.
+9.67

MacTech Search:
Community Search:

Software Updates via MacUpdate

Macgo Blu-ray Player 2.10.9.1750 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple iOS 8.1 - The latest version of Ap...
The latest version of iOS can be downloaded through iTunes. Apple iOS 8 comes with big updates to apps you use every day, like Messages and Photos. A whole new way to share content with your family.... Read more
TechTool Pro 7.0.5 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PDFKey Pro 4.0.2 - Edit and print passwo...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Yasu 2.9.1 - System maintenance app; per...
Yasu was originally created with System Administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks... Read more
Hazel 3.3 - Create rules for organizing...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a... Read more
Autopano Giga 3.7 - 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
MenuMeters 1.8 - CPU, memory, disk, and...
MenuMeters is a set of CPU, memory, disk, and network monitoring tools for Mac OS X. Although there are numerous other programs which do the same thing, none had quite the feature set I was looking... Read more
Coda 2.5 - One-window Web development su...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few... Read more
Arq 4.6.1 - Online backup to Google Driv...
Arq is super-easy online backup for the Mac. Back up to your own Google Drive storage (15GB free storage), your own Amazon Glacier ($.01/GB per month storage) or S3, or any SFTP server. Arq backs up... Read more

Latest Forum Discussions

See All

This Week at 148Apps: October 13-17, 201...
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »
Angry Birds Transformers Review
Angry Birds Transformers Review By Jennifer Allen on October 20th, 2014 Our Rating: :: TRANSFORMED BIRDSUniversal App - Designed for iPhone and iPad Transformed in a way you wouldn’t expect, Angry Birds Transformers is a quite... | Read more »
GAMEVIL Announces the Upcoming Launch of...
GAMEVIL Announces the Upcoming Launch of Mark of the Dragon Posted by Jessica Fisher on October 20th, 2014 [ permalink ] Mark of the Dragon, by GAMEVIL, put | Read more »
Interview With the Angry Birds Transform...
Angry Birds Transformers recently transformed and rolled out worldwide. This run-and-gun title is a hit with young Transformers fans, but the ample references to classic Transformers fandom has also earned it a place in the hearts of long-time... | Read more »
Find Free Food on Campus with Ypay
Find Free Food on Campus with Ypay Posted by Jessica Fisher on October 20th, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »
Strung Along Review
Strung Along Review By Jordan Minor on October 20th, 2014 Our Rating: :: GOT NO STRINGSUniversal App - Designed for iPhone and iPad A cool gimmick and a great art style keep Strung Along from completely falling apart.   | Read more »
P2P file transferring app Send Anywhere...
File sharing services like Dropbox have security issues. Email attachments can be problematic when it comes to sharing large files. USB dongles don’t fit into your phone. Send Anywhere, a peer-to-peer file transferring application, solves all of... | Read more »
Zero Age Review
Zero Age Review By Jordan Minor on October 20th, 2014 Our Rating: :: MORE THAN ZEROiPad Only App - Designed for the iPad With its mind-bending puzzles and spellbinding visuals, Zero Age has it all.   | Read more »
Hay Ewe Review
Hay Ewe Review By Campbell Bird on October 20th, 2014 Our Rating: :: SAVE YOUR SHEEPLEUniversal App - Designed for iPhone and iPad Pave the way for your flock in this line drawing puzzle game from the creators of Worms.   | Read more »
My Very Hungry Caterpillar (Education)
My Very Hungry Caterpillar 1.0.0 Device: iOS Universal Category: Education Price: $3.99, Version: 1.0.0 (iTunes) Description: Care for your very own Very Hungry Caterpillar! My Very Hungry Caterpillar will captivate you as he crawls... | Read more »

Price Scanner via MacPrices.net

2013 15-inch 2.0GHz Retina MacBook Pro availa...
B&H Photo has leftover previous-generation 15″ 2.0GHz Retina MacBook Pros now available for $1599 including free shipping plus NY sales tax only. Their price is $400 off original MSRP. B&H... Read more
Updated iPad Prices
We’ve updated our iPad Air Price Tracker and our iPad mini Price Tracker with the latest information on prices and availability from Apple and other resellers, including the new iPad Air 2 and the... Read more
Apple Pay Available to Millions of Visa Cardh...
Visa Inc. brings secure, convenient payments to iPad Air 2 and iPad mini 3as well as iPhone 6 and 6 Plus. Starting October 20th, eligible Visa cardholders in the U.S. will be able to use Apple Pay,... Read more
Textkraft Pocket – the missing TextEdit for i...
infovole GmbH has announced the release and immediate availability of Textkraft Pocket 1.0, a professional text editor and note taking app for Apple’s iPhone. In March 2014 rumors were all about... Read more
C Spire to offer iPad Air 2 and iPad mini 3,...
C Spire on Friday announced that it will offer iPad Air 2 and iPad mini 3, both with Wi-Fi + Cellular, on its 4G+ LTE network in the coming weeks. C Spire will offer the new iPads with a range of... Read more
Belkin Announces Full Line of Keyboards and C...
Belkin International has unveiled a new lineup of keyboard cases and accessories for Apple’s newest iPads, featuring three QODE keyboards and a collection of thin, lightweight folios for both the... Read more
Verizon offers new iPad Air 2 preorders for $...
Verizon Wireless is accepting preorders for the new iPad Air 2, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB iPad Air 2 WiFi... Read more
Price drops on refurbished Mac minis, now ava...
The Apple Store has dropped prices on Apple Certified Refurbished previous-generation Mac minis, with models now available starting at $419. Apple’s one-year warranty is included with each mini, and... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2014 MacBook Airs available for up to $180 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
Refurbished 2013 MacBook Pros available for u...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available starting at $929. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros (4GB RAM/... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** At the Apple Store, you connect business professionals and entrepreneurs with the tools they need in order to put Apple solutions to work in their Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** As businesses discover the power of Apple computers and mobile devices, it's your job - as a Solutions Engineer - to show them how to introduce these Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.