3 ms·

As author of the Binary Lambda Calculus (BLC), I find this quite fascinating. It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric langua

by tromp 4y ago

As author of the Binary Lambda Calculus (BLC), I find this quite fascinating. It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits. I'm still reading the document, but one thing that caught my eye is the List encoding with cons and nil, which is claimed to be a Mogensen-Scott one. Rather, cons \x\y\c. c x y is the Scott encoding of infinite lists that have no nil terminator (also known as streams) and thus only one constructor, while nil is the Scott encoding in nil-terminated lists with 2 constructors. Thus the given encoding is some non-standard hybrid of streams and lists that helps BLC achieve its conciseness. In Wikipedia [1] it's described as > Alternatively, with NIL := FALSE, the construct l (λh.λt.λz.deal_with_head_h_and_tail_t) (deal_with_nil) obviates the need for an explicit NULL test [1] https://en.wikipedia.org/wiki/Lambda_calculus#Pairs https://en.wikipedia.org/wiki/Lambda_calculus#Pairs

lisper 4y ago
> It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits. That's hardly a fair comparison. LambdaLisp includes a ton of features that BLC and BF do not.
- keithalewis 4y ago
  Slap yourself and reread the rest of the post.
  - lisper 4y ago
    Sorry, I’m going to need you to give me a little more of a clue what you are talking about.
    - keithalewis 4y ago
      You missed the substantive portion of the post.
tromp 4y ago
> Writing in continuation-passing style also helps the lambda calculus interpreter to prevent re-evaluating the same term multiple times. This is very, very important and critical when writing programs for the 521-byte binary lambda calculus interpreters Blc, tromp and uni, since it seems that they lack a memoization feature, although they readily have a garbage collection feature. Note that Melvin Zhang added a memoization feature (call-by-need evaluation with result sharing) in his refactoring [1] of my BLC interepreter. [1] https://github.com/melvinzhang/binary-lambda-calculus https://github.com/melvinzhang/binary-lambda-calculus
tromp 4y ago
> The pattern \lambda a. \lambda b. \lambda w. \lambda x. \lambda y. yλa.λb.λw.λx.λy.y is noticable in many places in lambdalisp.pdf, since isnil is used a lot of times in LambdaLisp. Sadly, this heavy use of the isnil operator derived in section [1] adds a lot of unnecessary verbosity, since instead of writing isnil list result1 (let { head = car list, tail = cdr list} in result2) one can simply write list (\head \tail \_ . result2) result1 [1] https://woodrush.github.io/blog/lambdalisp.html#deriving-isnil https://woodrush.github.io/blog/lambdalisp.html#deriving-isn...
woodrush 4y ago
Thank you for taking a look, and many thanks for your constructive comments. I found the BLC language and interpreter to be elegant and that was what brought me here. I was unaware of the nil-test-free method for Scott-encoded lists. It's true that it would remove a lot of bits from LambdaLisp's implementation. I'll also be using this for future projects. I was also unaware of Melvin Zhang's interpreter. I suspect that result sharing would improve the execution speed. I'll try to add that in one of the supported interpreters in the repository. Thank you very much for thoroughly reading my post and pointing these facts out. It has deepened my understanding and interest for binary lambda calculus. I also want to say that Lazy K is one of my all-time favorite languages, as I mentioned in the post. It was about 10 years ago when I first found out about Lazy K - at that time I wrote a blog post about a language I made that directly transpiles to Lazy K (written in Japanese). Although at that time I couldn't fully grasp the language, I'm happy that now I could write large programs for Lazy K. I was thrilled to find that the Lazy K language proposal was now published on your website.

by tromp 4y ago

lisper 4y ago

> It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits. That's hardly a fair comparison. LambdaLisp includes a ton of features that BLC and BF do not.

keithalewis 4y ago
Slap yourself and reread the rest of the post.
- lisper 4y ago
  Sorry, I’m going to need you to give me a little more of a clue what you are talking about.
  - keithalewis 4y ago
    You missed the substantive portion of the post.

tromp 4y ago

> Writing in continuation-passing style also helps the lambda calculus interpreter to prevent re-evaluating the same term multiple times. This is very, very important and critical when writing programs for the 521-byte binary lambda calculus interpreters Blc, tromp and uni, since it seems that they lack a memoization feature, although they readily have a garbage collection feature. Note that Melvin Zhang added a memoization feature (call-by-need evaluation with result sharing) in his refactoring [1] of my BLC interepreter. [1] https://github.com/melvinzhang/binary-lambda-calculus https://github.com/melvinzhang/binary-lambda-calculus

tromp 4y ago

> The pattern \lambda a. \lambda b. \lambda w. \lambda x. \lambda y. yλa.λb.λw.λx.λy.y is noticable in many places in lambdalisp.pdf, since isnil is used a lot of times in LambdaLisp. Sadly, this heavy use of the isnil operator derived in section [1] adds a lot of unnecessary verbosity, since instead of writing isnil list result1 (let { head = car list, tail = cdr list} in result2) one can simply write list (\head \tail \_ . result2) result1 [1] https://woodrush.github.io/blog/lambdalisp.html#deriving-isnil https://woodrush.github.io/blog/lambdalisp.html#deriving-isn...

woodrush 4y ago

Thank you for taking a look, and many thanks for your constructive comments. I found the BLC language and interpreter to be elegant and that was what brought me here. I was unaware of the nil-test-free method for Scott-encoded lists. It's true that it would remove a lot of bits from LambdaLisp's implementation. I'll also be using this for future projects. I was also unaware of Melvin Zhang's interpreter. I suspect that result sharing would improve the execution speed. I'll try to add that in one of the supported interpreters in the repository. Thank you very much for thoroughly reading my post and pointing these facts out. It has deepened my understanding and interest for binary lambda calculus. I also want to say that Lazy K is one of my all-time favorite languages, as I mentioned in the post. It was about 10 years ago when I first found out about Lazy K - at that time I wrote a blog post about a language I made that directly transpiles to Lazy K (written in Japanese). Although at that time I couldn't fully grasp the language, I'm happy that now I could write large programs for Lazy K. I was thrilled to find that the Lazy K language proposal was now published on your website.