S = (λfgx.fx(gx)) K = (λxy.x) I = (λx.x)All other use of λ is thus avoided, as well as the pesky variables. The syntax of this language, called combs here, is even simpler than for the λ calculus:
<expression> := S | K | I | (<expression> <expression>)Application is still left associative. Indeed these three functions can be explained ab initio without λ thus:
(Sfgx) → (fx(gx)) (Kxy) → x (Ix) → xwhere the small letters might stand for arbitrary expressions. Now any function is equivalent to some expression which includes only parentheses and the letters S, K and I.
Unlambda is a Polish version of this language.
The program cnvSch2 transforms a λ expression into a Scheme program with the same meaning. This Scheme function, C, inspired by this page converts the yield of cnvSch2 into combs. The Y-combinator (λfx.(f(xx))(λx.(f(xx)))) is transformed by cnvSch2 to the Scheme program
(λ(b)((λ(c)( b (λ(d)(( c c ) d ))))(λ(c)( b (λ(d)(( c c ) d ))))))which then converts by Scheme program C to:
Which may be shortened by exploiting the associativity convention with this program, ass, to:
(S (S (S (K S) (S (K K) I)) (S (S (K S) (S (S (K S) (S (K K) (K S))) (S (S (K S) (S (S (K S) (S (K K) (K S))) (S (S (K S) (S (K K) (K K))) (K I)))) (S (S (K S) (S (K K) (K K))) (K I))))) (S (K K) (K I)))) (S (S (K S) (S (K K) I)) (S (S (K S) (S (S (K S) (S (K K) (K S))) (S (S (K S) (S (S (K S) (S (K K) (K S))) (S (S (K S) (S (K K) (K K))) (K I)))) (S (S (K S) (S (K K) (K K))) (K I))))) (S (K K) (K I)))))
I do not pretend to read such programs and I do not find Formatting helpful.
((λSKI. ((λn.ni0) (( ((S ((S ((S (K S)) ((S (K K)) I))) ((S ((S (K S)) ((S ((S (K S)) ((S (K K)) (K S)))) ((S ((S (K S)) ((S ((S (K S)) ((S (K K)) (K S)))) ((S ((S (K S)) ((S (K K)) (K K)))) (K I))))) ((S ((S (K S)) ((S (K K)) (K K)))) (K I)))))) ((S (K K)) (K I))))) ((S ((S (K S)) ((S (K K)) I))) ((S ((S (K S)) ((S ((S (K S)) ((S (K K)) (K S)))) ((S ((S (K S)) ((S ((S (K S)) ((S (K K)) (K S)))) ((S ((S (K S)) ((S (K K)) (K K)))) (K I))))) ((S ((S (K S)) ((S (K K)) (K K)))) (K I)))))) ((S (K K)) (K I))))) (λrn.(zn(λd.H)(λD.((λnfx.f(nfx))(r(dn))))i))) 7)) ) (λfgx.fx(gx)) ; S (λxy.x) ; K (λx.x) ; I ) ; => 7