15 ms·
I should have said instruction set or intermediate representation (IR). For a stack machine a program is an array of instructions. For a tree-walking interprete
by noelwelsh 1mo ago
I should have said instruction set or intermediate representation (IR). For a stack machine a program is an array of instructions. For a tree-walking interpreter a program is a tree of instructions. The duality transforms one instruction set into the other.
Hope that clears it up.
- derdi 1mo agoFair! Though I still don't know what you mean by "removing" nodes from the tree-walking interpreter's AST. Assume we have an AST like: (Add (LoadConst 1) (LoadVar x)) The corresponding stack machine code might be: [PushConst 1, PushVar x, Add] In what way was anything "removed" from the tree?
- noelwelsh 1mo agoIt's a transform on the instruction set. If you have the following instruction set for a tree walking interpreter (Scala syntax) enum Expr: case Add(left: Expr, right: Expr) case Lit(val: Double) the corresponding stack machine instruction set is enum Expr: case Add case Lit(val: Double) The transformation in this direction is purely syntactic: where you see that a case has a parameter of type Expr in the instruction set, you simply remove that parameter for the corresponding stack machine instruction. The transformation in the other direction is not purely syntactic as you have to know that, e.g., Add gets two parameters from the stack and add those parameters back in.
- derdi 1mo agoGot it, thank you! I had read your "remove any occurrence of the expression type in the tree-walking AST" as removing nodes from the AST, but in some sense it's about removing edges, as in, the references from one operation to others.