Mcode: the Format of Compiled Program
I follow de Bruijn’s suggestion of coding an applied variable occurrence as merely the static depth of the binding—an integer.
The applied occurrence of r in (λrr) is at depth 0.
The depth of t in (λt(λi(λjt))) is 2.
The expression is compiled thus:
- <ident>
- char less than 253.
De Bruijn’s binding depth.
- (<Expression><Expression>)
- At increasing addresses:
- char = 254
- short = offset in bytes to 2nd Expression
- compiled first expression
- pad (if offset is too big)
- compiled second expression
- (λ<ident><Expression>)
-
- char = 255 (id forgotten—depth is manifest.)
- compiled expression
- <digs>
- char = 253
-
7 bits per byte—high first. High bit on last byte.
These are byte aligned.
Obviously there are size limitations.
I want to see what performance is with fixed limits.
We can contemplate different limits later.
Perhaps dynamic limits might be useful—but simple first!