在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之间的相互递归中编译尾部调用优化

回答

相关问题