3 ms·

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

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

lisper 4y ago
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 4y ago
It has to be slow. Multiplication will be O(N^2)!
- sudosysgen 4y ago
  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 4y ago
    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 https://en.wikipedia.org/wiki/Church_encoding Unless this HN submitted implementation doesn't use church encoding. In which case I am wrong.
    - atennapel 4y ago
      The page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.
    - wrbs 4y ago
      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 4y ago
        > {[]} = \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 4y ago
        Yeah I made huge assumptions!
woodrush 4y ago
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 4y ago

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 4y ago

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

sudosysgen 4y ago
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 4y ago
  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 https://en.wikipedia.org/wiki/Church_encoding Unless this HN submitted implementation doesn't use church encoding. In which case I am wrong.
  - atennapel 4y ago
    The page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.
  - wrbs 4y ago
    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 4y ago
      > {[]} = \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 4y ago
      Yeah I made huge assumptions!

woodrush 4y ago

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.