Posted on: March 21, 2014

Recently I was reading a book on programming languages design and came across something interesting related to Y combinator.

The Question: how to write recursion in lambda function without side effects and built-in recursion support?

First, let’s talk about Russell Paradox: Assume P is the set of all the set that does not contain itself. Does P belongs to P?

Under classical set theory, this is a paradox. The type system for dynamic language more or less resemble such set theory. Let’s say, F is a characteristic function of a set. F(x) = true if x is in the set and F(x) = false otherwise. Under such representation, {1, 2, 3} can be represented as F(x) = (x==1 OR x==2 OR x==3).