The hint file [1] of my 2012 IOCCC entry provides a nice introduction to the binary lambda calculus that this awesome piece of work runs on.

All the lambda terms on that page were manually optimized for minimum blc size. This C compiler term on the other hand was produced by several layers of translation, making it rather large. I suspect that a handwritten version could be written in a thousand pages of lambdas...

Btw, while it makes a nice stress test for LaTeX, I find it a bit odd that "pages of PDF" is the preferred way to express the size of the lambda binary:-)

Looking forward to seeing the binary lambda calculus back-end added to ELVM.

[1] https://www.ioccc.org/2012/tromp/hint.html

I actually mentioned your hint file in details.md. Quite a roundabout way to decode its secrets!

I too suspect that writing in lambda's native functional style could save a lot of space. Compiling lisp.c from the ELVM repository generates a code much longer than LambdaLisp [1], which empirically shows that well I believe.

As for the pages of PDF, in mathematical terms, since any variable encodes to weight 1, I believe it would be something close to an encoding that degenerates all De Bruijn indices to 1, or in other words, one that only tries to weigh (or gives larger weight to) the complexity of abstraction depths and applications. Since that erases information about the variable I would guess it's not a universal method for weighing lambda sizes.

In this particular case for LambdaVM programs however, since the memory initialization clause nor the instruction clause never increases the maximum De Bruijn index value, I believe both the BLC size and "lambda page size" approximately grows linearly with the number of instructions, so I thought it would serve as an approximately-off-by-a-factor metric for weighing its size.

As for the ELVM lambda calculus back-end, I'll be sending the pull request very soon!

[1] A Lisp interpreter implemented in lambda calculus: https://github.com/woodrush/lambdalisp

This is the most spectacular waste of time I have ever seen. I absolutely love it!

Not to mention printing resources. I already had to pause to refill the black toner cartridge twice and reloaded the paper tray countless times, and the end is nowhere near.

I was deceived by a glimmer of false hope: a page full of ). Alas, I then glanced at the page number---far short of the 18000+ goal.

It would probably be cheaper to use one of those "print-on-demand" book services and get multiple hardback volumes than pay for all that ink.

Volumes XVIII, XIX and XX: closing parens.

<https://github.com/woodrush/lambda-8cc/blob/main/bin/lambda-...>

Not necessarily, this actually sounds like a great bootstrapping tool. All you need to write on a new platform is a BLC interpreter, which should be easier to implement. Using the C->BCL translation, you might be able to build something like TinyCC and work up from there.

I would think that the amount of RAM used by the lambda-monster (100+ GB to compile single-page C files) would make a practical application like that rather unpractical, for the time being.

Definitely ranks up there.

My favorite is still INTERCAL [1] since the result is actually useful, and it ranks high on the levity meter.

[1] https://en.wikipedia.org/wiki/INTERCAL

For the curious ones, this is a cool page that presents the basics of lambda calculus: https://learnxinyminutes.com/docs/lambda-calculus/

Absolutely impressive project !

It's Friday, I'm in love...

Just the kind of ridiculous brilliance I needed at the end of a hard week. Bravo!

Hot dog. I dreamed of writing something like this, and this guy actually goes and does it. Mad props.

If God's name was 18,506 pages long, this would be it.

How does it work? Is it translating the C source code of the 8cc C compiler to lambda calculus?

So like C -> ELVM IR -> lambda calculus?

https://github.com/shinh/elvm

If so, it seems like 8cc is doing most of the heavy lifting

That was my question to. 8cc is doing the heavy lifting of compiling C.

Is the 18506 pages long lambda term the normal form? I wonder how much that can be minimized by not beta reducing everything.

No; the term has no normal form. It contains a lot of applications of the fix-point combinator Y. As a simpler example, here's a lambda term for reversing input:

    λ 1 ((λ 1 1) (λ λ λ λ 2 (4 4) (λ 1 4 2))) (λ λ 1)

which similarly has no normal form.

Ah yes, that makes sense. But is that PDF really the most minimal form? I can imagine if we write a program using lets:

  let nil = \n c. n;
  let cons = \hd tl n c. c hd tl;
  let map = ...;
  body

And compile it as:

  (\nil cons map. body) (\n c. n) (\hd tl n c. c hd tl) (...)

That we would get a more minimal form. But I cannot verify in what form the lambda expression in the PDF is. It just seems unbelievably large to me.

Yes, let bindings would get translated like that, but there would be some straightforward optimizations done, such as size-reducing beta-reductions, which strip out unused let bindings, and inline the single-use ones, as well as the multi-use ones whose definition is smaller than the unary encoded de-Bruijn index.

Yes, I wonder if these optimizations are done in the PDF. I found the BLC encoding of the lambda expressions which is 407171813 bits, about 5 mb.

I expect so, as the author is familiar with my tools [1] for doing these optimizations.

[1] https://github.com/tromp/AIT

Indeed he uses it here [1], which also gets used in lambda-8cc.

[1] https://github.com/woodrush/lambda-calculus-devkit

primes.c takes 241GB to compile

Nice

Meanwhile a prime number sieve written directly in binary lambda calculus takes no more than 167 bits (under 21 bytes).

I admire the commitment to the schtick.

Each individual schtick in the construction is the cathedral.

I’m in awe. Spectacular.