6 ms·

Show HN: Lambda-8cc – An x86 C compiler written in untyped lambda calculus

249 points by woodrush 4y ago

c-linkage 4y ago
This is the most spectacular waste of time I have ever seen. I absolutely love it!
- deleted 4y ago
  [deleted]
- deleted 4y ago
  [deleted]
- kazinator 4y ago
  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.
  - caslon 4y ago
    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.
    - planede 4y ago
      Volumes XVIII, XIX and XX: closing parens.
  - valleyer 4y ago
    <https://github.com/woodrush/lambda-8cc/blob/main/bin/lambda-8cc-page18506.png https://github.com/woodrush/lambda-8cc/blob/main/bin/lambda-...>
- daptaq 4y ago
  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.
  - unwind 4y ago
    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.
- cek 4y ago
  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 https://en.wikipedia.org/wiki/INTERCAL
apricot 4y ago
Hot dog. I dreamed of writing something like this, and this guy actually goes and does it. Mad props.
magicalhippo 4y ago
It's Friday, I'm in love... Just the kind of ridiculous brilliance I needed at the end of a hard week. Bravo!
graderjs 4y ago
primes.c takes 241GB to compile Nice
- tromp 4y ago
  Meanwhile a prime number sieve written directly in binary lambda calculus takes no more than 167 bits (under 21 bytes).
deleted 4y ago
[deleted]
chubot 4y ago
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 https://github.com/shinh/elvm If so, it seems like 8cc is doing most of the heavy lifting
- omegalulw 4y ago
  That was my question to. 8cc is doing the heavy lifting of compiling C.
newobj 4y ago
I admire the commitment to the schtick.
- AnthonBerg 4y ago
  Each individual schtick in the construction is the cathedral.
atennapel 4y ago
Is the 18506 pages long lambda term the normal form? I wonder how much that can be minimized by not beta reducing everything.
- tromp 4y ago
  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.
  - atennapel 4y ago
    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.
    - tromp 4y ago
      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.
      - atennapel 4y ago
        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.
        tromp 4y ago
        I expect so, as the author is familiar with my tools [1] for doing these optimizations. [1] https://github.com/tromp/AIT https://github.com/tromp/AIT
abricq 4y ago
For the curious ones, this is a cool page that presents the basics of lambda calculus: https://learnxinyminutes.com/docs/lambda-calculus/ https://learnxinyminutes.com/docs/lambda-calculus/ Absolutely impressive project !
zoom6628 4y ago
I’m in awe. Spectacular.
jart 4y ago
If God's name was 18,506 pages long, this would be it.
- deleted 4y ago
  [deleted]
tromp 4y ago
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 https://www.ioccc.org/2012/tromp/hint.html
- woodrush 4y ago
  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 https://github.com/woodrush/lambdalisp
pharmakom 4y ago
Now we need an untyped lambda calculus compiler for C!
- deleted 4y ago
  [deleted]

249 points by woodrush 4y ago

c-linkage 4y ago

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

deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
kazinator 4y ago
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.
- caslon 4y ago
  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.
  - planede 4y ago
    Volumes XVIII, XIX and XX: closing parens.
- valleyer 4y ago
  <https://github.com/woodrush/lambda-8cc/blob/main/bin/lambda-8cc-page18506.png https://github.com/woodrush/lambda-8cc/blob/main/bin/lambda-...>
daptaq 4y ago
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.
- unwind 4y ago
  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.
cek 4y ago
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 https://en.wikipedia.org/wiki/INTERCAL

apricot 4y ago

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

magicalhippo 4y ago

It's Friday, I'm in love... Just the kind of ridiculous brilliance I needed at the end of a hard week. Bravo!

graderjs 4y ago

primes.c takes 241GB to compile Nice

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

deleted 4y ago

[deleted]

chubot 4y ago

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 https://github.com/shinh/elvm If so, it seems like 8cc is doing most of the heavy lifting

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

newobj 4y ago

I admire the commitment to the schtick.

AnthonBerg 4y ago
Each individual schtick in the construction is the cathedral.

atennapel 4y ago

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

tromp 4y ago
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.
- atennapel 4y ago
  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.
  - tromp 4y ago
    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.
    - atennapel 4y ago
      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.
      - tromp 4y ago
        I expect so, as the author is familiar with my tools [1] for doing these optimizations. [1] https://github.com/tromp/AIT https://github.com/tromp/AIT

abricq 4y ago

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

zoom6628 4y ago

I’m in awe. Spectacular.

jart 4y ago

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

deleted 4y ago
[deleted]

tromp 4y ago

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 https://www.ioccc.org/2012/tromp/hint.html

woodrush 4y ago
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 https://github.com/woodrush/lambdalisp

pharmakom 4y ago

Now we need an untyped lambda calculus compiler for C!

deleted 4y ago
[deleted]