You can also be smart about memory with lexing for great winnage. Have a struct for your tokens that has an enum for your token type and either pointer or indices or a string_view (or a &str but lol lotsa luck with the borrow checker). You can then have a vector of your token structs for fast allocation and iteration and you have a slice for the token back into the original input, no substring copying.
Flattening ASTs and other compiler data structures (2023)
31–40 of 52 posts
Re: Flattening ASTs and other compiler data structures (2023)
#32One advantage to this is the ease with which it handles ephemeral annotations.
Suppose you want to attach additional information to some of the nodes of the AST. Different algorithms on the AST will attach different information; you don't necessarily need them all at the same time or know ahead of time what you'll need.
With nodes, you have to have some sort of node/value hash table, or hang a key/value map off each node. But with this flattened representation, each datum gets its own flat array as well, which can be independently allocated and deallocated.
One other thing I noticed about this flat representation is that it throws static typing into a cocked hat! All you have to refer to other nodes is indices. All different kinds of nodes are stored in the same array.
Re: Flattening ASTs and other compiler data structures (2023)
#33Twee (an equational theorem prover in Haskell used by quickspec) has an interesting take on this.
Terms are slices of arrays, but you get a normal interface including pattern matching via synonyms.
It can also be nice to use phantom types of your references (array offsets), so if you project them into flat view types you can do so type safely
Requires the language to have something equivalent to pattern synonyms to be as invisible as twee, though.
In twee a TermList is a slice of a bytearray (two ints for offset/length plus a pointer).
And a term is an int for the function symbol and an unpacked TermList for the arguments.
The pattern match synonyms load a flat representation from the array into a view type, and the allocation of the view type cancels out with the pattern matching so everything remains allocation free.
https://hackage.haskell.org/package/twee-lib-2.4.2/docs/Twee...
Re: Flattening ASTs and other compiler data structures (2023)
#34You can also be smart about memory with lexing for great winnage. Have a struct for your tokens that has an enum for your token type and either pointer or indices or a string_view (or a &str but lol lotsa luck with the borrow checker). You can then have a vector of your token structs for fast allocation and iteration and you have a slice for the token back into the original input, no substring copying.
Yes, the C FE I write (in C) does exactly this and othen utputs in one pass a flattened intermediate code. I did not see at as AST because it does semantic analysis during parsing, but it sitll has all the information.
Re: Flattening ASTs and other compiler data structures (2023)
#35"Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array." Zig compiler pipeline (AST, Zir, Air, Sema) does exactly this on all layers. Not only contiguous, but instead of array-of-structs it is struct-of-arrays, so walking the tree is even more cache friendly. For AST see: https://github.com/ziglang/zig/blob/master/lib/std/zig/Ast.z...
I work on a C dialect where everything is flattened. JSON and other trees in particular. Binary heaps are flat, merge sort and iterator heaps are absolutely great, can build LSM databases with that. Stacks, circular buffers, hash maps, etc, all flat. Templated output (PHP like) is done by a flat data structure. https://github.com/gritzko/librdx/blob/master/abc/B.md Apart from locality and lifetimes, these flat data s…
I worked in a language where all datastructures were "flattened", could be trivially serialized to disk, and read in again. Called print and read. The language was called lisp. All flat, just parens.
Some of my compilers export the AST as lisp trees. Much smaller and more readable than json, and it can be executed. Uniform like bricks
Re: Flattening ASTs and other compiler data structures (2023)
#36Cool! Carbon is doing exactly this. I had asked leads if there was a paper on this approach, but they didn't have anything for me. I'll send them this post!
Chandler discusses it in this video though! https://youtu.be/ZI198eFghJk
You get some traversals for free with this layout (preorder, reverse post order). Can search for subtrees with string searching algorithms or more complex things with regex.
Re: Flattening ASTs and other compiler data structures (2023)
#37I thought a reddit comment on this article had an interesting point: https://www.reddit.com/r/rust/comments/1d3b356/my_new_favori... [–]Timzhy0 3 points 7 months ago Btw I think one can go a step further than the author, there is no need to keep two explicit ExprRef baked in a binary node (lhs, rhs). You can exploit locality, basically the AST, seen it the LISP way, is just an arbitrarily nestable list, where element…
An arbitrarily nestable list is a tree, no?
Re: Flattening ASTs and other compiler data structures (2023)
#38Earlier quoted context omitted.
I work on a C dialect where everything is flattened. JSON and other trees in particular. Binary heaps are flat, merge sort and iterator heaps are absolutely great, can build LSM databases with that. Stacks, circular buffers, hash maps, etc, all flat. Templated output (PHP like) is done by a flat data structure. https://github.com/gritzko/librdx/blob/master/abc/B.md Apart from locality and lifetimes, these flat data s…
I worked in a language where all datastructures were "flattened", could be trivially serialized to disk, and read in again. Called print and read. The language was called lisp. All flat, just parens. Some of my compilers export the AST as lisp trees. Much smaller and more readable than json, and it can be executed. Uniform like bricks
> All flat, just parens.
So not flat then. Prefix is not postfix. Forth, and most concatenative languages, are much closer to actually bein, flat.
Lisp is trivial to flatten, but that's not the same thing.
Re: Flattening ASTs and other compiler data structures (2023)
#39> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array. This happens naturally if you bump-allocate them in a garbage-collected run-time, particularly under a copying collector. Free lists also tend to co-locate because they are produced during sweep phases of GC which run through heaps in order of address. Don't make me bring out the L word for the billionth tim…
And if you don’t need more than 32 GB of heap space, the JVM also gives you the ability to reduce reference sizes to 32 bits, with compressed references. (Due to alignment requirements, the lower 3 bits of a pointer are zero and hence do not need to be stored, which effectively gives you a 35-bit address space.) Of course, the presence of object headers counteracts this to a certain extent.
Re: Flattening ASTs and other compiler data structures (2023)
#40Twee (an equational theorem prover in Haskell used by quickspec) has an interesting take on this. Terms are slices of arrays, but you get a normal interface including pattern matching via synonyms. It can also be nice to use phantom types of your references (array offsets), so if you project them into flat view types you can do so type safely Requires the language to have something equivalent to pattern synonyms to b…
Forgot to mention: In the twee style, the int for the function id contains metadata (is it a unification variable or constant name? how many args does it take?). That way f1(f3(f5(), f7())) would be serialised as something like [1,3,5,7], without even references to other offsets