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

MacPilot 15.0.2 - $15.96 (53% off)
MacPilot gives you the power of UNIX and the simplicity of Macintosh, which means a phenomenal amount of untapped power in your hands! Use MacPilot to unlock over 1,200 features, and access them all... Read more
Visual Studio Code 1.85.0 - Cross-platfo...
Visual Studio Code provides developers with a new choice of developer tool that combines the simplicity and streamlined experience of a code editor with the best of what developers need for their... Read more
Spotify 1.2.26.1187 - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Transmission 4.0.5 - Popular BitTorrent...
Transmission is a fast, easy, and free multi-platform BitTorrent client. Transmission sets initial preferences so things "just work", while advanced features like watch directories, bad peer blocking... Read more
Fantastical 3.8.9 - Create calendar even...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event details... Read more
Notion 3.0.0 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks Release notes were unavailable when this listing was updated. Download Now]]> Read more
GarageBand 10.4.10 - Complete recording...
GarageBand is the easiest way to create a great-sounding song on your Mac. Add realistic, impeccably produced and performed drum grooves to your song with Drummer. Easily shape the sound of any... Read more
Pacifist 4.1.0 - Install individual file...
Pacifist opens up .pkg installer packages, .dmg disk images, .zip, .tar. tar.gz, .tar.bz2, .pax, and .xar archives and more, and lets you extract or install individual files out of them. This is... Read more
Xcode 15.0.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
Google Chrome 120.0.6099.62 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more

Latest Forum Discussions

See All

TouchArcade Game of the Week: ‘Sonic Dre...
I can still remember the time I played my first 3D Sonic game. It was at Hollywood Video (that’s a video rental store for you young ones out there) and my buddy was the manager, and he invited me and my friend to hang out in the store after they... | Read more »
SwitchArcade Round-Up: Strictly Limited...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 8th, 2023. In today’s article, we start off with a couple of news items. Nothing from The Game Awards, that’s a bit beyond the scope of what I usually do here. But I do have... | Read more »
Football Manager 2024 Interview – We Tal...
Last month, SEGA and Sports Interactive released Football Manager 2024 on Apple Arcade (Touch), Netflix (Mobile), consoles, PC, and even Game Pass. If you missed my detailed review covering many versions of the game, read it here. | Read more »
‘Shiren the Wanderer: The Mystery Dungeo...
Recently, my son and I were invited to attend a special hands-on preview event at Spike Chunsoft’s headquarters in Tokyo to play the upcoming Shiren the Wanderer: The Mystery Dungeon of Serpentcoil Island for Nintendo Switch, which is scheduled for... | Read more »
Apple Arcade Weekly Round-Up: Updates fo...
We just had a huge content drop on Apple Arcade earlier this week with Sonic Dream Team, Disney Dreamlight Valley, Puzzles and Dragons, and more hitting the service. Today (and as of a few days ago), many notable games on the service have gotten... | Read more »
‘Genshin Impact’ Version 4.3 Update “Ros...
Following two trailers during The Game Awards 2023, HoYoverse has more news today with the next major Genshin Impact (Free) update detailed for all platforms. | Read more »
Christmas comes to Pokemon Unite, closel...
It's time to swap your Pokeballs for snowballs as a new festive mode has launched in The Pokemon Company International’s 5v5 MOBA Pokemon Unite. The presents don't stop there, however, as a brand new challenger is entering the arena, all the way... | Read more »
What to expect in World of Tanks Blitz’s...
World of Tanks Blitz is updating that old story of Santa sneaking down your chimney and silently leaving presents like a jolly old ninja into something a little more modern. Vinnie Jones has traded the sleigh for a tank and is ringing in the... | Read more »
‘Arknights: Endfield’ From Gryphline Get...
Last year, Arknights developer Hypergryph announced Arknights: Endfield for mobile and PC platforms. Arknights: Endfield is a 3D real-time RPG with strategic elements set in the world of Arknights. | Read more »
‘Zenless Zone Zero’ TGA 2023 Trailer Con...
During The Game Awards 2023, HoYoverse had two trailers. The first was a quick recap video for Honkai Star Rail with a tease of things to come next year. It continues to look superb. The highlight was urban fantasy action RPG Zenless Zone Zero... | Read more »

