3 ms·

Hmm, what's a stack machine AST? I can't follow your description of the transform, what does "remove" mean here? I can remove all of the internal nodes of a tre

by derdi 2mo ago

Hmm, what's a stack machine AST? I can't follow your description of the transform, what does "remove" mean here? I can remove all of the internal nodes of a tree, which leaves me with a soup of leaf nodes, but how is that an AST for a stack machine?

noelwelsh 2mo 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 2mo ago
  Fair! 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 2mo ago
    It'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 2mo ago
      Got 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.
sirwhinesalot 2mo ago
Not the OP and I honestly have no idea what they mean, but the translation of a tree-walking interpreter for expressions to a stack-machine compiler is almost trivial. For example, if you have (in pseudo-code): class Add : Node { Node left; Node right; int interpret() { int l = left.interpret(); int r = right.interpret(); return l + r; } } You can turn it into: class Add : Node { Node left; Node right; void compile(bc: ByteCode) { left.compile(bc); right.compile(bc); bc.push(OP_ADD); } } The inputs to OP_ADD are implicit, I guess that is what "remove" means?

by derdi 2mo ago

noelwelsh 2mo 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 2mo ago
Fair! 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 2mo ago
  It'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 2mo ago
    Got 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.

sirwhinesalot 2mo ago

Not the OP and I honestly have no idea what they mean, but the translation of a tree-walking interpreter for expressions to a stack-machine compiler is almost trivial. For example, if you have (in pseudo-code): class Add : Node { Node left; Node right; int interpret() { int l = left.interpret(); int r = right.interpret(); return l + r; } } You can turn it into: class Add : Node { Node left; Node right; void compile(bc: ByteCode) { left.compile(bc); right.compile(bc); bc.push(OP_ADD); } } The inputs to OP_ADD are implicit, I guess that is what "remove" means?