New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Anonymous type function is accepted as higher-kinded parameter type, but does not unify with it #5075

Closed
scabug opened this Issue Oct 14, 2011 · 13 comments

Comments

Projects
None yet
7 participants
@scabug
Copy link

scabug commented Oct 14, 2011

I attached a minimal example reproducing the bug. Compiling it and checking the error messages might be faster than reading my description, but I still include a walkthrough of the bug. Suppose we have the following definitions (the values are irrelevant as you might verify, only the argument types count):

implicit def function[D[_]](t: TypeWithHigherKindParam[D]) = 1
val param: TypeWithHigherKindParam[PartialApply1Of2[Tuple2, Int]#Apply] = null

where PartialApply1Of2#Apply is a type function (it comes from Scalaz, is included in the attachment). Let's apply function to param:

function[PartialApply1Of2[Tuple2, Int]#Apply](param): Int //Compiles
function(param) //Does not compile

So, type inference cannot figure out the needed parameter. However, the error message hints that unification has the right inputs and is simply failing:

various/BugReport.scala:14: error: no type parameters for method function: (t: BugReport.TypeWithHigherKindParam[D])Int exist so that it can be applied to arguments (BugReport.TypeWithHigherKindParam[[B](Int, B)])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : BugReport.TypeWithHigherKindParam[[B](Int, B)]
 required: BugReport.TypeWithHigherKindParam[?D]

    function(param) //Does not compile

?D was declared as D[_] and has thus kind * -> * (in Haskell notation), like [B](Int, B), so unification should easily succeed.

Moreover, when making function implicit, I'd expect the compiler to be able to use it (as in the example) - that's (a reduced version of) my original use case, actually. More complex tests can be found commented out in the attachment.

FYI, I retested this also on a (hopefully) more recent version, getting the same results (plus extra unrelated warnings).
It was yesterday's HEAD of scala-virtualized (git://github.com/TiarkRompf/scala-virtualized.git), branch virtualized-master, commit 158bc26c7bf9552c99eba00690b15f5d351abfb6 (which seems to have last resynced to scala on this commit: scala/scala@b0d5648).

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Oct 14, 2011

Imported From: https://issues.scala-lang.org/browse/SI-5075?orig=1
Reporter: @Blaisorblade
Affected Versions: 2.9.1, 2.9.2
See #2712
Attachments:

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Oct 14, 2011

@retronym said:
The problem is with type argument inference, rather than with unification. AFAIK, scalac never infers a partially applied type constructor, even if it is handed to it on a plate, as in your example.

So probably a duplicate of #2712, although Adriaan will be the final arbiter of that.

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])

Very nicely reported bug, BTW.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Oct 15, 2011

@Blaisorblade said:
Thanks for the prompt answer, it's impressive.
I still hope that this subcase can be handled more easily, since here, unlike in #2712, Scalac does not have to synthesize a type function, but it is handed to it on a plate and it must just be kind-checked and the kind compared with the desired one.

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Jun 25, 2012

@adriaanm said:
this is not easy to do (in general, no point in solving this for some ad-hoc cases), so classifying as an improvement

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Mar 2, 2018

seems unlikely to progress in Scala 2

@SethTisue SethTisue closed this Mar 2, 2018

@milessabin

This comment has been minimized.

Copy link

milessabin commented Mar 3, 2018

Hold your horses ... this is actually fixed I would guess by the SI-2712 fix.

I think you're being a bit too free with "unlikely to progress in Scala 2".

milessabin added a commit to milessabin/scala that referenced this issue Mar 3, 2018

milessabin added a commit to milessabin/scala that referenced this issue Mar 3, 2018

@milessabin

This comment has been minimized.

Copy link

milessabin commented Mar 3, 2018

PR adding a test confirming the fix here: scala/scala#6366.

@S11001001

This comment has been minimized.

Copy link

S11001001 commented Mar 3, 2018

Fixing 2712 does not fix this, because "Scalac does not have to synthesize a type function, but it is handed to it on a plate and it must just be kind-checked and the kind compared with the desired one" as @Blaisorblade says, which is not what happens with -Ypartial-unification.

You can see this by using #Flip (type Flip[B] = T[B, A]) instead of #Apply in scala/scala#6336.

