A universal encoding for functions in Scala based on structural types
Methods in Scala are not first-class values: they cannot be passed around, only called. This is usually transparent for users since attempting to use a method as a value will cause it to be eta-expanded into a function by the typechecker. However, functions in Scala can only be used to express a subset of methods: scala.FunctionN can represent N-arity monomorphic methods with N ranging from 0 to 22. By contrast, methods can have arbitrary arity, type parameters, dependent parameters, implicit parameters, etc.
While this could in theory be solved by introducing functions as a first-class concept in the Scala type system, such a move would have far-reaching consequences and require a large amount of extra logic in the compiler. Instead, Dotty attempts to bridge the gap by introducing bespoke encodings that relies on existing features of the Scala type system, this leads to a moderate implementation complexity at the price of some usage restrictions.
Last year at the Scala Symposium, I presented an encoding in this spirit for polymorphic functions that we implemented in Dotty which relies on combining Scala’s structural typing support with special erasure rules to produce an efficient implementation.
This year however, I will go further and describe how this encoding can be extended to represent not just polymorphic functions but every sort of functions we may want to support in Scala. This simplifies the implementation (one encoding instead of many, at the price of a few extra typing rules) and means that we can avoid seemingly arbitrary usage restrictions. The key idea is to completely decouple the representation of functions during type checking from their runtime representation while being careful not to introduce any performance penalty (e.g., due to boxing), as an extra challenge this is done while preserving binary-compatibility with the existing Scala 2 ecosystem of libraries.
PhD student at EPFL in the LAMP group working on Dotty, the next-generation Scala compiler.
Wed 17 Jul
|10:30 - 11:00|
Alex JefferyUniversity of Sussex
|11:00 - 11:20|
|11:20 - 11:40|
Guillaume MartresEPFL, Switzerland
|11:40 - 12:10|