きしだのはてな このページをアンテナに追加 RSSフィード

2013-08-08(木) カリーハワード同型対応についてのまとめ

カリーハワード同型対応についてのまとめ 16:25 カリーハワード同型対応についてのまとめを含むブックマーク

昨日のエントリでカリーハワード同型対応について触れました。

関数を扱えることはどのようにプログラミング言語の能力をあげるか - きしだのはてな


ついでに、このエントリを書くのに調べたカリーハワード同型対応の資料をまとめておきます。


この記事では、カリーハワード同型対応で、どのような型がどのような論理命題に対応するかを解説してあります。

数理科学的バグ撲滅方法論のすすめ - 第14回 型=命題,プログラム=証明:ITpro


こちらのほうが、ちょっとくだけてるかな?

Curry-Howard Isomorphism - d.y.d.


カリーハワード同型対応での山場は、排中律Schemeのcall/ccに対応するというところで、gotoなどもだいたいこれにあてはまるようです。

排中律、つまり「a または not a」という命題です。これは証明としてはアヤシイので、古典論理からはずしましょうとなって、直観主義論理というのができました。

これが、gotoはアヤシイのでプログラミング言語からはずしましょうという話に対応するわけです。ここがおもしろい。


このあたりは、こちらのエントリが詳しいですが、かなり形式的な説明なので読むのは大変。

call/ccと古典論理のカリー・ハワード対応 - 再帰の反復


書籍としては昨日もあげた「論理の哲学」がとてもいいです。

知の教科書 論理の哲学 (講談社選書メチエ)

知の教科書 論理の哲学 (講談社選書メチエ)


形式的な説明はこちらに載ってます。

論理と計算のしくみ

論理と計算のしくみ


あとは、未読なんですが、この本も評判がよいようで上記「論理の哲学」でも取り上げられています。

情報科学における論理 (情報数学セミナー)

情報科学における論理 (情報数学セミナー)

トラックバック - http://d.hatena.ne.jp/nowokay/20130808