Hacker News Reader

Comment by derdi | Hacker News Reader

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?

View on HN

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.

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.

Reply on news.ycombinator.com