By: Quentin Bernet and Guillaume Martres
History
Date  Version 

Sep 23th 2022  Initial Draft 
Summary
We propose to extend etaexpansion to polymorphic methods. This means automatically transforming polymorphic methods into corresponding polymorphic functions when required, for example:
def f1[A](x: A): A = ???
val v1_1: [B] => B => B = f1 // f1 becomes [B'] => (y: B') => f1[B'](y)
Returning readers, for a quick glance at a wide array of examples illustrated like the above, go to Highlevel overview.
In the following, “Note” never introduces new concepts, it points out a nonobvious consequence, and/or reminds the reader of a pertinent fact about Scala.
Motivation
Regular etaexpansion is so ubiquitous that most users are not aware of it, for them it is intuitive and obvious that methods can be passed where functions are expected.
When manipulating polymorphic methods, we wager that most users find it confusing not to be able to do the same. This is the main motivation of this proposal.
It however remains to be demonstrated that such cases appear often enough for time and maintenance to be devoted to fixing it. To this end, the remainder of this section will show a manufactured example with tuples, as well as realworld examples taken from the Shapeless3 and kittens libraries.
Tuples
List(1, 2, 3).map(Some.apply) // works
("Hello", 2, 'u').map(Some.apply) // error:
// Found: Any => Some[Any], Required: [t] => (t) => Nothing
As tuples are becoming a powerful part of metaprogramming through Mirror
instances, we expect these kinds of cases to become more and more frequent.
Shapeless (source)
In the shapeless library, polymorphic functions are used relatively often, but they are usually small and unique, making them not very suitable for refactoring. There is however the following case, where a function is very large:
...
def readElems(s: String): Option[(T, String)] = {
type Acc = (String, Seq[String], Boolean)
inst.unfold[Acc]((s, labelling.elemLabels, true))(
[t] => (acc: Acc, rt: Read[t]) => {
val (s, labels, first) = acc
(for {
(_, tl0) < if(first) Some(("", s)) else head(s, "(,)(.*)".r)
(_, tl1) < head(tl0, s"(${labels.head}):(.*)".r)
(t, tl2) < rt.read(tl1)
} yield (t, tl2)) match {
case Some(t, tl2) => ((tl2, labels.tail, false), Some(t))
case None => ((s, labels, first), None)
}
}
) match {
case (s, None) => None
case (acc, Some(t)) => Some((t, acc._1))
}
}
By factoring out the function, it is possible to make the code more readable:
...
def readElems(s: String): Option[(T, String)] = {
type Acc = (String, Seq[String], Boolean)
val unfolder = [t] => (acc: Acc, rt: Read[t]) => {
val (s, labels, first) = acc
(for {
(_, tl0) < if(first) Some(("", s)) else head(s, "(,)(.*)".r)
(_, tl1) < head(tl0, s"(${labels.head}):(.*)".r)
(t, tl2) < rt.read(tl1)
} yield (t, tl2)) match {
case Some(t, tl2) => ((tl2, labels.tail, false), Some(t))
case None => ((s, labels, first), None)
}
}
inst.unfold[Acc]((s, labelling.elemLabels, true))(unfolder) match {
case (s, None) => None
case (acc, Some(t)) => Some((t, acc._1))
}
}
It is natural at this point to want to transform the function into a method, as the syntax for the latter is more familiar, and more readable:
...
def readElems(s: String): Option[(T, String)] = {
type Acc = (String, Seq[String], Boolean)
def unfolder[T](acc: Acc, rt: Read[T]): Acc = {
val (s, labels, first) = acc
(for {
(_, tl0) < if(first) Some(("", s)) else head(s, "(,)(.*)".r)
(_, tl1) < head(tl0, s"(${labels.head}):(.*)".r)
(t, tl2) < rt.read(tl1)
} yield (t, tl2)) match {
case Some(t, tl2) => ((tl2, labels.tail, false), Some(t))
case None => ((s, labels, first), None)
}
}
inst.unfold[Acc]((s, labelling.elemLabels, true))(unfolder) match {
case (s, None) => None
case (acc, Some(t)) => Some((t, acc._1))
}
}
However, this does not compile.
Only monomorphic etaexpansion is applied, leading to the same issue as with our previous Tuple.map
example.
Kittens (source)
In Kittens
, there is a case of particularly obvious etaexpansion done by hand (comments by me):
...
final override def traverse[G[_], A, B](fa: F[A])(f: A => G[B])
(using G: Applicative[G]): G[F[B]] =
val pure = [a] => (x: a) => G.pure(x) // etaexpansion
val map = [a, b] => (ga: G[a], f: a => b) => G.map(ga)(f) // ~etaexpansion
val ap = [a, b] => (gf: G[a => b], ga: G[a]) => G.ap(gf)(ga) // ~etaexpansion
inst.traverse[A, G, B](fa)(map)(pure)(ap)([f[_]] => (tf: T[f], fa: f[A]) => tf.traverse(fa)(f))
Sadly since map
and ap
are curried, assuming this proposal, only pure
can be eliminated:
...
final override def traverse[G[_], A, B](fa: F[A])(f: A => G[B])
(using G: Applicative[G]): G[F[B]] =
val map = [a, b] => (ga: G[a], f: a => b) => G.map(ga)(f)
val ap = [a, b] => (gf: G[a => b], ga: G[a]) => G.ap(gf)(ga)
inst.traverse[A, G, B](fa)(map)(G.pure)(ap)([f[_]] => (tf: T[f], fa: f[A]) => tf.traverse(fa)(f))
This already helps with readability, but we can postulate that given cases like this, an uncurried variant of map
and ap
would be implemented, allowing us to write:
...
final override def traverse[G[_], A, B](fa: F[A])(f: A => G[B])
(using G: Applicative[G]): G[F[B]] =
inst.traverse[A, G, B](fa)(G.map)(G.pure)(G.ap)([f[_]] => (tf: T[f], fa: f[A]) => tf.traverse(fa)(f))
If wanted, we can then factor the function into a method:
...
final override def traverse[G[_], A, B](fa: F[A])(f: A => G[B])
(using G: Applicative[G]): G[F[B]] =
def traverser[F[_]](tf: T[F], fa: F[A]) = tf.traverse(fa)(f)
inst.traverse[A, G, B](fa)(G.map)(G.pure)(G.ap)(traverser)
Proposed solution
Highlevel overview
As the previous section already describes how polymorphic etaexpansion affects the examples, we will use this section to give quantity of small, illustrative, examples, that should cover most of the range of this proposal.
In the following id'
means a copy of id
with a fresh name, and //reminder:
sections are unchanged by this proposal.
Explicit parameters:
def f1[A](x: A): A = ???
val v1_1: [B] => B => B = f1 // f1 becomes [B'] => (y: B') => f1[B'](y)
def f2[A]: A => A = ???
val v2_1: [B] => B => B = f2 // f2 becomes [B'] => (y: B') => f2[B'](y)
type F[C] = C => C
def f3[A]: F[A] = ???
val v3_1: [B] => B => B = f3 // f3 becomes [B'] => (y: B') => f3[B'](y)
//reminder:
val vErr: [B] => B = ??? // error: polymorphic function types must have a value parameter
Extension/Interleaved method:
extension (x: Int)
def extf1[A](x: A): A = ???
val extv1_1: [B] => B => B = extf1(4) // extf1(4) becomes [B'] => (y: B') => extf1(4)[B'](y)
val extv1_3: Int => [B] => B => B = extf1 // extf1 becomes (i: Int) => [B'] => (y: B') => extf1(i)[B'](y)
// See https://docs.scalalang.org/sips/clauseinterleaving.html
def interleaved(key: Key)[V >: key.Value](default: V): V = ???
val someKey: Key = ???
val interleaved_1: [A >: someKey.Value] => A => A = interleaved(someKey)
// interleaved(someKey) becomes [A' >: someKey.Value] => (default: A') => interleaved(someKey)[A'](default)
Implicit parameters:
def uf1[A](using x: A): A = ???
val vuf1_1: [B] => B ?=> B = uf1 // uf1 becomes [B'] => (y: B') ?=> uf1[B']
def uf2[A]: A = ???
val vuf2: [B] => B ?=> B = uf2 // uf2 becomes [B'] => (y: B') ?=> uf2[B']
//reminder:
val get: (String) ?=> Int = 22 // 22 becomes (s: String) ?=> 22
val err: () ?=> Int = ?? // error: context functions require at least one parameter
Specification
Before we go on, it is important to clarify what we mean by “polymorphic method”, we do not mean, as one would expect, “a method taking at least one type parameter clause”, but rather “a (potentially partially applied) method whose next clause is a type clause”, here is an example to illustrate:
extension (x: Int)
def poly[T](x: T): T = x
// signature: (Int)[T](T): T
poly(4) // polymorphic method: takes a [T]
poly // monomorphic method: takes an (Int)
Note: Since typechecking is recursive, etaexpansion of a monomorphic method like poly
can still trigger polymorphic etaexpansion, for example:
val voly: Int => [T] => T => T = poly
// poly expands to: (x: Int) => [T] => (y: T) => poly(x)[T](y)
As this feature only provides a shortcut to express already definable objects, the only impacted area is the type system.
When typing a polymorphic method m
there are two cases to consider:
Polymorphic expected type
If the expected type is a polymorphic function taking [T_1 <: U_1 >: L_1, ..., T_n <: U_n >: L_n]
as type parameters, (A_1, ..., A_k)
as term parameters and returning R
, we proceed as follows:
Note: Polymorphic functions always take term parameters (but k
can equal zero if the clause is explicit: [T] => () => T
).

