Two seemingly identical semantics: one binds implicitly, the other does not

Question

Hello: I've been learning Scala recently (my related background is mostly in C++ templates), and I've run into something I currently don't understand about Scala, and it is driving me insane. :(

(Also, this is my first post to StackOverflow, where I've noticed most of the really awesome Scala people seem to hang out, so I'm really sorry if I do something horrendously stupid with the mechanism.)

My specific confusion relates to implicit argument binding: I have come up with a specific case where the implicit argument refuses to bind, but a function with seemingly identical semantics does.

Now, it of course could be a compiler bug, but given that I just started working with Scala, the probability of me having already run into some kind of serious bug are sufficiently small that I'm expecting someone to explain what I did wrong. ;P

I have gone through the code and whittled it quite a bit in order to come up with the single example that doesn't work. Unfortunately, that example is still reasonably complex, as the problem seems to only occur in the generalization. :(

1) simplified code that does not work in the way I expected

import HList.::

trait HApplyOps {
    implicit def runNil
        (input :HNil)
        (context :Object)
        :HNil
    = {
        HNil()
    }

    implicit def runAll[Input <:HList, Output <:HList]
        (input :Int::Input)
        (context :Object)
        (implicit run :Input=>Object=>Output)
        :Int::Output
    = {
        HCons(0, run(input.tail)(context))
    }

    def runAny[Input <:HList, Output <:HList]
        (input :Input)
        (context :Object)
        (implicit run :Input=>Object=>Output)
        :Output
    = {
        run(input)(context)
    }
}

sealed trait HList

final case class HCons[Head, Tail <:HList]
    (head :Head, tail :Tail)
    extends HList
{
    def ::[Value](value :Value) = HCons(value, this)
}

final case class HNil()
    extends HList
{
    def ::[Value](value :Value) = HCons(value, this)
}

object HList extends HApplyOps {
    type ::[Head, Tail <:HList] = HCons[Head, Tail]
}

class Test {
    def main(args :Array[String]) {
        HList.runAny(   HNil())(null) // yay! ;P
        HList.runAny(0::HNil())(null) // fail :(
    }
}

This code, compiled with Scala 2.9.0.1, returns the following error:

broken1.scala:53: error: No implicit view available from HCons[Int,HNil] => (java.lang.Object) => Output.
        HList.runAny(0::HNil())(null)

My expectation in this case is that runAll would be bound to the implicit run argument to runAny.

Now, if I modify runAll so that, instead of taking its two arguments directly, it instead returns a function that in turn takes those two arguments (a trick I thought to try as I saw it in someone else's code), it works:

2) modified code that has the same runtime behavior and actually works

    implicit def runAll[Input <:HList, Output <:HList]
        (implicit run :Input=>Object=>Output)
        :Int::Input=>Object=>Int::Output
    = {
        input =>
        context =>
        HCons(0, run(input.tail)(context))
    }

In essence, my question is: why does this work? ;( I would expect that these two functions have the same overall type signature:

1: [Input <:HList, Output <:HList] (Int::Input)(Object):Int::Output
2: [Input <:Hlist, Output <:HList] :Int::Input=>Object=>Int::Output

If it helps understand the problem, some other changes also "work" (although these change the semantics of the function, and therefore are not usable solutions):

3) hard-coding runAll for only a second level by replacing Output with HNil

    implicit def runAll[Input <:HList, Output <:HList]
        (input :Int::Input)
        (context :Object)
        (implicit run :Input=>Object=>HNil)
        :Int::HNil
    = {
        HCons(0, run(input.tail)(context))
    }

4) removing the context argument from the implicit functions

trait HApplyOps {
    implicit def runNil
        (input :HNil)
        :HNil   
    = {
        HNil()  
    }

    implicit def runAll[Input <:HList, Output <:HList]
        (input :Int::Input)
        (implicit run :Input=>Output)
        :Int::Output
    = {
        HCons(0, run(input.tail))
    }

    def runAny[Input <:HList, Output <:HList]
        (input :Input) 
        (context :Object)
        (implicit run :Input=>Output)
        :Output 
    = {
        run(input)
    }
}

Any explanation anyone may have for this would be much appreciated. :(

(Currently, my best guess is that the order of the implicit argument with respect to the other arguments is the key factor that I'm missing, but one that I'm confused by: runAny has an implicit argument at the end as well, so the obvious "implicit def doesn't work well with trailing implicit" doesn't make sense to me.)

Answer 1

(Note: this is a summary of the discussion that took place in possibly more detail in the comments section of another answer on this question.)

It turns out that the problem here is that the implicit parameter is not first in runAny, but not because the implicit binding mechanism is ignoring it: instead, the issue is that the type parameter Output is not bound to anything, and needs to be indirectly inferred from the type of the run implicit parameter, which is happening "too late".

In essence, the code for "undetermined type parameters" (which is what Output is in this circumstance) only gets used in situations where the method in question is considered to be "implicit", which is determined by its direct parameter list: in this case, runAny's parameter list is actually just (input :Input), and isn't "implicit".

So, the type parameter for Input manages to work (getting set to Int::HNil), but Output is simply set to Nothing, which "sticks" and causes the type of the run argument to be Int::HNil=>Object=>Nothing, which is not satisfiable by runNil, causing runAny's type inferencing to fail, disqualifying it for usage as an implicit argument to runAll.

By reorganizing the parameters as done in my modified code sample #2, we make runAny itself be "implicit", allowing it to first get its type parameters fully determined before applying its remaining arguments: this happens because its implicit argument will first get bound to runNil (or runAny again for more than two levels), whose return type will get taken/bound.

To tie up the loose ends: the reason that the code sample #3 worked in this situation is that the Output parameter wasn't even required: the fact that it was bound to Nothing didn't affect any subsequent attempts to bind it to anything or use it for anything, and runNil was easily chosen to bind to its version of the run implicit parameter.

Finally, code sample #4 was actually degenerate, and shouldn't even have been considered to "work" (I had only verified that it compiled, not that it generated the appropriate output): the data types of its implicit parameters were so simplistic (Input=>Output, where Input and Output were actually intended to be the same type) that it would simply get bound to conforms:<:<[Input,Output]: a function that in turn acted as the identity in this circumstance.

(For more information on the #4 case, see this apparently dead-on related question: problem with implicit ambiguity between my method and conforms in Predef.)

Answer 2

When you declare an implicit def like this:

implicit def makeStr(i: Int): String = i.toString

then the compiler can automatically create an implicit Function object from this definition for you, and will insert it where an implicit of type Int => String is expected. This is what happens in your line HList.runAny(HNil())(null).

But when you define implicit defs which themselves accept implicit parameters (like your runAll method), it doesn't work any more, as the compiler cannot create a Function object whose apply method would require an implicit — much less guarantee that such an implicit would be available at the call site.

The solution to this is to define something like this instead of runAll:

implicit def runAllFct[Input <: HList, Output <: HList]
    (implicit run: Input => Object => Output):
        Int :: Input => Object => Int :: Output =
  { input: Int :: Input =>
    context: Object =>
      HCons(0, run(input.tail)(context))
  }

This definition is a bit more explicit, as the compiler now won't need to try to create a Function object from your def, but will instead call your def directly to get the needed function object. And, while calling it, will automatically insert the needed implicit parameter, which it can resolve right away.

In my opinion, whenever you expect implicit functions of this type, you should provide an implicit def that does indeed return a Function object. (Other users may disagree… anyone?) The fact that the compiler is able to create Function wrappers around an implicit def is there mainly, I suppose, to support implicit conversions with a more natural syntax, e.g. using view bounds together with simple implicit defs like my first Int to String conversion.