什麼是Spineless Tagless G-machine?

https://www.microsoft.com/en-us/research/wp-content/uploads/1992/04/spineless-tagless-gmachine.pdf

如果可以的話，能不能詳細說下跟The Implementation of Functional Programming Language的G-machine（有spine，tag）的區別？

這個問題我一起也問過，後來讀了SPJ的那兩篇論文大概就明白了：

G-machine：就是graph machine圖計算機，FP的程序基本上都可以用一個表達式的圖表示，圖計算機就是對這個圖求值的機器，總的說來對圖的求值是一個不停合併圖上的節點生產新節點的過程。例如：

let x = 2 + 3 in x * x


一個簡單的想法是先計算出5，然後創建一個新的節點5 * 5，然後再對這個節點求值，於是求值過程中就產生了很多臨時的、立即進入的節點，這些中間節點也被叫做是spine，求值過程是沿著spine完成的。

但是這樣就產生了很多額外的allocation，在The Spineless_G-machine那篇論文里，SPJ詳細描述了一種可以避免創建圖上的中間節點的方案。

首先有個基礎叫做lambda lifting，這是來自John Hughes的關鍵性觀察：我們可以把程序里，很多捕捉了外圍綁定的閉包函數中的這些綁定，轉換成函數的參數，從而消除閉包，得到的這個函數就可以自由脫離書寫的作用域，被靜態的編譯到機器碼里。這些被float out的函數也叫supercombinator（我擦，搞得跟超級賽亞人一樣什麼鬼）。然後一個程序就是一堆supercombinator的組合，整個程序的執行就和傳統的順序執行大大相似了，把main函數這個表達式求個值，遇到supercombinator就是一次call。

如果我們完全這樣順序執行會遇到一個問題，就是共享節點的冗餘計算問題：剛剛的例子里，如果我們不創建新的節點，順序計算完了第一個x，第二個x還會再被算一遍。於是SPJ提出了Spineless reduction的概念：我們只有當面臨需要重複計算的情況時，才去創建節點，不然就一路順序算下去。論文和核心思路是把圖的更新操作和共享聯繫起來，如果一個計算的結果沒有被共享，那就直接放到寄存器／棧上繼續執行下去，否則要更新對應的節點。

tagless是另一個非常有趣的設計：傳統的圖推導機需要區分thunk和WHNF，然後在求值過程中區別對待，但是SPJ意識到，WHNF不過是一段entry code比較特別的計算，於是他統一了thunk和WHNF的內存表示，由一個統一的header指針直接指向進入閉包（SPJ用閉包統一指代以上兩種情況）的機器碼，這部分內容在GHC wiki上有詳細的解釋：Commentary/Rts/Storage/HeapObjects - GHC ， 感興趣的讀者不妨仔細閱讀，非常的inspiring。

在tagless的基礎上，人們又進一步做了point tagging之類的優化，fascinating！