/ derivation of the applicative-order Y-combinator in Q / parallels http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html length:{\$[not count x;0;1+.z.s 1_ x]} / we want to replace recursive call with ??? / f1 takes a copy of itself as y f1:{\$[not count x;0;1+y[1_ x;y]]} f1[10 20 30]f1 / swap arguments f2:{\$[not count y;0;1+x[x;1_ y]]} f2[f2]10 20 30 / curry (project) f3:{\$[not count y;0;1+x[x]1_ y]} f3[f3]10 20 30 / short form: {..}[{..}] ~ f:{..};f:f[f] f4:{\$[not count y;0;1+x[x]1_ y]} f4[f4]10 20 30 / abstract self-application f5:{\$[not count y;0;1+{x[x]y}[x]1_ y]} f5[f5]10 20 30 / the equivalent of scheme's "let" f6:{r:{x[x]y}x;\$[not count y;0;1+r 1_ y]} f6[f6]10 20 30 / expand "let" to a lambda f7:{{\$[not count y;0;1+x 1_ y]}[{x[x]y}x]y} f7[f7]10 20 30 / let-ify once more f8:{m:{\$[not count y;0;1+x 1_ y]};m[{x[x]y}x]y} f8[f8]10 20 30 / expand again f9:{{x[{x[x]y}y]z}[{\$[not count y;0;1+x 1_ y]}][x]y} 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:{\$[not count y;0;1+x 1_ y]} Y[length]10 20 30 / abstract common function F:{x[{x[x]y}y]z} Y:{F[x][F x]y} Y[length]10 20 30 / reintroduce Y:{x[y][x y]z}{x[{x[x]y}y]z} / Y:{x[y;x y]z}{x[{x[x]y}y]z} attila v. Y[length]10 20 30 / recursive factorial = {\$[not x;1;x*.z.s x-1]} fac:{\$[not y;1;y*x y-1]} Y[fac]5 / fundamental property fac[Y fac][5]~Y[fac]5 / primitive recursion (attila) / recursive primrec:{\$[z;y[z;.z.s[x;y;z-1]];x]} primrec[1;*;5] / list primrec:{[f;x;y;z]\$[z;y[z;f(x;y;z-1)];x]} Y[{primrec[x]. y}](1;*;5) / project primrec:{[f;x;y;z]\$[z;y[z;f[x][y]z-1];x]} Y[primrec][1][*]5 / apply a:{\$[99