カレー - ハワードの等モルフィズムから生じる最も興味深い同等性は何ですか？

https://stackoverflow.com/questions/2969140

24-10-2019
|

質問

私は出会いましたカレー - ハワード同型私のプログラミングライフの比較的遅れて、おそらくこれは私がそれに完全に魅了されることに貢献しています。それは、すべてのプログラミングの概念に、正式な論理に正確な類似物が存在することを意味し、その逆も同様です。これは、私の頭の上から外れたそのような類推の「基本的な」リストです。

program/definition        | proof
type/declaration          | proposition
inhabited type            | theorem/lemma
function                  | implication
function argument         | hypothesis/antecedent
function result           | conclusion/consequent
function application      | modus ponens
recursion                 | induction
identity function         | tautology
non-terminating function  | absurdity/contradiction
tuple                     | conjunction (and)
disjoint union            | disjunction (or)          -- corrected by Antal S-Z
parametric polymorphism   | universal quantification

だから、私の質問に： この同型のより興味深い/不明瞭な意味は何ですか？ 私は論理士ではないので、このリストで表面を傷つけただけだと確信しています。

たとえば、ここでは、ロジックで私が柔らかい名前を知らないプログラミングの概念を紹介します。

currying                  | "((a & b) => c) iff (a => (b => c))"
scope                     | "known theory + hypotheses"

そして、ここに私がプログラミングの用語で完全に固定していないいくつかの論理的概念があります：

primitive type?           | axiom
set of valid programs?    | theory

編集：

応答から収集されたいくつかの同等のものを次に示します。

function composition      | syllogism                -- from Apocalisp
continuation-passing      | double negation          -- from camccann

解決

あなたは最も興味深いと不明瞭なものを明示的に求めたので：

CHを多くの興味深いロジックとロジックの定式化に拡張して、非常に多種多様な対応を取得できます。ここでは、あいまいなものではなく、より興味深いもののいくつかに加えて、まだ出ていない基本的なものに集中しようとしました。

evaluation             | proof normalisation/cut-elimination
variable               | assumption
S K combinators        | axiomatic formulation of logic   
pattern matching       | left-sequent rules 
subtyping              | implicit entailment (not reflected in expressions)
intersection types     | implicit conjunction
union types            | implicit disjunction
open code              | temporal next
closed code            | necessity
effects                | possibility
reachable state        | possible world
monadic metalanguage   | lax logic
non-termination        | truth in an unobservable possible world
distributed programs   | modal logic S5/Hybrid logic
meta variables         | modal assumptions
explicit substitutions | contextual modal necessity
pi-calculus            | linear logic

編集：CHの拡張についてもっと学ぶことに興味がある人にお勧めするリファレンス：

「モーダルロジックの判断の再構築」 http://www.cs.cmu.edu/~fp/papers/mscs00.pdf - これは、最初の原則から始まり、その多くが非学者/言語理論家がアクセスできることを目的としているため、始めるのに最適な場所です。（私は2番目の著者なので、偏見があります。）

他のヒント

あなたは非終了に関して少し物事を泥だらけにしています。虚偽はによって表されます 無人タイプ, 、定義上、そもそも評価するタイプのものが何もないため、定義上ではありません。

非終了は表されます矛盾- 一貫性のないロジック。もちろん、一貫性のないロジックがありますあなたが証明できるようにしますなんでも, しかし、虚偽を含む。

矛盾を無視すると、タイプシステムは通常anに対応します直観論的論理, 、そして必然的に構成主義者, 、これは、古典的なロジックの特定の部分を直接表現できないことを意味します。一方、これは有用です。タイプが有効な建設的な証明である場合、そのタイプの用語は あなたが存在を証明したものを構築する手段.

構成主義者の風味の主な特徴はそれです 二重否定 非陰謀と同等ではありません。実際、否定がタイプシステムの原始的であることはめったにないため、代わりに虚偽を暗示するものとして表現できます。 not P なります P -> Falsity. 。したがって、二重否定はタイプの関数になります (P -> Falsity) -> Falsity, 、明らかにタイプの何かと同等ではありません P.

しかし、これには興味深いひねりがあります！パラメトリック多型を持つ言語では、タイプ変数は無人のものを含むすべての可能なタイプにわたって範囲であるため、ような完全に多型のタイプがあります。 ∀a. a ある意味では、ほぼファルスです。では、多型を使用して二重のネギオンを書くとどうなりますか？このように見えるタイプを取得します。 ∀a. (P -> a) -> a. 。タイプのものに相当します P? 確かにそうです, 、単にID関数に適用します。

