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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Xcode 10.2.1 - Integrated development en...
Xcode includes everything developers need to create great applications for Mac, iPhone, iPad, and Apple Watch. Xcode provides developers a unified workflow for user interface design, coding, testing... Read more
OnyX 3.6.1 - Maintenance and optimizatio...
OnyX is a multifunction utility that you can use to verify the startup disk and the structure of its system files, to run miscellaneous maintenance and cleaning tasks, to configure parameters in the... Read more
MacFamilyTree 8.5.4 - Create and explore...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
Adobe Premiere Pro CC 2019 13.1.1 - Digi...
Premiere Pro CC 2019 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous Premiere Pro customer). Adobe Premiere Pro CC 2019 lets you edit... Read more
Safari Technology Preview 12.2 - The new...
Safari Technology Preview contains the most recent additions and improvements to WebKit and the latest advances in Safari web technologies. And once installed, you will receive notifications of... Read more
LibreOffice 6.2.3.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Opera 60.0.3255.56 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Microsoft Office 2016 16.16 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook, and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
BetterTouchTool 2.760 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Microsoft Office 365, 2019 16.24.1 - Pop...
Microsoft Office 365. The essentials to get it all done. Unmistakably Office, designed for Mac Get started quickly with new, modern versions of Word, Excel, PowerPoint, Outlook and OneNote-... Read more

Latest Forum Discussions

See All

Mobile games you probably haven't p...
The App Store is bursting at the seams with all kinds of apps and games of varying quality, but one of the most consistent issues with it is discoverability. Despite having what seems like unlimited money and a full App Store editorial team, Apple... | Read more »
AFK Arena guide - Tips and tricks for be...
AFK Arena may be a less intense form of a gacha game, but that doesn’t mean it’s totally straightforward. As with other games in this genre, there’s a bevy of systems, modes, currencies, etc. that you’ll want to be familiar with as soon as you... | Read more »
Spellsword Cards: Demontide guide - Tips...
Spellsword Cards: Demontide is a wonderful little single-player card game, but it can also be quite unforgiving. Parts of it definitely look and feel like Hearthstone, but you can’t just play this game like its your favorite collectible card game (... | Read more »
The best driving games on iOS
With the recent release of Rush Rally 3, it's easy to be excited about mobile driving games. Figuring out what games in this genre are worth picking up, on the other hand, is a whole other story. [Read more] | Read more »
Construction Simulator returns to Europe...
German publisher astragon Entertainment and developer weltenbauer. SE have just released the third installment of Construction Simulator. Unlike Construction Simulator 2, which was set in the U.S., Construction Simulator 3 returns to its roots in... | Read more »
The best superhero game on mobile
I don't know if you know this, but superheroes are Kind of A Big Deal. Every other week it feels like a new Marvel movie is coming out and the hype train for each release is undeniable. Just look at how the upcoming Avengers: Endgame broke sales... | Read more »
Globesweeper puts a 3D spin on the class...
Long before Minecraft came along to take the crown of 'most played' game, there was another goliath PC game with 'Mine' in its title which held that distinction - Minesweeper. Those with long memories of dial-up broadband and insanely heavy cathode... | Read more »
The stellar open-world skiing game, Gran...
Grand Mountain Adventure, a finalist at the Big Indie Awards 2018, has finally raced its way onto Android. The hugely impressive open-world skiing title hails from Swedish developer Toppluva, a studio made up of 3 snowboarding brothers. New... | Read more »
Onmyoji is celebrating its anniversary w...
NetEase has a deep well to dip into when it comes to sourcing new content for Onmyoji. The game is set during Japan’s Heian period, when elaborate folk tales of spirits – or shikigami – were fire-side favourites. In the world of Onmyoji, though,... | Read more »
The Elder Scrolls: Blades guide - How to...
Were you disappointed by The Elder Scrolls: Blades? You're not alone. It's a bad game that gives off one of the worst first impressions I've ever seen. [Read more] | Read more »

Price Scanner via MacPrices.net

Sprint offers 18 month Apple iPhone Xr leases...
Sprint has the new Apple 64GB iPhone Xr available for $15 per month for 18 months for new lines of service. That’s about 50% off the typical monthly rate for this phone. The fine print: “$15/mo.... Read more
These 2018 MacBook Pros at Apple, Certified R...
In the market for a 2018 15″ or 13″ MacBook Pro and looking for the lowest prices you can find? Apple’s refurbished prices are the lowest available for each model from any reseller. An standard Apple... Read more
Save $50-$74 on a new Mac mini today at Abt E...
Abt Electronics has the new 2018 4-Core and 6-Core Mac minis on sale for $50-$74 off Apple’s MSRP, with prices starting at $749. Shipping is free: – 3.6GHz Quad-Core mini: $749 $50 off MSRP – 3.0GHz... Read more
Deal Alert! Amazon is selling the 13″ 2.3GHz/...
Amazon has the 13″ 2.3GHz/256GB Dual-Core non-Touch Bar Space Gray MacBook Pro on sale for $500 off Apple’s MSRP today, only $999. Their price is the cheapest available for this model from any Apple... Read more
Amazon and Walmart have 9.7″ iPads on sale fo...
Amazon is offering new 9.7″ iPads with Apple Pencil Support for $50-$75 off MSRP today, with prices starting at only $249. These are the same iPads found in Apple’s retail and online stores: – 9.7″... Read more
Apple has refurbished quad-core and 6-core 20...
Apple has restocked Certified Refurbished 2018 Mac minis on their online store for $120-$170 off the cost of new models. Each mini comes with a new outer case plus a standard Apple one-year warranty... Read more
Key Features To Expect From Forthcoming Relea...
NEWS: 04.17.19- Details regarding a handful of key features from the forthcoming release of iOS 13, the next major version of the world’s most advanced mobile operating system designed in California... Read more
Deal Alert! 12″ 1.3GHz Gold MacBook on sale f...
B&H Photo has the 2017 12″ 1.3GHz Gold MacBook on sale today for $1049 including free shipping. Their price is $550 off Apple’s MSRP, and it’s currently the lowest price available for a Gold 1.... Read more
Amazon continues to offer sale prices on 11″...
Amazon has the new 2018 Apple 11″ iPad Pros in stock today and on sale for up to $200 off Apple’s MSRP. These are the same iPad Pros sold by Apple in its retail and online stores. Shipping is free... Read more
Amazon has 12″ iPad Pros on sale today for up...
Amazon has new 2018 12.9″ iPad Pros on sale for up to $200 off Apple’s MSRP for a limited time. These are the same iPad Pros sold by Apple in their retail and online stores. Be sure to choose Amazon... Read more

Jobs Board

Student Employment - *Apple* Campus Rep - S...
The people here at Apple don't just create products - they create the kind of wonder that's revolutionized entire industries. It's the diversity of those people and Read more
Sr. Software Engineer ( *Apple* Core Platfor...
We are looking for an iOS/tvOS engineer to join our Apple and Android Frameworks & Tooling team. This is an opportunity to help build frameworks and SDKs for the Read more
*Apple* /MAC Support Technician - AECOM (Unit...
…DC, Washington, DC **Job Summary** AECOM has an immediate opportunity for an Apple Support Engineer to support a government agency's capabilities in Washington, DC Read more
Best Buy *Apple* Computing Master - Best Bu...
**687175BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Location Number:** 001761-Park City-Store **Job Description:** The Read more
Best Buy *Apple* Computing Master - Best Bu...
**687108BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000309-Merrillville-Store **Job Description:** **What does a Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.