support vectors

[afilinski]

new type: [tau]
new functions:
  tab: {tau} -> [tau]
  seq : [tau] -> {tau}
  length (#) : [tau] -> int
  elt (x[y]) : ([tau],int) ->tau

note: can make seq a defined function:
  seq(v:[tau]):{tau} = {v[i] : i in &#v}

in svcode: now 4 primitive stream types: int, bool, [int], [bool] compiler translates arbitrary snesl types into primitive streams for nested vectors: data vector(s) + vector of segment lengths + vector of segment starts (= scan of lengths)

Also, since you will be modifying the types anyway, maybe consider also adding a unit () type to the source language, to complement binary products - and/or - to svcode (for representing control streams)

[afilinski]

Having looked a little closer at this, the implementation (and hence also cost model) gets a bit tricky for nested vectors, even without any parallelism. For example, consider a situation like this::

let m = [[1,2,3],[4,5,6],[7,8,9]] in let r = m[2] in r[1]

If we implement it by making r a copy of row 2 of the matrix (i.e., [7,8,9]), we are doing unexpectedly much work to access a single element. On the other hand, if we let r just point to a slice of the representation of m (which is fairly easy, since we have the starting index (6) and length (3)), then we cannot simply deallocate m when it goes out of scope in a situation like this:

let m = [[1,2,3],[4,5,6],[7,8,9]] in let r = m[2] in r

so we risk introducing a space leak. Resolving this properly looks non-trivial, so for now, maybe you should only allow vectors of primitive types, i.e., only [int] and [bool], and possibly also tuples of primitive types, e.g., [((int,bool),int)]. This will still allow many (most?) practical NESL examples to be coded. Once we have some results about cost-model preservation for this language, we may consider generalizing to nested vectors if there is still time.