Lambda
 Volume Number: 9 Issue Number: 9 Column Tag: Lisp Listener

# “The Lambda Lambada: Y Dance?”

## Mutual Recursion

By André van Meulebrouck, Chatsworth, California

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

“Mathematics is thought moving in the sphere of complete abstraction from any particular instance of what it is talking about.” - Alfred North Whitehead

Welcome once again to Mutual of Omo Oz Y Old Kingdom (with apologies to the similar named TV series of yesteryears).

In this installment, Lambda, the forbidden (in conventional languages) function, does the lambada-the forbidden (in l-calculus) dance. Film at 11.

In [vanMeule Jun 91] the question was raised as to whether everything needed to create a metacircular interpreter (using combinators) has been given to the reader.

One of the last (if not the last) remaining items not yet presented is mutual recursion, which allows an interpreter’s eval and apply functions to do their curious tango (the “lambda lambada”?!?).

In this article, the derivation of a Y2 function will be shown. Y2 herein will be the sister combinator of Y, to be used for handling mutual recursion (of two functions) in the applicative order. The derivation of Y2 will be done in a similar manner as was done for deriving Y from pass-fact in [vanMeule May 92].

This exercise will hopefully give novel insights into Computer Science and the art of programming. (This is the stuff of Überprogrammers!) This exercise should also give the reader a much deeper understanding of Scheme while developing programming muscles in ways that conventional programming won’t.

## Backdrop and motivation

[vanMeule Jun 91] described the minimalist game. The minimalist game is an attempt to program in Scheme using only those features of Scheme that have more or less direct counterparts in l-calculus. The aim of the minimalist game is (among other things):

1) To understand l-calculus and what it has to say about Computer Science.

2) To develop expressive skills. Part of the theory behind the minimalist game is that one’s expressive ability is not so much posited in how many programming constructs one knows, but in how cleverly one wields them. Hence, by deliberately limiting oneself to a restricted set of constructs, one is forced to exercise one’s expressive muscles in ways they would not normally get exercised when one has a large repertoire of constructs to choose from. The maxim here is: “learn few constructs, but learn them well”.

In l-calculus (and hence the minimalist game) there is no recursion. It turns out that recursion is a rather impure contortion in many ways! However, recursion can be simulated by making use of the higher order nature of l-calculus. A higher order function is a function which is either passed as an argument (to another function) or returned as a value. As thrifty as l-calculus is, it does have higher order functions, which is no small thing as very few conventional languages have such a capability, and those that do have it have only a very weak version of it. (This is one of the programming lessons to be learned from playing the minimalist game: The enormous power of higher order functions and the losses conventional languages suffer from not having them.)

## Different kinds of recursion

As soon as a language has global functions or procedures and parameter passing provided via a stack discipline, you’ve got recursion! In fact, there is essentially no difference between a procedure calling itself or calling a different function-the same stack machinery that handles the one case will automatically handle the other. (There’s no need for the stack machinery to know nor care whether the user is calling other procedures or the same procedure.)

However, as soon as a language has local procedures, it makes a very big difference if a procedure calls itself! The problem is that when a local procedure sees a call to itself from within itself, by the rules of lexical scoping, it must look for its own definition outside of its own scope! This is because the symbol naming the recursive function is a free variable with respect to the context it occurs in.

```; 1
>>> (let ((local-fact
(lambda (n)
(if (zero? n)
1
(* n (local-fact (1- n)))))))
(local-fact 5))
```
```ERROR:  Undefined global variable
local-fact

Entering debugger.  Enter ? for help.
debug:>
```

This is where letrec comes in.

```; 2

>>> (letrec ((local-fact
(lambda (n)
(if (zero? n)
1
(* n (local-fact (1- n)))))))
(local-fact 5))
120
```

To understand what letrec is doing let’s translate it to its semantic equivalent. letrec can be simulated using let and set! [CR 91].

```; 3
>>> (let ((local-fact ‘undefined))
(begin
(set! local-fact
(lambda (n)
(if (zero? n)
1
(* n (local-fact (1- n))))))
(local-fact 5)))
120
```

