Made 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 nonetheless. I don't think there is a simple equivalent for a register machine as, unless you have an infinite number of registers, you need to do register allocation.
(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.)
> (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.)
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 that some Scala specific thing for recursion?
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.
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.
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.
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;
}
}
It's not that bad... But it is bad. It looks cool, and I managed to read the first few paragraphs. But when the code scrolled into view, it stopped looking cool and became an eye-destroying disaster.
YMMV, but OP, if you read this, please consider disabling the text-shadow for code snippets... or disabling syntax highlighting in code snippets. These two things are not a good thing together.
I think they could get a close-enough effect by removing the horizontal lines on the text glyphs themselves. This would still keep the colorscheme and slight glow, but drastically improve readability.
It must depend on what you’re using to read it. It’s also readable for me on an OLED iPad, and gives me ideas about what I actually want when I wish I could turn the contrast down while reading it with low ambient light.
Bringing the brightness levels of the background and text closer together doesn’t ever seem to work, but being able to add a slight blurry dropshadow behind behind each character might be a way to reduce the artifacts OLEDs seem to create when my eyes are tired.
Then, with all due respect, you should not be anywhere near the design or evaluation of accessible systems.
There's people reading this blog with all types of devices, screens, lighting and range of visual acuity. Even if you're blessed with perfect vision and excellent displays, it should be obvious that readability has been lowered for no obvious reason.
The point of a blog is for people to read it, so it fails at its foremost job.
I wasn't saying that I thought it should be adopted as a standard for others to follow - just that (somewhat weirdly) I personally find the code segments on that page quite easy to read.
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 nonetheless. I don't think there is a simple equivalent for a register machine as, unless you have an infinite number of registers, you need to do register allocation.
(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/
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 that some Scala specific thing for recursion?
[0]: https://noelwelsh.com/posts/understanding-vm-dispatch/
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.
Hope that clears it up.
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.
There is a time and place for text and retro-CRT effects, this isn't one.
YMMV, but OP, if you read this, please consider disabling the text-shadow for code snippets... or disabling syntax highlighting in code snippets. These two things are not a good thing together.
Bringing the brightness levels of the background and text closer together doesn’t ever seem to work, but being able to add a slight blurry dropshadow behind behind each character might be a way to reduce the artifacts OLEDs seem to create when my eyes are tired.
There's people reading this blog with all types of devices, screens, lighting and range of visual acuity. Even if you're blessed with perfect vision and excellent displays, it should be obvious that readability has been lowered for no obvious reason.
The point of a blog is for people to read it, so it fails at its foremost job.