Out: Friday, February 15th, Due: Sunday, March 10th, 11:00pm
Administrative
This homework is only required for Master students. Undergrads
can do it too, and you will be graded as usual — but you will
not be able to withdraw a graded homework grade, so submit only
if you think that your work is good enough to improve your grade. (Note:
the homework grades are all weighted to compute your overall grade, so
adding another grade means that you get smaller portions for more grades,
which can serve as protection against local disasters.)
Note that while undergrads are not required to submit a solution, it will
be a very good idea to read the homework and go through the solution when
it is later posted — since you are expected to know the material.
Work and submission is with the same pairs.
The language for this homework is:
#lang pl 09
Introduction
As you might have noted, our fixpoint operator — the Y combinator, is very
limited: it can be used only with single argument functions. Another
possible limitation is that is that it can construct one recursive function,
but not several mutually recursive functions. In this homework you will
show that the Y combinator is actually capable of addressing both problems.
Begin your work with the definition of the Y combinator that is suitable for
plain Racket (untyped, and strict):
The first problem that we’re going to tackle is the fact that this
definition of the Y combinator is limited to recursive functions of one
argument only. This is because 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. For example, the following definition of the
Ackermann function doesn’t work:
(define ackermann
(Y (lambda (ackermann)
(lambda (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)
(Note: 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.)
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).
However, we can still get it to work. To avoid changing the test
expression, all we need to do is to make sure that ackermann is actually
bound to a two-argument function that uses the curried version to do its
work:
and we can also wrap the body (elided in this last example) so that it gets
a two-argument version of the function.
The same technique can be used to deal with functions of any arity. To make
things a bit more uniform, we can simply ignore the first argument, and
always pass some random value for this argument. In the ackermann case,
this leads to the following definition:
(define ackermann
(let ([g (Y (lambda (ackermann)
(lambda (_) ; we ignore this argument
(lambda (m n)
(let ([ackermann (ackermann #f)])
...same body for the function...)))))])
(g #f)))
Your job is to define a rewrite rule that does just that, thereby allowing
recursive function definitions of any arity. This is done with the
rewrite form that we have seen briefly in the Schlac language. Note
that this is very similar to writing a preprocessor (which you have done in
previous homeworks), except that now you’re extending your own language
instead of the language you’re implementing.
Here is a skeleton code to get you started:
(rewrite (define/rec (f x ...) E)
=> (define f
(let ([g (Y (lambda (f)
...finish this part...))])
(g #f))))
A note about using ‘...’ in templates: a ‘...’ in the input pattern
of a rewrite rule means match on any number of templates on the left of it
(so it’s very much like our use of ‘...’ in BNFs). In this case, the
output pattern must also have a ‘...’ after the same identifiers. For
example, here is a definition of a define/rec rewrite rule that is more
convenient to use than an explicit lambda:
(rewrite (define/fun (id x ...) body)
=> (define id
(lambda (x ...) body)))
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 rewrite rule, you can verify that
it’s working with a definition of ackermann and a matching test:
(define/rec (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)
(complete the ackermann definition with a type contract line and a
purpose statement. Note that the contract is ignored in this language, so
just put it in a comment.)
Mutual Recursion
Another limit of the Y combinator as defined above is that it supports
only a single recursive function, but having several mutually recursive
functions can be a very useful feature. As a toy example, consider this
expression that defines and uses two mutually-recursive functions:
(letrec ([even? (lambda (n) (if (= n 0) #t (odd? (- n 1))))]
[odd? (lambda (n) (if (= n 0) #f (even? (- n 1))))])
(even? 123))
We cannot do this directly with the Y combinator, but we can instead define
a single recursive function that packages the two recursive ones:
Note that these definitions always bind all names even when not needed —
but we will do something like this automatically using a rewrite rule.
To make things a little simpler, we will define a rewrite rule called
letfuns, which is a little different than letrec in that it can be
used to bind only functions. For example, instead of
(letrec ([foo (lambda (x) ...body...)]) ...)
we will use
(letfuns ([(foo x) ...body...]) ...)
We will also use a more systematic package of a number of functions: we use
a function that consumes a name of a function (a symbol), and returns the
appropriate function.
To summarize all of this, the following piece of code:
(letfuns ([(even? n) (if (= n 0) #t (odd? (- n 1)))]
[(odd? n) (if (= n 0) #f (even? (- n 1)))])
(even? 123))
Use the even?/odd? above as a test, but note that as is, you will
need to change the body so that you get complete coverage. When you run it
you’ll see that one part is still in red, so you should make the body
exercise it too (hint: and or or would be useful here).
Next, change the rewrite rule so it can work with mutually recursive
functions of any arity. This should be a very easy change. As a test
for your final version, here is an interesting use for several mutually
recursive functions: we implement an automaton (a state machine) that
consumes a string, and returns #t if the parens in the string are
balanced, and if every continuous block of numeric characters is strictly
increasing. Each “state” of this automaton is implemented via a function
(actually, some state is in arguments to these functions), and since states
call out to other states, the functions are mutually recursive. Note also
that tail-calls are crucial here: the compilation of this code will
basically be similar to a program with goto statements to jump around.
;; an extended example
(define scan
(letfuns ([(start str) (loop (string->symbols str) 0)]
[(loop l n) (match l
[(list)
(zero? n)]
[(cons 'open more)
(loop more (add1 n))]
[(cons 'close more)
(and (positive? n) (loop more (sub1 n)))]
[(cons (number: m) more)
(nums more m n)]
[(cons _ more)
(loop more n)])]
[(nums l m n) (match l
[(cons (number: m1) more)
(and (< m m1) (nums more m1 n))]
[else (loop l n)])])
start))
(test (scan "(()123(246x12)) (blah)"))
(test (not (scan "(1232)")))
(test (not (scan "()(")))
(test (not (scan "())")))