## Friday, May 19, 2006

### Programming SKI

As an interesting followup to the post on combinators: an extremely crazy individual actually implemented a SKI combinator calculus interpreter called Lazy K. And what's even crazier is, he implemented the Sieve of Eristathenes in LazyK. Here it is:

`K(SII(S(K(S(S(K(SII(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(SS(S(S(KS)K))(KK)))))(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(S(KS)(S(S(KS)(S(KK)(SII)))(K(SI(KK)))))))(K(S(K(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)(S(S(KS)K)I)(S(SII)I(S(S(KS)K)I)(S(S(KS)K)))))(SI(K(KI)))))))))(S(KK)K)))))))(K(S(KK)(S(SI(K(S(S(S(S(SSK(SI(K(KI))))(K(S(S(KS)K)I(S(S(KS)K)(S(S(KS)K)I))(S(K(S(SI(K(KI)))))K)(KK))))(KK))(S(S(KS)(S(K(SI))(S(KK)(S(K(S(S(KS)K)))(SI(KK))))))(K(K(KI)))))(S(S(KS)(S(K(SI))(SS(SI)(KK))))(S(KK)(S(K(S(S(KS)K)))(SI(K(KI)))))))))(K(K(KI))))))))))(K(KI)))))(SI(KK)))))(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))))K))))(S(S(KS)(S(KK)(SII)))(K(SI(K(KI)))))))(SII(S(K(S(S(KS)(S(K(S(S(SI(KK))(KI))))(SS(S(S(KS)(S(KK)(S(KS)(S(K(SI))K)))))(KK))))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))(K(S(S(KS)K)))))))(K(S(S(KS)(S(K(S(S(SI(KK))(KI))))(S(KK)(S(K(SII(S(K(S(S(KS)(S(K(S(K(S(S(KS)(S(KK)(S(KS)(S(K(SI))K))))(KK)))))(S(S(KS)(S(KK)(S(K(SI(KK)))(SI(KK)))))(K(SI(KK))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)(SII)))(K(SI(K(KI))))))))(K(K(SI(K(KI)))))))))(S(K(SII))(S(K(S(K(SI(K(KI))))))(S(S(KS)(S(KK)(SI(K(S(K(S(SI(K(KI)))))K)))))(K(S(K(S(SI(KK))))(S(KK)(SII)))))))))))(K(SI(K(KI))))))))(S(S(KS)K)I)(SII(S(K(S(K(S(SI(K(KI)))))K))(SII)))))`

• I'll be honest: I'm less scared by Brainfuck.

By Thomas Winwood, at 6:26 PM

By Anonymous, at 3:01 AM

• Sorry, but isn't it Eratosthenes?

By Graham Douglas, at 7:06 AM

• I like LazyK better than unlambda because it's pure. Unlambda has IO side effects; LazyK doesn't. I also prefer the lazyK syntax; unlambda is unreadable. LazyK is also unreadable, but it's unreadable because SKI calculus is unreadable, not because the syntax is obfuscatory. :-)

By MarkCC, at 8:31 AM

• graham:

Yeah, you're right. I always get that wrong. When I first learned about the sieve (all the way back in high school!), I learned about it reading a book on level-1 basic for the TRS-80, and that book had it wrong.

But it made an impression on me; it's *such* a fascinating algorithm, and it's the first real interesting algorithm that I recall learning. Since then, I've never been able to make myself remember that I learned it wrong. You'd think that after something like 27 years(!), I'd be able to get it straight.

(Just to give you an idea of what a geek I've always been: I was reading a book about TRS-80 basic when I was in 7th grade even though I *never* had a TRS-80. I'd seen my first computer, and I was fascinated, and that was the only book on programming at the library.)

By MarkCC, at 8:39 AM

Well now, if we allows ourselves to give names to SKI functions does it need to be unreadable?

I fact I would guess that the example given here was not originally constructed as we see it here and that instead this is expansion of an expression that was quite readable to its author and probably on the same order of intelligibility as the equivalent lambda calculas expression.

By mandrewa, at 2:25 AM

• And I don't mean to say that I thought he constructed these programs in lambda calculus, although he could have, but it's more likely he used a combinator language.

What I am saying is that I'm sceptical that the author constructed these programs using only the tools presented. Despite claims to the contrary; although in fact I'm not sure there is any explicit claim to the contrary, only an implication.

By mandrewa, at 2:38 AM

• mandrewa:

Actually, the author of that beast *does* admit that he generated with a lambda calculus translator. :-)

I *do* think that SKI calculus is intrinsically unreadable; the deliberate exclusion of variables has valuable and useful properties, but it makes it very hard for human readers.

If you know of a language or tool based on SKI that's readable, I'd love to see it. The concept of SKI is so amazing, I'd be really excited to see something that actually made it approachable/usable.

The best I've seen is the pure lazy lambda calculus languages which use SKI for compilation. Haskell, once you get the hang of it, can be an absolutely wonder of clarity, but the SKI is hidden under lamdba.

By MarkCC, at 7:43 AM