[actually_a_dog]

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.)

[woodrush]

Thanks for your feedback, I forgot to mention the execution speed in the post. The number guessing game example (44 lines long) in the Usage section actually runs with an instantaneous response time on the terminal. I added some remarks on the execution speed.

[lisper]

I haven't tried it either, but I would not bet my life savings on it being slow. I tried something similar to this a few years ago (see my top-level comment for a pointer) and was amazed at how fast it turned out to be.

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