Price Scanner via MacPrices.net

Update: Apple Watch Series 9 models now $70 o...
Walmart has Apple Watch Series 9 models on Holiday sale for $70 off MSRP on their online store this weekend (that’s $20 cheaper than their earlier price). Sale prices available for online orders only... Read more
Apple’s AirTags 4-Pack is on Holiday sale for...
Apple retailers have 4-pack AirTags on sale this weekend for $19 off MSRP as part of their Holiday sales. These make a great stocking stuffer: (1): Amazon has Apple AirTags 4 Pack on sale for $79.99... Read more
Sunday Sale: $100 off every Apple iPad mini 6
Amazon is offering Apple’s 8.3″ iPad minis for $100 off MSRP, including free shipping, as part of their Holiday sale this weekend. Prices start at $399. Amazon’s prices are the lowest currently... Read more
16-inch M3 Pro MacBook Pros (18GB/512GB) are...
Looking for the best price on a 16″ M3 Pro MacBook Pro this Holiday shopping season? B&H and Amazon are currently offering a $250 discount on the 16″ M3 Pro MacBook Pro (18GB RAM/512GB SSD),... Read more
Apple Watch SE models on Holiday sale for $50...
Walmart has Apple Watch SE GPS-only models on Holiday sale on their online store for $50 off MSRP this weekend. Sale prices for online orders only, in-store prices may vary. Order online, and choose... Read more
Apple Watch Series 9 models on Holiday sale t...
Walmart has Apple Watch Series 9 models on Holiday sale for $50 off MSRP on their online store this weekend. Sale prices available for online orders only, in-store prices may vary. Order online, and... Read more
Apple has the 13-inch M2 MacBook Air in stock...
Apple has Certified Refurbished 13″ M2 MacBook Airs available starting at only $929 and ranging up to $210 off MSRP. These are the cheapest M2-powered MacBooks for sale at Apple. Apple’s one-year... Read more
Apple’s 10th-generation iPads on Holiday sale...
Amazon has Apple’s 10th-generation WiFi iPads on sale for $100 off MSRP, starting at only $349, as part of their Holiday sales this weekend. With the discount, Amazon’s prices are the lowest we’ve... Read more
Apple Watch Series 9 models Holiday sale this...
Amazon has Apple Watch Series 9 models on sale for up to $90 off MSRP, each including free shipping, as part of their Holiday sale this weekend. Stock is likely to come and go at Amazon, so check... Read more
Apple Watch Ultra 2 models on Holiday sale th...
Amazon is offering a $50 discount on Apple Watch Ultra 2 models as part of their Holiday sale this weekend. Their price is now $749 for most models. Shipping is free. Amazon’s price is the lowest... Read more

Jobs Board

Principal Offering Sales - Modern Workplace...
…Job Description **Who you are** + **Drives Modern Workplace sale, focusing on Apple Managed Services across the enterprise globally.** + **Owns the Apple Read more
Material Handler 1 - *Apple* (1st shift) -...
Material Handler 1 - Apple (1st shift)Apply now " Apply now + Start apply with LinkedIn + Apply Now Start + Please wait Date:Dec 8, 2023 Location: Irwindale, CA, US, Read more
Macintosh/ *Apple* Systems Administrator, TS...
…to a team-based environment. + Perform systems administration support tasks for Apple MacOS and iOS operating systems. + TDY travel (approximately 25%) for Read more
Principal Offering Sales - Modern Workplace...
…Job Description **Who you are** + **Drives Modern Workplace sale, focusing on Apple Managed Services across the enterprise globally.** + **Owns the Apple Read more
*Apple* Systems Administrator - JAMF - Activ...
…**Public Trust/Other Required:** None **Job Family:** Systems Administration **Skills:** Apple Platforms,Computer Servers,Jamf Pro **Experience:** 3 + years of Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.