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
```

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.

Community Search:
MacTech Search:

Microsoft Office 2016 16.11 - 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
Adobe Photoshop CC 2018 19.1.2 - Profess...
Photoshop CC 2018 is available as part of Adobe Creative Cloud for as little as \$19.99/month (or \$9.99/month if you're a previous Photoshop customer). Adobe Photoshop CC 2018, the industry standard... Read more
Adobe Dreamweaver CC 2018 18.1.0.10155 -...
Dreamweaver CC 2018 is available as part of Adobe Creative Cloud for as little as \$19.99/month (or \$9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2018 allows you to... Read more
Adobe Flash Player 29.0.0.113 - Plug-in...
Adobe Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating systems.... Read more
Drive Genius 5.2.0 - \$79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
MegaSeg 6.0.6 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
ffWorks 1.0.7 - Convert multimedia files...
ffWorks (was iFFmpeg), focused on simplicity, brings a fresh approach to the use of FFmpeg, allowing you to create ultra-high-quality movies without the need to write a single line of code on the... Read more
Dash 4.1.5 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Evernote 7.0.3 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
jAlbum Pro 15.3 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. You can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly... Read more

## Latest Forum Discussions

All the best games on sale for iPhone an...
It might not have been the greatest week for new releases on the App Store, but don't let that get you down, because there are some truly incredible games on sale for iPhone and iPad right now. Seriously, you could buy anything on this list and I... | Read more »
Everything You Need to Know About The Fo...
In just over a week, Epic Games has made a flurry of announcements. First, they revealed that Fortnite—their ultra-popular PUBG competitor—is coming to mobile. This was followed by brief sign-up period for interested beta testers before sending out... | Read more »
The best games that came out for iPhone...
It's not been the best week for games on the App Store. There are a few decent ones here and there, but nothing that's really going to make you throw down what you're doing and run to the nearest WiFi hotspot in order to download it. That's not to... | Read more »
Death Coming (Games)
Death Coming 1.1.1.536 Device: iOS Universal Category: Games Price: \$1.99, Version: 1.1.1.536 (iTunes) Description: --- Background Story ---You Died. Pure and simple, but death was not the end. You have become an agent of Death: a... | Read more »
Hints, tips, and tricks for Empires and...
Empires and Puzzles is a slick match-stuff RPG that mixes in a bunch of city-building aspects to keep things fresh. And it's currently the Game of the Day over on the App Store. So, if you're picking it up for the first time today, we thought it'd... | Read more »
What You Need to Know About Sam Barlow’s...
Sam Barlow’s follow up to Her Story is #WarGames, an interactive video series that reimagines the 1983 film WarGames in a more present day context. It’s not exactly a game, but it’s definitely still interesting. Here are the top things you should... | Read more »
Pixel Plex Guide - How to Build Better T...
Pixel Plex is the latest city builder that has come to the App Store, and it takes a pretty different tact than the ones that came before it. Instead of being in charge of your own city by yourself, you have to work together with other players to... | Read more »
Fortnite Will Be Better Than PUBG on Mob...
Before last week, if you asked me which game I prefer between Fortnite Battle Royale and PlayerUnknown’s Battlegrounds (PUBG), I’d choose the latter just about 100% of the time. Now that we know that both games are primed to hit our mobile screens... | Read more »
Siege of Dragonspear (Games)
Siege of Dragonspear 2.5.12 Device: iOS Universal Category: Games Price: \$9.99, Version: 2.5.12 (iTunes) Description: Experience the Siege of Dragonspear, an epic Baldur’s Gate tale, filled with with intrigue, magic, and monsters.... | Read more »
7 Wonders Guide - Should You Buy The Lea...
The fantastic mobile version of 7 Wonders just got updated with an expansion that adds Leaders to the game. This new content adds a whole layer of depth to the game, but before you spend \$1.99 to buy it blindly, check out this breakdown of exactly... | Read more »

## Price Scanner via MacPrices.net

B&H drops prices on 15″ MacBook Pros up t...
B&H Photo has dropped prices on new 2017 15″ MacBook Pros, now up to \$300 off MSRP and matching Adorama’s price drop yesterday. Shipping is free, and B&H charges sales tax for NY & NJ... Read more
Apple restocks Certified Refurbished 2017 13″...
Apple has restocked Certified Refurbished 2017 13″ 2.3GHz MacBook Pros for \$200-\$230 off MSRP. A standard Apple one-year warranty is included with each MacBook, models receive new outer cases, and... Read more
13″ Space Gray Touch Bar MacBook Pros on sale...
Adorama has new 2017 13″ Space Gray Touch Bar MacBook Pros on sale for \$150 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (... Read more
Best deal of the year on 15″ Apple MacBook Pr...
Adorama has New 2017 15″ MacBook Pros on sale for up to \$300 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): \$... Read more
Save \$100-\$150+ on 13″ Touch Bar MacBook Pros...
B&H Photo has 13″ Touch Bar MacBook Pros on sale for \$100-\$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 3.1GHz/256GB Space Gray MacBook Pro... Read more
Current deals on 27″ Apple iMacs, models up t...
B&H Photo has 27″ iMacs on sale for up to \$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): \$2149 \$150 off MSRP – 27″ 3... Read more
Thursday Deal: 13″ 2.3GHz MacBook Pro for \$11...
B&H Photo has the 13″ 2.3GHz/128GB Space Gray MacBook Pro on sale for \$100 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz/128GB Space... Read more
How to save \$100-\$190 on 10″ & 12″ iPad P...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for \$100-\$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
Silver 12″ 1.3GHz MacBook on sale at B&H...
B&H Photo has the 2017 12″ 1.3GHz Silver MacBook on sale for \$1399.99 including free shipping plus sales tax for NY & NJ residents only. Their price is \$200 off MSRP, and it’s the lowest... Read more
Amazon offers 21″ Apple iMacs for up to \$150...
Amazon 21″ iMacs on sale today for \$50-\$150 off MSRP, depending on the model. Shipping is free: – 21″ 3.4GHz 4K iMac (MNE02LL/A): \$1349.99 \$150 off MSRP – 21″ 3.0GHz iMac (MNDY2LL/A): \$1199 \$100 off... Read more

## Jobs Board

*Apple* Certified Technician - iStore by St....
Job Description iStore by St. Moritz is an Authorized Apple Service Provider and our Headquarters is an Apple Premier Partner as well as a Premium Service Read more
*Apple* Certified Technician - Taycom (Unite...
Job Description Apple Computer Support Technician Taycom – Dallas, TX and surrounding area. Note: This position requires senior level Apple technical support Read more
*Apple* Certified Macintosh Technician - Mac...
…qualified persons who have a deep passion, dedication, and experience with the Apple Macintosh and iOS computer platforms. MacMedics is seeking Apple Certified Read more
*Apple* Part Time Reseller Specialist - Appl...
…in a reseller store, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
*Apple* Genius - Technical Customer Service...
Job Description: Job Summary As a Genius at the Apple Store, you maintain customers' trust in Apple as the skilled technical customer service expert, Read more