解答

📖 SKIコンビネータで遊んでみよう

👇 Swap:

  S(K(SI))K x y
= yx

👇 B combinator:

B x y z = S (K S) K x y z
        = x ( y z )

👇 Ω combinator:

Ω x = SII x
    = x x

👇 W combinator:

W x y = S S(S K) x y
      = x y y

👇 Y combinator:

Y f = S(K(SII))(S(S(KS)K)(K(SII))) f
    = S(K(SII))(S(S(KS)K)(K(SII))) f

SKIコンビネーター計算機のためのテストケース

👇 すべての変数

  abcdefghijklmnopqrstuvwxyz
= abcdefghijklmnopqrstuvwxyz

👇 I コンビネーター

  I x
= x

👇 K コンビネーター

  K x y
= x

👇 S コンビネーター

  S x y z
= xz(yz)

👇 丸括弧外し

  x(y)
= xy

x(y) が計算結果のケースであれば、それ以上、丸括弧は外さない。
計算中であれば、外さないと多重括弧になってしまう

👇 丸括弧外し

  a(b(c(d(e)f)g)h)i
= abcdefghi

👇 S コンビネーターでの丸括弧の取り扱い

  S (xx) y z
= xxz(yz)

  S x (yy) z
= xz((yy)z)

  S x y zz
= xz(y(zz))