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

11–20 of 35 posts

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

#11

Post by caslon »

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.

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.

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

#15

Post by daptaq »

c-linkage wrote: post #2

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

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.

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

#18

Post by unwind »

daptaq wrote: post #15
c-linkage wrote: post #2

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

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.

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

#19

Post by tromp »

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.

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

#20

Post by tromp »

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

Post reply on HN