Aaron Hsu shows how to manipulate and transform tree data in APL using arrays and inverted tables instead of pointers. He claims much smaller code, better performance and easier parallelisation.
Why Hacker News points people here: HN recommends it as a striking example of high-performance tree handling with array programming.
“He has one talk (available on YouTube) about his approach to using arrays to working with tree structures in a high-performance way in APL”HN comment, 2021
“Or how to model Trees without using pointers by using "Inverted Tables.”
Models trees without pointers using inverted tables in APL.
Full comment
Qualification: I was introduced to FP a number of years ago and have finally reached a point where I feel that I have a deep understanding of FP in general. In my mind, Haskell is the "best" language out there ("best" in that it provides the best overall gain when all tradeoffs are considered). I'm no longer confident that Haskell is the "best" language anymore. I was recently introduced to a language that might be even better than Haskell: Dyalog APL. ( link ). Try it out yourself ( link ) To explain why, I recommend watching Aaron Hsu's videos on Dyalog APL: - Does APL need a Type System? ( link ) - This is actually a very interesting question that is more nuanced than upon first glance. - Design Patterns and Anti-Patterns in APL ( link ) - The main takeaway from this video for me was the principle of "Idioms over libraries." - Higher Performance Tree-Wrangling, the APL way ( this video ) - Or how to model Trees without using pointers by using "Inverted Tables." (An inverted table is a table where the columns are the rows and the rows are the columns)
RecommendssnakyJan 2020
“great, as everything Aaron does”
Great presentation on manipulating and transforming trees in APL.
Full comment
I had this feeling exactly listening (great, as everything Aaron does) presentation about manipulation and transformation of trees in APL, this video
RecommendsjodrellblankJun 2021
“He has one talk (available on YouTube) about his approach to using arrays to working with tree structures in a high-performance way in APL”
Array approach to high-performance tree structures in APL.
Full comment
> " his saves on allocations, saves on total memory usage " Co-Dfns is Aaron Hsu's project, and he has a talk[1] on a compiler implemented in a nano-pass style, once in Racket, once in Chez Scheme[2] and once in Dyalog APL, each using CPU and GPU. For compiling an AST with ~16 million nodes, he gives benchmark figures that Dyalog APL takes 64MB RAM to hold it, Racket takes 1051MB and Chez Scheme takes 1485MB. His provocative statement for the talk is "pointers are the refined sugar of programming". The APL version is 1/50th of the lines of code[4], runs typically 9x faster on the CPU, 50x-200x faster on the GPU, despite being interpreted by Dyalog vs compiled Scheme. There are benchmarks where the APL version loses in runtime, under 1k lines of code (which he calls "tiny tiny") so lots of startup overhead and not enough big arrays to gain ground on. He has one talk (available on YouTube) about his approach to using arrays to working with tree structures in a high-performance way in APL[3]. [1] link [2] he used to be on the Scheme R6RS steering committee, so he's not new/inexperienced with it link [3] this video [4] 17 lines of code which took a PhD researcher (him) 5-10 years to write, mind you.
