News for hackers. Stuff that matters.
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by actually_a_dog on Saturday September 17, 2022 @04:51PM (#32881460)
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.)
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by woodrush on Sunday September 18, 2022 @11:04AM (#32888119)
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.
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by lisper on Saturday September 17, 2022 @07:04PM (#32882499)
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.
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by quickthrower2 on Saturday September 17, 2022 @08:25PM (#32883074)
It has to be slow. Multiplication will be O(N^2)!
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by sudosysgen on Saturday September 17, 2022 @08:50PM (#32883235)
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?
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by quickthrower2 on Saturday September 17, 2022 @09:14PM (#32883403)
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.

Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by wrbs on Sunday September 18, 2022 @08:36AM (#32887023)
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)
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by tromp on Sunday September 18, 2022 @09:22AM (#32887334)
> {[]} = \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
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by quickthrower2 on Sunday September 18, 2022 @08:08PM (#32892733)
Yeah I made huge assumptions!
Re:Show HN: LambdaLisp – A Lisp interpreter that runs on lam... by atennapel on Sunday September 18, 2022 @01:40AM (#32884730)
The page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.