scala> val param: TypeWithHigherKindParam[PartialApply1Of2[Tuple2, Int]#Apply] = null
param: TypeWithHigherKindParam[[B](Int, B)] = null

scala> function(param)
res2: Int = 1

scala> val param: TypeWithHigherKindParam[PartialApply1Of2[Tuple2, Int]#Flip] = null
param: TypeWithHigherKindParam[[B](B, Int)] = null

scala> function(param)
<console>:14: error: no type parameters for method function: (t: TypeWithHigherKindParam[D])Int exist so that it can be applied to arguments (TypeWithHigherKindParam[[B](B, Int)])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : TypeWithHigherKindParam[[B](B, Int)]
 required: TypeWithHigherKindParam[?D]

       function(param)
       ^
<console>:14: error: type mismatch;
 found   : TypeWithHigherKindParam[[B](B, Int)]
 required: TypeWithHigherKindParam[D]
       function(param)
                ^

scala> function[PartialApply1Of2[Tuple2, Int]#Flip](param)
res4: Int = 1
@Blaisorblade

This comment has been minimized.

Copy link

Blaisorblade commented Mar 3, 2018

What's more annoying is that inference here would rely on not dealiasing too much, while other inference issues would be fixed by dealiasing more. Which is impossible to balance.
I was also unhappy at how the SI-2712 fix relied on aliasing for control. Wonder if the Flip example could be fixed by additional indirection through additional aliases?

It'd be more principled to use some newtype type constructor, like in Haskell:

trait PartialApply1Of2[T[_, _], A] {
  class Apply[B](unwrap: T[A, B]) extends AnyVal
  class Flip[B](unwrap: T[B, A]) extends AnyVal
}

so that any amount of dealiasing couldn't change the result of type inference—the user has to explicitly coerce between the newtype and its implementation. It's as if you had aliases and a way of telling when the typechecker should unfold the alias (and replace it by its definition) and refold it (and replace the definition by the alias).

That would demand better value types—maybe opaque types could handle this? But since the typechecker can see the implementation of an opaque type (supposedly), it's not obvious they could be used to control inference.
Value classes seem more clearly/directly applicable, especially if extended through JVM support, but that doesn't have a clear timeline.

Overall, compared to Haskell, it's cool that you can write out type lambdas and pass them explicitly (and we should retain that possibility), but we know that inferring them robustly in general doesn't work. Partial-unification approaches the Haskell approach but still infers type lambdas, unlike Haskell, causing this problem.
I'm happy people are using it successfully now, but that will break if we start adding expectations.

@joroKr21

This comment has been minimized.

Copy link

joroKr21 commented Mar 3, 2018

@Blaisorblade I agree on all points. I don't know Dotty very well, but it looks to me that type aliases there are type lambdas under the hood. How does it deal with the conflicting needs to expand / not expand for the sake of unification?

Also I am really excited to have newtypes or whatever we choose to call them in Scala, but in this specific case we don't ever need a value of that type. Workaround today:

trait PartialApply1Of2[T[_, _], A] {
  type Apply[B] >: T[A, B] <: T[A, B]
  type Flip[B] >: T[B, A] <: T[B, A]
}
@Blaisorblade

This comment has been minimized.

Copy link

Blaisorblade commented Mar 3, 2018

@joroKr21

I don't know Dotty very well, but it looks to me that type aliases there are type lambdas under the hood.

Type aliases are still aliases — it's just that some aliases are to lambdas, so type Apply[B] = T[A, B] becomes type Apply = [B]T[A, B]. That doesn't mean Apply must be dealiased eagerly — even in Dotty eager dealiasing can trigger cycles.

Also I am really excited to have newtypes or whatever we choose to call them in Scala, but in this specific case we don't ever need a value of that type.

Well, the function call would just use the type, but at some point the code does manipulate actual instances of the type (in non-minimized applications).

It's fun this workaround might work, but at least in DOT (and I suspect in Dotty) type T >: A <: A and type T = A are the same thing.

@joroKr21

This comment has been minimized.

Copy link

joroKr21 commented Mar 4, 2018

Type aliases are still aliases — it's just that some aliases are to lambdas, so type Apply[B] = T[A, B] becomes type Apply = [B]T[A, B]. That doesn't mean Apply must be dealiased eagerly — even in Dotty eager dealiasing can trigger cycles.

That's definitely an improvement. In Scala 2 there is existentialAbstraction which does dealias eagerly and is used in a few places, including (I guess) for type projections and thus in the poor man's type lambda encoding.

Well, the function call would just use the type, but at some point the code does manipulate actual instances of the type (in non-minimized applications).

Ah, I was under the impression that you would only use it as a type lambda.

It's fun this workaround might work, but at least in DOT (and I suspect in Dotty) type T >: A <: A and type T = A are the same thing.

Bug or feature 🤔

@Blaisorblade

This comment has been minimized.

Copy link

Blaisorblade commented Mar 4, 2018

Caveat: I'm still a PL guy who understands DOT and is learning the real thing, so expect mistakes.

Bug or feature 🤔

Makes sense for the theory, couldn't point to any downside, if it knows the difference when talking to the user?

adriaanm added a commit to milessabin/scala that referenced this issue Jun 1, 2018

lrytz added a commit to scala/scala that referenced this issue Jun 1, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment