2D arrays

[rolyp]

A proposed syntax for arrays in Fluid, as a precursor to defining a formal syntax. Let’s start by rewriting the convolution example in “Fluid extended with array notation.” You can create a new file fluid/example/convolution.fld for this experiment. It won’t parse with our existing parser, but it will allow us to prototype how we want things to look before making changes to the grammar.

Take a look at the code examples in the fluid folder to see what you can currently do in the language (unfortunately there isn’t any documentation yet, and there are some oddities like Unicode arrows). We can probably assume our arrays have a fixed lower bound (0 or 1). My guess is that this will take multiple iterations before we settle on a design, especially we’re not clear yet on the relationship to lists.

If we’re going to end up needing comprehensions, you might like to take a look at https://www.haskell.org/onlinereport/exps.html#list-comprehensions for how Haskell translates list comprehensions into the core language.

• add names to primitives – defer to later task
• fix problem revealed by dependsNeither (output dependencies only relevant to constructed values)
• standardise on eval_fwd vs. desugarFwd

Done/dropped:

• prototype Fluid array syntax using convolution example
• list comprehensions (List comprehensions #277)
• formalise grammar, typing rules and evaluation rules for arrays
• factor branch and branches parsers into separate curried and uncurried versions
• rename range to enumFromTo, a la Haskell
• array construction
  • AST, eval rule
  • desugaring rules
  • parser
  • fwd slicing
  • bwd slicing
  • test case
• array dims, lookup
  • generalise primitives to deal with array arguments
  • switch to storing indices as the pair value used to compute them
  • forward slicing
    • rehash primitives design to allow for custom dependencies
  • backward slicing
    • rehash primitives design again to flatten representation of partially applied primitives
      • store list of operands along with primitives
      • associate arity with each primitive
• eliminate setα, getα
• desugar BinaryApp s1 op s2 into App (App (Op op) (desugar s1)) (desugar s2)

[rolyp]

@min-nguyen Realised that keeping lengthy discussions against commits isn’t very helpful, so created this task instead.

[min-nguyen]

Thanks! Also out of interest, is the need to introduce arrays due to wanting to implement matrix convolution? i.e. were there a way of performing convolution using only lists, would we not be interested in this?

[rolyp]

Yes, the main reason for arrays is simply that it’s a nicer fit for convolution and other similar applications. List^2 would be an alternative, although somewhat less type-constrained because there would be no requirement that the inner lists all be of the same size.

I guess one thing we can do before we add arrays to the language is add list comprehensions - it sounds like we will need these for arrays, and it would be a nice feature to have anyway. So I suggest starting with fluid/example/list-comprehension.fld instead - just a simple example we can use to settle on a syntax for comprehensions. Probably we want the simplest version of comprehensions we can get away with (Haskell no doubt has more features than we need). We can then turn that file into a failing test case for the parser, which will induce the task of modifying the parser to make the test pass.

We can then think about the evaluation semantics and slicing rules for list comprehensions, which would be a nice thing to have. (We’ll have to give a direct semantics for list comprehensions, rather than an indirect one expressed in terms of a translation to a core language. We can discuss why and what this would involve nearer the time.)

[rolyp]

Extracted a new task (#277) for list comprehensions, since they can be done first and will be an independently useful feature.