June 14, 2009 •

Factorial in Lazy K

(This is a copy of my archived answer on StackOverflow, for posterity, and so I can edit it to keep links up to date.)

Lazy K

Your pure functional programming nightmares come true!

The only Esoteric Turing-complete Programming Language that has:

A purely functional foundation, core, and libraries---in fact, here's the complete API: S K I
No lambdas even!
No numbers or lists needed or allowed
No explicit recursion but yet, allows recursion
A simple infinite lazy stream-based I/O mechanism

Here's the Factorial code in all its parenthetical glory:

K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
 (S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)

Features:

No subtraction or conditionals
Prints all factorials (if you wait long enough)
Uses a second layer of Church numerals to convert the Nth factorial to N! asterisks followed by a newline
Uses the Y combinator for recursion

In case you are interested in trying to understand it, here is the Scheme source code to run through the Lazier compiler:

(lazy-def '(fac input)
   '((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
       (* a n)))) 1 1))

(for suitable definitions of Y, cons, 1, 10, 42, 1+, and *).

EDIT:

Lazy K Factorial in Decimal

(10KB of gibberish or else I would paste it). For example, at the Unix prompt:

    $ echo "4" | ./lazy facdec.lazy
    24
    $ echo "5" | ./lazy facdec.lazy
    120

Rather slow for numbers above, say, 5.

The code is sort of bloated because we have to include library code for all of our own primitives (code written in Hazy, a lambda calculus interpreter and LC-to-Lazy K compiler written in Haskell).