しかし、ポイントは何ですか？なぜそのようなタイプを書くのですか？それをします平均プログラミングの観点から何か？まあ、あなたはそれをすでにタイプの何かを持っている関数と考えることができます P どこかで、あなたがそれにかかる関数を与える必要があります P 議論として、すべてが最終結果タイプで多型であることがあります。ある意味では、それはaを表します 一時停止した計算, 、残りが提供されるのを待っています。この意味で、これらの中断された計算は、一緒に構成、渡され、呼び出されます。これは、スキームやルビーなど、いくつかの言語のファンに馴染みのあるように聞こえるはずです。 二重付属はに対応します継続パススタイル, 、そして実際、私が上記で与えたタイプは、まさにHaskellの継続モナドです。

あなたのチャートはまったく正しくありません。多くの場合、タイプを用語と混同しています。

function type              implication
function                   proof of implication
function argument          proof of hypothesis
function result            proof of conclusion
function application RULE  modus ponens
recursion                  n/a [1]
structural induction       fold (foldr for lists)
mathematical induction     fold for naturals (data N = Z | S N)
identity function          proof of A -> A, for all A
non-terminating function   n/a [2]
tuple                      normal proof of conjunction
sum                        disjunction
n/a [3]                    first-order universal quantification
parametric polymorphism    second-order universal quantification
currying                   (A,B) -> C -||- A -> (B -> C), for all A,B,C
primitive type             axiom
types of typeable terms    theory
function composition       syllogism
substitution               cut rule
value                      normal proof

1]チューリング複雑な機能言語のロジックは一貫性がありません。再帰は、一貫した理論に対応していません。一貫性のない論理/不健全な証明理論では、それを矛盾/不健全さを引き起こすルールと呼ぶことができます。

2]繰り返しますが、これは完全性の結果です。これは、論理が一貫している場合、反理論の証拠になります。したがって、存在できません。

3]は、一次論理的特徴を排除するため、機能性言語では存在しません。すべての定量化とパラメータ化は式で行われます。一次機能がある場合、他の種類があります *, * -> *, 、など。談話のドメインの一種の要素。たとえば、in Father(X,Y) :- Parent(X,Y), Male(X), X と Y 談話のドメイン上の範囲（電話してください Dom）、と Male :: Dom -> *.

function composition      | syllogism

私はこの質問が本当に好きです。私はあまり知りませんが、私にはいくつかのことがあります（ウィキペディアの記事, 、これにはいくつかのきちんとしたテーブルなどがあります）：

