α変換 β変換

いやー。名前だけ聞いたらものすごい難しそうで避けて通ってたけど勉強してみたら以外に当たり前のことだった。
Wikipedia でお勉強

α変換

束縛変数（引数になっている変数）の名前を別の名前に変えること

function(x){ return (function(x){ return x })(x) }
// ↓ α変換
function(y){ return (function(x){ return x })(y) }
// ↓ α変換
function(y){ return (function(z){ return z })(y) }
// ↓ α変換
function(z){ return (function(z){ return z })(z) }

こんな感じか。
条件があって

1. 変換後の名前が、自由変数（引数になっていない変数）の名前と被っちゃダメ。
2. その束縛変数を持つラムダに内包されたラムダが変換前の名前の束縛変数を持つ場合はその中の変数名は変換しない。

おk

β変換

ラムダを式に適用しているときに、そのラムダの束縛変数を、適用されている式に「置き換え」てラムダを消す。（言葉で説明できない＞＜
また、束縛変数が未使用な場合は η 変換というらしい。
ちょっとチャーチ数の succ(1) を 2 に β変換してみる

(function(n){ return (function(f){ return function(x){ return f(n(f)(x)) }}})(function(f){ return function(x){ return x }})　// succ(1)
// ↓ β変換
function(f){ return function(x){ return f((function(f){ return function(x){ return x }})(f)(x)) }}
// ↓ η変換
function(f){ return function(x){ return f((function(x){ return x })(x)) }}
// ↓ β変換
function(f){ return function(x){ return f(x) }} // 2

なるほどー。
条件は

1. 適用されている式の自由変数が束縛変数になっちゃダメ＞＜

ということらしい