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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Posterino 3.3.7 - Create posters, collag...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Airmail 3.2.9 - Powerful, minimal email...
Airmail is an mail client with fast performance and intuitive interaction. Support for iCloud, MS Exchange, Gmail, Google Apps, IMAP, POP3, Yahoo!, AOL, Outlook.com, Live.com. Airmail was designed... Read more
Arq 5.8.4 - Online backup to Google Driv...
Arq is super-easy online backup for Mac and Windows computers. Back up to your own cloud account (Amazon Cloud Drive, Google Drive, Dropbox, OneDrive, Google Cloud Storage, any S3-compatible server... Read more
Microsoft Remote Desktop 8.0.39 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Arq 5.8.4 - Online backup to Google Driv...
Arq is super-easy online backup for Mac and Windows computers. Back up to your own cloud account (Amazon Cloud Drive, Google Drive, Dropbox, OneDrive, Google Cloud Storage, any S3-compatible server... Read more
Airmail 3.2.9 - Powerful, minimal email...
Airmail is an mail client with fast performance and intuitive interaction. Support for iCloud, MS Exchange, Gmail, Google Apps, IMAP, POP3, Yahoo!, AOL, Outlook.com, Live.com. Airmail was designed... Read more
Microsoft Remote Desktop 8.0.39 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Posterino 3.3.7 - Create posters, collag...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Airmail 3.2.8 - Powerful, minimal email...
Airmail is an mail client with fast performance and intuitive interaction. Support for iCloud, MS Exchange, Gmail, Google Apps, IMAP, POP3, Yahoo!, AOL, Outlook.com, Live.com. Airmail was designed... Read more
WhatRoute 2.0.21 - 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

Latest Forum Discussions

See All

Pokémon GO might be getting legendaries...
The long-awaited legendary Pokémon may soon be coming to Pokémon GO at long last. Data miners have already discovered that the legendary birds, Articuno, Moltres, and Zapdos are already in the game, it’s just a matter of time. [Read more] | Read more »
The best deals on the App Store this wee...
If you’ve got the Monday blues we have just the thing to cheer you up. The week is shaping up to be a spectacular one for sales. We’ve got a bunch of well-loved indie games at discounted prices this week along with a few that are a little more... | Read more »
Honor 8 Pro, a great choice for gamers
Honor is making strides to bring its brand to the forefront of mobile gaming with its latest phone, the Honor 8 Pro. The Pro sets itself apart from its predecessor, the Honor 8, with a host of premium updates that boost the device’s graphical and... | Read more »
The 4 best outdoor adventure apps
Now that we're well into the pleasant, warmer months, it's time to start making the most of the great outdoors. Spring and summer are ideal times for a bit of trekking or exploration. You don't have to go it alone, though. There are plenty of... | Read more »
Things 3 (Productivity)
Things 3 3.0.1 Device: iOS iPhone Category: Productivity Price: $7.99, Version: 3.0.1 (iTunes) Description: Meet the all-new Things! A complete rethinking of the original, award-winning task manager – with a perfect balance between... | Read more »
Oddball mash-up Arkanoid vs Space Invade...
In a move no one was really expecting, Square Enix has put forth an Arkanoid/Space Invaders mash-up aptly titled Arkanoid vs Space Invaders. The game launched today on both iOS and Android and the reviews are actually quite good. [Read more] | Read more »
Arkanoid vs Space Invaders (Games)
Arkanoid vs Space Invaders 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: LAUNCH SALE: GET THE GAME AT 20% OFF! Two of the most iconic classic games ever made meet in Arkanoid vs Space... | Read more »
The best new games we played this week
Things got off to a bit of a slow start this week, but as we steadily creep towards Friday a bunch of great games have started cropping up. If you're looking for a quality new release to play this weekend, we've got you covered. Here's a handy... | Read more »
No Stick Shooter (Games)
No Stick Shooter 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Happy Robot presents a fresh take on the classic retro-arcade shooters we all know and love. Featuring 30 levels of non-stop... | Read more »
Chroma Squad (Games)
Chroma Squad 1.0.85 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.85 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

Five To Six Million 10.5-inch iPad Pro Tablet...
Digitimes’ Siu Han and Joseph Tsai report that upstream supply chain shipments for Apple’s new 10.5-inch iPad Pro have been increasing, with monthly shipment volume expected to hit 600,000 units by... Read more
Georgia Tech Students Win Toyota and Net Impa...
Earlier this year, a team of students at Georgia Tech realized that there was a critical gap in transportation services for people who use wheelchairs, and wondered if the solution could be in the... Read more
13-inch 2.0GHz Space Gray MacBook Pro on sale...
Amazon has the 13″ 2.0GHz Space Gray non-Touch Bar MacBook Pro (MLL42LL/A) on sale for $1299.99 including free shipping. Their price is $200 off MSRP, and it’s currently the lowest price available... Read more
Roundup of 15-inch MacBook Pro sale prices, m...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 15″ 2.7GHz... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
B&H Photo has the 2015 15″ 2.2GHz Retina MacBook Pro (MJLQ2LL/A) on sale for $1849 including free shipping plus NY & NJ sales tax only. Their price is $150 off MSRP. Read more
21-inch iMacs on sale for $100 off MSRP, save...
B&H Photo has 21″ iMacs on sale for $100 off MSRP, each including free shipping plus NY & NJ sales tax only: - 21″ 3.1GHz iMac 4K: $1399.99 $100 off MSRP - 21″ 2.8GHz iMac: $1199.99 $100 off... Read more
Groupon Survey Finds Families Will Spend One-...
With warmer weather finally arriving in most parts of the country and the school year winding down to a close, Groupon (http://www.groupon.com) asked 1,000 U.S. parents how much time their families... Read more
Panasonic Anounces Toughbook 33 2-in-1 Rugged...
Panasonic has announced the U.S. availability of the Panasonic Toughbook 33, claimed to be the first fully-rugged 2-in-1 detachable laptop that features a 3:2 display. Inspired by the hard-working... Read more
9-inch 32GB iPad Pros available for up to $10...
Amazon resellers are offering new 9″ 32GB iPad Pros for up to $101 off MSRP, starting at $498, including free shipping. Colors may be Space Gray, Silver, Gold, or Rose Gold, depending on the reseller... Read more
Back in stock: Apple refurbished Mac minis st...
Apple has Certified Refurbished Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $80 off MSRP - 2.6GHz Mac... Read more

Jobs Board

Director, *Apple* Program - ERP & Cloud...
…make a real difference. Come, shine with us! Astellas is announcing a Director, Apple Program - ERP & Cloud Platform Architecture Lead opportunity in Northbrook, IL. Read more
*Apple* Mobile Master - Best Buy (United Sta...
**508102BR** **Job Title:** Apple Mobile Master **Location Number:** 000511-Athens-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
*Apple* Media Products - Commerce Engineerin...
Apple Media Products - Commerce Engineering Manager Job Number: 57037480 Santa Clara Valley, California, United States Posted: Apr. 18, 2017 Weekly Hours: 40.00 Job Read more
Geek Squad *Apple* Master Consultation Agen...
**500444BR** **Job Title:** Geek Squad Apple Master Consultation Agent **Location Number:** 000103-City Of Industry-Store **Job Description:** **What does a Geek Read more
Security Engineer, *Apple* Retail - Apple I...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.