On: Lambda Calculus in 383 Bytes (2022)

[johnisgood]

The 43-byte implementation might define only a subset of the functionality provided by the full VM, enough to "bootstrap" into the full implementation, most likely.

In fact, if the VM is Turing complete, it can theoretically emulate any computation, including its full implementation, even from a small subset of operations.

The point is that the 43-byte implementation does not need to encode the entire VM explicitly. For example, if the VM has built-in primitives for looping, branching, and memory management, the minimal implementation can leverage these to rebuild the remaining functionality.

[tromp → johnisgood]

My IOCCC entry [1] explains exactly what the 43-byte program is. It's a self-interpreter for BLC8, the byte based version of Binary Lambda Calculus.

The 521 byte interpreter on the other hand is written in x86 assembly, a language much less suitable for writing BLC8 interpreters than BLC8 itself.

Btw, with my latest lambda compiler, the BLC8 self interpreter is only 42 bytes:

    λ 1 ((λ 1 1) (λ (λ λ λ 1 (λ λ λ 2 (λ λ λ (λ 7 (10 (λ 5 (2 (λ λ 3 (λ 1 2 3)))
    (11 (λ 3 (λ 3 1 (2 1))))) 3) (4 (1 (λ 1 5) 3) (10 (λ 2 (λ 2 (1 6))) 6))) 8) 
    (λ 1 (λ 8 7 (λ 1 6 2)))) (λ 1 (4 3))) (1 1)) (λ λ 2 ((λ 1 1) (λ 1 1))))

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

[Dansvidania → tromp]

thanks, this is helping me understand the whole article a bit better.

[johnisgood → tromp]

Yeah, I just took a real look now. It uses a metacircular evaluator? I didn't look at the link provided just yet though! :D

[cess11 → johnisgood]

"For example, its metacircular evaluator is 232 bits. If we use the 8-bit version of the interpreter (the capital Blc one) which uses a true binary wire format, then we can get a sense of just how small the programs targeting this virtual machine can be."

From TFA. I think it's a very good article.