Mutual recursion is slightly different from “regular” recursion: instead of a function calling itself, it calls a different function that then calls the original function. For instance, “foo” and “fido” would be mutually recursive if foo called fido, and fido called foo. The letrec trick will work fine for mutual recursion.

```; 4

>>> (let ((my-even? ‘undefined)
(my-odd? ‘undefined))
(begin
(set! my-even?
(lambda (n)
(if (zero? n)
#t
(my-odd? (1- n)))))
(set! my-odd?
(lambda (n)
(if (zero? n)
#f
(my-even? (1- n)))))
(my-even? 80)))
#t
```

The reason this works is because both functions that had to have mutual knowledge of each other were defined as symbols in a lexical context outside of the context in which the definitions were evaluated.

However, all the above letrec examples rely on being able to modify state. l-calculus doesn’t allow state to be modified. (An aside: since parallel machines have similar problems and restrictions in dealing with state, there is ample motivation for finding non-state oriented solutions to such problems in l-calculus.)

The recursion in local-fact can be ridded by using the Y combinator. However, in the my-even? and my-odd? example the Y trick doesn’t work because in trying to eliminate recursion using Y, the mutual nature of the functions causes us to get into a chicken-before-the-egg dilemma.

It’s clear we need a special kind of Y for this situation. Let’s call it Y2.

## The pass-fact trick

[vanMeule May 92] derived the Y combinator in the style of [Gabriel 88] by starting with pass-fact (a version of the factorial function which avoids recursion by passing its own definition as an argument) and massaging it into two parts: a recursionless recursion mechanism and an abstracted version of the factorial function.

Let’s try the same trick for Y2, using my-even? and my-odd? as our starting point.

First, we want to massage my-even? and my-odd? into something that looks like pass-fact. Here’s what our “template” looks like:

```; 5

>>> (define pass-fact
(lambda (f n)
(if (zero? n)
1
(* n (f f (1- n))))))
```
```pass-fact
>>> (pass-fact pass-fact 5)
120
```

Here’s a version of my-even? and my-odd? modeled after the pass-fact “template”.

```; 6
>>> (define even-odd
(cons
(lambda (function-list)
(lambda (n)
(if (zero? n)
#t
(((cdr function-list) function-list)
(1- n)))))
(lambda (function-list)
(lambda (n)
(if (zero? n)
#f
(((car function-list) function-list)
(1- n)))))))
even-odd
>>> (define pass-even?
((car even-odd) even-odd))
pass-even?
>>> (define pass-odd?
((cdr even-odd) even-odd))
pass-odd?
>>> (pass-even? 8)
#t
```

## This could derive one crazy!

Now that we know we can use higher order functions to get rid of the mutual recursion in my-even? and my-odd? the next step is to massage out the recursionless mutual recursion mechanism from the definitional parts that came from my-even? and my-odd?. The following is the code of such a derivation, including test cases and comments.

