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

Maintenance 2.9.9 - System maintenance u...
Maintenance is a system maintenance and cleaning utility. It allows you to run miscellaneous tasks of system maintenance: Check the the structure of the disk Repair permissions Run periodic scripts... Read more
Deeper 2.8.8 - Enable hidden features in...
Deeper is a personalization utility for macOS which allows you to enable and disable the hidden functions of the Finder, Dock, QuickTime, Safari, iTunes, login window, Spotlight, and many of Apple's... Read more
BetterTouchTool 3.9998 - 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
OnyX 4.3.6 - 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
Acorn 7.3.2 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Google Chrome 109.0.5414.119 - Modern an...
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
ASPPPPP 1.3.99999999999 - Create cursor...
ASPPPPP brings Aperture Science's portal technology to your desktop. Avoid carpal canal syndrome and save millions of pixels of cursor moving. When launching the app, you first set the position of... Read more
beaTunes 5.2.31 - 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
FotoMagico 6.3.3 - Powerful slideshow cr...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
RoboForm 9.4.1 - Password manager; syncs...
RoboForm is a password manager that offers one-click login, mobile syncing, easy form filling, and reliable security. Password Manager. RoboForm remembers your passwords so you don't have to! Just... Read more

Latest Forum Discussions

See All

Rec Room will be playing host to major a...
It has been a good time for gaming and music lovers lately with names like Blackpink and Man with a Mission popping up in various mobile games, and now Rec room wants to get involved in a big way, striking a deal to bring Republic Records artists... | Read more »
‘Railbound’ Massive 2.0 Update To Bring...
Railbound from Afterburn Games is set to get a massive update this week. Since its launch, Railbound has gotten a good amount of support already. Read about the most recent big update here. Afterburn Games will bring Railbound 2.0 to mobile and PC... | Read more »
TouchArcade Game of the Week: ‘Madness/E...
Sometimes a game comes along that feels so purely built for mobile, and its controls and mechanics come together so well on the touchscreen, I say that Apple should just pre-install it on every iPhone it sells. I very much feel that way about... | Read more »
SwitchArcade Round-Up: ‘ATONE’, ‘Dance o...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for January 27th, 2023. In today’s article, we mop up the remaining releases of the week. There are quite a few, thanks to some slipping out after I went home last night. There are... | Read more »
‘Prehistoric Isle 2 ACA NEOGEO’ Review –...
It’s somewhat surprising how clearly one can draw a line between SNK before NEOGEO’s launch and after. The likes of Psycho Soldier and Ikari were relegated to cameo appearances, and only a few lucky pre-NEOGEO IPs ever saw follow-ups on the multi-... | Read more »
Old School RuneScape announces landmark...
Jagex has announced some groundbreaking news for fans of its iconic MMORPG, Old School RuneScape. For the first time in the game's 15-year history, the player base has voted in favour of the implementation of a new skill to the retro masterpiece... | Read more »
Physics Puzzler ‘Squiggle Drop’ From Noo...
Noodlecake’s Squiggle Drop () featuring more than 100 puzzles is the final new Apple Arcade release of January 2023. When Apple revealed the games for the month, I was very curious to see how Squiggle Drop would turn out. It seemed like a game I’d... | Read more »
‘Of Two Minds’, a Psychoanalytical FMV G...
We are truly in the renaissance of full-motion video games since the genre first arrived in the late ’80s and early ’90s before dying an ugly death due to the poor quality of those gaming experiences as well as the poor quality of the actual video... | Read more »
SwitchArcade Round-Up: ‘Goldeneye’ Comin...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for January 26th, 2023. The big news is that Goldeneye for Nintendo Switch Online finally has a release date, and it’s soon as it could be. We have a ton of new releases to go through... | Read more »
Previously Cancelled Co-Op City Builder...
Back in August of 2021 developer Supercell formally announced Everdale to the world, a cooperative city building game that had already been in a smaller form of beta testing under a different name for at least a year prior. That announcement kicked... | Read more »

Price Scanner via MacPrices.net

Apple to release new iPad with carbon fiber k...
According to analyst Ming-Chi Kuo, a new Apple iPad will be the beneficiary of all-new technology featuring a kickstand and folding OLED screen. There will be no new iPads released in the next nine... Read more
New sale: Apple 10.9″ iPad Airs for $100 off...
Amazon has 10.9″ M1 WiFi iPad Airs on sale for $100 off Apple’s MSRP, with prices starting at $499, for a limited time. Their prices are the lowest available among the Apple retailers we track: – 10.... Read more
Apple may release high-end Reality Pro device...
Mark Gurman, in this weeks’s Power On newsletter, states that Apple may attempt to release a high-end, nearly $3000, Reality Pro device in an attempt to move the VR market forward. With potential... Read more
13″ M2 MacBook Pros available today at Apple...
Apple standard-configuration 13″ MacBook Pros with M2 CPUs in stock and available today starting at $1169, Certified Refurbished, and ranging up to $150 off original MSRP. These are the cheapest 13″... Read more
Get a 13″ M2 MacBook Air at Apple today for a...
Apple has standard-configuration 13″ M2 MacBook Airs in stock and on sale starting at only $1079, Certified Refurbished, and ranging up to $150 off MSRP. These are the cheapest M2-powered MacBooks... Read more
Apple Card special offers for January and Feb...
Apple Card is offering special offers for January & February, 2023 which include a $75 Daily Cash offer for customers who open a new Apple Card through February and a $55 Daily Cash offer for new... Read more
New low price: Clearance 14″ M1 Pro MacBook P...
B&H Photo has dropped prices on Apple’s previous-generation 14″ 8-Core M1 Pro MacBook Pros by $300 off original MSRP, now only $1699. Free 1-2 day shipping is available to most US addresses: – 14... Read more
Apple has clearance 27-inch 5K iMacs in stock...
Apple has a full line of Certified Refurbished 2020 27″ 5K iMacs available starting at only $1169 and ranging up to $810 off original MSRP. Apple’s one-year warranty is standard, shipping is free,... Read more
Price drop! Apple has M1 Mac mini in stock fo...
Apple has dropped prices on clearance M1-powered Mac minis in their Certified Refurbished section to a new low starting price of only $469. Each mini comes with Apple’s one-year warranty, and... Read more
The Latest Rumors and Potential Features of a...
The rumors are flying and speculation is running rampant around the possibility of a new Apple iMac Pro. It is expected to be a powerful computer in Apple’s lineup, and people are already asking what... Read more

Jobs Board

Wireless Device Portfolio Manager - *Apple*...
…in our Retail Wireless journey. The successful Device Portfolio Manager - Apple will work cross-functionally to develop, oversee and execute a device roadmap Read more
Bilingual Level 1 *Apple* Support Specialis...
…generous employee benefits! Our client is currently seeking a qualified Bilingual Level 1 Apple Support Specialist to join their team. This role can be hybrid / Read more
Security Officer - *Apple* Store - NANA Reg...
…security is our \#1 priority\. This is a public environment at the Apple Store and surrounding areas with the corresponding levels of traffic \(employees, visitors, Read more
Device Portfolio Manager - *Apple* - DISH (...
…in our Retail Wireless journey. The successful Device Portfolio Manager - Apple will work cross-functionally to develop, oversee and execute a device roadmap Read more
Senior STE / *Apple* / OTT / Streaming Serv...
…and perform tests to validate large-scale content operations and releases. As an Apple STE, you'll partner with the content and streaming teams to ensure smooth Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.