在C和Haskell之間的相互遞歸中編譯尾部調用優化

我正在用Haskell中的外部函數接口進行試驗。我想實施一個簡單的測試，看看我能否做到相互遞歸。所以，我創建了下面的Haskell代碼：在C和Haskell之間的相互遞歸中編譯尾部調用優化

module MutualRecursion where 
import Data.Int 

foreign import ccall countdownC::Int32->IO() 
foreign export ccall countdownHaskell::Int32->IO() 

countdownHaskell::Int32->IO() 
countdownHaskell n = print n >> if n > 0 then countdownC (pred n) else return()

需要注意的是遞歸的情況是countdownC一個電話，所以這應該是尾遞歸。

在我的C代碼，我有

#include <stdio.h> 

#include "MutualRecursionHaskell_stub.h" 

void countdownC(int count) 
{ 
    printf("%d\n", count); 
    if(count > 0) 
     return countdownHaskell(count-1); 
} 

int main(int argc, char* argv[]) 
{ 
    hs_init(&argc, &argv); 

    countdownHaskell(10000); 

    hs_exit(); 
    return 0; 
}

這同樣是尾遞歸。於是我做一個

MutualRecursion: MutualRecursionHaskell_stub 
    ghc -O2 -no-hs-main MutualRecursionC.c MutualRecursionHaskell.o -o MutualRecursion 
MutualRecursionHaskell_stub: 
    ghc -O2 -c MutualRecursionHaskell.hs

與make MutualRecursion編譯。

And ...運行時，打印後出現段錯誤8991。就像一個測試，以確保海合會本身可以相互遞歸處理TCO，我做

void countdownC2(int); 

void countdownC(int count) 
{ 
    printf("%d\n", count); 
    if(count > 0) 
     return countdownC2(count-1); 
} 

void countdownC2(int count) 
{ 
    printf("%d\n", count); 
    if(count > 0) 
     return countdownC(count-1); 
}

而且做得很細。它也適用於C語言和Haskell中的單一遞歸情況。

所以我的問題是，有沒有辦法向GHC表明對外部C函數的調用是尾遞歸？我假設堆棧框架確實來自Haskell對C的調用，而不是其他方式，因爲C代碼非常清楚地返回了函數調用。

來源

2015-11-03 Crazycolorz5

我相信跨語言的C-Haskell尾部調用非常非常難以實現。

我不知道確切的細節，但C運行時和Haskell運行時是很大程度上不同。造成這種差別的主要因素，據我所看到的，分別是：

不同的模式：純功能VS勢在必行
垃圾收集VS手動內存管理
懶語義VS嚴格的一個

考慮到這種差異，在語言邊界內可能存在的優化類型接近於零。理論上，也許可以創建一個特別的C運行時和一個Haskell運行時，這樣一些優化是可行的，但是GHC和GCC不是以這種方式設計的。

只是爲了顯示的電位差一個例子，假設我們有以下的Haskell代碼

p :: Int -> Bool 
p x = x==42 

main = if p 42 
     then putStrLn "A"  -- A 
     else putStrLn "B"  -- B

一可能實施方案main的可能是以下方面：A

推地址在堆棧上
將堆棧上的B的地址推入
pus ħ42堆棧上
跳到p
A：打印「A」，跳轉到結束
B：打印「B」，跳轉到結束

而p是這樣實現的：

號碼：從棧
噗xb從堆棧
彈出a從堆棧
測試x對42
如果相等，跳轉到a
跳轉到b

注p如何調用與返回地址，每個可能的結果一個。這與C不同，C的標準實現只使用一個返回地址。跨越邊界時，編譯器必須考慮到這種差異並進行補償。

上面我也沒有說明當p的參數是一個thunk的情況，以保持簡單。 GHC分配器也可以觸發垃圾收集。

請注意，上述虛構實現過去由GHC（所謂的「推入/進入」STG機器）實際使用。即使現在它不再被使用，「eval/apply」STG機器也只是稍微接近C運行時。我甚至不確定使用常規C堆棧的GHC：我認爲它不會，使用它自己的堆棧。

你可以檢查GHC developer wiki看到血淋淋的細節。

來源

2015-11-03 19:39:40 chi

有沒有辦法來防止雙返回地點？例如，我使用模式匹配編寫了一個備用例程（對於基本情況爲0），但這並沒有幫助。一般來說，有沒有一種方法可以告訴GHC以一種允許跨越邊界遞歸的方式進行編譯？ – Crazycolorz5

@ Crazycolorz5調整運行時間是一項非常艱鉅的任務。你似乎相信GHC應該把它的運行時間調整到C標準。要弄清楚這是多麼困難，請考慮其他方式：修改GCC以便允許多個返回，垃圾回收等。這幾乎是不可能的。就目前的GHC而言，甚至在我看來，即使在遙遠的將來，你所要求的是非常非常不可能實現的。 – chi

雖然我不是Haskel-C interop的專家，但我不認爲從C到Haskel的調用可以是直接的函數調用 - 它很可能必須通過中介來設置環境。因此，您打給Haskel的電話實際上包括對此中介的電話。這個調用可能是由gcc優化的。但是從中間人到實際Haskel例程的呼叫並沒有得到必要的優化 - 所以我認爲，這就是你正在處理的問題。您可以檢查裝配輸出以確保。

來源

2015-11-03 18:40:35 SergeyA

在C和Haskell之間的相互遞歸中編譯尾部調用優化

回答

相關問題