Why the fuck make a tech web page unreadable with CRT effects? Thank god, there is reader mode in Firefox.
I actually find it quite readable - YMMV.
[deleted]
Tail-Call Interpreters in Rust – Jimmy Ostler
21–30 of 35 posts
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#22Made my day that it references an article I wrote! :-D Another thing that is kinda neat: there is a duality (a bidirectional transform) between the AST for a tree walking interpreter and the AST for a stack machine. To create the stack machine AST, all you do is remove any occurrence of the expression type in the tree-walking AST; these values are now found on the stack. Obvious when you think about it, but useful no…
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?
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#23Made my day that it references an article I wrote! :-D Another thing that is kinda neat: there is a duality (a bidirectional transform) between the AST for a tree walking interpreter and the AST for a stack machine. To create the stack machine AST, all you do is remove any occurrence of the expression type in the tree-walking AST; these values are now found on the stack. Obvious when you think about it, but useful no…
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?
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.
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#24Earlier quoted context omitted.
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?
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.
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))
[PushConst 1, PushVar x, Add]
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#25Made my day that it references an article I wrote! :-D Another thing that is kinda neat: there is a duality (a bidirectional transform) between the AST for a tree walking interpreter and the AST for a stack machine. To create the stack machine AST, all you do is remove any occurrence of the expression type in the tree-walking AST; these values are now found on the stack. Obvious when you think about it, but useful no…
> (If the author reads this, my name changed from Noel to Neal at some point. I don't really mind though; my name is a bit unusual and I've been called all sorts of things.)
I think it'd be good to update the about page with that info: https://noelwelsh.com/landing/about/
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#26Made my day that it references an article I wrote! :-D Another thing that is kinda neat: there is a duality (a bidirectional transform) between the AST for a tree walking interpreter and the AST for a stack machine. To create the stack machine AST, all you do is remove any occurrence of the expression type in the tree-walking AST; these values are now found on the stack. Obvious when you think about it, but useful no…
Just read your blog post[0], thanks for it! If I may leave some feedback here... It'd be cool if you could add some syntax highlighting, because being at it is, it's hard to distinguish comments from code paths. The code snippets are just Scala anyway, aren't they? Why, in the switch dispatch - and the subroutine threading -variants, is the recursive call in the dispatch function done with a call to loop(...) ? Is th…
Thanks for pointing those out. I've fixed both issues.
Syntax highlighting was a discrepancy between my local env and the Netlify env that deploys the site.
`loop` is what I usually call tail-recursive loops in my personal style. I think I changed that to `dispatch` for the blog post and didn't push the change all the way through.
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#27Made my day that it references an article I wrote! :-D Another thing that is kinda neat: there is a duality (a bidirectional transform) between the AST for a tree walking interpreter and the AST for a stack machine. To create the stack machine AST, all you do is remove any occurrence of the expression type in the tree-walking AST; these values are now found on the stack. Obvious when you think about it, but useful no…
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?
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;
}
}
class Add : Node {
Node left;
Node right;
void compile(bc: ByteCode) {
left.compile(bc);
right.compile(bc);
bc.push(OP_ADD);
}
}
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#28Earlier quoted context omitted.
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.
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?
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)
enum Expr:
case Add
case Lit(val: Double)
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.
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#29Made my day that it references an article I wrote! :-D Another thing that is kinda neat: there is a duality (a bidirectional transform) between the AST for a tree walking interpreter and the AST for a stack machine. To create the stack machine AST, all you do is remove any occurrence of the expression type in the tree-walking AST; these values are now found on the stack. Obvious when you think about it, but useful no…
> (If the author reads this, my name changed from Noel to Neal at some point. I don't really mind though; my name is a bit unusual and I've been called all sorts of things.) I think it'd be good to update the about page with that info: https://noelwelsh.com/landing/about/
Sorry, I wasn't clear. In OP's blog post they refer to me as Neal at one point (just after the heading "Indirect Dispatch"). My name is still Noel :-)
Re: Tail-Call Interpreters in Rust – Jimmy Ostler
#30Earlier quoted context omitted.
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?
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…
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.