46

次の値/式/関数のサンクは、Haskellヒープではどのように見えますか？

val = 5                -- is `val` a pointer to a box containing 5?
add x y = x + y        
result = add 2 val     
main = print $ result

遅延評価モードを考えると、これらがHaskellでどのように表現されているかを把握しておくと便利です。

4

5 に答える 5

70

公式回答

それはあなたの仕事ではありません。コンパイラの厳密な実装の詳細。

短い答え

はい。

長い答え

Haskellプログラム自体にとって、答えは常に「はい」ですが、パフォーマンス上の理由から、コンパイラーは、それを回避できることがわかった場合、異なる方法で処理を実行できます。

たとえば、'''add xy = x + y'''の場合、コンパイラはxとyのサンクを処理し、結果としてサンクを構築するコードを生成する場合があります。ただし、次のことを考慮してください。

foo :: Int -> Int -> Int
foo x y = x * x + y * y

ここで、最適化コンパイラは、最初にボックスからxとyを取り出し、次にすべての演算を実行し、結果をボックスに格納するコードを生成します。

高度な回答

このホワイトペーパーでは、GHCがサンクを実装する方法から、実際にはよりシンプルで高速な別の方法にどのように切り替えたかについて説明します。http: //research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

于 2011-12-12T18:00:22.323 に答える
13

一般に、Haskellのプリミティブ値（たとえば、IntおよびFloat型）でさえ、サンクで表されます。これは、非厳密なセマンティクスによって実際に必要とされます。次のフラグメントを検討してください。

bottom :: Int
bottom = div 1 0

この定義は、bottomの値が検査された場合にのみ、ゼロによるdivの例外を生成しますが、値が使用されない場合は生成しません。

ここで、add関数について考えてみましょう。

add :: Int -> Int -> Int
add x y = x+y

addの単純な実装では、サンクをxに強制し、サンクをyに強制し、値を追加して、結果の（評価された）サンクを作成する必要があります。これは、厳密な関数型言語（命令型言語は言うまでもなく）と比較して、算術の大きなオーバーヘッドです。

ただし、GHCなどの最適化コンパイラはほとんどこのオーバーヘッドを回避できます。これは、GHCが追加関数をどのように変換するかを簡略化したものです。

add :: Int -> Int -> Int
add (I# x) (I# y) = case# (x +# y) of z -> I# z

内部的には、Intのような基本型は、単一のコンストラクターを持つデータ型と見なされます。タイプInt＃は整数の「生の」マシンタイプであり、+＃は生のタイプの基本的な加算です。raw型の操作は、サンクではなくビットパターン（レジスタなど）に直接実装されます。ボクシングとアンボクシングは、コンストラクターアプリケーションとパターンマッチングとして変換されます。

このアプローチの利点（この単純な例では表示されません）は、コンパイラーがそのような定義をインライン化し、中間のボックス化/アンボックス化操作を削除して、最も外側の操作のみを残すことができる場合が多いことです。

于 2011-12-12T18:26:12.047 に答える
7

すべての値をサンクでラップすることは絶対に正しいでしょう。しかし、Haskellは厳密ではないため、コンパイラーはサンク/式をいつ評価するかを選択できます。特に、コンパイラーは、より良いコードが得られる場合、厳密に必要とされるよりも早く式を評価することを選択できます。

Haskellコンパイラー（GHC）の最適化は、厳密性分析を実行して、どの値が常に計算されるかを把握します。

最初に、コンパイラは、関数の引数が使用されていないことを前提としています。次に、関数の本体を調べて、1）引数（の少なくとも一部）が厳密であることがわかっており、2）関数の結果を計算するために常に評価する必要がある関数アプリケーションを見つけようとします。

あなたの例では(+)、両方の引数で厳密な関数があります。したがって、コンパイラは、xとの両方yがこの時点で常に評価される必要があることを認識しています。関数の結果を計算するには式が常に必要であるため、コンパイラは関数がとの両方で厳密でx+yあるという情報を格納できます。addxy

したがって、*に対して生成されたコードは、addサンクではなく、パラメーターとして整数値を期待します。再帰が含まれる場合（固定小数点の問題）、アルゴリズムははるかに複雑になりますが、基本的な考え方は同じです。

もう一つの例：

mkList x y = 
    if x then y : []
         else []

この関数はx、評価された形式（ブール値として）およびyサンクとして使用されます。式は、xを介して可能なすべての実行パスで評価される必要があるためmkList、呼び出し元に評価させることができます。一方、式yは、引数が厳密な関数適用では使用されません。cons-function:はそれを見ることがなくy、リストに格納するだけです。したがってy、怠惰なHaskellセマンティクスを満たすには、サンクとして渡す必要があります。

mkList False undefined -- absolutely legal

*：addもちろん多形であり、正確なタイプでxありy、インスタンス化に依存します。

于 2011-12-12T18:02:19.420 に答える
6

簡単な答え：はい。

長い答え：

val = 5

これはサンクに保存する必要があります。これをコードのどこかに記述した場合（インポートしたライブラリなど）を想像してみてください。

val = undefined

プログラムの起動時にこれを評価する必要がある場合、クラッシュしますよね？私たちが実際にその値を何かに使用する場合、それは私たちが望むものですが、それを使用しない場合、それは私たちのプログラムにそれほど壊滅的な影響を与えることができないはずです。

2番目の例では、少し変更します。

div x y = x / y

次のようなコードを想像してみてください。この値もサンクに格納する必要があります。

average list =
  if null list
     then 0
     else div (sum list) (length list)

ここで厳密にすると、リストが（別名：空）の場合divでも評価されます。つまり、空のリストが与えられたときnullに戻る機会がないため、このような関数を記述しても機能しません。0これは、この場合に必要なものです。

最後の例は例1のバリエーションにすぎず、同じ理由で怠惰である必要があります。

そうは言っても、コンパイラーにいくつかの値を厳密にすることを強制することは可能ですが、それはこの質問の範囲を超えています。

于 2011-12-12T17:49:24.757 に答える
4

他の人があなたの質問にうまく答えたと思いますが、完全を期すために、GHCはボックス化されていない値を直接使用する可能性も提供していることを付け加えておきます。これはHaskellWikiがそれについて言っていることです：

あなたが本当にスピードを切望していて、あなたが「生のビット」にすぐに取り掛かりたいとき。ボックス化されていないタイプの使用に関する情報については、GHCプリミティブを参照してください。

ただし、ボックス化されていない型とプリミティブは移植性がないため、これは最後の手段となるはずです。幸い、GHCのオプティマイザーは、知っている操作をインライン化し、厳密な関数引数をアンボックス化することで作業を実行できるため、通常、ボックス化されていない明示的な型とプリミティブを使用する必要はありません。厳密で解凍されたコンストラクターフィールドも大いに役立ちます。GHCが適切なコードを生成するために少し助けが必要な場合があるため、コア出力を調べて、微調整が実際に目的の効果を発揮しているかどうかを確認する必要があります。

ボックス化されていない型とプリミティブを使用する場合に言えることの1つは、GHCのオプティマイザーに依存して正しいことを行うのではなく、効率的なコードを記述していることを知っていることです。これはあなたにとって重要かもしれません、その場合はそれを行ってください。

前述のように、移植性がないため、GHC言語拡張機能が必要です。ドキュメントについては、こちらをご覧ください。

于 2011-12-13T15:14:05.687 に答える