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の場合の両方でも機能します。

私の質問は、外部C関数の呼び出しが末尾再帰的であることをGHCに示す方法ですか？私はスタックフレームがHaskellからCへの呼び出しから来ていると仮定していますが、Cコードは関数呼び出しの戻り値であるため、別の方法ではありません。

Answer 1

クロス言語のC-Haskellテールコールは非常に難しいと私は信じています。

正確な詳細はわかりませんが、CランタイムとHaskellランタイムはと大きく異なります。は異なります。この違いの主な要因は、私の知る限り、以下のとおりです。

• 異なるパラダイム：手動メモリ管理対不可欠
• ガベージコレクション
• 怠惰なセマンティクス対厳しい1

対純粋に機能

そのような違いがある場合、言語境界を越えて生き残る可能性のある最適化の種類は、ゼロの次にあります。おそらく、理論的には、Haskellランタイムと一緒に特別なCランタイムを作成し、いくつかの最適化が可能であるかもしれないが、GHCとGCCはこのように設計されていない可能性がある。Aの

• プッシュアドレス：

  だけ電位差の一例を示すように、我々はmainの可能な実装は、以下の可能性が

  p :: Int -> Bool 
  p x = x==42 
  
  main = if p 42 
       then putStrLn "A"  -- A 
       else putStrLn "B"  -- B 
  

  次Haskellコードを持っていると仮定スタック上に

• アドレスにBを押し込みます。
• pusプリント "A"、
• Bを終了するジャンプ：p
• Aにスタック
• ジャンプにH 42プリント "B"、次のようにpが実装されている間

を終了するジャンプ：

• P：スタック
• popからxをポップbポップa
スタックから42
• に対する試験x等しい場合
スタックから、 a
• ジャンプpが戻りアドレスで起動する方法注

bまでにジャンプし、可能な結果ごとに1つこれは、標準の実装で1つの戻りアドレスしか使用しないCとは異なります。境界を越えるときには、コンパイラはこの差異を考慮して補正する必要があります。

上記の私はまた、pの引数がサンクである場合を考慮しておらず、簡単にしています。 GHCアロケータは、ガベージコレクションを起動することもできます。

上記の架空の実装は、過去にGHC（いわゆる「プッシュ/入力」STGマシン）によって実際に使用されたことに注意してください。たとえそれがもはや使用されていなくても、 "評価/適用" STGマシンはわずかにCランタイムに近いだけです。私は普通のCスタックを使っているGHCについては確信していません。自分自身で使ってはいけないと思います。

GHC developer wikiを確認して詳細を確認できます。

Answer 2

私はHaskel-C interopの専門家はいませんが、CからHaskelへの呼び出しが直接関数呼び出しであるとは想像もしません。環境を設定するためには、おそらく仲介を経由しなければなりません。結果として、あなたのhaskelへの呼び出しは実際にこの仲介者への呼び出しで構成されます。この呼び出しはおそらくgccによって最適化されています。しかし、仲介から実際のハスケルルーチンへの呼び出しは、必然的に最適化されていませんでした。つまり、これはあなたが扱っているものです。アセンブリ出力を確認して確認することができます。