Introduce TypeRep to replace Manifest

[TiarkRompf]

Some DSLs like Scalan (https://github.com/scalan/Scalan-v2) need to attach domain specific information to types. In general it seems logical to abstract over the type representation, too, not just the terms (Rep[T]). The default would be TypeRep[T] = TypeTag[T].

[julienrf]

Where would the TypeRep[T] = TypeTag[T] definition live? In BaseExp?

[TiarkRompf]

We could put it directly in BaseExp, but maybe it will work better to use a different trait that is mixed in on a higher level. After all we also need to consider the case when we want to use something else than TypeTag[T], and it would be nice if we could use BaseExp as is.

[vjovanov]

It seems that this feature can not be implemented without macros. Here is the main blocker:

def list_new[A:TypeRep](xs: Seq[Rep[A]]): Rep[List[A]] = ListNew(xs)

results in "could not find implicit value for evidence parameter of type scala.lms.TypeRep[List[A]] ".

Apparently the compiler here finds the manifest of a type List[A] if it has a manifest for T in scope. We can not reproduce this without compiler support (e.g. macros). I think it is not worth the effort.

Simple TypeTag version is ready for a pull request.

[julienrf]

Maybe you need to help the compiler? Sometimes the type inference mechanism is not good when we use type aliases, what if you add the following?

trait TypeRepBase {
  type TypeRep[A]
}

trait TypeRepTypeTag extends TypeRepBase {
  type TypeRep[A] = TypeTag[A]
  implicit def typeTag2TypeRep[A : TypeTag]: TypeRep[A] = implicitly[TypeTag[A]]
}

[vjovanov]

Then you get a StackOverflow since typeTag2TypeRep has the highest priority.

[sstucki]

I'm confused. Can't we use this

type TypeRep[A] = TypeTag[A]
implicit def typeTag2TypeRep[A](implicit ev: TypeTag[A]): TypeRep[A] = ev

[vjovanov]

This is a diverging implicit.

[vjovanov]

And if you use the wrapper class then you get the error that I presented in the first comment.

[sstucki]

What does the wrapper class look like? implicit class TypeRep[+A](tt: TypeTag[A])?

[vjovanov]

It is not covariant, as the TypeTag is not covariant. And I use a method:

implicit def typeRepFromManifest[T](implicit mf: Manifest[T]): TypeRep[T] = TypeRepExp(mf)

Instead of the implicit class.

Now I am looking how does the compiler get an implicit Manifest[List[T]] when it has an implicit Manifest[T].

[sstucki]

What about changing the definition of list_new to

def list_new[A](xs: Seq[Rep[A]])(implicit ev: TypeRep[List[A]]): Rep[List[A]] = ListNew(xs)

so the TypeRep[List[A]] gets passed along? And you'd need to change the ListNew constructor too, so maybe it's a bit cumbersome.

[vjovanov]

As well as 111 other places in LMS :)

[sstucki]

Well yea, but short of changing the compiler, this is the only way, right? At least if you want to allow TypeRep[A] to be an actual class (so you can add additional info to it) rather than an alias for TypeTag[A]. How would you solve the problem using Macros?

[TiarkRompf]

how about defining

implicit def listTypeRep[A:TypeRep]: TypeRep[List[A]] 

in ListOps?

[vjovanov]

In case of type TypeRep[T] Macros can override the priorities of implicits so they could find the appropriate implicit in the scope.

In case of wrapper class, they could introduce the wrapped TypeTag as an implict, spawn an appropriate TypeTag for X[T], and finally wrap it again into the TypeTag.

[vjovanov]

@TiarkRompf This would require adding these implicits in many places for different types. We could make one for all higher kinds but how would the implementation of this method go?

[vjovanov]

Do we have a use case for this feature that would justify overheads in complexity that applies to compilation times, designers, and users?

[TiarkRompf]

Thinking about it, it seems to me that having DSL designers state explicitly "this is a type that can be lifted" may be a good thing. The main benefit is enabling polytypic programming: the TypeRep abstraction is a safe mechanism to define that e.g. a List[(A,B)] is globally represented as a (FastList[A], FastList[B]). It will also enable transformers that change types in such a way. Compared to the current Manifest situation, i hope that we can reduce complexity for users somewhat. For example, we can have better error messages when no implicit TypeRep is found (using implicitNotFound).

[vjovanov]

I have investigated what happens. In the malicious case, mentioned in the first comment, the compiler produces trees that do run-time reflection to create a new TypeTag[List[T]] based on the manifest of T. We could reproduce this, but then we are replicating parts of the compiler. Our modification would also need to copy all the additional data from the TypeTag[T] to the TypeTag[List[T]].

This logic should also include all of the possible cases: TypeTag[(T, U)], TypeTag[List[List[T]]], TypeTag[List[(T, U]] etc.

[vjovanov]

https://github.com/vjovanov/virtualization-lms-core/compare/TiarkRompf:develop-0.4...wip/typerep

Tests do not compile as I would need to resolve 60 more type errors there. Also there are some differences in behavior. For example, https://github.com/vjovanov/virtualization-lms-core/commit/93dbee0ea09cd5824e8055622f794e2bcc17c630.

If everyone is happy with this we need to fix the remaining tests and merge immediately. This pull request required a noticeable amount of work and it would be a shame to be wasted.

[TiarkRompf]

Awesome, this looks good to me. I think we should go ahead and merge it into develop-0.4 and then fix the tests. I can take care of the tests if you want.

[TiarkRompf]

Some minor comments:

• should we rename TypeRepExp to TypeExp in analogy with Rep/Exp, and move it from the Base world to BaseExp?
• I think it would also make sense to restrict the interface of trait TypeRep somewhat. DSL implementors can always pattern match to obtain a TypeExp, and for users the structure of a TypeRep shouldn't matter.
• in Effects.scala, there are checks typeRep[T] == manifest[Any]: should the rhs be typeRep[Any]?

[vjovanov]

Agreed. I thought that I found all manifest[.?] but it seems some are missed. I will fix those.

[vjovanov]

Something strange happened. Github says that I am up to date (https://github.com/vjovanov/virtualization-lms-core/compare/TiarkRompf:develop-0.4...wip/typerep). But when I rebase there are conflicts. I am fixing those.