ezyang’s blog

the arc of software bends towards understanding

The Y Combinator and strict positivity

One of the most mind-bending features of the untyped lambda calculus is the fixed-point combinator, which is a function fix with the property that fix f == f (fix f). Writing these combinators requires nothing besides lambdas; one of the most famous of which is the Y combinator λf.(λx.f (x x)) (λx.f (x x)). Now, […]

  • September 12, 2012