將非類型化的Lisp數據映射到編譯函數中使用的類型二進制格式

Question

背景：我在Haskell中編寫了一個玩具Lisp（Scheme）解釋器。我希望能夠使用LLVM編譯代碼。我已經花了幾天時間想出了將非類型化的Lisp值提供給編譯函數的各種方式，這些編譯函數期望知道數據到達它們的格式。我覺得我不是第一個需要解決這個問題的人。

問題：將無類型數據映射爲有效二進制格式的歷史成功方法是什麼？

附錄：事實上，我知道大約有十幾種不同類型的數據中的哪一種，我只是不知道在編譯時哪一種可能被髮送到函數。函數本身需要一種方法來確定它得到了什麼。

Answer 1

您的意思是，「我只是不知道哪個[類型]可能會被髮送到功能運行時」？這不是數據沒有輸入;當然1和'()有不同的類型。相反，數據不是靜態類型的，即在編譯時不知道給定變量的類型是什麼。這被稱爲dynamic typing。

你是對的，你不是第一個需要解決這個問題的人。規範的解決方案是將標籤中的每個運行時值與其類型進行比較。例如，如果你有一打的類型，它們編號如下所示：

• 0 =整數
• 1 = cons對
• 2 =向量
• 等

一旦已經完成了這項工作，爲標籤預留每個單詞的前四位。然後，每當兩個對象傳入+時，首先執行一個簡單的位掩碼來驗證兩個對象的前四位是0b0000，即它們都是整數。如果不是，則跳轉到錯誤消息;否則，您繼續添加，並確保結果也被相應標記。

這種技術實質上是使每個運行時值都是手動的 - tagged union，如果您已經使用了C，那麼您應該很熟悉它。實際上，它也就像一個Haskell數據類型，除了在Haskell中標記更多抽象。

我猜你熟悉指針，如果你想編寫一個Scheme編譯器。爲了避免限制可用內存空間，使用底部（最低有效）四位而不是頂部可能更爲合理。更好的是，因爲對齊的雙字指針在底部已經有三個毫無意義的位，所以只要將引用的位標記爲您的標記，只要取消引用實際地址而不是標記的位。

這有幫助嗎？

Answer 2

您的默認解決方案應該是簡單的標記聯合。如果你想把你的打字範圍縮小到更具體的類型，你可以做到 - 但它不會再是「玩具」。要看的東西叫abstract interpretation。

這種優化很少成功實施，其中V8可能是最普遍的。在計劃世界中，最積極優化的實施方案是Stalin。