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

Question

我正在试验 Haskell 中的外部函数接口(interface)。我想实现一个简单的测试，看看我是否可以进行相互递归。因此，我创建了以下 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 运行时非常不同。据我所知，造成这种差异的主要因素是:

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

鉴于此类差异接近于零，可能会跨语言边界生存的优化类型。或许，理论上，人们可以发明一个专门的 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”，跳转到末尾

而p的实现如下:

• p: 从栈中弹出x
• 从栈中弹出b
• 从栈中弹出a
• 针对 42 测试 x
• 如果相等，跳转到a
• 跳转到b

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

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

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

您可以查看 GHC developer wiki查看血淋淋的细节。