トータルファンクショナルプログラミングとは何ですか?

functional-programming programming-languages
トータルファンクショナルプログラミングとは何ですか?

Wikipediaはこう言っています:

_
完全な関数型プログラミング(通常の関数型プログラミングまたは弱い関数型プログラミングとは対照的に、強力な関数型プログラミングとも呼ばれます)は、プログラムの範囲を終了する可能性のあるものに制限するプログラミングパラダイムです。
_

and

_
これらの制限は、関数型プログラミング全体がチューリング完全ではないことを意味します。 しかし、使用できるアルゴリズムのセットはまだ巨大です。 例えば、漸近的な上限が計算された任意のアルゴリズムは、その上限を追加の引数として使用することによって証明終了関数に自明に変換することができ、これは各反復または再帰のたびに減分される。
_

http://lambda-the-ultimate.org/node/2003 [Total Functional Programming]に関する論文についてのLambda The Ultimate Postもあります。

私は先週メーリングリストでそれに出会ったことはありませんでした。

あなたが知っている他のリソース、参照、または実装例がありますか。

  18  9


ベストアンサー

私がそれを正しく理解したならば、Total Functional Programmingはそれを意味します:Total Functionsによるプログラミング。 私の数学の授業を正しく覚えていれば、トータル関数はそのドメイン全体にわたって定義される関数であり、パーシャル関数はその定義に「穴」があるものです。

さて、ある入力値 v`が無限再帰や無限ループに陥る、あるいは他の方法で終了しないような関数があるなら、その関数は v`に対して定義されていないので、部分的な、すなわち 合計ではありません。

Total Functional Programmingでは、このような関数を書くことはできません。 すべての関数は常にすべての可能な入力に対して結果を返します。そして型チェッカーはこれが事実であることを確認します。

これはエラー処理を非常に簡単にすると私は思います。

欠点はあなたの引用ですでに述べられています:それはチューリング完全ではありません。 E.g. オペレーティングシステムは本質的に巨大な無限ループです。 確かに、オペレーティングシステムを終了させたくはありません。この動作を「クラッシュ」と呼び、それについて私たちのコンピュータに叫んでいます。

23


これは昔からの質問ですが、これまでのところ、完全な関数型プログラミングの本当の動機については触れられていません。

プログラムが証明であり、証明がプログラムであるならば、「穴」を持つプログラムは証明として意味をなさない、そして論理的な矛盾を導入する。

基本的に、証明がプログラムの場合、無限ループを使用して_anything_を証明できます。 これは本当に悪いことで、なぜ私たちが完全にプログラムしたいのかについての動機の多くを提供します。 他の答えは紙の裏側を説明しない傾向があります。 言語は完全には完成していませんが、共帰納的な定義と関数を使用することで、たくさんの興味深いプログラムを回復できます。 私たちは_誘導データを考える傾向がありますが、_codata_は無限の定義を完全に定義することができるこれらの言語では重要な目的を果たします(そして実際に終了する計算をするとき、あなたは潜在的にこの限られた部分だけを使うでしょう)あるいは、オペレーティングシステムを書いているのであれば、そうではないかもしれません!)

Coqなど、ほとんどの証明アシスタントがこの原則に基づいて機能することも注目に値します。

10


慈善団体は終了を保証するもう一つの言語です:http://pll.cpsc.ucalgary.ca/charity1/www/home.html

ヒュームは4つのレベルを持つ言語です。 外側のレベルはチューリング完全であり、最も内側の層は終了を保証します。http://www-fp.cs.st-andrews.ac.uk/hume/report/

9


タイトルとURLをコピーしました