Y-Combinator Beta Reduction

I've been intrigued by the Y-Combinator since I was first introduced to the idea by a friend. On face value, the idea of recursion via nothing but lambda expressions is a subtle and powerful concept that takes time to sink in and reveal its inner elegance and simplicity. It truly feels like a wonder of wonders.

Yet, today I attempted to convey that wonder of wonders to my coworkers. As part of my 30 days of Haskell challenge, I prepared a short presentation about the λ (lambda) calculus. The goal was two-fold, provide enough basic context about the λ calculus to feel comfortable with Beta Reduction, so that it would be possible to Beta Reduce the Y-Combinator to show how it allows for recursion through Divergence.

But most of all, I wanted to provide others that have the same curiosity I have about the Y-Combinator, with a pure λ calculus visual Beta Reduction that reveals how the divergence occurs. My goal was to allow others the ability to experience the wonder of the Y-Combinator for themselves, and to experience that "Aha!" moment when it finally clicks, by hopefully providing them with enough visual context to put the pieces together for themselves.

The slides of the presentation are available here. If you have any feedback, or critiques, please feel free to contact me at rick dot winfrey at gmail dot com.

If you are wanting to learn more about the λ calculus, I highly recommend you read Chris Allen's and Julie Moronuki's treatment of the λ calculus in Haskell Programming from first principles, and then continue on with Raul Rojas' A Tutorial Introduction to the Lambda Calculus.

Happy λ!