Subscribe

Deriving the Y Combinator

Published on Thursday, October 5th, 2017 :: programming-languages, y-combinator

Updated on Sunday, December 9th, 2018

The Y combinator is a somewhat magical aspect of the untyped lambda calculus. Many people tried to explain this magic, but I found them somewhat unsatisfactory.

  • Most explanations show the combinator in the beginning and then simply demonstrate that the given combinator is correct.
  • Some other explanations contain lines like “Why don’t we try passing it to itself? And look, this turns out to be exactly what we want!”

The problem with these is that they don’t give an intuition for how one could constructively derive the combinator. What on earth makes you think that passing it to itself is a good idea? As such, this post, intended for those who know the Y combinator already but do not satisfy with the existing explanations, attempts to explain how one could constructively derive the Y combinator.

Rainbow in Pygments

Published on Tuesday, January 3rd, 2017 :: racket, blog, pygments

Updated on Thursday, December 6th, 2018

I tried to learn continuations yesterday. This led me to a tutorial on composable continuations in schemewiki.org. It explains things nicely, but what really intrigues me is something completely different: rainbow parentheses on mouse hovering.

This post, of course, explains how I managed to get it on my website!

1
(define x (+ 1 (+ 3 (+ 2 4) (+ 9 9))))