CEng 242 Homework 2
Due: 22 March 2000

You are given a datatype let_expr with the following definition:

datatype let_expr =
         const of int | var of string | plus of let_expr * let_expr | 
         minus of let_expr * let_expr | letexpr of string list * let_expr;

A let_expr is one of the following:

letexpr([x,y,z],expr) declares the variables [x,y,z] in the scope of the expr. Redeclaration of same variable is possible and local declaration overrides the previous one.

A variable reference var "x" is called bound if "x" is listed in any of the upper level letexpr's in the same path. If a variable reference is not bound it is called a free variable.

a)
Write a function FV that will get a let_expr and return the list of free variables in the let expression. Multiple free occurrences of the same variable symbol should be listed once. Function will have the following type signature:
FV : let_expr -> string list

Examples:

- FV(letexpr(["x"],plus(var "x",const 1)));
- val it = [] : string list;

- FV(plus(var "x",plus(letexpr(["y"],plus(var "z",var "z")),
                       var "z")));
- val it = ["x","z"] : string list;

- FV(letexpr(["x"],plus(letexpr(["w"],plus(var "w",
                                           minus(var "x",
                                                 const 3))),
                        var "w")));
- val it = ["w"] : string list;

- FV(letexpr(["w"],plus(letexpr(["x"],plus(var "w",
                                           minus(var "x",
                                                 const 3))),
                        var "w")));
- val it = [] : string list;

b)
Write a function substitute which will take 2 string parameters x1 and x2 and a let_expr parameter expr1 . It will return a new let_expr expr2 where all free occurences of variable symbol x1 will be replaced by the variable symbol x2 in expr1 . Bound occurences of x1 should remain same.
subsitute : string*string*let_expr -> let_expr

Example:

- substitute("w","a",(letexpr(["w"],plus(letexpr(["x"],plus(var "w",
                                                            minus(var "x",
                                                                  const 3))),
                                         var "w"))));
(* Result should be the same expression *)

- substitute("w","a",(letexpr(["x"],plus(letexpr(["w"],plus(var "w",
                                                            minus(var "x",
                                                                  const 3))),
                                         var "w"))));
(* Result should be: *)
  letexpr(["x"],plus(letexpr(["w"],plus(var "w",
                                        minus(var "x",
                                              const 3))),
                     var "a")))

- substitute("z","a",plus(var "x",plus(letexpr(["y"],plus(var "z",var "z")),
                                       var "z")));
(* Result should be: *)
    plus(var "x",plus(letexpr(["y"],plus(var "a",var "a")),
                      var "a")))