在C和Haskell的相互递归中编译尾调用优化

Question

我正在试验Haskell中的外部函数接口.我想实现一个简单的测试,看看我是否可以进行相互递归.所以,我创建了以下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.

并且......在运行时,它会在打印后出现段错误8991.就像确保gcc本身可以在相互递归中处理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代码非常明显地是函数调用的返回.

Answer 1

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

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

• 不同的范式：纯函数式与命令式
• 垃圾收集与手动内存管理
• 惰性语义与严格语义

鉴于这种差异，可能跨语言边界生存的优化种类接近于零。也许，从理论上讲，人们可以与 Haskell 运行时一起发明一种临时 C 运行时，以便进行一些优化，但 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 不同，C 的标准实现仅使用一个返回地址。当跨越边界时，编译器必须考虑这种差异并进行补偿。

为了简单起见，上面我也没有考虑 的参数p是 thunk 时的情况。GHC 分配器还可以触发垃圾收集。

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

您可以查看GHC 开发者 wiki以查看详细信息。