This is a very interesting talk on treeless parsing and IR. The first half about treeless parsing doesn’t apply to Julia what without user facing AST. However, the second half is about using a graph of nodes to represent the structure of the program instead of linear instructions. Optimizations are then applied as a series of graph substitutions and machine code is generated by walking the final graph.
I thought Julia internals nerds might enjoy
PS This comes from a new conference. The other talks on their channel have been very fun!
Perhaps relevant, but V8 (the JavaScript engine developed by Google) famously got rid of their Sea Of Nodes architecture:
My gut feeling is that in order to benefit from a Sea Of Nodes implementation, a language has to be designed with that in mind. Julia has quite a few things that make this challenging, like @goto (even in its limited form) due to being unstructured control flow.
Nice to see a sneaking suspicion of my validated. As he goes through the talk, he starts to add a keep alive object, then control flow nodes, then memory nodes that keep orderedness… but it started to look like more and more of the graph was just a linked list.
The speaker is writing his own language, so I’m sure his language design is in dialog with his compiler design which sands off some of those rough edges.
Well, there’s that, but it’s also important that his entire goal was a single pass compiler without using a tree-like datastructure. So that’s probably something that influenced his design quite a lot! Since Julia, kind of by design, is not single pass, it’s even harder to justify moving to a Sea of Nodes IR.
The general idea here vaguely reminded me of Metatheory.jl and e-graph rewriting. Trying to find how they relate, I came across this Q&A on StackExchange which seems to be a pretty nice (to my untrained eyes) high level overview.
