23

私はスーパーコンビネータとは何かに苦労しています：

スーパーコンビネータは、定数、またはサブ式としてスーパーコンビネータのみを含むコンビネータのいずれかです。

また、ConstantApplicativeFormsとは次のとおりです。

ラムダ抽象化ではないスーパーコンビネータ。これには、12、（（+）1 2）、[1,2,3]などの真に定数の式と、（（+）4）などの部分的に適用される関数が含まれます。この最後の例は、eta抽象化では、CAFではない\ x->（+）4xと同等であることに注意してください。

これは私には意味がありません！((+) 4)12と同じくらい「本当に一定」ではありませんか？CAFは、私の単純な心には価値観のように聞こえます。

4

2 に答える 2

31

あなたが参照しているこれらの Haskell wiki ページは古く、残念ながら書かれていると思います。特に残念なのは、CAF とスーパーコンビネーターを混同していることです。スーパーコンビネーターは興味深いものですが、GHC とは無関係です。CAF は依然として GHC の一部であり、スーパーコンビネーターを参照しなくても理解できます。

それでは、スーパーコンビネーターから始めましょう。コンビネータは組み合わせロジックから派生し、ここでの使用法では、渡された値を何らかの形で相互に適用するだけの関数で構成されます。つまり、引数を結合します。コンビネータの最も有名なセットは、S、K、および Iであり、これらを合わせてチューリング完全です。このコンテキストでのスーパーコンビネーターは、渡された値、コンビネーター、およびその他のスーパーコンビネーターのみで構築された関数です。したがって、任意のスーパーコンビネーターは、置換によって単純な古いコンビネーターに拡張できます。

関数型言語 (GHC ではない!) のコンパイラの中には、コンパイルの中間ステップとしてコンビネータとスーパーコンビネータを使用するものがあります。他の同様のコンパイラ テクノロジと同様に、これを行う理由は、このような単純化された最小限の言語でより簡単に実行できる最適化分析を認めるためです。スーパーコンビネーター上に構築されたそのようなコア言語の 1 つは、Edwin Brady のepicです。

定適用形は、まったく別のものです。それらはもう少し微妙で、いくつかの落とし穴があります。それらを考える方法は、別個のセマンティックな意味を持たないコンパイラ実装の側面としてですが、実行時のパフォーマンスに大きな影響を与える可能性があります。以下は CAF の完全な説明ではないかもしれませんが、それが何であるかについての私の直感を伝えようとします。GHC Commentary Wikiのクリーンな「正式な」説明は次のとおりです。

Constant Applicative Forms (略して CAF) は、プログラムで定義されたトップレベルの値です。基本的に、これらは実行時に動的に割り当てられるのではなく、プログラムの静的データの一部であるオブジェクトです。

それは良いスタートです。純粋で関数型の怠惰な言語は、ある意味ではグラフ縮小マシンと考えることができます。ノードの値を初めて要求すると、その評価が強制され、サブノードなどの値が要求される可能性があります。ノードが評価されると、結果の値が保持されます (ただし、保持する必要はありませんが--これは純粋な言語であるため、常にサブノードを有効に保ち、セマンティックな影響なしで再計算できます)。CAF は実際には単なる値です。しかし、コンテキストでは、特殊な種類の値 (コンパイラが決定できる値) は、そのサブノードに完全に依存する意味を持ちます。つまり、次のようになります。

foo x = ...
  where thisIsACaf = [1..10::Int]

        thisIsNotACaf = [1..x::Int]
        thisIsAlsoNotACaf :: Num a => [a]
        thisIsAlsoNotACaf = [1..10] -- oops, polymorphic! the "num" dictionary is implicitly a parameter.

        thisCouldBeACaf = const [1..10::Int] x -- requires a sufficiently smart compiler
        thisAlsoCouldBeACaf _ = [1..10::Int] -- also requires a sufficiently smart compiler

では、物事が CAF であるかどうかを気にするのはなぜでしょうか? 基本的に、何かを再計算したくない場合があるため (たとえば、メモ可能です!)、適切に共有されていることを確認したい場合があります。他の時には私たちは本当にそうします何かを再計算したい (たとえば、巨大で退屈で簡単に生成できるリスト (たとえば、今歩いているナチュラル リストなど)) を再計算したいが、それを永遠にメモリに残したくない。名前を付けて let でバインドしたり、インラインで記述したりすることで、通常、自然で直感的な方法でこれらの種類のものを指定できます。しかし、時折、コンパイラは私たちが期待するよりも賢く、または愚かであり、一度しか計算されるべきではないと思われるものが常に再計算されたり、しがみつきたくないものが CAF として取り除かれたりします。次に、物事をより慎重に検討する必要があります。関連するトリッキーさのいくつかについてのアイデアを得るには、このディスカッションを参照してください。「共有」を回避する良い方法は?

[ちなみに、私はそれをする気はありませんが、既存の Haskell Wiki ページと統合して改善/更新したい場合は、この回答を好きなだけ自由に使用してください]

于 2011-11-30T18:13:48.267 に答える