Comment by johnisgood

Comment by johnisgood 3 days ago

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 3 days ago

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/

Reply View 3 replies

Dansvidania 3 days ago

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

Reply View | 0 replies
johnisgood 3 days ago

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

Reply View | 1 reply
- cess11 3 days ago
  
  "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.
  
  Reply View | 0 replies