Homework #7: Making Y-combinator (somewhat) practical
Out: Friday, February 24th, Due: Friday, March 3rd, 4:30pm


Administrative

The language for this homework is: 

#lang plait #:untyped

Unlike most of our assignments, we will not modify an interpreter for a toy language, but rather use define-syntax-rule to modify plait itself.

For reasons explained in the next section, there is quite a rigid coding style for this assignment. In particular no top-level function you write should be (directly) recursive.

Introduction

In class we saw how to define recursive functions using only let and lambda. The machinery we used is rather famous in the logic and programming languages literatures, where it is known as the "fixpoint operator" or or "Y combinator". Our implementation in class had two major flaws. First, it seemed to require a fair amount of boilerplate to be copied around for each function definition, and second it only handled single argument functions. We will show how to mitigate these problems in this assignment by using currying and syntax rules.

Begin your work with the following definition of lambda/rec, based on an extension of the discussion in Lecture 11. 

(define-syntax-rule (lambda/rec fun def)
  ((lambda (f)
     ((lambda (x) (f (lambda (n) ((x x) n))))
      (lambda (x) (f (lambda (n) ((x x) n))))))
   (lambda (fun) def)))
Here is an example of using this syntax rule to avoid copying boilerplate. 
(let
    ([fact
      (lambda/rec fact
         (lambda (n)
           (if (zero? n) 1
               (* n (fact (- n 1))))))])
  (fact 5))

In this assignment we want to satisfy two somewhat conflicting constraints. On the one hand, we want to demonstrate that our solutions do not rely on the racket define form to introduce recursion. On other hand, we need to define top level functions for the handin tests. For these reasons all of the functions we define in this assignment will have the following form. 

(define (func-wrapper-num arg ...)
  (let* (...
        [func expression])
    (func arg ...)))
The number is just in case we need to define multiple versions of the same function. For the specific example of the factorial definition above, this looks like 
(define (fact-wrapper-0 n)
  (let*
      ([fact
        (lambda/rec fact
            (lambda (n)
              (if (zero? n) 1
                  (* n (fact (- n 1))))))])
    (fact n)))
(test (fact-wrapper-0 6) 720)
There is no advantage to let* over let here, but it will be useful below. Note that the test is outside the let* (and the wrapper definition).


Multiple Arguments via Currying

Ackermann’s function is an interesting case of a function that cannot be expressed using ‘simple’ recursion; it creates extremely large numbers for small inputs — specifically, don’t try to use more than 3 for the first argument, since the result can easily be too big to fit in your computer’s memory. See the Wikipedia article about this for more information and interesting facts.

Here is a definition of Ackermann’s function 

(define (ackermann m n)
  (cond [(zero? m) (+ n 1)]
        [(zero? n) (ackermann (- m 1) 1)]
        [else      (ackermann (- m 1)
                              (ackermann m (- n 1)))]))
(test (ackermann 3 3) 61)

Consider a direct attempt to use lambda/rec to implement Ackermann’s function. 

(let ([ackermann
       (lambda/rec ackermann
           (lambda (m n)
             (cond [(zero? m) (+ n 1)]
                   [(zero? n) (ackermann (- m 1) 1)]
                   [else      (ackermann (- m 1)
                                         (ackermann m (- n 1)))])))])
   (ackermann 3 3))
This fails because our definition of lambda/rec is limited to recursive functions of one argument only, since it relies on (lambda (z) ((x x) z)) being the same as (x x), which is true only when the latter is a one-argument function.

We can get around this by writing a curried definition of the ackermann function, but this means that the function is called in a different way, which means changing both its body (the recursive calls) and the place that uses it (the test expression). This can be avoided using similar "local function redefinition" tricks to those we used in Lecture 11.

As a first step, fill in the necessary parts of the definition below so that the test passes. In particular notice the ackermann in the body has two arguments, while the function passed in is curried, and has only one.

In all of the code samples given here, you may have to add more closing parens on the end after you insert code where indicated. Try to minimize your edits to the given code other than closing parens.

