ラムダ計算
(2つ組の)順序対のデータ型は、 TRUE および FALSE を用いて定義することができる。これらはチャーチ対(英語版)(英: Church pairs)とよばれている。
CONS := λs b f. f s b
CAR := λp. p TRUE
CDR := λp. p FALSE
リンク型のリスト構造は、空リストのために特定の予約された値(例えば FALSE )を用い、リストをその先頭要素と後続リストの CONS 対として表現することによって実現できる。
また、非形式的な説明で述べたようにMをラムダ式としたとき、λx. (λy. M)をλxy. Mと略記する。
ラムダ抽象によって束縛されていない変数を自由変数(英: free variable)という。式 λx. (x y) において、 y は自由変数である。ある変数の出現が自由出現であるかどうかは、より正確には以下のように帰納的に定義されている。
ラムダ式 V が変数のとき、 V は自由出現である。
ラムダ式 λV. E において、 E で自由出現している変数のうち V 以外のものが自由出現である。このとき、 E 中の変数 V はラムダに束縛されたという。
ラムダ式 (E E′) において、 E での自由出現と E′ での自由出現の和が自由出現である。
ラムダ式の集合の上での同値関係(ここでは == と書くことにする)は、直感的には、2つのラムダ式が同じ関数を表していることである。この同値関係は以下で述べるα-変換とβ-簡約によって定義される。第3の規則としてη-変換と呼ばれる規則が導入されることもある。