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

Skype 8.71.0.45 - Voice-over-internet ph...
Skype is a telecommunications app that provides HD video calls, instant messaging, calling to any phone number or landline, and Skype for Business for productive cooperation on the projects. This... Read more
A Better Finder Attributes 7.11 - Change...
A Better Finder Attributes allows you to change JPEG & RAW shooting dates, JPEG EXIF meta-data tags, file creation & modification dates, file flags and deal with invisible files. Correct EXIF... Read more
VirtualBox 6.1.20 - x86 virtualization s...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
MySQL 8.0.24 - Industry-leading open-sou...
MySQL, the industry-leading open-source SQL database, is an accessible, easy-to-use relational database management system (RDBMS). As an alternative to Oracle and SQL server, MySQL offers features... Read more
Arq 7.5.1 - Online backup to Google Driv...
Arq is super-easy online backup for Mac and Windows computers. Back up to your own cloud account (Amazon Cloud Drive, Google Drive, Dropbox, OneDrive, Google Cloud Storage, any S3-compatible server... Read more
The Unarchiver 4.3.0 - Replacement for t...
The Unarchiver is a much more capable replacement for "Archive Utility.app", the built-in archive unpacker program in OS X. The Unarchiver is designed to handle many more formats than Archive Utility... Read more
Live Home 3D Pro 4.0 - $49.99
Live Home 3D Pro is powerful yet intuitive home design software that lets you build the house of your dreams right on your Mac, iPhone or iPad. It has every feature of Live Home 3D, plus some... Read more
Adobe InDesign 16.2 - Professional print...
InDesign is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous InDesign customer). Adobe InDesign is part of Creative Cloud. That means you... Read more
Microsoft Remote Desktop 10.6.1 - Connec...
Microsoft Remote Desktop for Mac is an application that allows connecting to virtual apps or another PC remotely. Discover the power of Windows with Remote Desktop designed to help you manage your... Read more
File Juicer 4.94 - Extract images, video...
File Juicer is a drag-and-drop can opener and data archaeologist. Its specialty is to find and extract images, video, audio, or text from files which are hard to open in other ways. In computer... Read more

Latest Forum Discussions

See All

