News for hackers. Stuff that matters.
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!