Good Math/Bad Math

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)))))

posted by MarkCC at 5:58 PM

5 Comments:

  • How about Unlambda then?

    http://www.madore.org/~david/programs/unlambda/

    By Anonymous Anonymous, at 3:01 AM  

  • Sorry, but isn't it Eratosthenes?

    By Anonymous Anonymous, 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 Blogger 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 Blogger MarkCC, at 8:39 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 Blogger MarkCC, at 7:43 AM  

Post a Comment

<< Home