How hard is it to implement eta-expansion for dependent methods?

[Eugene Burmako]

Today's another today, when this bit me, so I decided to ask around.
What would it take to implement this functionality?

[Eugene Burmako]

JIRA issue for the reference: https://issues.scala-lang.org/browse/SI-4751

[Adriaan Moors]

one of the complexities would be to specify the type for a dependent function

( (x: AnyRef) => (x: x.type)) : (Function1[x.type, x.type] forSome { val x: AnyRef })

an alternative could be Function1[AnyRef, AnyRef]{def apply(x: AnyRef): x.type}  (as Lukas is doing for his work on tracking effects)

in other words, the short answer to your question is "a lot of implementation and specification work"

[Lukas Rytz]

On Tue, Jan 15, 2013 at 7:23 PM, Adriaan Moors <adriaa...@typesafe.com> wrote:

one of the complexities would be to specify the type for a dependent function

( (x: AnyRef) => (x: x.type)) : (Function1[x.type, x.type] forSome { val x: AnyRef })

an alternative could be Function1[AnyRef, AnyRef]{def apply(x: AnyRef): x.type}  (as Lukas is doing for his work on tracking effects)

This gets very messy with currying, btw :)

def f(x: AnyRef)(y: AnyRef): x.type

(AnyRef => AnyRef => AnyRef) { def apply(x: AnyRef): (AnyRef => AnyRef) { def apply(y: AnyRef): x.type } }

[Jason Zaugg]

On Tue, Jan 15, 2013 at 8:04 PM, Lukas Rytz <lukas...@epfl.ch> wrote:

On Tue, Jan 15, 2013 at 7:23 PM, Adriaan Moors <adriaa...@typesafe.com> wrote:

one of the complexities would be to specify the type for a dependent function

( (x: AnyRef) => (x: x.type)) : (Function1[x.type, x.type] forSome { val x: AnyRef })

an alternative could be Function1[AnyRef, AnyRef]{def apply(x: AnyRef): x.type}  (as Lukas is doing for his work on tracking effects)

This gets very messy with currying, btw :)

def f(x: AnyRef)(y: AnyRef): x.type

(AnyRef => AnyRef => AnyRef) { def apply(x: AnyRef): (AnyRef => AnyRef) { def apply(y: AnyRef): x.type } }

Another (more left-field) approach: from my comment on the ticket:

scala> trait DepFunction1[-A <: AnyRef, +Return[_]] { def apply(a: A) : Return[a.type] }
warning: there were 1 feature warnings; re-run with -feature for details
defined trait DepFunction1

