I had a spare day yesterday so, rather than clean my house, I made a model of the SKI combinator calculus out of a pizza box.
[youtube url=http://www.youtube.com/watch?v=fZQMmgElRMI]
Ingredients:
- this sheet of combinator tiles
- some cardboard (I used an old pizza box, which was a terrible, smelly idea)
- glue
- blu-tack
- a quick read of the Wikipedia page on the SKI calculus
You’ve almost definitely heard of Turing machines and Turing completeness. You might have heard of the λ-calculus, which was invented by Alonzo Church around the same time as Turing was thinking about machines, and has exactly the same computing power (the Church-Turing thesis!) but looks very different. λ-calculus deals purely with functions and function application, in a very abstract algebraic way, so unlike with Turing machines it’s very hard to fix in your head a physical model of how computations happen.
The SKI calculus boils λ-calculus down to just three operations, or combinators. Those three (( in fact you only need S and K or, if you’re really Zen, you can create a single combinator which does everything )) are enough to recreate every expression you can create with λ-calculus. I’ve been meaning to get my head round it for a while, but implementing it on a computer wasn’t very enlightening.
So I had a brainwave recently, which was that I could make tiles representing the combinators, and the way they fit together would dictate how they act. I just about worked out something reasonable yesterday, which is why I decided to record a video. I hope you found it interesting!
Further reading:
A nice page by Mike O’Donnell introducing the SKI calculus and explaining why it’s so great.
A browser-based SKI expression evaluator (it uses a different notation to the one I used in the video)
Lazy K, an SKI-based programming language you can use to write actual useful (( subject to your definition of the word ‘useful’ )) programs in!