如何解析Haskell中未知類型的函數？

Question

我是一個Haskell新手，我正在嘗試編寫一個解析器來評估一組簡單的Haskell表達式。然而，當我事先不知道它們是什麼類型時，我遇到了功能上的困難。

假設，例如，我知道我想解析的字符串評估爲一個整數。以下是可能的字符串的一些可能性。

"succ 4"

"head [5,6,7]"

"sum [1,3,1]"

"length [a,b,c,d,e]"

"pred $ sum $ take 3 $ iterate succ 1"

天真什麼，我想這樣的事情最後一個例子做的是這樣的一個過程。

1. 解析出功能pred，從事實，即它的類型爲(Enum a) => a -> a，我的字符串代表一個整數，字符串（美元）之後的其餘部分仍然是一個整數推斷。

2. 解析出函數sum並推導出我正在嘗試評估一個整數列表。

3. 解析出函數take並推斷出我正在尋找一個整數和整數列表。

4. 解析出3並推斷字符串的其餘部分應該是一個整數列表。

5. 解析出iterate並推斷出我正在尋找類型爲Int -> Int的函數和一個整數。

6. 解析出succ和1。

7. 執行評估。

問題在於，在流程的每個階段，我遇到的下一個對象都有很多可能的類型，如示例所示。所以我不能編寫一些通用的解析器來抽出一個函數，並留下代表它的參數（或參數）的字符串。但是如果我必須爲每種可能的函數編寫單獨的解析器，那麼它將很快成爲一場噩夢，尤其是當我必須查看多個變量的函數時。

我意識到它並沒有那麼糟糕，因爲許多函數都是爲幾種不同的類型定義的。但是，例如，如果我說「如果字符串以」succ「開頭，然後將它拉出來並將succ應用於評估字符串的其餘部分」，那麼它會抱怨我應該指定我正在處理Enum類中的類型。但是當我處理不屬於該類的類型時，我遇到了麻煩。

完全披露：我在Graham Hutton的書中使用簡單的解析器來構建我想要構建的東西。所以也許答案是有更高級的解析器可以解決這類問題，而且我應該使用它。

Answer 1

正如在評論中指出的那樣，編譯器和解釋器一般都是分幾次傳遞，並且不要在每次傳遞中都做太多工作。

通常解析是一次通過，也許在前面是lexing。接下來是類型檢查，然後是編譯器翻譯爲目標語言（通常需要多次傳遞），或者解釋器評估。對於快速而骯髒的實驗或動態語言，可以省略類型檢查。

您應該首先定義一個抽象語法樹來表示已分析的表達式 - Haskell代數數據類型對此非常理想。例如，您的"succ 4"可能會解析爲像Apply (Symbol "succ") (Int 4)這樣的術語。您只需要本地信息即可生成此信息，而不需要周圍值的類型 - 例如4轉換爲Int 4只是因爲它是一個數字而不是符號。

然後，您可以定義類型檢查器以在語法樹上工作，或者直接跳轉到評估它並檢查類型是否有意義。恰當地類型檢查Haskell這樣的語言並不簡單 - 如果你真的想這麼做，那麼經典的論文"Typing Haskell in Haskell"可能是最好的起點。