目次
アロンゾ・チャーチと電子計算機
アロンゾ・チャーチ（Alonzo Church、1903-1995）はアメリカの数学者です。プリンストン大学で公理的集合論に関する論文で博士号を取得、その後、ハーバード大学、ゲッティンゲン大学等を経てプリンストン大学で数学と哲学の教授に就任。数理論理学と計算機科学の基礎に多大な貢献をしました。特に計算可能性の理論への貢献は、今日の計算機科学の基礎を築きました。
多くの弟子を育て36人の博士を輩出。有名なチャーチ＝チューリングのテーゼはチャーチがチューリングの指導教官時代に発表されました。
チャーチ＝チューリングのテーゼとは、「計算可能な関数」という直観的な概念を帰納的関数の概念と同一視する考え方。簡単には、計算可能な関数とは電子計算機で実行できる関数と同じだという主張のことです。
電子計算機で実行できる計算はすべて帰納的関数によって表現できる。
チャーチ＝チューリングのテーゼ
チャーチは1930年代に計算可能性を研究するためのツールとしてラムダ計算を考案、計算可能なものはすべてラムダ計算で計算可能であることを示しました。さらに、ラムダ計算を用いて1階述語論理が決定不可能である（任意の数学命題が真か偽かを決定するアルゴリズムが存在しない）ことも証明してみせました。
関数型プログラミング（関数を主軸にしたプログラミング）はラムダ計算から発展しました。とりわけラムダ計算が影響を与えたのがLispです。最初の関数型プログラミング言語Lispは、1958年に「AI」（人工知能）の命名で有名な数学者ジョン・マッカーシーによってラムダ計算とともに開発されました。そして、すぐに人工知能の研究に使われるプログラミング言語となりました。
Lispはその語に開発されるプログラミング言語に影響を与えました。Haskell、JavaScript、Mathematica、ML、Perl、Python、R、Ruby、Smalltalkなどがそうです。
ラムダ計算
関数は普通、f(x)、g(x)のようにfやgと名前を付けることを教科書で習います。それは普通のことで当たり前のように私たちは関数を扱う（計算）ことができます。さてラムダ計算とは関数に名前を付けずに取り扱えるようにしたものです。
例えば、
f(x) = x + 2
という関数はラムダ計算ではλ（ラムダ）という記号を用いて
λx. x + 2
のように表します。この式はラムダ式とも呼ばれます。
そして関数のxに何かを代入する場合、たとえばf(x)のxに1を代入する
f(1)
= 1 + 2
= 3
はラムダ計算では次のように記述します。
（λx. x + 2）1
→ 1 + 2
→ 3
なぜラムダ計算なのか？
「f(x) = x + 2」という表現には、2つの意味
・関数の定義
・xという値に対して関数fを適用した
がありますがその区別ができません。私たちは文脈から判別して「f(x) = x + 2」を扱うことができます。
ラムダ計算ならばその2つをいま説明したように区別できます。私たちは自然に計算ができます。当たり前のように計算ができます。しかし、その計算とは何かと問われると実は曖昧なことがわかります。
当時、ヒルベルト、チャーチ、チューリングといった数学者は「計算とは何か」を厳密に定義することをテーマとしていました。
その大きな成果が、チャーチによるラムダ計算とチューリングによるチューリングマシンです。チューリングマシンはその名前にマシンがあることから仮想的ではあるが「マシン」を想像することができます。それに対してラムダ計算はその意義も目的も明らかではありません。発表当時、ラムダ計算は評価されませんでした。
その最大の理由は「マシン」──電子計算機がなかったからです。もし当時電子計算機があれば、ラムダ計算は電子計算機のためにあることが理解されたことでしょう。しかし、現実はその逆でした。
ラムダ計算のおかげで電子計算機、とくにプログラミングの世界がつくられていくことになったのです。それが最初に紹介したプログラミング言語Lispの誕生です。数学者ジョン・マッカーシーはラムダ計算の実装に成功しました。
チャーチ数
０、１、２、３、４、５、６、７、８、９、…
という自然数はまさに私たち人間にとって自然です。電子計算機は自然数を持ち合わせていません（知らない）。ラムダ計算によって自然数をつくる（定義する）ことができます。それがチャーチ数です。
zero = λf.λx. x
one = λf.λx. f x
two = λf.λx. f (f x)
three = λf.λx. f (f (f x))
このチャーチ数の考え方は次の通りです。xはzero、fは引数に+1する関数に対応しています。
zeroはxをそのまま返す
oneは f x = 1 + 0 (=1) を返す
twoは f (f x) = 1 + ( 1 + 0 ) = 1 + 1 + 0 (=2) を返す
thre は f (f (f x)) = 1 + ( 1 + (1 + 0 ) ) = 1 + 1 + 1 + 0 (=3) を返す
というように関数fを適用する回数に自然数を対応させることで自然数が表現できます。
電子計算機は人間のように自然に当たり前に“計算”できません。ラムダ計算のおかげで電子計算機は“計算”できるようになります。“計算”とは何かを定義できたのはラムダ計算のおかげです。
ラムダ計算を使えば高度な“計算”が可能になります。例えば高階関数です。高階関数とは関数を引数にとることができる、または関数を返すことができる関数のことです。
無名関数
電子計算機が登場する以前にチャーチが発明したラムダ計算は、1958年のLisp以来、多くのプログラミング言語に「無名関数」として搭載されています。ラムダ計算には関数の名前がないことからこう呼ばれています。
たし算 a+bを無名関数で定義する例
Lisp (setq add (lambda (a b) (+ a b)))
Ruby add = lambda{ |a, b| a + b }
Python add = lambda a, b: a + b
C++ auto add = [](int a, int b){ return a + b; };
C# Func<int, int, int> add = (a, b) => a + b;
PHP $add = function($a, $b){ return $a + $b; };
Lua add = function(a, b) return a + b end
Kotlin val add = {a:Int, b:Int -> a + b}
コンピューター言語では無名関数を「lambda」として定義しているものもあります。Lisp、Ruby、そして筆者の大好きなPythonなどです。Pythonの無名関数「ラムダ式」はラムダ計算を試してみるのに打って付けの文法です。
次はさきほどラムダ計算で定義したチャーチ数をPythonのラムダ式でコーディングしたものです。両者を比べてみるとコードが見事に対応していることが読み取れます。
ラムダ計算
zero = λf.λx. x
Pythonのラムダ式
zero = lambda f: lambda x: x
0から3までをチャーチ数として定義して、チャーチ数を整数に変換する関数を作っておくことで、チャーチ数zeroが整数0、チャーチ数oneが整数1に対応していることが確認できます。
チャーチ数を使ってたし算をしてみます。ラムダ計算でたし算を定義すると
plus = lambda m: lambda n: lambda f: lambda x: m(f)(n(f)(x))
となります。引数mとnにチャーチ数を渡してあげることでチャーチ数のたし算ができます。戻り値（チャーチ数）を整数に変換することでたし算ができていることを確認できます。
ぜひみなさんもご自身の電子計算機でラムダ計算をためしてみてはいかがでしょうか。現在は電子計算機にプログラミング環境をインストールせずに、Web上でコーディングが可能です。
