TweetFollow Us on Twitter

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?.

Exercises for the Reader

• 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.)

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 “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.

 
AAPL
$98.15
Apple Inc.
-0.23
MSFT
$43.58
Microsoft Corpora
-0.31
GOOG
$587.42
Google Inc.
+1.81

MacTech Search:
Community Search:

Software Updates via MacUpdate

Knock 1.1.7 - Unlock your Mac by knockin...
Knock is a faster, safer way to sign in. You keep your iPhone with you all the time. Now you can use it as a password. You never have to open the app -- just knock on your phone twice, even when it's... Read more
Mellel 3.3.6 - Powerful word processor w...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
LibreOffice 4.3.0.4 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Freeway Pro 7.0 - Drag-and-drop Web desi...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With it's user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Drive Genius 3.2.4 - Powerful system uti...
Drive Genius is an OS X utility designed to provide unsurpassed storage management. Featuring an easy-to-use interface, Drive Genius is packed with powerful tools such as a drive optimizer, a... Read more
Vitamin-R 2.15 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
Toast Titanium 12.0 - The ultimate media...
Toast Titanium goes way beyond the very basic burning in the Mac OS and iLife software, and sets the standard for burning CDs, DVDs, and now Blu-ray discs on the Mac. Create superior sounding audio... Read more
OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more

Latest Forum Discussions

See All

Murl the Squirrel (Games)
Murl the Squirrel 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Meet Murl. He is teased by a group of flying squirrels because he can't fly. Determined to show them he's can fly, he meets... | Read more »
Celleste (Games)
Celleste 0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 0.1 (iTunes) Description: Lots of cute action with amazing 3D graphics and a new type of gameplay! Take control over the forces of the universe to help a group... | Read more »
Super Heavy Sword (Games)
Super Heavy Sword 0.0.1 Device: iOS Universal Category: Games Price: $.99, Version: 0.0.1 (iTunes) Description: Get Ready to Get HEAVY! Monster Robot Studios presents SUPER Heavy Sword! The sequel to the smash hit HEAVY sword which... | Read more »
Angels In The Sky (Games)
Angels In The Sky 1.00 Device: iOS Universal Category: Games Price: $6.99, Version: 1.00 (iTunes) Description: - This game is only for the iPhone 5s. please do not use the iPad, iPhone 5 or earlier devices.- Just touch or holding... | Read more »
80 Days (Games)
80 Days 1.0.2 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.2 (iTunes) Description: 1872, with a steampunk twist. Phileas Fogg has wagered he can circumnavigate the world in just eighty days. Choose your own route... | Read more »
Micromon (Games)
Micromon 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: 130+ Animated Monsters to Catch & Battle! No waiting, play at your own pace! Embark on an epic monster capture RPG like none... | Read more »
Empire Manager (Games)
Empire Manager 1.0 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: Become ruler of an empire. Manage your economy, develop technology, hire an army and conquer the world in this addictive turn-... | Read more »
Empire Manager HD (Games)
Empire Manager HD 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: Become ruler of an empire. Manage your economy, develop technology, hire an army and conquer the world in this addictive... | Read more »
Star Admiral Review
Star Admiral Review By Rob Thomas on July 30th, 2014 Our Rating: :: ADMIRABLE ADMIRALSUniversal App - Designed for iPhone and iPad While this new digital CCG may feel a bit familiar, Star Admiral offers a sci-fi twist and galaxy’s... | Read more »
Zap! Pow! Become a Badass Wizard in Phan...
Zap! Pow! | Read more »

Price Scanner via MacPrices.net

iPad Cannibalization Threat “Overblown”
Seeking Alpha’s Kevin Greenhalgh observes that while many commentators think Apple’s forthcoming 5.5-inch panel iPhone 6 will cannibalize iPad sales, in his estimation, these concerns are being... Read more
Primate Labs Releases July 2014 MacBook Pro P...
Primate Labs’ John Poole has posted Geekbench 3 results for most of the new MacBook Pro models that Apple released on Tuesday. Poole observes that overall performance improvements for the new MacBook... Read more
Apple Re-Releases Bugfixed MacBook Air EFI Fi...
Apple has posted a bugfixed version EFI Firmware Update 2.9 a for MacBook Air (Mid 2011) models. The update addresses an issue where systems may take longer to wake from sleep than expected, and... Read more
Save $50 on the 2.5GHz Mac mini, plus free sh...
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more
Save up to $140 on an iPad Air with Apple ref...
Apple is offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. Stock tends to come and go with some of these... Read more
$250 price drop on leftover 15-inch Retina Ma...
B&H Photo has dropped prices on 2013 15″ Retina MacBook Pros by $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.3GHz Retina MacBook Pro: $2249, $250 off... Read more
More iPad Upgrade Musings – The ‘Book Mystiqu...
Much discussed recently, what with Apple reporting iPad sales shrinkage over two consecutive quarters, is that it had apparently been widely assumed that tablet users would follow a two-year hardware... Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $999.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Save up to $300 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $300 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. These are the best prices on... Read more
WaterField Unveils 15″ Outback Solo & 13″...
Hard on the heels of Apple’s refreshed MacBook Pro Retina laptops announcement, WaterField Designs has unveiled a 15-inch version of the waxed-canvas and leather Outback Solo and a 13-inch version of... Read more

Jobs Board

Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.