Flattening ASTs (and Other Compiler Data Structures)

Re:Flattening ASTs (and Other Compiler Data Structures) by gritzko on Saturday January 11, 2025 @02:32AM (#42664068)

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 structures improve composability. When every data structure is a flat buffer, you can mmap them or zip them or send them by the network, all by the same routine. They are uniform like bricks, in a sense.

[ Parent | on HN ]

Re:Flattening ASTs (and Other Compiler Data Structures) by rurban on Saturday January 11, 2025 @10:52AM (#42666649)

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

[ Parent | on HN ]

Re:Flattening ASTs (and Other Compiler Data Structures) by vanderZwan on Saturday January 11, 2025 @01:36PM (#42667948)

> 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.

[ Parent | on HN ]