[dmagyari]

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

[gritzko]

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.

[rurban]

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

[vanderZwan]

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

[agumonkey]

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)

[gsf_emergency]

Do you have a link to such an example of Aaron's code? Thank you in advance!

[082349872349872]

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

[gsf_emergency]

Thanks. Was hoping for low-level code that might even blow a deue(I?)ng(m?)ker's mind on THE semantics-syntax duality..

This was closest: https://www.dyalog.com/blog/2018/01/stackless-traversal/

Your links should still be useful for orienteering!

[agumonkey]

Can't remember where exactly but he did demo his code in talks/conferences with links.

[gsf_emergency]

I've given up on finding relevant low-level CUDA(? tacit? asm??!!) code from Hsu*, but I did push the following to my to-watch stack

https://youtu.be/z8MVKianh54

Does APL need a type system

Guess it's time to reverse whatever else I can find

https://www.dyalog.com/uploads/conference/dyalog16/prerequis...

*Bad faith, or just a run o' the mill, aka compleatly forgiveable profiteering?

[gsf_emergency]

Ahh apologies

https://news.ycombinator.com/item?id=13797797

https://news.ycombinator.com/item?id=13576176

[082349872349872]

He must be referring to https://dl.acm.org/doi/pdf/10.1145/2935323.2935331 ?

Just looking at refs for the moment: Henglein and Hinze's discriminators are interesting, whenever you come back up for air. (are they also amenable to sorting codata?)

The oft-cited R Bernecky is, IIRC, also known as "Boolean Bob" for his SWAR-style algos. EDIT: nope, confused him with R Smith: https://aplwiki.com/wiki/Bob_Smith

(I once asked Boolean Bob if any of his tricks went back to the card processing days —I could even believe the keyed tree* might?— but he was too young to know, and the people he'd have liked to ask are no longer available.)

EDIT: Aardappel also has some interesting languages: https://strlen.com/#programming-languages

* for manipulating Bills of Materials despite the linearity of card decks?

EDIT2: compare "§3.2.1 Constructing Node Coordinates" (p34) with [T in "Table 1.19 Full list matrices of the tree of Fig. 1.16" in A Programming Language (p50): https://archive.org/details/aprogramminglanguage1962/page/n6...

        Fc
  1 0 0 0 0
  1 1 0 0 0
  1 1 1 0 0
  1 1 1 1 0
  1 1 1 1 1
  1 1 1 1 2
  1 1 1 1 3
  1 1 2 0 0
  1 1 2 2 0
        Ec
  1 0 0
  1 1 0
  1 1 1
  1 1 2
  1 1 3
  1 2 0
  1 3 0
  1 3 4
  1 3 5
  1 3 6

[all three appear to be 1-origin, probably due to the phenomenon mentioned in the footnote on p49 of APL]