[wrbs]

There's nothing about the lambda calculus which forces you to use the church encoding of natural numbers.

You could also come up with an encoding based on booleans as bits:

  {true} = \t f. t
  {false} = \t f. f

then bytes:

  {0b00001111} = \f. f [false] [false] [false] [false] [true] [true] [true] [true]

which you could merge up into larger integers just like real computers.

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]

which you could imagine using to implement a way more efficient shift-and-add multiply, O(log M * log N)

[tromp]

> {[]} = \c n. n

> {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

[quickthrower2]

Yeah I made huge assumptions!