/ derivation of the applicative-order Y-combinator in K / parallels http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html length:{:[~#x;0;1+_f 1_ x]} / we want to replace recursive call _f with ??? / f1 takes a copy of itself as y f1:{:[~#x;0;1+y[1_ x;y]]} f1[10 20 30;f1] / swap arguments f2:{:[~#y;0;1+x[x;1_ y]]} f2[f2;10 20 30] / curry (project) f3:{:[~#y;0;1+x[x]1_ y]} f3[f3;10 20 30] / short form: {..}[{..}] ~ f:{..};f:f[f] f4:{:[~#y;0;1+x[x]1_ y]} f4:f4[f4] f4 10 20 30 / abstract self-application f5:{:[~#y;0;1+{x[x]y}[x]1_ y]} f5:f5[f5] f5 10 20 30 / the equivalent of scheme's "let" f6:{r:{x[x]y}[x];:[~#y;0;1+r 1_ y]} f6:f6[f6] f6 10 20 30 / expand "let" to a lambda f7:{{:[~#y;0;1+x 1_ y]}[{x[x]y}[x]]y} f7:f7[f7] f7 10 20 30 / let-ify once more f8:{m:{:[~#y;0;1+x 1_ y]};m[{x[x]y}[x]]y} f8:f8[f8] f8 10 20 30 / expand again f9:{{x[{x[x]y}[y]]z}[{:[~#y;0;1+x 1_ y]}][x]y} f9:f9[f9] f9 10 20 30 / final step: extract f leaving Y (revert to long form) Y:{{x[{x[x]y}[y]]z}[x][{x[{x[x]y}[y]]z}[x]]y} length:{:[~#y;0;1+x 1_ y]} Y[length]10 20 30 / recursive factorial = {:[~x;1;x*_f x-1]} fac:{:[~y;1;y*x y-1]} Y[fac]5 / http://okmij.org/ftp/Computation/fixed-point-combinators.html U:{x[x]} U[{:[~y;1;y*U[x]y-1]}]5 / tromp: Y = SSK(S(K(SS(S(SSK))))K) / curry: Y = S(K(SII))(S(S(KS)K)(K(SII))) S:{x[z][y[z]]} K:{y;x} I:{x} curry:S[K[S[I][I]]][S[S[K[S]][K]][K[S[I][I]]]] tromp:S[S][K][S[K[S[S][S[S[S][K]]]]][K]]