7

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 のみの単一再帰の場合でも機能します。

私の質問は、外部 C 関数の呼び出しが末尾再帰であることを GHC に示す方法はありますか? Cコードは明らかに関数呼び出しのリターンであるため、スタックフレームはHaskellからCへの呼び出しから来ており、その逆ではないと仮定しています。

4

2 に答える 2

3

クロス言語の 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" を出力し、末尾にジャンプ

whilepは次のように実装されます。

  • p:xスタックからポップ
  • bスタックからポップ
  • aスタックからポップ
  • x42に対するテスト
  • 等しければジャンプa
  • にジャンプb

可能な結果ごとに 1 つずつ、2 つのp戻りアドレスで がどのように呼び出されるかに注意してください。これは、標準実装が 1 つの戻りアドレスのみを使用する C とは異なります。境界を超える場合、コンパイラはこの違いを考慮して補正する必要があります。

p上記では、簡単にするために、の引数がサンクの場合も説明しませんでした。GHC アロケータは、ガベージ コレクションをトリガーすることもできます。

上記の架空の実装は、過去に GHC (いわゆる「プッシュ/エンター」STG マシン) によって実際に使用されたことに注意してください。現在は使用されていませんが、「評価/適用」STG マシンは C ランタイムにわずかに近いだけです。通常の C スタックを使用している GHC についてもよくわかりません。

GHC 開発者 wikiをチェックして、悲惨な詳細を確認できます。

于 2015-11-03T19:39:40.137 に答える
0

私は Haskel-C 相互運用の専門家ではありませんが、C から Haskel への呼び出しが単純な関数呼び出しになるとは思いません。おそらく、環境をセットアップするために仲介を経由する必要があります。その結果、haskel への呼び出しは、実際にはこの仲介者への呼び出しで構成されます。この呼び出しは、gcc によって最適化された可能性があります。しかし、仲介から実際の Haskel ルーチンへの呼び出しは必ずしも最適化されていませんでした。アセンブリ出力を確認して確認できます。

于 2015-11-03T18:40:35.867 に答える