scala> trait Function1[-A <: AnyRef, +R] extends DepFunction1[A, ({type l[_] = R})#l]
defined trait Function1

scala> object stringId extends DepFunction1[String, ({type Id[x] = x})#Id] { def apply(s: String): s.type = s }
defined object stringId

-jason

[Paolo G. Giarrusso]

Il giorno martedì 15 gennaio 2013 20:11:49 UTC+1, Jason Zaugg ha scritto:

Another (more left-field) approach: from my comment on the ticket:

scala> trait DepFunction1[-A <: AnyRef, +Return[_]] { def apply(a: A) : Return[a.type] }
warning: there were 1 feature warnings; re-run with -feature for details
defined trait DepFunction1

scala> trait Function1[-A <: AnyRef, +R] extends DepFunction1[A, ({type l[_] = R})#l]
defined trait Function1

scala> object stringId extends DepFunction1[String, ({type Id[x] = x})#Id] { def apply(s: String): s.type = s }
defined object stringId

To me that'd be the obvious thing to do. I gave up on it (mistakenly) because without currying, you need an exponential number of such traits. But restricting eta-expansion to curried methods — or even restricting dependent typing to curried methods — makes the problem disappear and gives a predictable (if concrete-syntax-wise ugly) solution. A couple small issues in type inference remain, but I'd guess they can be solved before 2.11.

Why would you need so many DepFunctionXYZ traits? Consider eta-expanding these types:

def f(a: T1, b: a.MemberT2)

def f(a: T1, b: T2)(b: a.MemberT2): b.MemberT3

and now generalize to N parameter lists, each with up to M members, to get M^N traits to generate, having up to M*N type constructor parameters, and each with up to M*N-1 parameters. One could avoid this exponential explosion (in practice, not in theory) by generating the needed ones (and only those), either at compile-time (but you'd get dup copies of these traits, as discussed for Tuples a couple of days ago), or at load-time with a Java/Scala JVM agent (or Javassist-like techniques), to avoid the duplication.

But I'd prefer currying. I'm even happy to curry *all* my dependently typed methods, and have a style-checker enforce that over all code I use.

== The two small issues ==

The rest of the emails details two small missing features arising in my limited tests of DepFunction1.

With a small variant, DepFunction1 can express the type of:

def f(a: T1)(b: a.MemberT2): b.MemberT3

and with a "small" amount of type annotations, I even managed to eta-expand it in only 5 lines. Since the blowup factor is so small, I think that automatic eta-expansion is not necessary :-P. I noted down the details in the bug-tracker for longer-term memory. What's amazing is that in the whole process I found only *one* Scalac bug, and it's even workaroundable since it's only in type inference.

Also, you taught me that scalac never infers a partially applied type constructor, even if it is handed to it on a plate, as in your example. (https://issues.scala-lang.org/browse/SI-5075) and it seems that inferring Return (required for automatic eta-expansion) would be "too hard" for Scalac, at least as hard as inferring D in this example:

trait TypeWithHKParam[D[_]]

def function[D[_]](t: TypeWithHKParam[D]) = 1

function(null: TypeWithHKParam[Option]) //okay 

//Does not compile
function(null: TypeWithHKParam[({type l[a] = (Int, a)})#l])

In fact, inferring D there requires only checking that the type constructor has the right kind - for Return, you also need to create a type lambda before. Doesn't look like rocket science in general; in fact, using dependent function types only requires the special case discussed in SI-5075, which was not implemented because it's just a special case and the general case is much harder.

== Question ==

Finally, since the above construction seems to give co- and contra-variance as expected, I'm confused about the relation with this other discussion, where Martin explains that method types are invariant in the argument in Scala (maybe just for overriding):

https://groups.google.com/d/msg/scala-internals/kSJLzYkmif0/T_CTI8M5oqsJ

Cheers,
Paolo

[Miles Sabin]

On Fri, Jan 18, 2013 at 5:16 PM, Paolo G. Giarrusso
<p.gia...@gmail.com> wrote:
> Why would you need so many DepFunctionXYZ traits? Consider eta-expanding
> these types:
>
> def f(a: T1, b: a.MemberT2)
> def f(a: T1, b: T2)(b: a.MemberT2): b.MemberT3
>
> and now generalize to N parameter lists, each with up to M members, to get
> M^N traits to generate, having up to M*N type constructor parameters, and
> each with up to M*N-1 parameters. One could avoid this exponential explosion
> (in practice, not in theory) by generating the needed ones (and only those),
> either at compile-time (but you'd get dup copies of these traits, as
> discussed for Tuples a couple of days ago), or at load-time with a
> Java/Scala JVM agent (or Javassist-like techniques), to avoid the
> duplication.

Hang on though ... these all erase down to one (erased) function type
per arity ... can't we exploit that here?

Cheers,


Miles

--
Miles Sabin
tel: +44 7813 944 528
skype: milessabin
gtalk: mi...@milessabin.com
g+: http://www.milessabin.com
http://twitter.com/milessabin

[Paolo Giarrusso]

On Fri, Jan 18, 2013 at 6:19 PM, Miles Sabin <mi...@milessabin.com> wrote:

On Fri, Jan 18, 2013 at 5:16 PM, Paolo G. Giarrusso
<p.gia...@gmail.com> wrote:
> Why would you need so many DepFunctionXYZ traits? Consider eta-expanding
> these types:
>
> def f(a: T1, b: a.MemberT2)
> def f(a: T1, b: T2)(b: a.MemberT2): b.MemberT3
>
> and now generalize to N parameter lists, each with up to M members, to get
> M^N traits to generate, having up to M*N type constructor parameters, and
> each with up to M*N-1 parameters. One could avoid this exponential explosion
> (in practice, not in theory) by generating the needed ones (and only those),
> either at compile-time (but you'd get dup copies of these traits, as
> discussed for Tuples a couple of days ago), or at load-time with a
> Java/Scala JVM agent (or Javassist-like techniques), to avoid the
> duplication.

Hang on though ... these all erase down to one (erased) function type
per arity ...

Good point!

can't we exploit that here?

If you erase DepFunction12, DepFunction21 etc. (where XY are lengths of parameter lists) *in the compiler* to the same DepFunction3, yes. The compiler should somehow have the type definitions of DepFunctionXX without having bytecode for it, which might or might not violate serious invariants - but that's maybe like AnyVal?

But unless scalac maintainers let that in (they might well want not to), I'll keep pushing for currying, so that at least DepFunction1 gets in and the issues are solved.

--
Paolo G. Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/