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 orsource 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))))