Requirements for Generic Programming Support in Scala

[odersky]

We would like to add some mechanisms for generic programming support in Dotty. As a first step, we should work on a document that lists

Requirements: What changes do we envision? Some possibilities to consider are:

• Get rid of the 22 limit for tuples, products and functions
• Allow type-safe generic operations over tuples/products/functions
• Allow generic operations over all case classes and all ADTs (sealed class with case class children)
• Provide an easily accessible and robust way to enumerate all cases of an ADT

Use cases: What are typical generic operations? How would we hope to be able to express them in a generic way? To start the list, here are some:

• serializing/deserializing to various output formats
• equality
• displaying, potentially with custom printers
• generating random values

What are other good examples?

State of the Art: What has been done before that could help us find the right solution? Obvious precursors are

• Shapeless
• Haskell's "Scrap Your Boilerplate"

What other interesting solutions are out there?

Design Elements: What are possible combinations of language changes and library code to achieve the requirements? We should collect possible design elements and then boil them down into coherent strawman proposals.

[DarkDimius]

Do we want to include performance of emitted code in our guidelines?

Rodriguez Yakushev ([1], Figure 4.9) in his thesis about SYB did benchmarks and found that functions written using SYB are from 30 upto 160 times slower than handwritten code.

AFAIK the state of the art of getting performance back is [2] which relies on HERMIT. The closest analogue of HERMIT that we have is rewrite rules with meta as it needs complex optimizations specific to SYB.

[1] Rodriguez Yakushev A. Towards Getting Generic Programming Ready for Prime Time. – Utrecht University, 2009. [2] Adams M. D., Farmer A., Magalhães J. P. Optimizing SYB is easy! //Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation. – ACM, 2014. – С. 71-82.

[julienrf]

Use cases: What are typical generic operations?

More generally, several typeclasses (e.g. Functor, SemiGroup, etc.) can be implemented generically. milessabin/kittens is good example of such generic implementations.

@DarkDimius We’ll probably need first-class staging support ;) (see https://www.cl.cam.ac.uk/~jdy22/papers/staging-generic-programming.pdf)

[xeno-by]

@julienrf What features would be necessary from first-class staging support? Can meta provide these features?

[DarkDimius]

@julienrf, have a look at paper that I've cited. It proposes a mechanism other than staging that has both simpler user-facing abstraction and straightforward internal implementation, generating code that achieves performance similar to hand tuned code without requiring to change any library\user-code and without introduction of Rep[T]. I'd propose to go similar way as it will be in line with tooling that we already intend to develop.

[julienrf]

@xeno-by Indeed I think meta would be enough, actually.

Another example of use case: computing diffs between ADT values (see https://github.com/stacycurl/delta or https://github.com/xdotai/diff).

[DarkDimius]

@julienrf, nice examples indeed. Thinking about it @nicolasstucki just implemented diffing trees using external Java tool that works on Strings. Diffing Dotty trees structurally using proposed generic programing tools may be a good case-study.

[julienrf]

Maybe not related, but that would be also interesting to support function arity abstraction. Currently, this is what shapeless does: https://github.com/milessabin/shapeless/wiki/Feature-overview:-shapeless-2.0.0#facilities-for-abstracting-over-arity This paper may also be relevant: http://www.cs.yale.edu/publications/techreports/tr1191.pdf

[lihaoyi]

FWIW uPickle and PPrint are pretty heavy uses of generic derivation. uPickle is very common in Scala.js land since it's lightweight and cross-platform, and PPrint is used by the Ammonite REPL.

Both make use of the same, bespoke generic-derivation system which lives entirely in https://github.com/lihaoyi/upickle-pprint/blob/master/derive/shared/src/main/scala/derive/Derive.scala. They suffer tons of bugs and edge cases around generic derivation; if there was a standard mechanism I could leverage I would gladly jump on board

FastParse makes use of implicits to let you "append stuff to" tuples, in order to keep type signatures simple: e.g. Parser[(Int, String)] ~ Parser[Double] gives a Parser[(Int, String, Double)]. This is implemented here and generally doesn't cause issues, but could also piggy back on whatever mechanism you guys come up with

[eaplatanios]

Hi all! Are there any updates on the status of Generic Programming Support in Dotty? Thanks! :)

[OlivierBlanvillain]

@eaplatanios It's actively being worked on, so the status is (still) "work in progress" :)

[eaplatanios]

@OlivierBlanvillain Thanks for the update! :) Is there any chance you could open up some of the discussion? I am using generic derivations extensively in TensorFlow Scala, but I am curious to learn more about how you go about designing such a language feature. Mainly as an educational experience. :)

[OlivierBlanvillain]

@eaplatanios I will make sure to keep you in the loop when we get to that point!

[eaplatanios]

@OlivierBlanvillain Sounds good! Thanks! :)

[winitzki]

A question: the current documentation for generic derivation in Dotty only talks about sum and product types. What about function types? Are they not supported by the Mirror mechanism?

Example:

case class P[A](x: Int, y: A => String)
case class Q[A](x: P[A] => A)

Is it possible automatically to derive a Functor typeclass instance for Q[_] and a Contrafunctor typeclass instance for P[_]? It is not clear from the current documentation whether the Mirror mechanism supports such derivation.