Lazy じゃない K
- i(a,...) → a(...)
- k(a,b,...) → a(...)
- s(a,b,c,...) → a(c,b(c),...)
という変換をするマクロを書いてみた。
define(`apply',`ifelse($2,,$1, regexp($1,[a-z]\(()\)?$),-1,`regexp($1,\([a-z]\)(\(.*\)),\1(\2,shift($@)))', `regexp($1,\([a-z]\),\1(shift($@)))')')dnl define(`i',`ifelse($#,0,``i'',$1,,``i'',`apply($1,shift($@))')')dnl define(`k',`ifelse($#,0,``k'',$1,,``k'',$2,,``k''($1), `apply($1,shift(shift($@)))')')dnl define(`s',`ifelse($#,0,``s'',$1,,``s'',$3,,``s''($@), `apply(apply($1,$3,apply($2,$3)),shift(shift(shift($@))))')')dnl dnl test i i() i(a) i(a()) i(a,b) i(a(),b) i(a(b),c) i(a,b,c) i(a(),b(c),d) i(a(b),c,d) i(a,b,c,d) i(a(),b,c,d) k k() k(a) k(a()) k(a,b) k(a(),b) k(a(b),c) k(a,b,c) k(a(),b(c),d) k(a(b),c,d) k(a,b,c,d) k(a(),b,c,d) s s() s(a) s(a()) s(a,b) s(a(),b) s(a(b),c) s(a,b,c) s(a(),b(c),d) s(a(b),c,d) s(a,b,c,d) s(a(),b,c,d) s(a(b),c,d,e) s(s(s(s(i,k(k(i))),k(k(k(S)))),k(k(I))),k(K)) s(s(s(s(i,k(k(i))),k(k(k(S)))),k(k(I))),k(K),s) s(s(s(s(i,k(k(i))),k(k(k(S)))),k(k(I))),k(K),k) s(s(s(s(i,k(k(i))),k(k(k(S)))),k(k(I))),k(K),i)
遅延評価しないので、
k(A,s(i,i,s(i,i)))
のようなヤツは再帰の段数が限度を越えてしまってエラーになる。
ところで Lazy じゃない Lazy K はチューリング完全なのだろうか。
