如何为sml绘制类型推断分析树

Question

所以我正在练习期末考试，有一个问题要求我为这个sml代码画一个语法分析树：

fun ff f x y = if (f x y) then (f 3 y) else (f x "zero")

val ff = fn : (int -> string -> bool) -> int -> string -> bool

我知道如何获取此类型，但不太确定如何绘制解析树来表示它。

对于我的家庭作业，我们确实做了这样的问题，这要简单得多：image for my other homework

Answer 1

我能想到的最简单的方法是稍微重新格式化代码，然后基本上将每个子表达式放在自己的行上。儿童用增加的缩进来表示。

让我们以你的例子为例：

fun ff f x y = if (f x y) then (f 3 y) else (f x "zero")

首先，我们需要做一点去除垃圾的工作。上面的代码等同于：

val ff =
  fn f =>
    fn x =>
      fn y =>
        if (f x y) then (f 3 y) else (f x "zero")

现在，让我们将每个子表达式放在自己的行上(在这个特定的示例中，段落是多余的；没有它们，一切都很好)：

val ff =
  fn f =>
    fn x =>
      fn y =>
        if
          f
            x
              y
          then
            f
              3
                y
          else
            f
              x
                "zero"

最后，让我们为每个子表达式附加一个类型，但是让我们对我们还不知道的类型使用类型变量。请注意，对于相同的事件，我们使用相同的类型变量。例如，x的类型为t3 everywhere。

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | t1 -> t2
    fn x =>            | t3 -> t4
      fn y =>          | t5 -> t6
        if             | t7 (* the type of the whole `if` expression *)
          f            | t1
            x          | t3
              y        | t5
          then         | t8 (* the type of the whole `then` part *)
            f          | t1
              3        | int
                y      | t5
          else         | t9 (* the type of the whole `else` part *)
            f          | t1
              x        | t3
                "zero" | string

然后，您可以通过注意某些类型变量是等价的或在某些上下文中使用它们来进一步简化。例如，从这三个对f的调用中

• f x y
• f 2 y
• f x "zero"

我们可以推断出x必须是int类型，y必须是string类型。所以，让我们用int替换x的类型，即t3，用string替换y的类型，即t5。我们在任何地方都这样做：

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | t1 -> t2
    fn x =>            | int -> t4
      fn y =>          | string -> t6
        if             | t7
          f            | t1
            x          | int
              y        | string
          then         | t8
            f          | t1
              3        | int
                y      | string
          else         | t9
            f          | t1
              x        | int
                "zero" | string

此外，f还用作每次都会传递int的函数。结果也被用作函数，并被传递给一个string。这意味着t1，也就是赋值给f的类型变量，必须是int -> string -> r0类型，对于一些我们还不知道的r0。让我们用int -> string -> r0替换所有出现的t1。

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> r0) -> t2
    fn x =>            | int -> t4
      fn y =>          | string -> t6
        if             | t7
          f            | int -> string -> r0
            x          | int
              y        | string
          then         | t8
            f          | int -> string -> r0
              3        | int
                y      | string
          else         | t9
            f          | int -> string -> r0
              x        | int
                "zero" | string

但请注意，r0必须被视为bool，因为f x y的结果用于if表达式的条件部分，所以让我们到处用bool替换r0：

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> bool) -> t2
    fn x =>            | int -> t4
      fn y =>          | string -> t6
        if             | t7
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | t8
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | t9
            f          | int -> string -> bool
              x        | int
                "zero" | string

接下来，整个if表达式的类型必须与then部件的类型相同，该类型必须与else部件的类型相同。因此t7、t8和t9必须都是相同的。让我们在看到t8和t9的地方使用t7。

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> bool) -> t2
    fn x =>            | int -> t4
      fn y =>          | string -> t6
        if             | t7
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | t7
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | t7
            f          | int -> string -> bool
              x        | int
                "zero" | string

接下来，t7必须是bool类型，因为f 3 y和f x "zero"的类型都是bool

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> bool) -> t2
    fn x =>            | int -> t4
      fn y =>          | string -> t6
        if             | bool
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | bool
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | bool
            f          | int -> string -> bool
              x        | int
                "zero" | string

接下来，t6也必须是一个bool，因为我们将返回if表达式的结果：

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> bool) -> t2
    fn x =>            | int -> t4
      fn y =>          | string -> bool
        if             | bool
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | bool
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | bool
            f          | int -> string -> bool
              x        | int
                "zero" | string

接下来，t4必须是string -> bool类型，因为这就是它主体的类型：

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> bool) -> t2
    fn x =>            | int -> string -> bool
      fn y =>          | string -> bool
        if             | bool
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | bool
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | bool
            f          | int -> string -> bool
              x        | int
                "zero" | string

什么是t2？它必须是主体的类型，即int -> string -> bool

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | t0
  fn f =>              | (int -> string -> bool) -> int -> string -> bool
    fn x =>            | int -> string -> bool
      fn y =>          | string -> bool
        if             | bool
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | bool
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | bool
            f          | int -> string -> bool
              x        | int
                "zero" | string

最后，ff的类型t0必须与分配给ff的值的类型相同。所以：

Subexpression          | Type
---------------------- | ------------------------------------------
val ff =               | (int -> string -> bool) -> int -> string -> bool
  fn f =>              | (int -> string -> bool) -> int -> string -> bool
    fn x =>            | int -> string -> bool
      fn y =>          | string -> bool
        if             | bool
          f            | int -> string -> bool
            x          | int
              y        | string
          then         | bool
            f          | int -> string -> bool
              3        | int
                y      | string
          else         | bool
            f          | int -> string -> bool
              x        | int
                "zero" | string

这就是你的最终结果。