Skip to content
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

@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
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
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
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
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
Copy link
Member

seems unlikely to progress in Scala 2

@milessabin
Copy link

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
Copy link

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

@S11001001
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
Copy link

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
Copy link
Member

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
Copy link

@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
Copy link
Member

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
Copy link

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 pushed 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
S11001001 added a commit to digital-asset/daml that referenced this issue May 28, 2019
- this fails because the TC parameter should be a type member to avoid
  scala/bug#5075 but it is not
S11001001 added a commit to digital-asset/daml that referenced this issue May 27, 2020
* equalz Scalatest matcher in new daml-lf/scalatest-tools library

* equalz typing tests

* a 'should' replacing design

* a 'MatcherFactory1' design

- this fails because the TC parameter should be a type member to avoid
  scala/bug#5075 but it is not

* MatcherFactory1 with chained Lub+Equal typeclass

- requires partial-unification at point of use, which is not great

* LubEqual's extra tparam is probably unneeded

* better LtEqual

* demonstrate that HK LubEqual's resolve with DMT should + MatcherFactory

* remove unneeded 3rd param from LubEqual, again

* update dependency specs and license headers

* allow use with should, shouldNot in some cases, preserving the shouldx/shouldNotx alternatives

* move Equalz to libs-scala/scalatest-utils

* rename bzl targets and place in com.daml.scalatest package

* add scalatest-utils to release

* move *SpecCheckLaws, Unnatural to scalatest-utils

* missed scalacheck dep in scalatest-utils

* downstreams of *SpecCheckLaws now get them from scalatest-utils

* test equal-types case as well

* update LF documentation

CHANGELOG_BEGIN
CHANGELOG_END

* whitespace error
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

7 participants