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

Minecraft 795 - Popular sandbox building...
Minecraft allows players to build constructions out of textured cubes in a 3D procedurally generated world. Other activities in the game include exploration, gathering resources, crafting, and combat... Read more
djay Pro 3.0.5 - Transform your Mac into...
djay Pro provides a complete toolkit for performing DJs. Its unique modern interface is built around a sophisticated integration with iTunes and Spotify, giving you instant access to millions of... Read more
Unicorn HTTPS 1.5.54 - Change DNS quickl...
Unicorn HTTPS can change DNS quickly and easily. Every function is served free of charge, no advertisement. Your personal information is never collected by us. Please use it with confidence. Faster... Read more
MarsEdit 4.4.11 - Quick and convenient b...
MarsEdit is a blog editor for OS X that makes editing your blog like writing email, with spell-checking, drafts, multiple windows, and even AppleScript support. It works with with most blog services... Read more
Printopia 3.0.16 - Share Mac printers wi...
Run Printopia on your Mac to share its printers to any capable iPhone, iPad, or iPod Touch. Printopia will also add virtual printers, allowing you to save print-outs to your Mac and send to apps.... Read more
beaTunes 5.2.19 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
Navicat Premium Essentials 15.0.25 - Pro...
Navicat Premium Essentials is a compact version of Navicat which provides basic and necessary features you will need to perform simple administration on a database. It supports the latest features... Read more
Apple Pages 10.3.9 - Apple's word p...
Apple Pages is a powerful word processor that gives you everything you need to create documents that look beautiful. And read beautifully. It lets you work seamlessly between Mac and iOS devices, and... Read more
Numbers 10.3.9 - Apple's spreadshee...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
Suitcase Fusion 21.2.2 - Font management...
Suitcase Fusion is the creative professional's font manager. Every professional font manager should deliver the basics: spectacular previews, powerful search tools, and efficient font organization.... Read more

Latest Forum Discussions

See All

Super JetPak DX’s physical preorders sti...
The physical cartridge edition of Pocket Pixel Design’s Super JetPak DX is still available to preorder and will be until 31st January, with the game launching later this year on the Nintendo Game Boy. [Read more] | Read more »
Honkai Impact 3rd has revealed more deta...
Honkai Impact 3rd has now announced more details about its upcoming crossover with Neon Genesis Evangelion. This is set to arrive next week on January 22nd and will introduce an exclusive story, battlesuit and weapon to the popular action-RPG. [... | Read more »
Space Frog Intern, James Bolton's a...
James Bolton's arcade shooter Space Frog Intern is now available for Android devices following its release on iOS last year. It sees players taking control of the titular amphibian and blasting their way through various space beasties. [Read more... | Read more »
The 5 Best Mobile Ports
Ports or coversions of games from one platform to another can be quite tricky. This is especially true when porting games to phones and tablets, as these titles have to be designed with workable touch controls and account for smaller screen sizes... | Read more »
Erica, the PS4-exclusive FMV thriller, c...
London-based studio Flavourworks is bringing its FMV game Erica to iOS on Friday as a free trial, with a full release presumably following later. This is the second platform the game has launched on after its original release on PlayStation 4 two... | Read more »
Cute simulation game Dinosaur Park: Prim...
Dinosaur Park: Primeval Zoo is a cute zoo simulation game from upjers, and it sounds perfect for anyone who’s a dinosaur fan. It’s coming to Android in February, and is available right now for pre-registration. [Read more] | Read more »
Genshin Impact - Lost Riches Guide
| Read more »
Figment: Journey into the Mind, the surr...
Following its release on iOS devices last year, Bedtime Digital Games' surreal action-puzzler Figment: Journey into the mind will be heading for Android next Thursday, January 14th. If you're unfamiliar, it follows Dusty and his pal Piper as they... | Read more »
Skylanders Ring of Heroes' latest u...
Following the various game-changing updates made to Skylanders Ring of Heroes last year, the latest update to Activision and Com2uS' team-based RPG has introduced a new battle mode and they will celebrate its arrival with various in-game events... | Read more »
Distract Yourself With These Great Mobil...
There’s a lot going on right now, and I don’t really feel like trying to write some kind of pithy intro for it. All I’ll say is lots of people have been coming together and helping each other in small ways, and I’m choosing to focus on that as I... | Read more »

Price Scanner via MacPrices.net

At only $809, these are the cheapest MacBooks...
Apple has restocked at full line of Certified Refurbished 2020 13″ Intel-based MacBook Airs available starting at only $809 and up to $280 off original MSRP. Each MacBook features a new outer case,... Read more
Find the best price on an Apple iPhone MagSaf...
Looking for an Apple MagSafe Charger for your new iPhone 12, or perhaps an Apple MagSafe Duo Charger for your new iPhone and Apple Watch? Check out our new MagSafe Charger Price Tracker. We scan the... Read more
Save $67 on 13″ M1 MacBook Pros at Expercom,...
Apple reseller Expercom has 2020 13″ M1 MacBook Pros on sale for $67 off Apple’s MSRP with prices starting at $1232. In addition to their MacBook Pro sale prices, take $40 off AppleCare+ when... Read more
Back in stock! 16″ MacBook Pros starting at o...
After a long absence, Apple has restocked a full line of Certified Refurbished 16″ MacBook Pros for up to $420 off the cost of new models, starting at $2039. Each model features a new outer case,... Read more
Saturday Steal! Clearance 2020 Mac mini for o...
Other World Computing has clearance 2020 Intel-based 4-core Mac minis on sale for only $549 this weekend, $250 off Apple’s original MSRP. These are new, unopened, factory-sealed models: – 3.6GHz 4-... Read more
Save up to $112 on 13″ Intel-based MacBook Pr...
Apple reseller Expercom has 2020 13″ 2.0GHz Intel-based MacBook Pros on sale for $100-$112 off Apple’s MSRP with prices starting at $1699. In addition to their MacBook Pro sale prices, take $70 off... Read more
New sale at B&H: Apple’s hot new 13″ M1 M...
Apple’s new 2020 13″ MacBook Pros with M1 Apple Silicon CPUs are on sale at B&H Photo today for $50-$100 off MSRP, starting at $1239. Free expedited shipping is available for most addresses in... Read more
New at US Cellular: Your choice of free iPhon...
US Cellular has the 64GB Apple iPhone 12, 64GB iPhone 12 mini, and 64GB iPhone SE each available for free for new customers signing up for an Unlimited data plan. Cost of the phone is spread over a... Read more
Verizon offers $30 discount on Apple AirPods...
Verizon has Apple AirPods Pro on sale for $219.99 on their online store through January 22, 2021. Their price is $30 off Apple’s MSRP, and it’s among the lowest prices currently available for AirPods... Read more
Apple has clearance 2020 13″ 1.4GHz Intel-bas...
Apple has clearance, Certified Refurbished, 2020 13″ 1.4GHz 4-Core Intel-based MacBook Pros available starting at $1059 and up to $270 off original MSRP. These are the cheapest MacBook Pros for sale... Read more

Jobs Board

*Apple* Administrator - Freedom Mortgage (Un...
Apple Administrator + Job ID:8595 + Functional Area:Information Technology + Employment Type:Full Time + Location:Moorestown, NJ + Department:IT Conferencing & AV + Read more
Systems Architect, *Apple* Production Engin...
…package beginning on your first day? If so, we hope you'll keep reading! The Apple Sales Engineering and account team is looking for a stellar presales engineer with Read more
*Apple* /Mac Support Engineer - BRMi (United...
**Overview** BRMi Technology is currently seeking an Apple /Mac Support Engineer for a large client. The support engineer will research, evaluate, design, implement, Read more
Security Officer - Temporary - *Apple* Stor...
**Security Officer \- Temporary \- Apple Store** **Description** Summary The Security Officer provides services for a variety of large and small business clients Read more
Transition Into Practice (TIP) - April 2021-R...
…Academy-Transition into Practice (TIP) Residency program at **St Mary Medical Center in Apple Valley, CA.** **We are seeking Registered Nurses who are:** + New Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.