「カリー/ハワード対応への障壁」において、カリー/ハワード対応(Curry-Howard correspondence/isomorphism)をうまく説明するのは難しい、という話をしました。その記事の最後の一言は: いまだベストと思える説明に届かず。 その後も、ベスト(に近い)説明とはどんなものかと考えています。以前から僕は「大きなラムダ計算」という方法を使っているのですが、これをベースにするのがやはり良いように思えます。大きなラムダ計算は型付きラムダ計算の定式化のひとつです。大きなラムダ計算をまともに紹介したことがなかったので、この記事と引き続く記事の2回に分けて説明します(続く第2回もほぼ書き終えていますよ ^_^)。 この2回の記事で、大きなラムダ計算の構文的・証明論的側面を紹介します。ラムダ式への型付けアルゴリズムを形式的証明と捉えて、その証明系の性質を調べます。カリー/ハワード