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.
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;
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")))