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)!
[ Parent
| on HN ]
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!