Copies of
T_i
s are created, and replaced inU_i
s,L_i
s,A_i
s andR
, noted respectivelyT'_i
,U'_i
,L'_i
,A'_i
andR'
.  Is the expected type a polymorphic context function ?

 If yes then
m
is replaced by the following:[T'_1 <: U'_1 >: L'_1, ... , T'_n <: U'_n >: L'_n] => (a_1: A'_1 ..., a_k: A'_k) ?=> m[T'_1, ..., T'_n]
 If yes then

 If no then
m
is replaced by the following:[T'_1 <: U'_1 >: L'_1, ... , T'_n <: U'_n >: L'_n] => (a_1: A'_1 ..., a_k: A'_k) => m[T'_1, ..., T'_n](a_1, ..., a_k)
 If no then

 the application of
m
is typechecked with expected typeR'

 If it succeeds, the above is the created tree.

 If it fails, go to Default.

At 3.ii. if the cause of the error is such that Nonpolymorphic expected type will never succeed, we might return that error directly, this is at the discretion of the implementation, to make errors as clear as possible.
Note: Type checking will be in charge of overloading resolution, as well as term inference, so the following will work:
def f[A](using Int)(x: A)(using String): A
def f[B](x: B, y: B): B
given i: Int = ???
given s: String = ???
val v: [T] => T => T = f
// f expands to: [T'] => (t: T') => f[T'](t)
// and then to: [T'] => (t: T') => f[T'](using i)(t)(using s)
def g[C](using C): C
val vg: [T] => T ?=> T = g
// g expands to: [T'] => (t: T') ?=> g[T']
// and then to: [T'] => (t: T') ?=> g[T'](using t)
Note: Type checking at 3. will have to recursively typecheck m[T'_1, ..., T'_n](a_1, ..., a_k)
with expected type R
, this can lead to further etaexpansion:
extension [A](x: A)
def foo[B](y: B) = (x, y)
val voo: [T] => T => [U] => U => (T, U) = foo
// foo expands to:
// [T'] => (t: T') => ( foo[T'](t) with expected type [U] => U => (T', U) )
// [T'] => (t: T') => [U'] => (u: U') => foo[T'](t)[U'](u)
Nonpolymorphic expected type
No polymorphic etaexpansion is performed, this corresponds to the old behaviour, written here as a reminder:
Fresh variables are applied to m
, typing constraints are generated, and typing continues, for example:
def ident[T](x: T): T = x
val idInt: Int => Int = ident
// ident becomes:
// ident[X] with expected type Int => Int
// (x: X) => ident[X](x) of type X => X with expected type Int => Int
// therefore X := Int
// (x: Int) => ident[Int](x)
Compatibility
Binary and TASTy
As this proposal never generates code that couldn’t have been written by hand before, these changes are binary and TASTy compatible.
Source
This proposal conserves source compatibility when a nonpolymorphic expected type is present, or when there is no expected type, since by definition the behaviour is the same.
In the case the expected type is polymorphic, either the code did not compile before, or there was an implicit conversion from the inferred monomorphic function to the expected polymorphic function. In the latter case, source compatibility is broken, since polymorphic etaexpansion will apply before search for implicit conversions, for example:
import scala.language.implicitConversions
given conv: Conversion[Any => Any, [T] => T => T] = f => ([T] => (x: T) => x)
def method[T](x: T): T = x
val function: [T] => T => T = method
// before: method is etaexpanded to Any => Any, and then converted using conv to [T] => T => T
// now: method is etaexpanded to [T] => T => T (conv is not called)
Restrictions
Not included in this proposal are:
 Applying polymorphic etaexpansion when there is no return type
 Expanding
[T] => T => T
to[T] => T => Id[T]
to maketuple.map(identity)
work (might work out of the box anyways, but not guaranteed)  Expanding
x => x
to[T] => (x: T) => x
if necessary (and generalizations)  Expanding
_
to[T] => (x: T) => x
if necessary (and generalizations)  Polymorphic SAM conversion
 Polymorphic functions from wildcard:
foo[_](_)
While all of the above could be argued to be valuable, we deem they are out of the scope of this proposal.
We encourage the creation of followup proposals to motivate their inclusion.
Open questions
Related work
 PreSIP: https://contributors.scalalang.org/t/polymorphicetaexpansion/5516
 A naive implementation can be found at https://github.com/lampepfl/dotty/pull/14015 (it is more general than this proposal and thus breaks compatibility)
 A compatibilitypreserving implementation is in development.