```; 7
(define my-even?
(lambda (n)
(if (zero? n)
#t
(my-odd? (1- n)))))
;
(define my-odd?
(lambda (n)
(if (zero? n)
#f
(my-even? (1- n)))))
;
(my-even? 5)
;
; Get out of global environment-use local environment.
;
(define mutual-even?
(letrec
((my-even? (lambda (n)
(if (zero? n)
#t
(my-odd? (1- n)))))
(my-odd? (lambda (n)
(if (zero? n)
#f
(my-even? (1- n))))))
my-even?))
;
(mutual-even? 5)
;
; Get rid of destructive letrec.  Use let instead.
; Make a list of the mutually recursive functions.
;
(define mutual-even?
(lambda (n)
(let
((function-list
(cons (lambda (functions n) ; even?
(if (zero? n)
#t
((cdr functions) functions
(1- n))))
(lambda (functions n) ; odd?
(if (zero? n)
#f
((car functions) functions
(1- n)))))))
((car function-list) function-list n))))
;
(mutual-even? 5)
;
; Curry, and get rid of initial (lambda (n) ...) .
;
(define mutual-even?
(let
((function-list
(cons (lambda (functions) ; even?
(lambda (n)
(if (zero? n)
#t
(((cdr functions) functions)
(1- n)))))
(lambda (functions) ; odd?
(lambda (n)
(if (zero? n)
#f
(((car functions) functions)
(1- n))))))))
((car function-list) function-list)))
;
(mutual-even? 5)
;
; Abstract ((cdr functions) functions) out of if, etc..
;
(define mutual-even?
(let
((function-list
(cons (lambda (functions)
(lambda (n)
((lambda (f)
(if (zero? n)
#t
(f (1- n))))
((cdr functions) functions))))
(lambda (functions)
(lambda (n)
((lambda (f)
(if (zero? n)
#f
(f (1- n))))
((car functions) functions)))))))
((car function-list) function-list)))
;
(mutual-even? 5)
;
; Massage functions into abstracted versions of
; originals.
;
(define mutual-even?
(let
((function-list
(cons (lambda (functions)
(lambda (n)
(((lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1- n)))))
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1- n)))))
((car functions) functions))
n))))))
((car function-list) function-list)))
;
(mutual-even? 5)
;
; Separate abstracted functions out from recursive
; mechanism.
;
(define mutual-even?
(let
((abstracted-functions
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1- n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1- n))))))))
(let
((function-list
(cons (lambda (functions)
(lambda (n)
(((car abstracted-functions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstracted-functions)
((car functions) functions))
n))))))
((car function-list) function-list))))
;
(mutual-even? 5)
;
; Abstract out variable abstracted-functions in 2nd let.
;
(define mutual-even?
(let
((abstracted-functions
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1- n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1- n))))))))
((lambda (abstracted-functions)
(let
((function-list
(cons (lambda (functions)
(lambda (n)
(((car abstracted-functions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstracted-functions)
((car functions) functions))
n))))))
((car function-list) function-list)))
abstracted-functions)))
;
(mutual-even? 5)
;
; Separate recursion mechanism into separate function.
;
(define y2
(lambda (abstracted-functions)
(let
((function-list
(cons (lambda (functions)
(lambda (n)
(((car abstracted-functions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstracted-functions)
((car functions) functions))
n))))))
((car function-list) function-list))))
;
(define mutual-even?
(y2
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1- n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1- n))))))))
;
(mutual-even? 5)
;
; y2 has selector built into it-generalize it!
;
(define y2-choose
(lambda (abstracted-functions)
(lambda (selector)
(let
((function-list
(cons (lambda (functions)
(lambda (n)
(((car abstracted-functions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstracted-functions)
((car functions) functions))
n))))))
((selector function-list) function-list)))))
;
; Now we can achieve the desired result-defining
; both mutual-even? and mutual-odd? without recursion.
;
(define mutual-even-odd?
(y2-choose
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1- n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1- n))))))))
;
(define mutual-even?
(mutual-even-odd? car))
;
(define mutual-odd?
(mutual-even-odd? cdr))
;
(mutual-even? 5)
(mutual-odd? 5)
(mutual-even? 4)
(mutual-odd? 4)
```

## Deriving Mutual Satisfaction

Notice that mutual-even? and mutual-odd? could have been defined using y2 instead of y2-choose, however, the definitional bodies of my-even? and my-odd? would have been repeated in defining mutual-even? and mutual-odd?.

• Herein Y2 was derived from mutual-even?. Try deriving it instead from pass-even?.

• 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: evaluation in l-calculus is normal order.)

Creating a “minimalist” (i.e., combinator based) metacircular interpreter might now be possible if we can tackle the problem of manipulating state!

## Thanks to:

The local great horned owls that watch over everything from on high; regularly letting fellow “night owls” know that all is well by bellowing their calming, reassuring “Who-w-h-o-o” sounds.

Bugs/infelicities due to: burning too much midnite oil!

## Bibliography and References

