CS 3520 Homework 2

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

Difficulty:  ★★★☆

Part 1 — Maximum

Start with the interpreter with functions, and add a max operation that takes two numbers and returns the larger of them. The syntax for max should be similar to a function call.

Since you must change the Exp datatype, and since different people may change it in different ways, you must update the parse function, which accepts an syntax object and produces an Exp value.

Some examples:

  check: interp(parse('max(1, 2)'),
                [])
         ~is 2
  check: interp(parse('max(4+5, 2+3)'),
                [])
         ~is 9

Part 2 — Functions that Accept Multiple Arguments

Extend the interpreter to support multiple or zero arguments to a function, and multiple or zero arguments in a function call.

For example,

fun area(w, h): w * h

defines a function that takes two arguments, while

fun five(): 5

defines a function that takes zero arguments. Similarly,

area(3, 4)

calls the function area with two arguments, while

five()

calls the function five with zero arguments.

At run-time, a new error is now possible: function application with the wrong number of arguments. Your interp function should detect the mismatch and report an error that includes the words “wrong arity”.

To support functions with multiple arguments, you’ll have to change fd and appE and all tests that use them. When you update the parse function, note that match supports ... in a pattern to indicate zero or more repetitions of the preceding pattern, and so do templates, and syntax_to_list recognizes []-shaped syntax. So '$sym($arg, ...)' matches any number of arguments, and syntax_to_list('[$arg, ...]') converts the arguments into a list of syntax objects. Beware of putting the multi-argument application pattern too early in parse, since that pattern is likely to match other forms. In addition, you’ll need to update the parse_fundef function that takes one quoted fun form and produces a FunDef value.

Some examples:

  check: interp(parse('f(1, 2)'),
                [parse_fundef('fun f(x, y): x + y')])
         ~is 3
  check: interp(parse('f() + f()'),
                [parse_fundef('fun f(): 5')])
         ~is 10
  check: interp(parse('f(2, 3)'),
                [parse_fundef('fun f(x, y): y + x + x')])
         ~is 7
  check: interp(parse('f(1)'),
                [parse_fundef('fun f(x, y): x+y')])
         ~raises "wrong arity"

Remember that Shplait provides map, which takes a function and a list, and applies the function to each element in the list, returning a list of results. For example, if ars is a list of syntax objects to parse, map(parse, ars) produces a list of ExpEs by parsing each syntax object.

But also remember that map doesn’t work for everything. Sometimes, when you have a list to process (or maybe two lists in parallel), then you need to write a new function using the template for lists.

Part 3 — Function Argument Checking (CS 6520)

This exercise is required only for CS 6520 students. CS 3520 students are welcome to complete the exercise, but it does not count for extra credit.

A function is ill-defined if two of its argument names are the same. To prevent this problem, update your parse-fundef function can detect this problem and report a “bad syntax” error.

For example, parse_fundef('fun f(x, x): x') must report a “bad syntax” error, while parse_fundef('fun f(x, y): x') should produce a FunDef value.