Stack-Folding

[emdash]

This documents a strategy for performing type-checking, const-folding, thunk-folding, and potentially other optimizations in a single pass.

The idea is to leverage the IR documented in #36 simplify the implementation back-end.

After parsing and module imports, an AST is immediately lowered to IR in a naive depth-first traversal pass. No pruning is done on the parse tree. The resulting code is then processed by an optimizer which is essentially a modified stack VM. It partially evaluates the IR in a single pass, emitting optimized IR. If this pass succeeds without error, then the resulting output IR is assumed to be type-correct.

This approach can be combined with #37 to achieve optimized compilation of partial expressions.

Simple Example

Consider this toy stack language, with the following types:

• Int
• Str

And the following instructions:

• plus
• times
• over
• in (reads an int)

Then

1 1 + => 2 1 in + => 1 in + 2 in times 1 plus => 2 in times 1 plus 2 1 times 1 plus => 3 2 1 times in plus 4 3 * over => 2 in plus 12 over 'a' 'b' plus => 'ab' 'a' 1 plus => type error 'a' in plus => type error, since in has type Int in this example.

• When execution encounters a constant, it is placed onto a stack.
• When execution encounters an in instruction, then in is placed on the stack.
• When execution encounters any other instruction, the result depends on stack configuration.
  • If all required operands are constant, then
  • the operands are consumed,
  • the operation is performed,
  • if any operand types mismatch, the compilation fails,
  • otherwise, the result is placed on the stack.
  • If any token appearing in the operand position on the stack is an instruction, including in, then:
  • the operands are type-checked, as above.
  • if this succeeds, then the operands are placed onto the stack unmodified.
  • the instruction is tagged with the type of its result, and placed on the stack.

When execution reaches the end of the program without a type error, I believe it can be shown that the stack contents contain the optimal instruction sequence.

Application to uDLang

I believe this approach can be extended to uDLang, though it is more complex than the toy stack language described above. In particular, the above example does not cover calls or branches, or the fact that as proposed in #36, a program is not a continuous instruction stream, but rather a list of blocks.

Nevertheless I believe the approach is fundamentally sound, and it's just a question of working out these details.

[emdash]

Related idea: "futamura projection".

I'm not sure if this is any better / easier to understand / etc than a tree-based const-folding pass.