如何繪製類型推斷解析樹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。

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類型。因此，我們將x，即t3，int以及y的類型即t5替換爲string。我們這樣做是無處不在：

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必須全部相同。我們使用t7，其中我們看到t8和t9。

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 

最後，類型的fft0必須與分配給所述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 

而這就是你的最終結果。