CS 3520 Homework 5

Due: Friday, October 6th, 2023 11:59pm

Difficulty:  ★★☆☆

Start with lambda_if0.rhm, which doesn’t already include recursive binding and also doesn’t include * for multiplication.

Part 1 — Syntactic Sugar for Recursive Bindings

Extend the parse function so that it supports a letrec form for recursive function bindings. The parsing precedence for letrec should be lowest.

  <Exp> = ...
        | letrec <Symbol> = <Exp>:
            <Exp>

You must not change the interp function at all.

The October 2 lecture slides spell out how to extend the parser to make letrec work, especially at the end of part 4. You may find the following definition useful:

  def mk_rec_fun:
    '(fun (body_proc):
        let fX = (fun (fX):
                    let f = (fun (x):
                               fX(fX)(x)):
                      body_proc(f)):
          fX(fX))'

The above definition makes sense only if you can keep track of different languages and how they interact. The mk_rec_fun definition above is a Shplait definition. The value of mk_rec_fun is a representation of the concrete syntax of a Moe expression. If you pass mk_rec_fun to parse, you get a Shplait value that is an interpretable representation of a Moe expression.

Example:

  check: interp(parse('letrec f = (fun (n):
                                     if n == 0
                                     | 0
                                     | f(n + -1) + -1):
                         f(10)'),
                mt_env)
         ~is intV(-10)

Note on testing: Normally, when you modify parse, you should add an example/test to illustrate and check the addition. This exercise, however, is one of the rare cases where a parse example/test doesn’t really help, because the expected value for even a simple input is unweildy, and a test can do little more than repeat the implementation. So, you are excused from adding a parse test in this case. An interp test like the one above is more useful.

Part 2 — Implementing a Two-Argument Function in Moe

Define the Shplait constant plus as a representation of the concrete syntax of a Moe expression such that

   interp(parse('($plus)(n)(m)'), mt_env)

produces the same value as

   interp(parse('n + m'), mt_env)

for any Moe numbers n and m.

In other words, you add a Shplait definition

   def plus = '(fun ....)'

to the interpreter program, replacing the .... with something that creates the desired Moe function.

You should not change the interp or parse function for this part.

The suggested shape of plus above uses parentheses around the function. Those parentheses are not required, but they avoid errors it you try using $plus in a template and omit parentheses around the use. We will only try your plus in a context with parentheses around it, though, like in '($plus)(n)(m)'.

Part 3 — Implementing a Recursive Function in Moe

Define the Shplait constant times such that

   interp(parse('($times)(n)(m)'), mt_env)

produces the same value as

   intV(n * m)

for any non-negative integers n and m.

You should not change the interp or parse function for this part.