純函數編譯器如何用類型信息註釋AST？

在語法分析階段，命令式編譯器可以在構建期間已經包含已經包含設置爲null的type字段的節點構建AST，然後在語義分析階段，通過分配聲明來填充類型/推斷類型到type字段中。純函數編譯器如何用類型信息註釋AST？

純粹的功能性語言如何處理這個問題，在那裏你沒有奢侈的任務？是否將無類型AST映射到類型豐富的AST的另一種種類？這是否意味着我需要爲每個AST節點定義兩種類型，一種用於語法階段，另一種用於語義階段？

是否存在純粹的函數式編程技巧，可以幫助編譯器編寫者解決這個問題？

來源

2015-04-12 fredoverflow

缺乏分配如何導致問題，完全是？我不確定我是否遵循... – MathematicalOrchid

它是AST的事實並不特別;這個「問題」與命令程序員使用變異來更新結構的其他情況沒有什麼不同。 – Ben

@Ben Right，但有趣的是它是一個基於節點的遞歸結構。 – fredoverflow

像關係數據庫打交道時的情況下，在函數式編程它往往是一個好主意，不要把一切都在一個單一的數據結構。

特別是，可能沒有數據結構是「AST」。

最有可能的是，會有表示解析表達式的數據結構。處理類型信息的一種可能方式是在解析過程中已經爲樹的每個節點分配了一個唯一的標識符（如整數），並且有一些合適的數據結構（如散列圖），將這些節點標識符與類型關聯起來。那麼類型推斷的工作就是創建這張地圖。

來源

2015-04-19 11:14:24 Ingo

有幾種方法可以對此進行建模。您可以使用同一種可爲空的數據字段的在你的當務之急情況：

data Exp = Var Name (Maybe Type) | ... 
parse :: String -> Maybe Exp  -- types are Nothings here 
typeCheck :: Exp -> Maybe Exp -- turns Nothings into Justs

甚至，使用更精確的類型

data Exp ty = Var Name ty | ... 
parse :: String -> Maybe (Exp()) 
typeCheck :: Exp() -> Maybe (Exp Type)

來源

2015-04-12 10:36:27 chi

我通常重寫源（或已經有幾個步驟降低）AST轉換爲新格式，用一對(tag, expression)替換每個expression節點。

標記是唯一的數字或符號，然後由下一個從AST中派生類型方程的通道使用。例如，a + b將產生類似於{} numeric(Tag_b).equals(Tag_a, Tag_b).equals(Tag_e, Tag_a).}。

然後解決類型方程（例如，通過簡單地將它們作爲Prolog程序運行），並且如果成功，所有標記（它們是該程序中的變量）現在都綁定到具體類型，如果不是，它們'留下來作爲類型參數。

在下一步中，我們先前的AST再次被重寫，這次用所有推斷的類型信息替換標籤。

整個過程是一系列純粹的重寫，無需在AST中破壞性地替換任何東西。典型的編譯流水線可能需要幾十次重寫，其中一些更改AST數據類型。

來源

2015-04-12 11:45:48

我不能因爲它是應該做怎麼說，但我沒有做到這一點在F＃中的C＃編譯器here

的方法是根本 - 建立從源頭的AST，留下的東西像類型信息無約束 - 所以AST.fs基本上是AST類型名稱，函數名稱等字符串。

當AST開始被編譯爲（在本例中）.NET IL時，我們最終得到了更多的類型信息（我們在源中創建類型 - 讓我們調用這些類型存根）。然後這給我們提供了創建方法存根所需的信息（代碼可能有簽名，包括類型存根以及內置類型）。從這裏我們現在有足夠的類型信息來解析代碼中的任何類型名稱或方法簽名。

我將它存儲在文件TypedAST.fs中。我一次性做到這一點，但這種做法可能太天真了。

現在我們有了一個完整的AST，然後可以編譯它，完全分析它，或者任何你喜歡的東西。

所以在回答問題「這是否意味着我需要爲每個AST節點定義兩種類型，一種用於語法階段，一種用於語義階段？」，我無法確切地說明是這種情況，但這當然是我做的，似乎是MS與Roslyn做了什麼（雖然他們基本上裝飾了類型信息IIRC的原始樹）

「10是否有純粹的函數式編程技巧可以幫助編譯器有這個問題的作者？「鑑於AST基本上是鏡像在我的情況下，它將是可能的使其通用和轉換樹，但代碼可能結束（更多）可怕。

即

 
type 'type AST; 
| MethodInvoke of 'type * Name * 'type list 
| ....

來源

2015-04-13 14:48:18

純函數編譯器如何用類型信息註釋AST？

回答

相關問題