First, it is hard to give precise hint since functions lookup
, augment_env_with_vars
and some types are unknown.
However, guessing from what you've provided, it could be done like:
Take 1
type const = int
type var = string
type env = (var * const) list
datatype value = Const_p of const | Var_p of var
exception Not_found
fun lookup_env (e, v) =
case e of
[] => raise Not_found
| (a, b)::xs => if a = v then b else lookup_env (xs, v)
fun new_env (l, e) =
case l of
[] => e
| (a, b)::xs =>
case b of
Const_p _ => new_env (xs, e)
| Var_p b => new_env (xs, e @ [(a, lookup_env (e, b))])
(* test *)
val e = [("x", 1), ("y", 2), ("z", 3)]
val s = [("v", Var_p "z"), ("w", Var_p "v"), ("u", Var_p "w")]
val test = new_env (s, e)
Result 1
val e = [("x",1),("y",2),("z",3)] : (string * int) list
val s = [("v",Var_p "z"),("w",Var_p "v"),("u",Var_p "w")]
: (string * value) list
val test = [("x",1),("y",2),("z",3),("v",3),("w",3),("u",3)]
: (var * int) list
However, if any variable in your substitution list comes before its definition, new_env
will fail. To solve this, just scan the substitution list before referring to lookup_env
:
Take 2
fun lookup_var (l, v) =
case l of
[] => v
| (a, b)::xs =>
case b of
Const_p _ => lookup_var (xs, v)
| Var_p b => lookup_var (if a = v then (l, b) else (xs, v))
fun new_env2 (l, e) =
case l of
[] => e
| (a, b)::xs =>
case b of
Const_p _ => new_env2 (xs, e)
| Var_p b => new_env2 (xs, e @ [(a, lookup_env (e, lookup_var (l, b)))])
(* test *)
val e = [("x", 1), ("y", 2), ("z", 3)]
val s2 = [("v", Var_p "z"), ("u", Var_p "w"), ("w", Var_p "v")]
val test2 = new_env2 (s2, e)
Result 2
val e = [("x",1),("y",2),("z",3)] : (string * int) list
val s2 = [("v",Var_p "z"),("u",Var_p "w"),("w",Var_p "v")]
: (string * value) list
val test2 = [("x",1),("y",2),("z",3),("v",3),("u",3),("w",3)]
: (var * int) list
Note the swapped "u" and "w" in the second example.