CSE 340 HW 2
Due Friday, Feb 6th

Here is a BNF for a language. called MiniScheme (or MS)  that looks a lot like the Scheme language.  In this BNF, nonterminals, such as <var> and <expression> are in angle brackets. Curly braces {} surround the parts of the grammar that could appear 0 or more times.

Note that some expressions such as (+ (lambda (x) x)) are syntactically correct according to this grammar, but will produce a runtime error.

<expression> ::= <var>
              | (lambda (<var>) <expression>) 
              | (<expression> <expression>)
              | <number>
              | (<prim> {<expression>})
              | (let (<var> <expression>) <expression>)

<prim> ::= + | * | -

The difference between MS and Scheme is the let expression. In Scheme, lets may bind a number of variables simultaneously, but this version of let only binds one variable at a time. Consequently, MS's let needs fewer parentheses. It is a little more difficult to program in this language, but the functions that you will write for this assignment will be simpler.

This archive contains an abstract syntax, lexer and parser for the MS language. The file scope.ml contains many operations over the abstract syntax of MS, but these operations are currently unimplemented.  You can find more details about these operations in Section 1.3 of your textbook, EOPL. Your job is to fill them in. You can use the Makefile in the archive to compile and test your program. After unpacking the archive to a directory, do the following:
    touch .depend
    make depend
    make
    main < test.ss 

Be sure to add more tests to test.ss to test your operations. For this assignment, you only need to submit your version of the file scope.ml. You should not need to modify any other  files.

  1. Write and test the functions bound_vars and free_vars that produce a set of the free and bound variables found in a MS expression. You should use the Set module from the O'Caml standard library.
     
  2. Write and test the function is_closed that returns whether a MS expression contains any free variables.
     
  3. Write and test the function subst that given any expression exp, an expression subst_exp and a variable subst_var, iterates
    over exp and substitutes subst_exp for each free occurrence of subst_var. You may assume that the free variables of subst_exp are different from the bound variables of exp.
     
  4. Write and test the function eval that reduces a MS expression to a value by reducing each function application, let or
    primitive expression. You may assume that the given expression is closed.
     
  5. Two expressions are alpha-equivalent if they are the same except that their bound variables have different names. The bound variables must be consistently renamed.

    For example, (lambda (x) x) and (lambda (y) y) are alpha-equivalent, but (lambda (x) x) and (lambda (y) x) are not.

    Note that the free variables of an expression must all be the same.

    (lambda (x) (x y)) and (lambda (x) (x z)) are not alpha-equivalent because the free variables y and z differ.

    Write and test the function is_aeq that takes two expressions and determines whether they are alpha-equivalent to each other.

Last modified: 01/28/2004 09:25 AM