7

I'm experimenting with the foreign-function interface in Haskell. I wanted to implement a simple test to see if I could do mutual recursion. So, I created the following Haskell code:

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 ()

Note that the recursive case is a call to countdownC, so this should be tail-recursive.

In my C code, I have

#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;
}

Which is likewise tail recursive. So then I make a

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

and compile with make MutualRecursion.

And... upon running, it segfaults after printing 8991. Just as a test to make sure gcc itself can handle tco in mutual recursion, I did 

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);
}

and that worked quite fine. It also works in the single-recursion case of just in C and just in Haskell.

So my question is, is there a way to indicate to GHC that the call to the external C function is tail recursive? I'm assuming that the stack frame does come from the call from Haskell to C and not the other way around, since the C code is very clearly a return of a function call.

4

2 回答 2

3

我相信跨语言的 C-Haskell 尾调用非常非常难以实现。

我不知道确切的细节，但 C 运行时和 Haskell 运行时有很大不同。据我所知，造成这种差异的主要因素是：

  • 不同的范式：纯函数式 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入栈中
  • 压栈42_
  • 跳到p
  • A: 打印“A”，跳转到结尾
  • B: 打印“B”，跳转到结尾

whilep实现如下：

  • xp：从堆栈中弹出
  • b从堆栈中弹出
  • a从堆栈中弹出
  • x针对 42进行测试
  • 如果相等，跳转到a
  • 跳到b

请注意如何使用两个p返回地址调用，每个返回地址对应一个可能的结果。这与 C 不同，后者的标准实现只使用一个返回地址。跨越边界时，编译器必须考虑这种差异并进行补偿。

上面我也没有考虑当参数p是 thunk 时的情况，以保持简单。GHC 分配器也可以触发垃圾回收。

请注意，上述虚构的实现实际上是 GHC 过去使用的（所谓的“推送/输入”STG 机器）。即使现在不再使用它，“eval/apply”STG 机器也只是稍微接近 C 运行时。我什至不确定 GHC 是否使用常规 C 堆栈：我认为它没有，使用它自己的堆栈。

您可以查看GHC 开发者 wiki以查看血腥细节。

于 2015-11-03T19:39:40.137 回答
0

虽然我不是 Haskel-C 互操作方面的专家，但我不认为从 C 到 Haskel 的调用可以是直接的函数调用——它很可能必须通过中介来设置环境。因此，您对 haskel 的调用实际上将包括对这个中介的调用。这个调用可能是由 gcc 优化的。但是从中介到实际 Haskel 例程的调用没有必要优化 - 所以我假设，这就是你正在处理的。您可以检查程序集输出以确保。

于 2015-11-03T18:40:35.867 回答