Re:Show HN: Lambda-8cc – An x86 C compiler written in untype...
by atennapel on Friday October 07, 2022 @01:38AM
(#33117807)
Is the 18506 pages long lambda term the normal form? I wonder how much that can be minimized by not beta reducing everything.
[ Parent
| on HN ]
Re:Show HN: Lambda-8cc – An x86 C compiler written in untype...
by tromp on Friday October 07, 2022 @04:26AM
(#33118682)
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 untype...
by atennapel on Friday October 07, 2022 @04:54AM
(#33118886)
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 untype...
by tromp on Friday October 07, 2022 @05:20AM
(#33119070)
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 untype...
by atennapel on Friday October 07, 2022 @05:45AM
(#33119220)
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 untype...
by tromp on Friday October 07, 2022 @06:41AM
(#33119524)
I expect so, as the author is familiar with my tools [1] for doing these optimizations.