[Munksgaard]

Interesting talk. He mentions Futhark a few times, but fails to point out that his ideal way of programming is almost 1:1 how it would be done in Futhark.

His example is:

  sequence
    .map(|x: T0| ...: T1)
    .scan(|a: T1, b: T1| ...: T1)
    .filter(|x: T1| ...: bool)
    .flat_map(|x: T1| ...: sequence<T2>)
    .collect()

It would be written in Futhark something like this:

  sequence
    |> map (\x -> ...)
    |> scan (\x y -> ...)
    |> filter (\x -> ...)
    |> map (\x -> ...) 
    |> flatten

[Munksgaard]

Also, while not exactly the algorithm Raph is looking for, here is a bracket matching function (from Pareas, which he also mentions in the talk) in Futhark: https://github.com/Snektron/pareas/blob/master/src/compiler/...

I haven't studied it in depth, but it's pretty readable.

[pythomancer]

(author here) check_brackets_bt is actually exactly the algorithm that Raph mentions

[raphlinus]

Right. This is the binary tree version of the algorithm, and is nice and concise, very readable. What would take it to the next level for me is the version in the stack monoid paper, which chunks things up into workgroups. I haven't done benchmarks against the Pareas version (unfortunately it's not that easy), but I would expect the workgroup optimized version to be quite a bit faster.

[Munksgaard]

To be clear, you can express workgroup parallelism in Futhark, or rather, if the compiler sees that you've programmed your problem in such a way that it can take advantage of workgroup parallelism, it will.

But you're right, it would be interesting to see how the different approaches stack up to each other. The Pareas project linked above also includes an implementation using radix sort.

[convolvatron]

I've been playing with one using scans. too bad that's not really on the map for architectural reasons, it opens up a lot of uses.

[kragen]

Yeah, monoid prefix sum is a surprisingly powerful tool for parallel and incremental algorithm design!

[Munksgaard]

Thanks for clarifying! It would indeed be interesting to see a comparison between similar implementations in other languages, both in terms of readability and performance. I feel like the readability can hardly get much better than what you wrote, but I don't know!

[snthpy]

Very cool. I have seen Futhark mentioned before but I don't know anything about it.

The example you showed is very much how I think about PRQL pipelines. Syntax is slightly different but semantics are very similar.

At first I thought that PRQL doesn't have scan but actually loop fulfills the same function. I'm going to look more into comparing those.