Array short-circuiting | Hacker News Reader

Array short-circuiting

futhark-lang.org

66 pointsMunksgaard12 comments

There was an interesting paper I read related to this topic, aaaand... I can't find it right now. It could have been this one: https://www.microsoft.com/en-us/research/publication/a-short...

Is this something that could benefit other functional programming languages like Haskell, as long as you're willing to add a SMT solver into your compiler? Or is this technique only relevant when you have complicated array slicing operations? Could a language like e.g. Julia benefit?

This is interesting because it seems to operate simultaneously on a contiguous block of memory, as opposed to sequentially on some tree structure. The general class of transforms seems to be called 'deforestation'.

Spotting when something can be mutated in place instead of creating a new instance is fairly common. There's a paper that does it at runtime using reference counting and various compilers for functional languages will try to do it ahead of time.

That would roughly lead to updating each element in the array in sequence without making a new array. This is an extension to that when the updates can occur simultaneously which is a more complicated lifetime invariant to recognise.

As an aside, compilers probably should have constraint solvers embedded. Lots of compilation is expressible as a constraint problem.

> As an aside, compilers probably should have constraint solvers embedded. Lots of compilation is expressible as a constraint problem.

If we had constraint solvers in our compilers, would refinement types also be a lot easier to implement?

Haskell puts a lot more emphasis on linked/tree structures than arrays. Built-in support for arrays in Haskell is pretty crappy.

Are Haskell lists actually implemented as linked lists? I would have thought they were compiled as "array lists" like Python (arrays of pointers, but with extra space pre-allocated to make extending cheap)

> Are Haskell lists actually implemented as linked lists?

Yes, the type "[]" from the Prelude is a linked list.

> I would have thought they were compiled as "array lists" like Python (arrays of pointers, but with extra space pre-allocated to make extending cheap)

No, and that doesn't quite work for immutable types, since there's nothing you can do with the "extra space pre-allocated". You can't mutate it! Nonetheless, rope-like structures will work fine, and there are surely plenty of them floating around.

The main point of linked lists in Haskell is that you can compute them lazily. So a Haskell list is more like a python "generator", a callback function that gives you the next element. This is nice because we don't need a separate interface for generators, streams, ranges, etc.; they are all just lists in Haskell.

If you force computation of a whole list sand save it, the representation in memory would be just a basic linked list. But that's not really recommended as it's a quite inefficient way to store and work with non-tiny amounts data.

There are also true arrays in Haskell which are not very useful due to reasons.

Perhaps the most flexible structures we have are various tree-based array implementations, similar to Clojure's arrays.

We have gone through a similar journey on a project at work - starting by using Z3 then moving to a simpler in-house built boolean constraint solver. Will see if it is something that could be open sourced.

Maybe I'm stupid but this approach seems very similar to other methods for analyzing loop-carried dependencies such as polyhedral compilation.

It has similarities, at least on the ultimate goals (creating efficient parallel code), but the approach is different: We start from already fully parallelized code and are just trying to recoup some of the performance loss of high-level programming language guarantees. While failing to parallelize loops in FORTRAN-like languages can be catastrophic (meaning that the code stays sequential), we at most pay the cost of the memory overhead.

no native Windows support:

https://github.com/diku-dk/futhark/issues/1761

Reply on news.ycombinator.com