CS 3520 Homework 3

Due: Friday, September 15th, 2023 11:59pm

Difficulty:  ★★☆☆

Part 1 — Booleans

Start with the interpreter with function values, and extend the implementation to support boolean literals, an equality test, and a conditional form:

  <Exp> = ....
        | #true
        | #false
        | <Exp> == <Exp>
        | if <Exp> | <Exp> | <Exp>

The == operator should only work on number values, and if should only work when the value of the first subexpression is a boolean. Report a “not a number” error if a subexpression of == produces a non-number value, and report a “not a boolean” error when the first subexpression of if does not produce a boolean. The if form should evaluate its second subexpression only when the first subexpression’s value is true, and it should evaluate its third subexpression only when the first subexpression’s value is false. The precedence of == should be lower than +, and if should have the lowest precedence like let.

Note that you not only need to extend Exp with new kinds of expressions, you will also need to add booleans to Value.

For example,

#true

should produce a true value, while

if #true
| 1 + 2
| 5

should produce 3, and

if 1
| 2
| 3

should report a “not a boolean” error.

As usual, update parse to support the extended language.

More examples:

  check: interp(parse('1 + 2 == 3'),
                mt_env)
         ~is interp(parse('#true'),
                    mt_env)
  check: interp(parse('if 2 == 1 + 1 
                       | 7 
                       | 8'),
                mt_env)
         ~is interp(parse('7'),
                    mt_env)
  check: interp(parse('if #false 
                       | 1 + (fun (x): x) 
                       | 9'),
                mt_env)
         ~is interp(parse('9'),
                    mt_env)
  check: interp(parse('if #true 
                       | 10 
                       | 1 + (fun (x): x)'),
                mt_env)
         ~is interp(parse('10'),
                    mt_env)
  check: interp(parse('if 1 | 2 | 3'),
                mt_env)
         ~raises "not a boolean"

Part 2 — Hiding Variables

Add an unlet form (lowest precedence) that hides the nearest visible binding (if any) of a specified variable, but lets other bindings through. For example,

let x = 1:
  unlet x:
    x

should raise a “free variable” exception, but

let x = 1:
  let x = 2:
    unlet x:
      x

should produce 1. If there’s no visible binding of a variable around an unlet of the variable, the unlet does not hide anything (but it’s not an error).

As before, you must update the parse function.

Some examples:

  check: interp(parse('let x = 1:
                         unlet x:
                           x'),
                mt_env)
         ~raises "free variable"
  check: interp(parse('let x = 1:
                         x + (unlet x:
                                1)'),
                mt_env)
         ~is interp(parse('2'), mt_env)
  check: interp(parse('let x = 1:
                         let x = 2:
                            x + (unlet x:
                                   x)'),
                mt_env)
         ~is interp(parse('3'), mt_env)
  check: interp(parse('let x = 1:
                         let x = 2:
                           let z = 3:
                              x + (unlet x:
                                     x + z)'),
                mt_env)
         ~is interp(parse('6'), mt_env)
  check: interp(parse('let f = (fun (z):
                                  let z = 8:
                                    unlet z:
                                      z):
                         f(2)'),
                mt_env)
         ~is interp(parse('2'), mt_env)

Part 3 — Thunks

A thunk is like a function of zero arguments, whose purpose is to delay a computation. Extend your interpreter with a delay form that creates a thunk, and a force form that causes a thunk’s expression to be evaluated:

  <Exp> = ....
        | delay: <Exp>
        | force(<Exp>)

A thunk is a new kind of value, like a number, function, or boolean.For parsing, delay has lowest precedence. The force form has a precedence like function calls, but it should be preferred by the parser over a function-call form, so it can be matched just before a function-call form in parse.

For example,

delay: 1 + (fun (x): x)

produces a thunk value without complaining that a function is not a number, while

force(delay: 1 + (fun (x): x))

triggers a “not a number” error. As another example,

let ok = (delay: 1 + 2):
  let bad = (delay: 1 + #false):
    force(ok)

produces 3, while

let ok = (delay: 1 + 2):
  let bad = (delay: 1 + #false):
    force(bad)

triggers a “not a number” error.

More examples:

  check: interp(parse('force(1)'),
                mt_env)
         ~raises "not a thunk"
  check: interp(parse('force(if 8 == 8 | (delay: 7) | (delay: 9))'),
                mt_env)
         ~is interp(parse('7'),
                    mt_env)
  check: interp(parse('let d = (let y = 8:
                                  delay: y + 7):
                         let y = 9:
                           force(d)'),
                mt_env)
         ~is interp(parse('15'),
                    mt_env)

Note: In some languages, delay creates a promise. A promise is like a thunk, but when a promise is forced multiple times, the result from the first time is remembered and returned all the other times, so that the expression in a promise is evaluated at most once. We’re not concerned with that facet of delay and force, for now.


Last update: Thursday, November 9th, 2023
mflatt@cs.utah.edu