6

Haskell で書くと、

 fac n = facRec n 1
   where facRec 0 acc = acc
         facRec n acc = facRec (n-1) (acc*n)

GHCでコンパイルすると、結果は私が使用した場合とは異なりますか

 fac 0 = 1
 fac n = n * fac (n-1)

私は簡単にすべてを実行fac n = product [1..n]して回避することができましたが、末尾再帰の試みが怠惰な言語でどのように機能するかに興味があります。サンクが蓄積されているため、スタック オーバーフローが発生する可能性があることはわかりましたが、アキュムレータを使用した場合と単純な再帰を述べた場合では、(コンパイルされたプログラムの結果に関して) 実際には何か違うことが起こりますか? 読みやすさの向上以外に、末尾再帰を除外する利点はありますか? runhaskell最初にコンパイルするのではなく、計算を実行するために使用している場合、答えはまったく変わりますか?

4

3 に答える 3

10

アキュムレータが厳密な場合、(GHC) Haskellでは末尾再帰は意味があります。問題を示すために、末尾再帰定義の「トレース」を次に示しますfac。

   fac 4
~> facRec 4 1
~> facRec 3 (1*4)
~> facRec 2 ((1*4)*3)
~> facRec 1 (((1*4)*3)*2)
~> facRec 0 ((((1*4)*3)*2)*1)
~> (((1*4)*3)*2) * 1
  ~> ((1*4)*3) * 2
    ~> (1*4) * 3
      ~> 1*4
    ~> 4 * 3
  ~> 12 * 2
~> 24 * 1
~> 24

インデント レベルは (おおよそ) スタック レベルに対応します。アキュムレータは最後にのみ評価されるため、スタック オーバーフローが発生する可能性があることに注意してください。もちろん、秘訣はアキュムレータを厳密にすることです。厳密なコンテキストで呼び出された場合、facRec が厳密であることを示すことは理論的に可能ですが、それを行うコンパイラ、ATM は知りません。ただし、 GHCは末尾呼び出しの最適化を行うため、facRec呼び出しは一定のスタック スペースを使用します。

同じ理由で、前者はアキュムレータで厳密であるため、foldl'通常は よりも優先されます。foldl

2 番目の部分については、runhaskell/runghcは GHCi の単なるラッパーです。GHCi がコンパイルされたコードを見つけた場合、それを使用します。そうでない場合は、ほとんど最適化を実行しないバイトコード インタープリタを使用します。

于 2010-11-26T14:54:37.583 に答える
3

Haskell では、アキュムレータが厳密で、結果全体が必要な場合にのみ、末尾再帰的な方法でプログラムを作成するのに役立ちます。

ghc の runHaskell ではプログラムが最適化されないため、厳密性分析が行われず、スタック オーバーフローが発生する可能性があります。一方、最適化を使用してコンパイルすると、コンパイラはアキュムレータを厳密にする必要があることを検出し、それに応じて最適化する場合があります。

物事がどのように異なるか (または起こらないか) を確認するには、生成されたコア言語を調べるのが最善の方法です。ちなみに、彼のブログ投稿の多くは、パフォーマンスに興味がある場合に興味深いものです。

于 2010-11-26T10:55:08.200 に答える
1

あなたの質問は完全ではありません。私はあなたがGHCを意味していると仮定します.少なくとも最適化なしでは答えは「はい」です.ワーカー関数(facRec最初またはfac2番目)は1と比較してアリティ2を持ち、アセンブリはこれを反映します. 最適化または JHC を使用した場合、答えはおそらく「いいえ」です。

于 2010-11-26T03:54:26.223 に答える