スキー計算とBCKWの実用的な応用
-
02-10-2019 - |
質問
スキーとBCKWの計算を作成して考える方法を理解できますが、実用的な用途を見つけることはできません。多分私は十分に深く見ていませんか?つまり、(例として、これが真実ではないことを暗示しているわけではありません)Java Servletsは広範囲に使用し、PythonジェネレーターはBCWの例であり、木の森を見ることができませんか?
解決
Haskellでは、彼らはそうです どこにでも!
- b は
<$>
- c は
flip
- k は
pure
- 私 は
id
- s は
<*>
- w は
join
Haskellの観点から、 <$>
「文脈で行う」を意味します。
(+2) <$> (*3)
2つを追加することを意味します 3を掛けた後.(+2) <$> [1,2,3]
2に追加することを意味します リスト内の各要素.(+2) <$> (read . getLine)
2に追加することを意味します 私が読んだばかりの番号.(+2) <$> someParser
2に追加することを意味します 解析した数字.
コンテキストがあるものが呼ばれます 機能者. 。すべてのJava/Python/C ++ Iteratorsは、機能者の奇妙な裏返しバージョンです。
別の接続:SとKの組み合わせは、チューリングが完全です。 Haskellで、 pure
と <*>
一緒にアプリケーションファンチャーを形成します。
もちろん、他のコンビネーターがどのように適合するかを理解するには、Haskellを学習する必要があります。しかし、この例は、コンビネーターが言語にどのように定着しているかを示しています。
他のヒント
スキーとBCKWの計算は、ラムダ計算(機能プログラミングの概念でよく知られているアプリケーションがある)から離れています。 ポイントフリーフォーム. 。参照してください 暗黙のプログラミング. 。それらは、名前の引数なしで機能プログラムを構築する方法を理解する基礎を形成します。
特定の言語でそれのアプリケーションが表示されます(例: 喜び と 猫)。一度 lambda-the-gultimate.orgに投稿されました SK微積分と猫と喜びとの関係について。
その価値について:BCKWとSKI(またはSK)Calculiは実質的に同一ですが、BCKWベースはVogueから脱落しました。
LambdaとSki Calculusは、ほとんどのプログラミング言語(グラフィック、ネットワーク接続、標準入力、出力など)の入力および出力システムを反映していませんが、実用的なコンピュータープログラミングの構造はLambda(したがってスキーとスキーとスキーとBCKW)、再帰のアイデアや、機能が呼ばれる方法など。これらのプログラミング言語の多くには、機能として使用するためのLambda抽象化があります。
コントロールがすべてです。
たぶん下位レベルから始めてください。アプリケーションシステムは、オブジェクトを他のオブジェクトに適用できるシステムです。適用システムの簡単な例はbashです。 ls |より多くの人は、それらがある環境にあり、上記が環境上でLSを行うことを意味すると仮定するかもしれません。アプリケーション表記では、これは @(LS @環境)が多いですが、LSのようなより複雑なことをすることができます。グレップパターン|さらに、アプリケーション表記では、これは @((grep @ pattern) @(ls @環境))です。 grep @ patternに注意してください。 GREPはパターンに適用され、LSの結果でそのパターンに一致するプログラムを返します。これがアプリケーションのポイントであり、プログラムを議論に適用し、「Atomic」(別名Builtin)プログラムから新しいプログラムを構築します。ただし、プリミティブアプリケーションまたはビルトインだけでプログラミングを行うことはできません。入力と入力へのプリミティブの適用を構築する方法が必要です。
Lambdaが登場する場所です。Lambdaを使用すると、(grep @ pattern)を一般化して、grepを任意の入力に適用できます(grep @ x)ただし、Grepに入力を取得する方法が必要です。したがって、通常、関数を使用します。 f(x)= grep @ x上記のプロセスは、引数を抽象化すると呼ばれます。しかし、名前が特別であると考える理由はないので、そのための構文があります:lambda x。 grep @ x then lambda x. grep @ x、入力に適用でき、入力を体に置き換えて評価します。ただし、置換が乱雑でバインドされた変数をマシンに実装するのに面倒な場合があります。 Ski(またはB、C、K、W)は、代替なしでラムダのものを行う方法を提供し、代わりにアプリケーションを交換するだけです。
要約すると、アプリケーションはそれがすべてのものです。プログラムを何か(おそらく別のプログラム)に適用するレベルで推論するのは非常に便利です。 Lambda Calculusは、プログラムの入力と適用を議論に構築する方法を提供します。スキーは、明示的に代用することなくラムダを行う方法を提供します。
スキーの削減は本質的に怠zyであることに注意する必要があるため、アプリケーションを構築するためにスキーの現実世界で使用することで、ある程度の考慮が必要になる場合があります。実際、議論は現在完全に評価されている可能性があり、同様に部分的なアプリケーションである可能性があります。タイプ理論でこれを回避することができ、プログラムがアプリケーションのヘッド位置にある場合にのみ、その入力に関するプログラムを評価することができます。つまり、閉じたラムダの用語で書いて、スキーに翻訳された場合、p @ arg1 @ .... p @ arg1 @ .... pが原始プログラムである場合、書き換えが完了したため、すべての議論は1です。 )利用可能、2)完全に評価された。しかし、私はこれを証明していません、そしてそれは十分な強いタイプ理論では真実ではないかもしれません...