3

我创建了自己的数据类型：

datatype typ = Bool | Int | Arrow of typ*typ;
(* i.e., Arrow(argType, returnType) *)
(* diMLazy expressions *)
datatype expr = TrueExpr
              | FalseExpr
              | IntExpr of int
              | VarExpr of string
              | PlusExpr of expr*expr
              | LessExpr of expr*expr
              | IfExpr of expr*expr*expr
              | ApplyExpr of expr*expr
              | FunExpr of string*string*typ*typ*expr

使用这些，我需要编写一个函数 isFV，它返回传递给函数的任何自由变量的列表。到目前为止，我的代码是：

fun isFV (exp:expr) =
    let
      val bound_list = [];
    (*Contains returns true if x:string is within a string list.*)
      fun contains (i:string, str_list:string list) =
          foldr(fn (x,y) => i = x orelse y) false str_list;

      fun anaExp (ex:expr, aggr_list:string list) =
          case ex of 
              TrueExpr => []
            | FalseExpr => []
            | IntExpr (a) => []
            | PlusExpr (a, b) => anaExp(a,aggr_list) @ anaExp(b,aggr_list)
            | LessExpr (a, b) => anaExp(a,aggr_list) @ anaExp(b,aggr_list)
            | IfExpr (a, b, c) => anaExp(a,aggr_list) @ anaExp(b,aggr_list) @ anaExp(c,aggr_List)
            | ApplyExpr (a,b) => anaExp(a,aggr_list) @ anaExp(b,aggr_list)
            | FunExpr (a, b, c, d, e) => ??????
            | VarExpr (a) = if(contains (a,aggr_List)) then [] else [a]
    in
      anaExp(exp, bound_list)
    end

anaExp 意味着最初采用一个空列表并递归调用自身，直到它得到一个 VarExpr 项。然后它会将其添加到 aggr_list。

我如何应用 FuncExpr？我知道将 VarExpr 用作字符串类型，但我将什么用作 typ 类型？目前我有：

|   FunExpr (a, b, c, d, e) => anaExp(VarExpr(a),aggr_list) @ anaExp(VarExpr(b),aggr_list) 
                                    @ anaExp(c,aggr_list) @ anaExp(d,aggr_list) @ anaExp(e,aggr_list)

但是我们知道将 typ 传递给 anaExp 会导致类型错误（c 和 d）。

4

2 回答 2

3

[...] 一个函数 isFV，它返回传递给函数的任何自由变量的列表。

以下是一些反馈：

  • 对于返回列表的函数来说，这听起来是个坏名字。这听起来像是一个判断某事物是否为自由变量的谓词函数的好名字。此外，功能似乎有点不清楚。我认为它是任何表达式馈送到isFV.

  • 我认为这FunExpr是一个 lambda。例如，表达式(λx.x+y) 5被编码为ApplyExpr (FunExpr ("x", ?, Int, Int, PlusExpr (VarExpr "x", VarExpr "y")), IntExpr 5)。

    我不确定第二个字符串参数的FunExpr用途。也许它是命名函数或匿名函数？那可能应该使参数之一成为字符串选项...

    如果FunExpr是 lambda，x应该被视为表达式(λx.x+y) x中的自由变量还是绑定变量？显然，x都在不同的时间，但函数应该返回什么？

  • 你有一个很好的基本策略：一个遍历表达式并保留在子表达式中看到的变量的“聚合列表”的递归函数。如果再次看到一个表达式，则第二次不包括在内。

    但是如果一个变量出现在单独的子表达式中，它们都会被包括在内，例如PlusExpr (VarExpr "a", VarExpr "a")会产生["a"] @ ["a"]，因为在子表达式的调用之间聚合列表不会更新。

  • 您似乎没有区分自由变量和绑定变量。假设 aFunExpr实际上创建了一个绑定变量，则递归函数的聚合状态必须稍微复杂一点才能区分：

    一个变量不仅是自由的，因为它是一个变量，还因为它没有作为当前范围内的绑定变量出现（由一组当前绑定的变量维护）。

  • 使用集合类型而不是列表类型可能更容易。根据您的 SML 编译器，可能有一个内置的集合类型。例如，在 SML/NJ 中，您有一个基于列表的集合函子：

    structure Set = ListSetFn(struct
                            type ord_key = string
                            val compare = String.compare
                          end)

这是一个解决方案的模板：

fun getVars expr0 =
  let
    fun gv bound free expr =
        case expr of
            TrueExpr => (bound, free)
          | FalseExpr => (bound, free)
          | IntExpr => (bound, free)
          | VarExpr var => if Set.member (var, bound)
                           then ...
                           else ...
          | PlusExpr (a, b) =>
            let val (bound', free') = gv bound free a
                val (bound'', free'') = gv ... ... b
            in (..., ...) end
          | LessExpr (a, b) => ...
          | IfExpr (a, b, c) => ...
          | ApplyExpr (a, b) => ...
          | FunExpr (var, whatIsThis, _, _, a) =>
            let val bound' = Set.add (bound, var)
                val (bound'', free'') = gv ... ... a
            in (..., ...) end

    val (bound, free) = gv Set.empty Set.empty expr0
  in
    ...
  end

在这，想想

  • 何时更新绑定集和自由集，以及
  • if/when 使用返回的绑定集和自由集。

我如何应用 FuncExpr？

我不明白那个问题。如果您的意思是如何FunExpr在函数中编写子句，则必须指定它试图实现的目标以获得任何合理的反馈。到目前为止，我对这些构造函数应该做什么有一些猜测。

我用什么作为典型类型？

正如 Ionuț 所说，类型对于这个函数的输出并不重要。

于 2017-02-27T14:32:24.980 回答
1

该FunExpr案例应该增加aggr_list函数采用的参数的名称。我假设第一个string是FunExpr函数名，第二个string是参数名。然后，您应该将此参数名称添加到绑定变量列表中，即 ，aggr_list然后在函数的主体上递归。对于这个问题，您可以放心地忽略函数的类型。

于 2017-02-27T12:23:43.777 回答