Irregular data structures

[AriMKatz]

Hi,

how does dex plan to support graphs and trees and such? Can they be expressed as tables/index sets, and if so, would that be efficient?

[AriMKatz]

Oops, I should have searched:#526 (comment)

Still, I'm generally curious about how far index sets can get us with non array like things

[dougalm]

This is still an area of open exploration! @duvenaud has played with array-backed graphs in #526, as you noticed. There's also a longstanding dream of adding recursion and recursive algebraic data types like you get in conventional functional languages (#331) which are perfect for representing trees.

In general, there's a lot of fun work to do in figuring out how to use Dex's primitives for sophisticated data structures in a way that's safe and parallel. Early functional programmers had to invent new data structure that worked in a functional setting, (see e.g. Chris Okasaki's book). We might find ourselves doing something analogous.

[AriMKatz]

Makes sense, thanks!

[apaszke]

Here's a relevant issue too! We're planning to do some work on it this year (hopefully with @tscholak), but the timelines are still a bit unclear.

[AriMKatz]

Interesting. Are you thinking it might be possible to for the compiler to automatically lay out something like a tree built with Recursive ADTs as a dense memory region, then to parallelize traversals?

Or is the approach to keep the pointer-ey structure but make it easy to jump around in parallel, so that would remain on the host but be fast and safe as possible?

[tscholak]

Yes 😊

For the former option, I have some early exploration in Haskell written up on my blog, https://tscholak.github.io/posts/Unrecurse.html and https://tscholak.github.io/posts/Flattening.html. This is just a warmup, real work on this has still to kick off. @apaszke, let's reconnect 😊

[duvenaud]

If you want another example, @chenzizhao wrote a few tree-based algorithms + datastructures in Dex. For example, Monte Carlo Tree Search:

https://github.com/chenzizhao/dex-lang/blob/mcts/examples/mcts.dx

It's still a bit awkward though, since we have to manually convert all recursion to while loops for the time being.

[AriMKatz]

Hi, this is a very interesting example. I thought it was getting away without having to do any manual index arithmetic...but someone asked me about the first line (def (+!) {a} (n:a) (m:Int) : a = ((ordinal n) + m)@_) . How does the indexing work ?

[duvenaud]

Good point. You're right that part of the point of Dex is to avoid this kind of arithmetic, which we used in that example to flatten the tree unto an array. That code was written before custom index sets were available. I suspect that now we'd at least be able to hide the use of +! into the ordinal and fromOrdinal functions of an instance of Ix for some a Tree index set.