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:

• An integer constant
• A string representing a variable
• plus or minus operation of two let_expr's
• A letexpr declaring a list of strings as local variable names on the following let_expr.

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 x₁ and x₂ and a let_expr parameter expr₁ . It will return a new let_expr expr₂ where all free occurences of variable symbol x₁ will be replaced by the variable symbol x₂ in expr₁ . Bound occurences of x₁ 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")))