在 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 代码很明显是函数调用的 return。

Answer 1

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

Answer 2

我相信跨语言 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
测试 x 对抗 42
如果相等，跳转到a
跳转到b

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

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

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

您可以查看 GHC developer wiki 以查看详细信息。

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

Compiling Tail-Call Optimization In Mutual Recursion Across C and Haskell

c

haskell

multiple-languages

tail-call-optimization

mutual-recursion