This is undoubtedly cool, but I'd be really impressed if it wasn't stupidly slow. (I'm not saying it is stupidly slow, because I haven't had a chance to run it, just that I'd be impressed if it wasn't.)
Adding these would be O(N+M) where N and M are the numbers, not the number of bits.
Multiplying is O(N*M) where again it is the numbers.
1000*1000 would require a million operations at least. It takes a million operations just to store/read the number million!
See: https://en.wikipedia.org/wiki/Church_encoding
Unless this HN submitted implementation doesn't use church encoding. In which case I am wrong.
You could also come up with an encoding based on booleans as bits:
{true} = \t f. t
{false} = \t f. f
{0b00001111} = \f. f [false] [false] [false] [false] [true] [true] [true] [true]
or for one less based on the 8-bits and to keep the infinite range you could just represent integers as lists of binary numbers:
{[]} = \c n. n
{x::y} = \c n. c x y
{0} = []
{1} = [true]
{2} = [false, true] (i.e. reversed 0b10)
{3} = [true, true]
{4} = [false, false, true]
> {x::y} = \c n. c x y
Note that Binary Lambda Calculus uses the simpler {x::y} = \c. c x y, which allows you to operate on a list l with
l (\head \tail \dummy. non_null_case) null_case