Homework #4: Flang++
Out: Friday, February 3rd, Due: Friday, February 10th, 4:30pm

The language for this homework is:

#lang plait

Introduction

In this assignment you will extend the FLANG environment based interpreter to handle any number of arguments to a function.

Begin by downloading the template file to serve as the basis of your work. Compared to the interpreter we studied in class, this one uses a slightly different surface syntax, closer to that of Racket. In particular the parameters of a lam form are enclosed in an extra set of parens, so e.g. the identity function is written {lam {x} x}.

Update the evaluator to handle multiple arguments

You are given a parser that can handle any number of parameters in a lam form, and any number of arguments in a function call. In this part your task is to extend the interpreter (without modifying the parser) to correctly handle the following tests. There are several possible approaches. The recommended approach is to explicitely add each parameter (id) / argument (value) pair to the environment before evaluating the function body. You have to take some care to evaluate all of the arguments in the calling environment.

(module+ test
  ;; test no arguments
  (test (run `{let1 {g {lam {} 42}}
                    {g}})
        42)

  ;; test multiple arguments, lexical scope
  (test (run `{let1 {z 3}
                    {let1 {f {lam {x y} {/ {- x y} z}}}
                          {let1 {z 2}
                                {f 15 12}}}})
        1)

  ;; higher order function
  (test (run `{let1 {identity {lam {x} x}}
                    {let1 {plus {lam {x y} {+ x y}}}
                          {{identity plus}  123 1}}})
        124)

  ;; higher order function with multiple arguments
  (test (run `{let1 {apply {lam {f x y} {f x y}}}
                    {let1 {plus {lam {x y} {+ x y}}}
                          {apply plus 123 1}}})
        124)
  )

Write duplicate-symbol?

In the next part of the assignment you will want a function to check a list of symbols for duplicates. This can be done efficiently by using immutable hash tables and tail recursion. This is very similar to the census function in the hash table mini-tutorial. You may also find the mini-tutorial on implementing sets using hash tables helpful, but you don’t need to be that fancy. More specifically write a function duplicate-symbol? that passes the following tests:

(module+ test
  (test (duplicate-symbol? '()) #f)
  (test (duplicate-symbol? '(a b c)) #f)
  (test (duplicate-symbol? '(a b c d b e)) #t))

Check for duplicate parameters

Use your duplicate-symbol? function to check functions for duplicate argument names. You can add your check to the parser (that’s what I did) or to interp. In either case use the word "duplicate" in your error message so the following test passes.

(test/exn (run `{lam {x y x} 42}) "duplicate")

Finally