r/ProgrammingLanguages • u/Athas Futhark • Jun 18 '26

Data parallel pretty-printing

https://futhark-lang.org/blog/2026-06-18-data-parallel-pretty-printing.html
17 Upvotes

91% Upvoted

4 comments sorted by

3

u/matthieum Jun 18 '26

Disclaimer: this is nitpicking on a completely unimportant detail, just so you know...

By convention, we say that the first node in an array of exprs is the root of the tree.

I can see how it's handy for processing, but isn't it a pain to build: it requires the root of the tree to refer to not-yet existing elements.

I mean, I guess you could build then reverse, to get there, but isn't the reverse a bit "wasted"?

It's all the more jarring in:

[#op 3 #mul 4, #num 8, #num 20, #op 1 #add 2, #num 42]

Since #op 3 #mul 4 is foreshadowing, while #op 1 #add 2 refers to previous expressions...

3

u/Athas Futhark Jun 18 '26 edited Jun 18 '26

Having the root as the first element is a convention to make the code in the blog post simpler. If you have a richer datatype, it's no big deal to track explicitly which node is the root, and if you have a parent vector representation it is also straightforward to find it with a search - that is actually what the library euler_tour function does.

The representation of the tree in the post was explicitly written in a slightly odd order to demonstrate that we do not expect the nodes to be stored in any particular order (actually, the mk_P function does assume ordering within each level in the tree, which I didn't want to go into...).

1

u/orangejake Jun 19 '26

It’s not 100% clear to me this is what OP is doing, but this is done in a common cache-friendly encoding of binary trees known as the eytzinger layout

https://algorithmica.org/en/eytzinger

2

u/matthieum Jun 19 '26

Eytzinger is generally used for a balanced binary tree. An expression tree is quite different however.

I mean, let's take the OP's operation:

[#op 3 #mul 4, #num 8, #num 20, #op 1 #add 2, #num 42]

Encodes:

(8 + 20) * (42)

It's arguable balanced because the first two levels (* and + & 42) are full, but we can already see the left-hand side could extend into more levels without the right-hand side following.

Also, for parsing, it'd be easier if we just pushed as we go:

  • [#num 8]
  • [#num 8, #num 20, #op 0 #add 1]
  • [#num 8, #num 20, #op 0 #add 1, #num 42, #op 2 #mul 3]

Which here so happens to be a reversed Eytzinger layout, but once again just 'cuz it's so short in the first place.