[quickthrower2]

It has to be slow. Multiplication will be O(N^2)!

[sudosysgen]

Multiplication is generally done in O(n^2) of the number of bits so I'm not sure what you mean to say. Do you mean O(n^2) of the size of the operands?

[quickthrower2]

In Lambda calculus, numbers are encoded using 0 and successor. So 3 = S(S(S(0)))

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.

[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!

[atennapel]

The page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.