(define (ackermann-wrapper-1 m n)
  (let ([ackermann
         (lambda/rec ackermann
         (—«fill-in»—
          (cond [(zero? m) (+ n 1)]
                [(zero? n) (ackermann (- m 1) 1)]
                [else      (ackermann (- m 1)
                                      (ackermann m (- n 1)))])))])
    ((ackermann m) n)))
(test (ackermann-wrapper-1 3 3) 61)
(test (ackermann-wrapper-1 3 5) 253)

Modify your definition for ackermann from the previous part, and provide a binding ackermann in the body of let* that takes two arguments.

(define (ackermann-wrapper-2 m n)
  (let* (—«modify previous solution»—
                   (cond [(zero? m) (+ n 1)]
                         [(zero? n) (ackermann (- m 1) 1)]
                         [else      (ackermann (- m 1)
                                               (ackermann m (- n 1))))))
    (ackermann m n))))
(test (ackermann-wrapper-2 3 3) 61)
(test (ackermann-wrapper-2 3 5) 253)

A variation on delay

We saw just above (and in class) that a crucial part of the lambda/rec machinery is the use of (lambda (z) ((x x) z)) to delay the evaluation of (x x). If we have to use curried functions anyway, it may be more convenient to just ignore the argument of the lambda. As a warmup, fill in the missing parts of the definition of fact. Note that dummy should not be used in the code. 

(define (fact-wrapper-1 n)
  (let* ([fact (lambda/rec fact
                   (lambda (dummy)
                     (—«fill-in»—
                      (if (zero? n)
                          1
                          (* n (fact (- n 1)))))))]
         [—«fill-in»—])
    (fact n)))

(test (fact-wrapper-1 5) 120))

There doesn’t seem to be much point in adding the extra dummy argument for single argument functions, but it turns out to be useful for multiple argument functions. Mimic the approach of fact above to provide another implementation of Ackermann’s function. 

(define (ackermann-wrapper-3 m n)
  (let* ([ackermann
          (lambda/rec ackermann
              —«fill-in»—
            (lambda (m n)
              —«fill-in»—
              (cond [(zero? m) (+ n 1)]
                    [(zero? n) (ackermann (- m 1) 1)]
                    [else      (ackermann (- m 1)
                                          (ackermann m (- n 1)))])))]
         [—«fill-in»—])
    (ackermann m n)))

(test (ackermann-wrapper-3 3 3) 61))


Prettying up the syntax

The last variation with the dummy argument is not very nice from a programmer point of view, as it intersperses "user code" with boilerplate needed for lambda/rec. It turns out that this kind of manipulation of code is easy for a computer to do, and we can provide a nice syntax to the user by automating it.

Your job is to define a syntax rule that does just that, thereby allowing recursive function definitions of any arity. This is done with the define-syntax-rule form. Note that this is very similar to writing a preprocessor (which you have done in previous homeworks), except that now you’re extending plait instead of the language you’re implementing.
Here is a skeleton code to get you started: 

(define-syntax-rule (lambda/rec* (f x ...) E)
  (let ([g  (lambda/rec f
                —«fill-in»— )
    (g #f)))))

A note about using ‘...’ in templates: a ‘...’ in the input pattern of a syntax rule means match on any number of templates on the left of it In this case, the output pattern must also have a ‘...’ after the same identifiers. For example, here is a definition of a define/fun syntax rule that is more convenient to use than an explicit lambda: 

(define-syntax-rule (define/fun (id x ...) body)
  (define id
    (lambda (x ...) body)))
(i.e. mimics part of the functionality of the built in define form). Note that x matches anything, and because of the ‘...’ it matches a sequence of “anythings” — so the right side of the rule also must have ‘...’ following the x.

Once you have a good definition of this syntax rule, you can verify that it’s working with a definition of ackermann and a matching test: 

(define (ackermann-wrapper-4 m n)
  (let ([ackermann (lambda/rec*  (ackermann m n)
                       (cond [(zero? m) (+ n 1)]
                             [(zero? n) (ackermann (- m 1) 1)]
                             [else      (ackermann (- m 1)
                                                   (ackermann m (- n 1)))]))])
    (ackermann m n)))
You should also use lambda/rec* to define fact, and at least one more recursive function with multiple arguments.