Vectorized interpretation

[pchiusano]

Related to #1055 and some inspiration from @ekmett - Ed if you are reading this, would like to hear your latest thinking / links to more reading for this sort of thing.

This is an idea I'm interested in exploring for writing high performance vectorized code in Unison in what looks like a straightforward scalar style. Assume we have a type, Vec a, which denotes a (Set Nat, Nat -> Maybe a), basically a subset of indices and a way of grabbing the value at any index. It's implementation would be something super efficient, backed by unboxed, packed vectors. API sketch:

Vec.nat.range : Nat -> Nat -> Vec Nat
Vec.nat.scale : Nat -> Vec Nat -> Vec Nat
Vec.nat.increment : Nat -> Vec Nat -> Vec Nat
Vec.choice : Vec Bool -> Vec a -> Vec a -> Vec a
Vec.switch : Vec a -> [(a, Vec b)] -> Vec b
Vec.left : Vec a -> Vec (Either a b)
Vec.right : Vec b -> Vec (Either a b)
... etc

You could write code directly with this and it would all be efficient unboxed operations with loops happening on the Haskell side hopefully using SIMD rather than in pure Unison.

Now assume we have an ability Vectorized, which lets us write straightforward-looking scalar code:

ability Vectorized where
  vec : Vec a -> a

-- builtin
vectorize  : (a ->{Vectorized} b) -> Vec a -> Vec b

-- equivalent to  `'(Vec.nat.increment 1 (Vec.nat.range 0 1000))`
ex _ = 
  n = vec (nat.range 0 1000)
  n  + 1

> vectorize ex 

The idea here is that the vectorize is a builtin function which has a special handler. The handler actually inspects the continuation, peels off the head operation of that continuation, and lifts it to operate on Vec. In this case, the continuation is n -> n + 1, which the runtime converts to a call to Vec.nat.increment rather than doing the loop in pure Unison.

[pchiusano]

This looks like a good one. I like that you can get both the zippy and cartesian-producty version from the same API: http://blog.ezyang.com/2020/01/vmap-in-haskell/

[pchiusano]

And here's a zippy ability: https://gist.github.com/pchiusano/f12d1ebdf1e4396fb1e311ad460ec9a8