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

Luminar 1.0.2 - Powerful, adaptive, conf...
Luminar is the new full-featured image editor that adapts to the way you edit photos. Over 300 essential tools to fix, edit, and enhance your photos with comfort. The future of photo editing is here... Read more
WhatRoute 2.0.10 - Geographically trace...
WhatRoute is designed to find the names of all the routers an IP packet passes through on its way from your Mac to a destination host. It also measures the round-trip time from your Mac to the router... Read more
Slack 2.3.3 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 2.3.3: Fixed window zoom jumping back-and-forth OS X 10.9... Read more
Lens Blur 1.4.3 - True out-of-focus boke...
Lens Blur transforms your existing photo into true SLR-quality out-of-focus bokeh effect! Everyone needs a gorgeous personalized background for a social profile, blog, Web/UI design, presentation, or... Read more
CleanMyMac 3.6.0 - $39.95
CleanMyMac makes space for the things you love. Sporting a range of ingenious new features, CleanMyMac lets you safely and intelligently scan and clean your entire system, delete large, unused files... Read more
DEVONthink Pro 2.9.8 - Knowledge base, i...
DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research papers, your life often fills your hard drive in the... Read more
MacFamilyTree 8.1 - Create and explore y...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
HoudahSpot 4.2.7 - Advanced file-search...
HoudahSpot is a powerful file search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the way... Read more
TunnelBear 3.0.7 - Subscription-based pr...
TunnelBear is a subscription-based virtual private network (VPN) service and companion app, enabling you to browse the internet privately and securely. Features Browse privately - Secure your data... Read more
Garmin Express 4.5.0.0 - Manage your Gar...
Garmin Express is your essential tool for managing your Garmin devices. Update maps, golf courses and device software. You can even register your device. Update maps Update software Register your... Read more

Latest Forum Discussions

See All

Amateur Surgeon 4 Guide: Become the worl...
It's time to wield your trusty pizza cutter again, as Amateur Surgeon has returned with a whole fresh set of challenges (and some old, familiar ones, too). Starting anew isn't easy, especially when all you have at your disposal is a lighter, the... | Read more »
Le Parker: Sous Chef Extraordinaire (Ga...
Le Parker: Sous Chef Extraordinaire 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Telltale Games really is working on a Gu...
Telltale Games' next episodic adventure is indeed Guardians of the Galaxy. A document tied to the voice actors strike suggested that the project was in the work, but now we have direct confirmation following an announcement at the Game Awards that... | Read more »
Amateur Surgeon returns to iOS and Andro...
Amateur Surgeon and its two sequels disappeared from the App Store some time and it was sad days for all. But now, just in time for the holidays, the Adult Swim favorite makes its joyous return in the shape of Amateur Surgeon 4, a remake with... | Read more »
The best board games on mobile
Sometimes you need to ditch all of the high speed, high action games in favor of something a little more traditional. If you don't feel like parting ways from your mobile device, though, there are still plenty of ways to get that old-school fix.... | Read more »
The best Facebook Messenger Instant Game...
Facebook's new Instant Games is now here, meaning you can play games with your friends directly via Facebook. It's a fun new way to connect with friends, of course, but it's also proving to be a solid gaming experience in its own right, with a... | Read more »
You can now play game's on Facebook...
Facebook launched its new Instant Games platform in an exciting new attempt to engage its user base. As a result, you can now play a number of different games directly through Facebook Messenger. All of these games run with HTML5, meaning you play... | Read more »
Apollo Justice Ace Attorney (Games)
Apollo Justice Ace Attorney 1.00.00 Device: iOS Universal Category: Games Price: $.99, Version: 1.00.00 (iTunes) Description: Court Is Back In Session Star as rookie defense attorney, Apollo Justice, as he visits crime scenes,... | Read more »
KORG iWAVESTATION (Music)
KORG iWAVESTATION 1.0 Device: iOS Universal Category: Music Price: $19.99, Version: 1.0 (iTunes) Description: A revolutionary new world of sound.The Wave Sequence Synthesizer for iPad - KORG iWAVESTATION | Read more »
Don't Grind Guide: Tips for becomin...
Don’t Grind is a surprising, derpy little one touch game with fun hand-drawn graphics. The goal is simple -- get the high score without being chopped to bits. That can be tough when you’re not used to the game, and that’s compounded by the fact... | Read more »

Price Scanner via MacPrices.net

Parallels Toolbox 1.3 for Mac Offers 25 Singl...
Parallels has launched Parallels Toolbox 1.3 for Mac, an upgrade that adds five new utilities to the stand-alone application which was released in August and is available exclusively online at http... Read more
OWC Mercury Elite Pro Dual mini Ultra-Portabl...
OWC has introduced the new OWC Mercury Elite Pro Dual mini, a powerful yet ultra-portable dual-drive RAID solution. The new Mercury Elite Pro Dual mini packs phenomenal performance into a small... Read more
Clearance 13-inch Retina MacBook Pros availab...
B&H Photo has clearance 2015 13″ Retina Apple MacBook Pros available for up to $200 off original MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $... Read more
Roundup of 2016 13-inch 2.0GHz MacBook Pro sa...
B&H has the non-Touch Bar 13″ MacBook Pros in stock today for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro Space Gray (MLL42LL/A): $1449 $... Read more
New 13-inch 2.0GHz Space Gray MacBook Pro in...
Adorama has the new 13″ 2.0GHz Space Gray MacBook Pro (non-Touch Bar, MLL42LL/A) in stock for $1499 including a free 3-year AppleCare Protection Plan. Shipping is free, and Adorama charges sales tax... Read more
Finnair Adopts iOS Enterprise iPad Apps from...
Finnair and IBM have announced a first-of-its-kind agreement to utilize iOS enterprise apps from IBM to support the airline’s overall digital transformation. Finnair is focused on Asia-Europe traffic... Read more
Tech21 Launches Evo Go iPhone 7 Case Availabl...
Tech21 has announced the launch of the Evo Go case for Apple iPhone 7 and iPhone 7 Plus, exclusively at T-Mobile. Available online and at participating T-Mobile stores nationwide, Evo Go cases start... Read more
Apple Turns (RED) with More Ways to Join the...
In recognition of World AIDS Day, Apple is offering more ways than ever for customers to join (RED) in its mission to create an AIDS-free generation. Apple is the worlds largest corporate contributor... Read more
Deals on new 15-inch Touch Bar MacBook Pros,...
B&H Photo has new 2016 Apple 15″ Touch Bar MacBook Pro models in stock today with some available for $50 off MSRP, each including free shipping plus NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
12-inch Retina MacBooks on sale for up to $10...
12-inch Retina MacBooks remain on sale at B&H Photo with models available for up to $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. B&H will also include a free copy... Read more

Jobs Board

Automotive Detailer - *Apple* Used Autos -...
We are currently conductinginterviews and will be accepting applications for a part-time detailer. Apple Used Autos is a great place to work andstart a career. We Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
US- *Apple* Store Leader Program - Apple (Un...
…Summary Learn and grow as you explore the art of leadership at the Apple Store. You'll master our retail business inside and out through training, hands-on Read more
*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Dallas TX Introduction: We have immediate job openings for several Desktop Support Technicians with one of our most Read more
*Apple* &Amp Pc Desktop Support Technici...
Apple & PC Desktop Support Technician job in Monroe, CT Introduction: We have immediate job openings for several Desktop Support Technicians with one of our most Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.