ocaml中的類型建模

Question

我有一組Ocaml類型來表示一個語法樹。有類型的程序，類，方法，表達式等。例如，一種方法是通過一個記錄類型是這樣表示的：

type method = { return:typeid; args:typeid list; body:expr } 

它包括一個返回類型，一種類型的每個參數，並且主體定義。我想鍵入檢查語法樹，併產生一種新的樹，看起來非常像舊的樹，除了每個表達式都有一個明確的typeid（僅在類型檢查後知道）與它相關聯。

一種選擇是聲明一組平行的類型：

type typed_expr = expr * typeid 
type typed_method = { return:typeid; args:typeid list; body:typed_expr } 
(* ... there are more types *) 

的typed_method是必要的，因爲typed_expr是不同的類型。但我不想爲未檢查的AST和檢查的AST維護兩組幾乎相同的類型。

另一種方法是如下定義表達式：

type expr = {...; typ:typeid option} 

這使我使用相同的類型定義爲輸入既檢驗器和輸出。區別在於我將大量檢查移動到檢查的語法樹的使用者代碼中。這裏有一個合同，typ字段永遠不會在類型檢查器輸出中爲None，並且在類型檢查器輸入中始終爲None。

現在，每次我使用鍵入的樹時，訪問typ字段內部值的唯一方法是首先檢查它是否爲None（它不應該是）。這使得所有後來的消費者代碼因爲額外的檢查而變得醜陋。

這些方法都不令我感到滿意。你會如何模型？

Answer 1

第一個比第二個更好：可能有兩組數據類型看起來很相似，但是很安全：第二種方法需要處理的不變量可以通過類型來解決。實際上OCaml編譯器實現採用這種方法：請參閱parsetree.mli和typedtree.mli。

第一和第二之間，你可能要定義的數據類型，其typ字段參數：

type 'typ expr = { ...; typ : 'typ } 

然後你可以使用unit expr對於非類型化AST和typeid expr爲類型化的AST。

我仍然更喜歡第一種方法爲不同類型和不同類型的數據類型設置不同的集合，因爲這兩個世界的AST通常會比類型有一些其他差異。