Rediscovering techniques that were somewhat well-known in the 70s and 80s.
Flattening ASTs and other compiler data structures (2023)
21–30 of 52 posts
Re: Flattening ASTs and other compiler data structures (2023)
#22Rediscovering techniques that were somewhat well-known in the 70s and 80s. See also: https://en.wikipedia.org/wiki/Binary_heap
heh - I built compilers this back in the 70s because the machine I was working on didn't really do pointers as a 1st class data structure (B6700 algol), it's not really surprising finding someone doing something similar in another language that makes pointers difficult to deal with
Re: Flattening ASTs and other compiler data structures (2023)
#23This is a fantastic idea. AST works well in an array based allocation block since it has no need for freeing individual nodes. It’s an add-only allocation.
What about transforming the AST after it is built, or deriving a new tree which partly aliases the original in persistent structure fashion?
Re: Flattening ASTs and other compiler data structures (2023)
#24[deleted]
Re: Flattening ASTs and other compiler data structures (2023)
#25I guess Rust's contribution to high performance programming is that its borrow checker is so loathsome that it pushes people into using ideas like ECS or arenas just to not have to bother with it.
Re: Flattening ASTs and other compiler data structures (2023)
#26Rediscovering techniques that were somewhat well-known in the 70s and 80s. See also: https://en.wikipedia.org/wiki/Binary_heap
Yup, and chances are if you're using a good C++ stl implementation, most containers already use packed storage internally. It doesn't even have a heap data structure, it uses an std::vector, with a set of helper functions.
Re: Flattening ASTs and other compiler data structures (2023)
#27About 10 years ago working with AST trees I (re)invented a flat structure representing trees in a flat array. It reminds me of what is described here but not exactly. In my case I needed only two indices per node: total sub-region length of all the children and sub-children and parent index (so no need to have indices of all children). Total sub-length basically can be interpreted as the index of the next sibling. With such a structure it's easy/cheap to execute FindFirstChild/FindNextSibling.
Later the theory behind such structures was revealed as "Nested set model" [1]. The article seems to not mention the internal representation, but I think that the implementation should use something like my solution, so fixed number of references per node
Re: Flattening ASTs and other compiler data structures (2023)
#28Earlier quoted context omitted.
Makes me wonder if people in APL/J/K community have not been influenced or influencing this kind of technique. IIRC Aaron Hsu does tree processing through arrays (but i'm not skilled enough to analyze his code)
Do you have a link to such an example of Aaron's code? Thank you in advance!
https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-...
Iverson's 1962 book also mentions tree representations, see pp45-62: https://archive.org/details/aprogramminglanguage1962/page/n6...
Re: Flattening ASTs and other compiler data structures (2023)
#29Earlier quoted context omitted.
Makes me wonder if people in APL/J/K community have not been influenced or influencing this kind of technique. IIRC Aaron Hsu does tree processing through arrays (but i'm not skilled enough to analyze his code)
Do you have a link to such an example of Aaron's code? Thank you in advance!
Can't remember where exactly but he did demo his code in talks/conferences with links.
Re: Flattening ASTs and other compiler data structures (2023)
#30Did the author just reinvent Forth?