High-performance Tree Wrangling, the APL Way // Aaron Hsu // Dyalog '18

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 ( [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)

I had this feeling exactly listening (great, as everything Aaron does) presentation about manipulation and transformation of trees in APL, [VIDEO]

> " 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] [VIDEO] [4] 17 lines of code which took a PhD researcher (him) 5-10 years to write, mind you.