to mock a mockingbirdを読む(1)9章

スマリヤンの本の9章から、コンビネータ論理についての話が始まります。
ただし、コンビネータという言葉を使わずにコンビネータのことを鳥(bird)と呼ぶことにして
話が展開されてゆきます。本書を読み進めていくと最終的には不完全性定理に行きつきます。
楽しみにしておいてください。

鳥Aと鳥Bがいるとして、鳥ABとはBの名前を聞いたときに鳥Aによって名前がつけられた鳥のことを表します。
これだと長いので鳥Aへの鳥Bの反応をABと書くということにします。

一般的にABはBAと同じとは限りません(交換法則が成り立たない)

さらに鳥Cも加えたとき、
一般的にA(BC)は(AB)Cと同じとは限りません(結合法則が成り立たない)

単にABCと書いたとき、これがA(BC)を意味するのか(AB)Cを意味するのか知ることはできません。
注：本書にはこう書かれていますが一般的にはABCは(AB)Cを表すこととし(関数適用が左結合だとみなす)
そうすることによって生じる曖昧さもありません。
本サイトではこちらを採用することとします。
追記：本書でも11章で左結合の記法が採用されます。

Mockingbirds

常に次の条件をみたす鳥Mをmockingbird(ものまね鳥)と呼ぶ

Mx = xx

Mがmockingbirdと呼ばれるのは、Mのxへの反応は
xのx自身への反応と同じという単純な理由によります。

Composition

任意の鳥A,B,C,x(異なっている必要はない)について
次の条件を満たすときCはAとBの合成(composition)と呼ぶ

Cx = A(Bx)

Cのxへの反応は、Aの(Bのxへの反応)への反応と同じことを表します。