Mastodawn

Artyom Bologov Jan 11, 2025

@Laauurraaa the smallest binary footprint dream is actually quite close to #BinaryLambdaCalculus—there are only three (relatively high-level!) primitives that are expressed by short patterns of bits.

And you might've seen me boasting a 350-bit sorting program already, so something taking a whole screen of C code fits into 50 bytes, actually!

Given some (relatively primitive) compiler building, one can have a strictly typed&inferred language that compiles down to raw applicative #LambdaCalculus and actually looks easy on the eye! Something like Scheme & #prescheme, but even more minimalist in the computation basis! And yes, fast too, given a bit of (trivial) optimization and maybe your FPGA ideas

Artyom Bologov Jan 8, 2025

Wait... Wait... No, that can't be right. I made a sorting algorithms in 350 bits of #BinaryLambdaCalculus! It's even less than John Tromp's 436 bits, and it's pretty readable by the #LambdaCalculus standards! I can probably codegolf it down to 320 bits, but I'm not really interested in that right now. The mere fact of it working is an achievement already. And hey, have you ever seen a 350 BITS sorting algorithm?

Find the commit adding it at https://github.com/aartaka/stdlambda/commit/b9e8a671268a3cda2ceb6a8aa5a1dc10dc6f7511

#theWorkshop

list(sort): Add. · aartaka/stdlambda@b9e8a67

Standard library for Lambda Calculus, finally making LC a practical programming language. - list(sort): Add. · aartaka/stdlambda@b9e8a67

GitHub

Artyom Bologov Jan 5, 2025

I think I finally got the trick of wrapping everything into lambdas that applicative order computation forces. Before that, I was blindly using an applicative order #YCombinator and hoping that it's enough. It's not. I have to wrap all the possibly endless loop branches into lambdas and then call these lambdas, but only when they were properly chosen by the branching function. I'm not sure if I'm even making sense here, but you have to trust me on that.

I am now enlightened in the ways of applicative #LambdaCalculus. And my is-sorted function is only taking 70 bytes when compiled to #BinaryLambdaCalculus. And I didn't even optimize it yet!

It seems I have to live with the 10-bit-per-branch overhead of this applicative order juggling 😢

#theWorkshop