[CR 91] William Clinger and Jonathan Rees (editors). “Revised4 Report on the Algorithmic Language Scheme”, LISP Pointers, SIGPLAN Special Interest Publication on LISP, Volume IV, Number 3, July-September, 1991. ACM Press.

[Gabriel 88] Richard P. Gabriel. “The Why of Y”, LISP Pointers, Vol. II, Number 2, October-November-December, 1988.

[vanMeule May 91] André van Meulebrouck. “A Calculus for the Algebraic-like Manipulation of Computer Code” (Lambda Calculus), MacTutor, Anaheim, CA, May 1991.

[vanMeule Jun 91] André van Meulebrouck. “Going Back to Church” (Church numerals.), MacTutor, Anaheim, CA, June 1991.

[vanMeule May 92] André van Meulebrouck. “Deriving Miss Daze Y”, (Deriving Y), MacTutor, Los Angeles, CA, April/May 1992.

Community Search:
MacTech Search:

Microsoft Office 2016 16.11 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook, and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
Adobe Photoshop CC 2018 19.1.2 - Profess...
Photoshop CC 2018 is available as part of Adobe Creative Cloud for as little as \$19.99/month (or \$9.99/month if you're a previous Photoshop customer). Adobe Photoshop CC 2018, the industry standard... Read more
Adobe Dreamweaver CC 2018 18.1.0.10155 -...
Dreamweaver CC 2018 is available as part of Adobe Creative Cloud for as little as \$19.99/month (or \$9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2018 allows you to... Read more
Adobe Flash Player 29.0.0.113 - Plug-in...
Adobe Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating systems.... Read more
Drive Genius 5.2.0 - \$79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
MegaSeg 6.0.6 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
ffWorks 1.0.7 - Convert multimedia files...
ffWorks (was iFFmpeg), focused on simplicity, brings a fresh approach to the use of FFmpeg, allowing you to create ultra-high-quality movies without the need to write a single line of code on the... Read more
Dash 4.1.5 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Evernote 7.0.3 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
jAlbum Pro 15.3 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. You can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly... Read more

## Latest Forum Discussions

All the best games on sale for iPhone an...
It might not have been the greatest week for new releases on the App Store, but don't let that get you down, because there are some truly incredible games on sale for iPhone and iPad right now. Seriously, you could buy anything on this list and I... | Read more »
Everything You Need to Know About The Fo...
In just over a week, Epic Games has made a flurry of announcements. First, they revealed that Fortnite—their ultra-popular PUBG competitor—is coming to mobile. This was followed by brief sign-up period for interested beta testers before sending out... | Read more »
The best games that came out for iPhone...
It's not been the best week for games on the App Store. There are a few decent ones here and there, but nothing that's really going to make you throw down what you're doing and run to the nearest WiFi hotspot in order to download it. That's not to... | Read more »
Death Coming (Games)
Death Coming 1.1.1.536 Device: iOS Universal Category: Games Price: \$1.99, Version: 1.1.1.536 (iTunes) Description: --- Background Story ---You Died. Pure and simple, but death was not the end. You have become an agent of Death: a... | Read more »
Hints, tips, and tricks for Empires and...
Empires and Puzzles is a slick match-stuff RPG that mixes in a bunch of city-building aspects to keep things fresh. And it's currently the Game of the Day over on the App Store. So, if you're picking it up for the first time today, we thought it'd... | Read more »
What You Need to Know About Sam Barlow’s...
Sam Barlow’s follow up to Her Story is #WarGames, an interactive video series that reimagines the 1983 film WarGames in a more present day context. It’s not exactly a game, but it’s definitely still interesting. Here are the top things you should... | Read more »
Pixel Plex Guide - How to Build Better T...
Pixel Plex is the latest city builder that has come to the App Store, and it takes a pretty different tact than the ones that came before it. Instead of being in charge of your own city by yourself, you have to work together with other players to... | Read more »
Fortnite Will Be Better Than PUBG on Mob...
Before last week, if you asked me which game I prefer between Fortnite Battle Royale and PlayerUnknown’s Battlegrounds (PUBG), I’d choose the latter just about 100% of the time. Now that we know that both games are primed to hit our mobile screens... | Read more »
Siege of Dragonspear (Games)
Siege of Dragonspear 2.5.12 Device: iOS Universal Category: Games Price: \$9.99, Version: 2.5.12 (iTunes) Description: Experience the Siege of Dragonspear, an epic Baldur’s Gate tale, filled with with intrigue, magic, and monsters.... | Read more »
7 Wonders Guide - Should You Buy The Lea...
The fantastic mobile version of 7 Wonders just got updated with an expansion that adds Leaders to the game. This new content adds a whole layer of depth to the game, but before you spend \$1.99 to buy it blindly, check out this breakdown of exactly... | Read more »

## Price Scanner via MacPrices.net

B&H drops prices on 15″ MacBook Pros up t...
B&H Photo has dropped prices on new 2017 15″ MacBook Pros, now up to \$300 off MSRP and matching Adorama’s price drop yesterday. Shipping is free, and B&H charges sales tax for NY & NJ... Read more
Apple restocks Certified Refurbished 2017 13″...
Apple has restocked Certified Refurbished 2017 13″ 2.3GHz MacBook Pros for \$200-\$230 off MSRP. A standard Apple one-year warranty is included with each MacBook, models receive new outer cases, and... Read more
13″ Space Gray Touch Bar MacBook Pros on sale...
Adorama has new 2017 13″ Space Gray Touch Bar MacBook Pros on sale for \$150 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (... Read more
Best deal of the year on 15″ Apple MacBook Pr...
Adorama has New 2017 15″ MacBook Pros on sale for up to \$300 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): \$... Read more
Save \$100-\$150+ on 13″ Touch Bar MacBook Pros...
B&H Photo has 13″ Touch Bar MacBook Pros on sale for \$100-\$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 3.1GHz/256GB Space Gray MacBook Pro... Read more
Current deals on 27″ Apple iMacs, models up t...
B&H Photo has 27″ iMacs on sale for up to \$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): \$2149 \$150 off MSRP – 27″ 3... Read more
Thursday Deal: 13″ 2.3GHz MacBook Pro for \$11...
B&H Photo has the 13″ 2.3GHz/128GB Space Gray MacBook Pro on sale for \$100 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz/128GB Space... Read more
How to save \$100-\$190 on 10″ & 12″ iPad P...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for \$100-\$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
Silver 12″ 1.3GHz MacBook on sale at B&H...
B&H Photo has the 2017 12″ 1.3GHz Silver MacBook on sale for \$1399.99 including free shipping plus sales tax for NY & NJ residents only. Their price is \$200 off MSRP, and it’s the lowest... Read more
Amazon offers 21″ Apple iMacs for up to \$150...
Amazon 21″ iMacs on sale today for \$50-\$150 off MSRP, depending on the model. Shipping is free: – 21″ 3.4GHz 4K iMac (MNE02LL/A): \$1349.99 \$150 off MSRP – 21″ 3.0GHz iMac (MNDY2LL/A): \$1199 \$100 off... Read more

## Jobs Board

*Apple* Certified Technician - iStore by St....
Job Description iStore by St. Moritz is an Authorized Apple Service Provider and our Headquarters is an Apple Premier Partner as well as a Premium Service Read more
*Apple* Certified Technician - Taycom (Unite...
Job Description Apple Computer Support Technician Taycom – Dallas, TX and surrounding area. Note: This position requires senior level Apple technical support Read more
*Apple* Certified Macintosh Technician - Mac...
…qualified persons who have a deep passion, dedication, and experience with the Apple Macintosh and iOS computer platforms. MacMedics is seeking Apple Certified Read more
*Apple* Part Time Reseller Specialist - Appl...
…in a reseller store, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
*Apple* Genius - Technical Customer Service...
Job Description: Job Summary As a Genius at the Apple Store, you maintain customers' trust in Apple as the skilled technical customer service expert, Read more