Y-Combinator with Clojure


I spent the past weekend working through the talk by Jim Weirich on the Y-Combinator. The talk is available at InfoQ. This talk is similar to the Ruby talk he gave at RubyConf 2012.

This post is the gist of that demo. Jim does a phenomenal job of walking through the example. I have shared the gist to make it easy to follow the demo.

Some neat things I got to learn from the talk are the refactoring techniques and how with these techqniques one could arrive at the Y-Combinator. Staring at the Y-Combinator definition before this talk always made me wonder how Church could have arrived at this definition. In this talk, you will also understand the simplicity of lambda calculus.

Refactoring in functional programming : Even though I have seen the techniques while factoring out variables, it was nice to put names to such techniques. The four techniques you will hear about in the talk are)

  • Tennent Correspondence Principle
  • Introducing Bindings
  • Wrapping functions
  • Inlining

Just with these four techniques Jim shows how a naive implementation of a factorial function can be converted to pure lambda calculus form. This conversion motivates the need for the combinator known as the Y-Combinator (generally called Fixed-Point Combinator.