合計タイプ/ユニオンタイプ（例えば data Either a b = Left a | Right b）と同等です 包括的 分離。そして、私はカレー・ハワードにあまりよく知っていませんが、これはそれを示していると思います。次の機能を検討してください。
```
andImpliesOr :: (a,b) -> Either a b
andImpliesOr (a,_) = Left a
```
私が物事を正しく理解しているなら、タイプはそれを言います（a ∧ b) → (a ★ b）そして定義は、これが真実であると言っています、★は包括的または排他的、またはどちらかです Either 表現します。あなたが持っている Either 排他的または⊕を表す;でも、（a ∧ b) ↛ (a ⊕ b）。たとえば、⊤∧⊤弁ですが、⊤⊕⊥弁、および⊤↛⊥。言い換えれば、両方の場合 a と b 真実であり、仮説は真実ですが、結論は誤りであるため、この意味は虚偽でなければなりません。しかし、明らかに（a ∧ b) → (a ∨ b）、両方の場合 a と b 真実ですが、少なくとも1つは真です。したがって、識別された組合が何らかの形の分離である場合、それらは包括的な多様性でなければなりません。これは証拠としてもたらされると思いますが、この概念を私に自由に否定することはできません。
同様に、アイデンティティ関数と非終了機能としての張会と不条理の定義は、それぞれ少しオフです。真の式は、によって表されます ユニット型, 、これは1つの要素しか持たないタイプです（data ⊤ = ⊤;しばしば綴られています () および/または Unit 機能的なプログラミング言語で）。これは理にかなっています：そのタイプはそうです 保証されています 住むこと、そして住民が1つしかないので、それは真実でなければなりません。アイデンティティ関数は、特定のトートロジーを表すだけです a → a.

非終了機能についてのあなたのコメントは、あなたが何を意味するのかによって、もっとオフです。 Curry-howardはタイプシステムで機能しますが、非終了はそこでエンコードされていません。によるとウィキペディア, 、非終了に対処することは問題です。それを追加すると、一貫性のないロジックが生成されるためです（例えば, 、定義することができます wrong :: a -> b に wrong x = wrong x, 、したがって、それを「証明」します a → b どちらのために a と b）。これが「不条理」の意味である場合、あなたはまったく正しいです。代わりに、あなたが虚偽の声明を意味した場合、あなたが望むのは無人のタイプです、 例えば によって定義されたもの data ⊥- つまり、それを構築する方法のないデータ型です。これにより、値がまったくないことが保証されるため、falseに相当する無人である必要があります。おそらく使用できると思います a -> b, 、非終了機能を禁止した場合、これも無人ですが、100％確信がありません。
ウィキペディア公理は、Curry-howardの解釈方法に応じて、2つの異なる方法でエンコードされていると言います：コンビネーターまたは変数のいずれか。コンビネータービューは、指定されたプリミティブ関数がデフォルトで言うことができることをエンコードすることを意味すると思います（関数アプリケーションは原始的であるため、モデンのポネンが公理である方法と同様）。そして私 考える 変数ビューが実際に同じことを意味する可能性があることは、結局のところ、コンビネーターは特定の機能であるグローバル変数にすぎません。プリミティブタイプに関しては、これについて正しく考えている場合、原始的なタイプはエンティティであると思います。これは、私たちが物事を証明しようとしている原始的なオブジェクトです。
私の論理とセマンティクスのクラスによると、a ∧ b) → c ≡ a → (b → c）（そしてそれも b → (a → c））は、少なくとも自然控除証明において、輸出等価法と呼ばれます。私はそれがただのカレーであることに気づきませんでした - 私は持っていたらいいのに、それはクールだからです！
今では表現する方法がありますが 包括的 分離、排他的な品種を表す方法はありません。排他的な分離の定義を使用して、それを表現できるはずです。 a ⊕ b ≡ (a ∨ b) ∧ ¬(a ∧ b）。否定を書く方法がわかりませんが、私はそれを知っています¬p ≡ p→⊥、そして含意と虚偽の両方が簡単です。したがって、次のように排他的な分離を表すことができるはずです。
```
data ⊥
data Xor a b = Xor (Either a b) ((a,b) -> ⊥)
```
これは定義します ⊥ 虚偽に対応する値のない空のタイプであること。 Xor 次に、両方を含むように定義されます（と) Either an a またはa b (また）および関数（含意）から （a、b） (と）ボトムタイプまで（間違い). ~~しかし、私はこれが何であるか分かりません意味.~~ (編集1： 今、私はそうします、次の段落を見てください！）タイプの値がないためです (a,b) -> ⊥ （ありますか？）、これがプログラムで何を意味するのかを推測することはできません。誰かがこの定義または別の定義について考えるより良い方法を知っていますか？ (編集1： はい、 Camccann.)

編集1： ありがとう Camccannの答え（特に、彼が私を助けるために彼がそれに残したコメント）、私はここで何が起こっているのか見ていると思います。タイプの値を構築します Xor a b, 、2つのことを提供する必要があります。まず、どちらの要素の存在の証人 a また b 最初の議論として;あれは Left a またはa Right b. 。そして第二に、両方のタイプの要素がないという証拠 a と b- 言い換えれば、その証拠 (a,b) 2番目の引数として、無人です。あなたはからの関数を書くことができるので (a,b) -> ⊥ もしも (a,b) 無人ですが、それが事実であるとはどういう意味ですか？それは、タイプのオブジェクトの一部が (a,b) 構築できませんでした。言い換えれば、それは少なくとも1つ、そしておそらく両方が a と b 同様に無人です！この場合、パターンのマッチングについて考えている場合、そのようなタプルでパターンマッチすることはできませんでした。 b 無人ですが、そのタプルの第2部に一致することができるものは何ですか？したがって、私たちはそれと一致することをパターン化することはできません。これにより、なぜこれがそれを無人にするのかを理解するのに役立つかもしれません。さて、引数を取得しない合計関数を持つ唯一の方法（これがしなければならないように、 (a,b) 結果は無人のタイプであるためです。パターンマッチングの観点からこれについて考えている場合、これは関数にはケースがない場合でも、不可能なことを意味します。体どちらも持っている可能性があるので、すべてが大丈夫です。

これの多くは、私が声を出して（できれば）その場で（うまくいけば）ことを考えていることですが、それが役に立つことを願っています。本当にお勧めしますウィキペディアの記事;私はそれをどのような詳細で読んでいませんが、そのテーブルは本当に素晴らしい要約であり、それは非常に徹底的です。

これは、私が驚いたわずかにあいまいなものです。私が以前に育てられなかったのは驚いていません。「古典的な」機能的反応性プログラミングは、時間論的論理に対応しています。

もちろん、あなたが哲学者、数学者、または強迫的な機能プログラマーでない限り、これはおそらくさらにいくつかの質問をもたらします。

それで、最初に：機能的なリアクティブプログラミングとは何ですか？それは協力する宣言的な方法です 時変値. 。これは、ユーザーからの入力が時間とともに異なる値であるため、ユーザーインターフェイスのようなものを書くのに役立ちます。「クラシック」FRPには、イベントと動作という2つの基本的なデータ型があります。

イベントは、個別の時間でのみ存在する値を表します。キーストロークは素晴らしい例です。キーボードからの入力を特定の時間にキャラクターと考えることができます。各キープレスは、キーのキャラクターとそれが押された時間とのみのペアです。

動作は、絶えず存在するが、継続的に変化する可能性がある値です。マウスの位置は素晴らしい例です。x、y座標の単なる動作です。結局のところ、マウス いつも ポジションがあり、概念的には、この位置は変わります 継続的に マウスを動かすとき。結局のところ、マウスの移動は単一の長期にわたる作用であり、個別の手順の束ではありません。

そして、時間的論理とは何ですか？適切には、それは時間の経過とともに定量化された命題に対処するための一連の論理ルールです。基本的に、それは2つの数量剤を使用して通常の1次ロジックを拡張します：□および◇。最初のことは「常に」を意味します：読み取り□φは「常に保持されます」として。 2番目は「最終的に」です。これは特定の種類ですモーダルロジック. 。次の2つの法律は、量子に関連しています。

□φ ⇔ ¬◇¬φ
◇φ ⇔ ¬□¬φ

したがって、□そして◇は∀と∃と同じ方法で互いに二重です。

これらの2つの数量は、FRPの2つのタイプに対応しています。特に、□は動作に対応し、イベントに対応します。これらのタイプがどのように居住しているかを考えると、これは理にかなっているはずです。毎日可能な時間、イベントは一度しか起こりません。

継続と二重否定の関係に関連して、コール/CCのタイプはパースの法則です http://en.wikipedia.org/wiki/call-with-current-continuation

CHは通常、直観論的論理とプログラムの間の対応として述べられています。ただし、Call-with-Current-Continuation（CallCC）オペレーター（Peirceの法律に対応する）を追加すると、間に通信が得られます。 古典的なロジック CallCCを使用したプログラム。

単純な同型ではありませんが、建設的なLEMのこの議論非常に興味深い結果です。特に、結論のセクションでは、Oleg Kiselyovは、建設的な論理で二重交渉排除を得るためのモナドの使用が、すべての命題と計算的に決定可能な提案（LEMが建設的な設定で有効である）を区別することにどのように類似しているかについて説明します。モナドが計算効果をキャプチャするという概念は古いものですが、このカレーのこの例は、ハワードの同型性を把握するのに役立ち、ダブルネギオンが実際に「意味する」ことをするのに役立ちます。

ファーストクラスの継続サポートを使用すると、$ p lor neg p $を表現できます。トリックは、継続を呼び出さず、ある程度の表現で退出することは、同じ表現で継続を呼び出すことと同等であるという事実に基づいています。

詳細については、参照してください。 http://www.cs.cmu.edu/~rwh/courses/logic/www-ald/handouts/callcc.pdf

2-continuation           | Sheffer stoke
n-continuation language  | Existential graph
Recursion                | Mathematical Induction

重要なことの1つは、まだ調査されていないことです。2連合の関係（2つのパラメーターを取る継続）とシェファーストローク. 。古典的な論理では、Shefferストロークはそれ自体で完全なロジックシステムを形成できます（さらに、いくつかの非操作者の概念）。それは馴染みのあることを意味します and, or, not Sheffer Stokeまたは nand.

これは、単一のタイプコンビネーターを使用して他のすべてのタイプを形成できることを促しているため、プログラミングタイプの対応の重要な事実です。

2つの継続のタイプの署名はです (a,b) -> Void. 。この実装により、1つの凝集（通常の継続）を次のように定義できます。 (a,a) - > void、製品タイプAS ((a,b)->Void,(a,b)->Void)->Void, 、合計タイプAS ((a,a)->Void,(b,b)->Void)->Void. 。これにより、表現力の力が印象的です。

さらに掘ると、その作品がわかります実存グラフ唯一のデータ型がn-continuationである言語に相当しますが、既存の言語がこの形式にあるとは表示されませんでした。だから、それを発明するのは面白いと思う。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow