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 CDROM 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 lambadathe forbidden (in lcalculus) 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 passfact 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 lcalculus. The aim of the minimalist game is (among other things):
1) To understand lcalculus 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 lcalculus (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 lcalculus. 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 lcalculus 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 functionthe 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 ((localfact
(lambda (n)
(if (zero? n)
1
(* n (localfact (1 n)))))))
(localfact 5))
ERROR: Undefined global variable
localfact
Entering debugger. Enter ? for help.
debug:>
This is where letrec comes in.
; 2
>>> (letrec ((localfact
(lambda (n)
(if (zero? n)
1
(* n (localfact (1 n)))))))
(localfact 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 ((localfact ‘undefined))
(begin
(set! localfact
(lambda (n)
(if (zero? n)
1
(* n (localfact (1 n))))))
(localfact 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 ((myeven? ‘undefined)
(myodd? ‘undefined))
(begin
(set! myeven?
(lambda (n)
(if (zero? n)
#t
(myodd? (1 n)))))
(set! myodd?
(lambda (n)
(if (zero? n)
#f
(myeven? (1 n)))))
(myeven? 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. lcalculus 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 nonstate oriented solutions to such problems in lcalculus.)
The recursion in localfact can be ridded by using the Y combinator. However, in the myeven? and myodd? 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 chickenbeforetheegg dilemma.
It’s clear we need a special kind of Y for this situation. Let’s call it Y2.
The passfact trick
[vanMeule May 92] derived the Y combinator in the style of [Gabriel 88] by starting with passfact (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 myeven? and myodd? as our starting point.
First, we want to massage myeven? and myodd? into something that looks like passfact. Here’s what our “template” looks like:
; 5
>>> (define passfact
(lambda (f n)
(if (zero? n)
1
(* n (f f (1 n))))))
passfact
>>> (passfact passfact 5)
120
Here’s a version of myeven? and myodd? modeled after the passfact “template”.
; 6
>>> (define evenodd
(cons
(lambda (functionlist)
(lambda (n)
(if (zero? n)
#t
(((cdr functionlist) functionlist)
(1 n)))))
(lambda (functionlist)
(lambda (n)
(if (zero? n)
#f
(((car functionlist) functionlist)
(1 n)))))))
evenodd
>>> (define passeven?
((car evenodd) evenodd))
passeven?
>>> (define passodd?
((cdr evenodd) evenodd))
passodd?
>>> (passeven? 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 myeven? and myodd? the next step is to massage out the recursionless mutual recursion mechanism from the definitional parts that came from myeven? and myodd?. The following is the code of such a derivation, including test cases and comments.
; 7
(define myeven?
(lambda (n)
(if (zero? n)
#t
(myodd? (1 n)))))
;
(define myodd?
(lambda (n)
(if (zero? n)
#f
(myeven? (1 n)))))
;
(myeven? 5)
;
; Get out of global environmentuse local environment.
;
(define mutualeven?
(letrec
((myeven? (lambda (n)
(if (zero? n)
#t
(myodd? (1 n)))))
(myodd? (lambda (n)
(if (zero? n)
#f
(myeven? (1 n))))))
myeven?))
;
(mutualeven? 5)
;
; Get rid of destructive letrec. Use let instead.
; Make a list of the mutually recursive functions.
;
(define mutualeven?
(lambda (n)
(let
((functionlist
(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 functionlist) functionlist n))))
;
(mutualeven? 5)
;
; Curry, and get rid of initial (lambda (n) ...) .
;
(define mutualeven?
(let
((functionlist
(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 functionlist) functionlist)))
;
(mutualeven? 5)
;
; Abstract ((cdr functions) functions) out of if, etc..
;
(define mutualeven?
(let
((functionlist
(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 functionlist) functionlist)))
;
(mutualeven? 5)
;
; Massage functions into abstracted versions of
; originals.
;
(define mutualeven?
(let
((functionlist
(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 functionlist) functionlist)))
;
(mutualeven? 5)
;
; Separate abstracted functions out from recursive
; mechanism.
;
(define mutualeven?
(let
((abstractedfunctions
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1 n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1 n))))))))
(let
((functionlist
(cons (lambda (functions)
(lambda (n)
(((car abstractedfunctions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstractedfunctions)
((car functions) functions))
n))))))
((car functionlist) functionlist))))
;
(mutualeven? 5)
;
; Abstract out variable abstractedfunctions in 2nd let.
;
(define mutualeven?
(let
((abstractedfunctions
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1 n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1 n))))))))
((lambda (abstractedfunctions)
(let
((functionlist
(cons (lambda (functions)
(lambda (n)
(((car abstractedfunctions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstractedfunctions)
((car functions) functions))
n))))))
((car functionlist) functionlist)))
abstractedfunctions)))
;
(mutualeven? 5)
;
; Separate recursion mechanism into separate function.
;
(define y2
(lambda (abstractedfunctions)
(let
((functionlist
(cons (lambda (functions)
(lambda (n)
(((car abstractedfunctions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstractedfunctions)
((car functions) functions))
n))))))
((car functionlist) functionlist))))
;
(define mutualeven?
(y2
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1 n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1 n))))))))
;
(mutualeven? 5)
;
; y2 has selector built into itgeneralize it!
;
(define y2choose
(lambda (abstractedfunctions)
(lambda (selector)
(let
((functionlist
(cons (lambda (functions)
(lambda (n)
(((car abstractedfunctions)
((cdr functions) functions))
n)))
(lambda (functions)
(lambda (n)
(((cdr abstractedfunctions)
((car functions) functions))
n))))))
((selector functionlist) functionlist)))))
;
; Now we can achieve the desired resultdefining
; both mutualeven? and mutualodd? without recursion.
;
(define mutualevenodd?
(y2choose
(cons (lambda (f)
(lambda (n)
(if (zero? n)
#t
(f (1 n)))))
(lambda (f)
(lambda (n)
(if (zero? n)
#f
(f (1 n))))))))
;
(define mutualeven?
(mutualevenodd? car))
;
(define mutualodd?
(mutualevenodd? cdr))
;
(mutualeven? 5)
(mutualodd? 5)
(mutualeven? 4)
(mutualodd? 4)
Deriving Mutual Satisfaction
Notice that mutualeven? and mutualodd? could have been defined using y2 instead of y2choose, however, the definitional bodies of myeven? and myodd? would have been repeated in defining mutualeven? and mutualodd?.
Exercises for the Reader
• Herein Y2 was derived from mutualeven?. Try deriving it instead from passeven?.
• 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 lcalculus is normal order.)
Looking Ahead
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 “Whowhoo” 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, JulySeptember, 1991. ACM Press.
[Gabriel 88] Richard P. Gabriel. “The Why of Y”, LISP Pointers, Vol. II, Number 2, OctoberNovemberDecember, 1988.
[vanMeule May 91] André van Meulebrouck. “A Calculus for the Algebraiclike 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.