[HN Gopher] Array short-circuiting
       ___________________________________________________________________
        
       Array short-circuiting
        
       Author : Munksgaard
       Score  : 59 points
       Date   : 2022-11-12 20:52 UTC (1 days ago)
        
 (HTM) web link (futhark-lang.org)
 (TXT) w3m dump (futhark-lang.org)
        
       | rwmj wrote:
       | 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...
        
       | svnpenn wrote:
       | no native Windows support:
       | 
       | https://github.com/diku-dk/futhark/issues/1761
        
       | pstoll wrote:
       | 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.
        
       | nerdponx wrote:
       | 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?
        
         | colonwqbang wrote:
         | Haskell puts a lot more emphasis on linked/tree structures than
         | arrays. Built-in support for arrays in Haskell is pretty
         | crappy.
        
         | JonChesterfield wrote:
         | 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.
        
       | bjourne wrote:
       | Maybe I'm stupid but this approach seems very similar to other
       | methods for analyzing loop-carried dependencies such as
       | polyhedral compilation.
        
       ___________________________________________________________________
       (page generated 2022-11-13 23:01 UTC)