0

I have an environment list which keeps associations between variables and values, such as env = [("x", 1), ("y", 2), ("z", 3), ...]. I also have another substitution list (which is returned by a pattern matching control function) that keeps associations between variables and pattern, such as s = [("v", Var_p "z"), ("w", Var_p "v"), ("u", Var_p "w"), ...]. Let's consider the first pair ("v", Var_p "z"): my function should check the value corresponding to zin the environment, create a new association between v and z's value (i. e. ("v", 3)) and put it into the environment. My code for this function is the following.

fun augment_env ([], e : env) = e
  | augment_env (s :: srest, e : env) =
     let
        val (a, b) = s
     in
        case b of
           Const_p i => [] @ augment_env_with_vars (srest, e)
         | Var_p x =>
            if (exists (e, x)) then (a, lookup (e, x)) :: augment_env_with_vars (srest, e)
     end;

Here, s is the substitution list and exists and lookup are functions which check the existence of a variable in the environment and look for the corresponding value, respectively. The problem with this function is that works fine only for direct associations (in the example, it puts the direct association between v and 3 into the environment). It obviously doesn't work for the transitive associations unless I call it multiple times (which I don't know in advance how many they are). To recall the example, by the end of this function, my environment list should be env = [("x", 1), ("y", 2), ("z", 3), ("v", 3), ("w", 3), ("u", 3), ...].

Could you please give me a hint about how to modify this function to work fine with the transitive associations, too?

Thanks in advance!

4

1 回答 1

1

首先，由于函数，很难给出准确的提示lookup，augment_env_with_vars而且有些类型是未知的。

但是，根据您提供的内容猜测，可以这样做：

拿 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)

结果 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

但是，如果您的替换列表中的任何变量在其定义之前出现，new_env都会失败。要解决这个问题，只需在参考之前扫描替换列表lookup_env：

拿 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)

结果 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

请注意第二个示例中交换的“u”和“w”。

于 2013-06-11T17:31:24.293 回答