Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

21–30 of 35 posts

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

#21

Post by atennapel »

tromp wrote: post #19
atennapel wrote: post #13

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.

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

#22

Post by tromp »

atennapel wrote: post #21
tromp wrote: post #19

Earlier quoted context omitted.

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.

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

#23

Post by atennapel »

tromp wrote: post #22
atennapel wrote: post #21

Earlier quoted context omitted.

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.

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

#24

Post by valleyer »

kazinator wrote: post #8
c-linkage wrote: post #2

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.

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

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

#25

Post by tromp »

atennapel wrote: post #23
tromp wrote: post #22

Earlier quoted context omitted.

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

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

#27

Post by planede »

caslon wrote: post #11
kazinator wrote: post #8

Earlier quoted context omitted.

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.

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

#28

Post by woodrush »

tromp wrote: post #20

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... B…

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

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

#29

Post by omegalulw »

chubot wrote: post #10

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.
Post reply on HN