Alonzo ChurchとStephen Cole Kleeneが1930年代に発明した計算モデル

すべての計算が関数定義と関数適用の基本的な演算に帰着される

変数や値も全てラムダ抽象で表す

例えばtrueも自然数も関数

ref Church encoding

四則演算子などもない、必要であれば無から関数で構成する

二変数関数は一変数関数を返す関数として定義

ラムダ計算の実行順序は、継続によって決まる

イメージ的には以下のような階層関係

それ以外の型付きラムダ計算

こういうふうにも見れる

ラムダ計算

それ以外の型付きラムダ計算

「型なしラムダ計算」を「1つの型しか持たない型付きラムダ計算」、と見ている

ラムダ計算の実行の抽象化

関連

ラムダ計算の処理系

勉強のための資料集

参考

今読んだ中では一番くわしい

『C言語による計算の理論』 11章

計算可能性の話に重点を置いて、関連してラムダ計算の紹介がある

実践より

Schemeでごにょる