Apex Legends Mobile begins Android close...
Electronic Arts has announced that it is moving forward with some closed beta tests of the upcoming Apex Legends Mobile in selected regions. [Read more] | Read more »
Call of Duty Mobile Season 3 goes live w...
Activision has released a new seasonal update for its mobile shooter Call of Duty Mobile, which is now live across iOS and Android devices after being teased last week. [Read more] | Read more »
Pokemon Masters EX's latest update...
Two new Sync Pairs have made their way into Pokemon Masters today. Both pairs hail from the Alola region, Elio & Popplio and Selene & Rowlet. Their arrival coincides with an event called Trials on the Isle. [Read more] | Read more »
Shrouded Citadel: navigate your escape i...
Having been cooped up over the past 12 months due to winter and covid, Pifer is encouraging gamers to start enjoying the great outdoors again with its recently launched AR adventure epic, Shrouded Citadel. | Read more »
Moonlight Sculptor is an upcoming MMORPG...
Kakao Games and XL Games – who you might be familiar with from their previous game ArcheAge – have announced that their MMORPG Moonlight Sculptor is now available to pre-order for iOS and Android devices. Moonlight Sculptor has previously launched... | Read more »
MU Archangel is now open for pre-registr...
MU Archangel is now open for pre-registration in Southeast Asia following its massive success in other territories. Players from Singapore, Thailand, Malaysia, Indonesia, and the Philippines (except Vietnam) can now join in on the fun by applying... | Read more »
Compete, a new social media app you can...
Whoever told you you can’t get rich making videos has obviously never heard of Compete, Competitive Media Technologies Limited’s hot new social media app where you can rake in all the dough just by doing what you love. Video monetization that... | Read more »
Bethesda has released a new DOOM mobile...
Bethesda Softworks has released a new DOOM game out of the blue exclusively for mobile devices. It’s called Mighty DOOM and is currently only available as an early access title on Android but will be expanding to more users in the future. [Read... | Read more »
Anagraphs is a word puzzle game with a t...
Cinq-Mars Media has released its word puzzle game Anagraphs for iOS and Android devices. The game released last week after a short delay in getting it onto the appropriate platforms. [Read more] | Read more »
These are the top 5 best iPhone games li...
Fortnite has been the big hitter in mobile gaming this year, and it's not hard to see why. Thanks to some excellent marketing, and a polished experience that almost anyone can enjoy, it's really taken the App Store by storm. But there are other... | Read more »

Price Scanner via MacPrices.net

Expercom to offer preorder discounts on new M...
Apple reseller Expercom will be offering preorder discounts on the new M1 iPad Pros ranging up to $147 off Apple’s MSRP. Their prices are the lowest we’ve seen so far on these new iPads. Ordering... Read more
New sale: 13″ 2.0GHz Intel-based MacBook Pros...
Amazon has 2020 13″ MacBook Pros with 10th generation Intel CPUs on sale for $200-$300 off Apple’s MSRP today. Shipping is free. Be sure to purchase the MacBook Pro from Amazon, rather than a third-... Read more
Apple is blowing out clearance 2020 13″ Intel...
In addition to refurbished 13″ M1 MacBook Pros starting at $1099, Apple has dropped prices on Certified Refurbished 2020 13″ 1.4GHz 4-Core Intel-based MacBook Pros with models now available starting... Read more
New at Apple: Buy any iPad with WiFi + Cellul...
Apple has a new, and rate, offer for cellular iPad users. Buy any new iPad with WiFi + Cellular at Apple, and get up to $200 back with carrier activation via AT&T, T-Mobile/Sprint, or Verizon.... Read more
Apple drops prices on clearance, Certified Re...
Apple has dropped prices on clearance, Certified Refurbished, 2020 13″ Intel-based MacBook Airs with models now available starting at only $719 and up to $370 off original MSRP. Each MacBook features... Read more
Apple introduces new iPad Pro with M1 Apple C...
Apple today introduced a new iPad Pro with Apple’s M1 Apple CPU. Main features include: – M1 CPU – 8-Core CPU – 50% faster performance, 75X faster than original iPad Pro – 8-Core GPU with 40% faster... Read more
Apple introduces new 24″ M1 iMac in multiple...
Apple today introduced the new 2021 24″ M1 iMac. The new iMac features a single sheet of glass with a small chin, seven different colors, aluminum stand, thin bezels, and Apple’s M1 processor. The... Read more
Apple updates 4K Apple TV
Apple today updated the 4K Apple TV with a new siri remote, better color balance, and better high fidelity. Sold for $179 32GB or $199 for 64GB, the updated models will be available in the second... Read more
Apple introduces AirTags to work with their F...
Apple today introduced AirTags, a $29 accessory available starting 4/30/21 to work with Apple’s FindMy network to find your stuff. A 4-pack with sell for $99. AirTags work especially well with... Read more
Is Apple Looking To Its Past For Inspiration...
FEATURE: 04.20.21 – Apple seems to be getting a bit nostalgic over the Mac when it comes to updating its design… back to the late 1990s and early 2000s to be exact. The first Apple Event of 2021 —... Read more

Jobs Board

Mobile Device Auditor ( *Apple* ) - Aerotek (...
…and labeled based on size, shape, and model. **Skills:** Computer repair, Apple , iPhone, software, OS, Downlaod, Data Wipe, Repair, Repair techniques, Computer Read more
Support Technician II - A+, *Apple* - Compu...
…job skills and company policies and procedures to complete assigned tasks pertaining to Apple or PC hardware, software, and Apple / Microsoft operating systems + Read more
Geek Squad *Apple* Consultation Professiona...
**801884BR** **Job Title:** Geek Squad Apple Consultation Professional **Job Category:** Store Associates **Store Number or Department:** 001468-West Simsbury-Store Read more
*Apple* / Macintosh / ADM Systems Administra...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
*Apple* Computing Specialist - Best Buy (Uni...
**800413BR** **Job Title:** Apple Computing Specialist **Job Category:** Store Associates **Store Number or Department:** 000416-East Lansing-Store **Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.