types - 返回 SML 中的自由(未绑定(bind))变量列表

Question

我已经创建了自己的数据类型:

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

Answer 1

[...] a function isFV that returns a list of any free variables passed into the function.

这里是一些反馈:

• 对于返回列表的函数来说，这个名字听起来不太好。这听起来像是判断某事是否 是自由变量的谓词函数的好名字。此外，功能 似乎有点不清楚。我假设它是提供给 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 中的自由变量还是绑定(bind)变量>?很明显，x 都在不同的时间，但是函数应该返回什么？

• 您有一个很好的基本策略:一个遍历表达式并保留在子表达式中出现的变量的“聚合列表”的递归函数。如果再次出现一个表达式，则不会第二次包含它。

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

• 您似乎没有区分自由变量和绑定(bind)变量。假设 FunExpr 实际上创建了一个绑定(bind)变量，您的递归函数的聚合状态必须更复杂一些才能捕捉到区别:

  一个变量不仅是自由的，因为它是一个变量，还因为它在当前范围内没有作为绑定(bind)变量出现(由一些当前绑定(bind)变量集维护)。

• 使用集合类型可能比使用列表类型更容易。根据您的 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

在此，想到

• 何时更新绑定(bind)集和自由集，以及
• 是否/何时使用返回的绑定(bind)和自由集。

How do i apply the FuncExpr?

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

what do i use as a typ type?

正如 Ionuş 所说，类型对于此函数的输出无关紧要。