`Manifest` -> `Type` change proposal

[Angelogeb]

This PR introduces a Type typeclass based representation of types in LMS.

This implementation is based on the one present on the previous version of LMS and the one presented in "Reflections on LMS: exploring front-end alternatives".

Rationale

LMS relies on Manifests in Adapter.typeMap for keeping track of types of nodes in the graph. Although manifests are in general only used in the backend for code generation, there are cases where we would like to provide additional information in the types of the nodes. This has so far been overcome in ad-hoc ways adding this information at the Node level outside of the typeMap (example1, example2). Although convenient, this is not uniform and requires additional code to keep the information in sync between the typeMap and the nodes.

Design

• The typeMap is updated from a Map[Exp, Manifest[_]] to Map[Exp, TypeExp].
• Types are represented as graph terms. This might allow using LMS in new contexts.
• Types are reflected on the graph by Wrap
• To introduce new types a Type instance must be provided
• The Type type class provides two reify methods: one for simple types and one for types that might need to inspect the Expression before reflecting a type (in the case of the tensors example2 above, this allows to promote the shape to the type level). I am not sure about the latter design decision and if there are alternatives.

Open questions

• Should the type nodes be in the same graph as the expressions?
  • Do we have to change some parts of the backend to ignore such nodes or are they ignored by default?

Tasks

• [x] Typeclass sketch with example in Main to be deleted
• [ ] Extend interface for easier migration (equivalent of manifest[] etc.)
• [ ] Adapter.typeMap and Adapter.oldTypeMap: HashMap[Exp, Manifest[_]] -> HashMap[Exp, TypeExp]
• [ ] Wrap[T:Manifest] -> Wrap[T:Type]
• [ ] Update code using Manifest to Type
  • This will be a bit time consuming because the usage of Manifests hasn't been abstracted away using UtilOps which would have allowed using refactoring tools.

[TiarkRompf]

Thanks for having a go at this! This looks like a good start. Couple questions/remarks:

• My mental model so far has been that typeMap: HashMap[Exp,Exp] needs to be part of a central class such as GraphBuilder itself, so I'm curious about the trade-offs with the approach taken here.
• As a general scheme I'd propose to name things ArrayT, TensorT, FunT, etc when referring to the term that represents the types, so a dependent function type constructor could be FunT(argtpe => ... restpe)
• I think we need to "play through" a couple more test cases to see how things work. In particular I'm thinking of a minimal extension of the simply-typed API in frontend.scala, perhaps keeping the same user-facing API but representing and checking/propagating types internally. This should include all relevant test cases.
• What will lambda calculus with dependent types look like? See here on how to implement.
• For tensor types, what will be the type of matmul, written using fun?

Happy to meet and discuss, or for you to do another iteration first, whichever you prefer.

[Angelogeb]

• I think we need to "play through" a couple more test cases to see how things work. In particular I'm thinking of a minimal extension of the simply-typed API in frontend.scala, perhaps keeping the same user-facing API but representing and checking/propagating types internally. This should include all relevant test cases.
• What will lambda calculus with dependent types look like? See here on how to implement.
• For tensor types, what will be the type of matmul, written using fun?

Happy to meet and discuss, or for you to do another iteration first, whichever you prefer.

Currently working on this