6

次のようなプログラムがあるとしましょう:

list = [1..10000000]

main = print $ sum list

これをコンパイルして、実行可能ファイルが 50000005000000 を出力するだけで、それほど時間と労力をかけないようにしたいと考えています。

基本的に、確実に計算される式 (ここでは厳密性分析が役立つかもしれません) は、コンパイル時に事前に計算できます(つまり、参照透過性を使用して、値を計算するときに実際には問題にならないことを示します)。

要するに：「計算する必要があります」+参照透過性=事前に計算できます

これは、入力に依存する何かに到達するまでプログラムを実行するようなものです (つまり、すべての入力に共通するプログラムのコアは事前に計算されます)。

現在これを達成するための既存のメカニズムはありますか (Haskell または他の言語で)? [そもそも参照透過性がないため、C++ のテンプレートのようなものを指さないでください。]

そうでない場合、この問題はどれほど難しいですか? [付随する技術的 (および理論的) 問題は何ですか?]

4

3 に答える 3

11

コンパイル時の計算を行うための汎用的な答えは、TemplateHaskellを使用することです。ただし、この特定のユースケースでは、ベクターパッケージとLLVMバックエンドを使用でき、GHCはこの合計を最適化します。

sorghum:~% cat >test.hs
import Data.Vector.Unboxed as V
main = print (V.sum $ V.enumFromN (1 :: Int) 10000000)
sorghum:~% ghc --make -O2 -fllvm test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
sorghum:~% time ./test
50000005000000
./test  0.00s user 0.00s system 0% cpu 0.002 total
sorghum:~% objdump -d test | grep 2d7988896b40
  40653d:   48 bb 40 6b 89 88 79    movabs $0x2d7988896b40,%rbx
  406547:   49 be 40 6b 89 88 79    movabs $0x2d7988896b40,%r14

（すぐにわからない場合は、0x2d79888896b40です50000005000000。）

于 2012-04-10T18:01:22.400 に答える
11

これは一般的なケースでは安全ではありません。その理由は、Haskellの式は純粋かもしれないが、終了に失敗する可能性もあるからです。コンパイラは常に終了する必要があるため、「この結果の1,000ステップを評価する」ことが最善の方法です。1しかし、そのような制限を追加した場合、テラバイトのRAMを搭載したスーパーコンピュータークラスターで実行するプログラムをコンパイルしていて、コンパイラーがメモリを使い果たした場合はどうなるでしょうか。

多くの制限を追加できますが、最終的には最適化を定数畳み込みの遅い形式に減らします（特に、計算が実行時のユーザー入力に依存するプログラムの大部分ではそうです）。また、sum [1..10000000]ここでは0.5秒かかるため、妥当な制限に該当する可能性はほとんどありません。

もちろん、このような特定のケースは多くの場合最適化でき、GHCはこのような複雑な表現を最適化することがよくあります。ただし、コンパイラはコンパイル時に式を安全に評価することはできません。それは非常に制約されている必要があり、それらの制約の下でそれがどれほど役立つかは議論の余地があります。これはコンパイラであり、インタプリタではありません:)

1これは、多くの無限ループを含むプログラムのコンパイルを大幅に遅くします— Haskellは厳密ではないため、想像以上に可能性が高くなります）。または、より一般的には、長時間実行される計算を多く含むプログラム。

于 2012-04-10T18:01:24.493 に答える
1

スーパーコンパイルの仕事のように聞こえます! 質問はその説明のように聞こえますが、非終了の議論は、スーパーコンパイラの開発者が直面する問題を反映しています。GHC wiki で、誰かがそれ用の製品スーパーコンパイラに取り組んでいるのを見ましたが、それがどうなったかはわかりません。

于 2012-04-12T01:00:02.220 に答える