Re: [scala-user] Caching implicit convertion: map.getOrElseUpdate throws unexpected exception

[Paul Phillips]

[Redirected to scala-language since I'm not on scala-user.]

Someone asked me recently why I'm against extending Function1 casually.  In this we have a pretty good example.  I'm not sure why you declared the map to be an implicit val:

  implicit val cache = mutable.Map[Int, String]()

I imagine you didn't do that with the intention of placing a competing implicit conversion in scope, because your Map is also an Int => String.  And for whatever reason it's not ambiguous - the val is preferred over the def I guess.

So this line:

  println(3.startsWith("whatever"))

Is using the cache directly to implicitly convert Int to String, i.e. it's calling cache.apply, not cache.getOrElseUpdate.

On Thu, Aug 2, 2012 at 2:33 PM, Bruno Woltzenlogel Paleo <brun...@gmail.com> wrote:

Hi!

I would like to have an implicit conversion with caching of the results (in a mutable map). However, when called implicitly, the map's getOrElseUpdate throws an exception. The following is a simplification of my real code (in particular, in my real code the conversion is not between Int and String).

  import language.implicitConversions

  import collection.mutable.{Map => MMap}

  implicit val cache : MMap[Int, String] = MMap() 

  implicit def intToString(p: Int): String = cache.getOrElseUpdate(p, "number " + p.toString + " !" ) 

  

  

// Everything works fine in the following line, 

// "false" is printed and (2 -> "number 2 !") is added to cache as expected

  println(intToString(2).startsWith("whatever")) 

// But when intToString is called implicitly, as in the line below, an exception is thrown

  println(3.startsWith("whatever")) // But here, surprisingly, an exception is thrown

   

The exception message is:

java.lang.ExceptionInInitializerError

at at.logic.skeptik.Main.main(Main.scala)

at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)

at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)

at java.lang.reflect.Method.invoke(Method.java:597)

Caused by: java.util.NoSuchElementException: key not found: 3

at scala.collection.MapLike$class.default(MapLike.scala:228)

at scala.collection.AbstractMap.default(Map.scala:58)

at scala.collection.mutable.HashMap.apply(HashMap.scala:63)

at at.logic.skeptik.Main$.<init>(Main.scala:55)

at at.logic.skeptik.Main$.<clinit>(Main.scala)

at at.logic.skeptik.Main.main(Main.scala)

at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)

at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)

at java.lang.reflect.Method.invoke(Method.java:597)

java.lang.RuntimeException: Nonzero exit code: 1

at scala.sys.package$.error(package.scala:27)

Is this a bug of the Scala (2.10.0-M5) language? It seems to me that getOrElseUpdate tries something and catches an exception if the key is not found, but for some reason the exception is escaping the catch when the call to getOrElseUpdate is made from within an implicitly called implicit conversion...

Or is this expected behavior? If so, what should I do to make getOrElseUpdate work also from within an implicit call?

I would also be happy to hear any alternative idea for implementing an implicit converter that caches and reuses the conversions.

Best regards,

Bruno

[Bruno Woltzenlogel Paleo]

Someone asked me recently why I'm against extending Function1 casually.  In this we have a pretty good example.  I'm not sure why you declared the map to be an implicit val:

  implicit val cache = mutable.Map[Int, String]()

Originally (and also in my real code) "cache" was passed as an implicit argument to the implicit "intToString" conversion, as follows.

implicit def intToString(p: Int)(implicit cache: Map[Int, String]): String = cache.getOrElseUpdate(p, "number " + p.toString + " !" ) 

That is why I forgot the "implicit" modifier preceding "val cache = ...". 

This original version also throws the same exception, by the way.

So this line:

  println(3.startsWith("whatever"))

Is using the cache directly to implicitly convert Int to String, i.e. it's calling cache.apply, not cache.getOrElseUpdate.

Yes. If I had read the exception message more carefully, I might have figured this out. I didn't think about this possibility, because I wrongly thought that a "val" couldn't be used as an implicit conversion, but only as an implicit argument, and because I forgot that Map extends Function1.

I imagine you didn't do that with the intention of placing a competing implicit conversion in scope, because your Map is also an Int => String.  And for whatever reason it's not ambiguous - the val is preferred over the def I guess.

This is what I still find strange. I wish I had gotten a compilation error informing me of the ambiguity.

Thanks for your answer, Paul. Now that I understand what is happening, I will manage to work around the ambiguity.

Best regards,

Bruno

[Paolo Giarrusso]

Il giorno venerdì 3 agosto 2012 13:48:16 UTC+2, Bruno ha scritto:

Someone asked me recently why I'm against extending Function1 casually.  In this we have a pretty good example.  I'm not sure why you declared the map to be an implicit val:

  implicit val cache = mutable.Map[Int, String]()

Originally (and also in my real code) "cache" was passed as an implicit argument to the implicit "intToString" conversion, as follows.

implicit def intToString(p: Int)(implicit cache: Map[Int, String]): String = cache.getOrElseUpdate(p, "number " + p.toString + " !" )

I would say that passing a Map implicitly is quite debatable. The moment some other module imports your code and does the same thing, you get either an ambiguity or undesirable behavior. In fact, that's exactly what is happening in your code: you have a location which needs an implicit of function type, which happens to include Maps.

Also, in this example you could simply access the cache directly; I will assume that in your real code you have some reason against that.

I see two patterns of using implicit parameters:

(1) in cases like this, declare a wrapper class:

case class MyCache(cache: Map[Int, String])

//extends AnyVal //Since 2.10, you can add this clause to remove the performance overhead due to the wrapping.

And make the implicits have this type:

implicit def intToString(p: Int)(implicit cache: MyCache)

implicit val cache: MyCache = MyCache(MMap())

This way, intToString will only receive implicits intended for it. You can't make sure that every implicit Map[Int, String] is a valid parameter, but you can ensure that every implicit MyCache is a valid parameter.

As a bonus, such a pattern will prevent your cache being used as a function.

(2) The other pattern, which does not apply here, is the one used for Numeric[T], Ordering[T], CanBuildFrom[From, Elem, To] and so on. An implicit parameter of type Foo[T] (say, Ordering[T]) defines some operation on type T. Often, for each T there's a single implicit instance of the given type (in our example, Ordering[T]), although you can build other non-implicit instances and pass them explicitly.

 

I imagine you didn't do that with the intention of placing a competing implicit conversion in scope, because your Map is also an Int => String.  And for whatever reason it's not ambiguous - the val is preferred over the def I guess.

Paul, the fact you're confused worries me. First because I can't find any val-vs-def precedence rule around (http://stackoverflow.com/questions/5598085/where-does-scala-look-for-implicits or ScalaReference); second because why would such a rule be useful?

I guess the situation is sane just because Map[Int, String] <: Int => String, so that cache wins because it has a more specific type (a rule which usually _does_ make sense). Bruno, this seems enough to explain why you didn't get an error about ambiguity.

This is what I still find strange. I wish I had gotten a compilation error informing me of the ambiguity.

 

Best regards

[Paul Phillips]

On Fri, Aug 3, 2012 at 3:45 PM, Paolo Giarrusso <p.gia...@gmail.com> wrote:

Paul, the fact you're confused worries me. First because I can't find any val-vs-def precedence rule around (http://stackoverflow.com/questions/5598085/where-does-scala-look-for-implicits or ScalaReference); second because why would such a rule be useful?

I guess the situation is sane just because Map[Int, String] <: Int => String, so that cache wins because it has a more specific type (a rule which usually _does_ make sense). Bruno, this seems enough to explain why you didn't get an error about ambiguity.

It is a good explanation, but it doesn't seem to be the actual reason.  In the following f1 and f2 are not ambiguous.  The overload of g1 is ambiguous.  I thought overloading rules were how one resolved the implicit, but if so, it's in some other way than the way I read it.

object Test {

  implicit val f1: String => Int = _ => 1

  implicit def f2(s: String): Int = 2

  

  val g1: String => Int = _ => 1

  def g1(s: String): Int = 2

  // ./a.scala:10: error: ambiguous reference to overloaded definition,

  // both method g1 in object Test of type (s: String)Int

  // and  value g1 in object Test of type => String => Int

  // match argument types (String) and expected result type Any

  //     println(g1(""))

  //             ^

  // one error found

  

  def main(args: Array[String]): Unit = {

    println(implicitly[String => Int] apply "")

    println(g1(""))

  }

}

[Paolo Giarrusso]

Il giorno giovedì 2 agosto 2012 23:53:41 UTC+2, Paul Phillips ha scritto:

[Redirected to scala-language since I'm not on scala-user.]

Someone asked me recently why I'm against extending Function1 casually.  In this we have a pretty good example.

Isn't this example only valid if you have _implicits_ of type Foo with Foo <: Function1? For that case the example is enlightening, but in general, I don't think one should pass implicitly Maps or Sets (both extending Function1) or most other types, for which the specific value passed is not boilerplate.

Instead, the fact that Map extends Function1 allows to reuse function-oriented abstractions on Map:

def translate[T, U](s: Traversable[T], translatorMap: Map[T, U]) = otherSteps(s map translatorMap)

I'm pretty sure better examples exist. And allowing this kind of abstraction is typical of functional programming - or at least, of functional programming as done in Haskell. The difference there is that you don't limit yourself to functions, but you extend the same kind of reasoning to other mathematical abstractions like monoids, monads, and all other esoteric concepts. The usual counterargument there is that they are esoteric - but surely this doesn't apply to Function1.

Best regards

[Paolo Giarrusso]

Il giorno sabato 4 agosto 2012 00:57:35 UTC+2, Paul Phillips ha scritto:

On Fri, Aug 3, 2012 at 3:45 PM, Paolo Giarrusso <p.gia...@gmail.com> wrote:

Paul, the fact you're confused worries me. First because I can't find any val-vs-def precedence rule around (http://stackoverflow.com/questions/5598085/where-does-scala-look-for-implicits or ScalaReference); second because why would such a rule be useful?

I guess the situation is sane just because Map[Int, String] <: Int => String, so that cache wins because it has a more specific type (a rule which usually _does_ make sense). Bruno, this seems enough to explain why you didn't get an error about ambiguity.

It is a good explanation, but it doesn't seem to be the actual reason.  In the following f1 and f2 are not ambiguous.  The overload of g1 is ambiguous.  I thought overloading rules were how one resolved the implicit, but if so, it's in some other way than the way I read it.

 

Whenever Scalac confuses you on such simple things, I guess it scares all of us mere mortals - it sure scares me.

I'm not opening a bug report because I remember such a discussion already, but I can't find it so easily. Except that in this comment, Martin Odersky himself confirms that such a behavior was not expected, when he talks about "the spec, which treats fields and parameterless methods the same":

https://issues.scala-lang.org/browse/SI-5354?focusedCommentId=55703#comment-55703

Later, he said that the behavior does not arise, but your example shows otherwise for both 2.9.1 and 2.10.0-M6.

He then explains that changing such behavior might be dangerous and break existing code. I would consider adding some kind of migration warning before changing the behavior, for any code which currently compiles.

Should I open the bug report, or do you prefer to open it yourself?

If this is still relevant, beyond Daniel Sobral's StackOverflow answer I linked earlier, I've looked for this also in Josh Suereth's presentation, finding nothing. And of course I've re-read the SLS.

http://suereth.blogspot.de/2011/02/slides-for-todays-nescala-talk.html

Best regards

[Paul Phillips]

On Fri, Aug 3, 2012 at 4:10 PM, Paolo Giarrusso <p.gia...@gmail.com> wrote:

Instead, the fact that Map extends Function1 allows to reuse function-oriented abstractions on Map:

No, one can already do that.  What Map extending Function1 accomplishes is to make it impossible not to reuse function orientation, whether one wishes it or not.

implicit def mapIsFunction1[K, V](map: Map[K, V]): K => V = x => map(x)

[Jason Zaugg]

On Sat, Aug 4, 2012 at 1:46 AM, Paolo Giarrusso <p.gia...@gmail.com> wrote:
> I'm not opening a bug report because I remember such a discussion already,
> but I can't find it so easily. Except that in this comment, Martin Odersky
> himself confirms that such a behavior was not expected, when he talks about
> "the spec, which treats fields and parameterless methods the same":
>
> https://issues.scala-lang.org/browse/SI-5354?focusedCommentId=55703#comment-55703

Normal overload resolution [1] uses `followApply` before comparing the
candidates; this means that it compares two MethodTypes: Test.f2 and
Function1[String, Int]#apply.

Implicit resolution [2] doesn't call `followApply, so it compares the
MethodType Test.f2 against the the result type of the nullary method,
Function1[String, Int]. This falls through the checks in
`Infer.isApplicable`.

There is a reason for the different treatment: Implicit application
should only call the apply method of a Function1 (this is expressed in
`Implicits#checkCompatibility`.) The REPL would explain it this way:

scala> implicit val foo = new { def apply(x: Int): String = ""}
foo: Object{def apply(x: Int): String} = $anon$1@50608423

scala> 1: String
<console>:12: error: type mismatch;
found : Int(1)
required: String
1: String
^

scala> foo(1)
res11: String = ""

I'd classify this as a bug. Implicit resolution should use something
like followFunction1Apply.

-jason

[1] https://github.com/scala/scala/blob/4e437f7/src/compiler/scala/tools/nsc/typechecker/Infer.scala#L1683

[1] https://github.com/scala/scala/blob/4e437f7/src/compiler/scala/tools/nsc/typechecker/Implicits.scala#L310

[Alex Cruise]

On Fri, Aug 3, 2012 at 4:56 PM, Paul Phillips <pa...@improving.org> wrote:
> No, one can already do that. What Map extending Function1 accomplishes is
> to make it impossible not to reuse function orientation, whether one wishes
> it or not.
>
> implicit def mapIsFunction1[K, V](map: Map[K, V]): K => V = x => map(x)

I don't recall any debate about removing Function1-ness from Map and
Set... If there hasn't been any yet, it seems worthy of discussion.

Personally, I use the Function1-ness of Set all the time, and of Map
less often, but I would be fine if I had to call .toFunction or
somesuch to grease the skids, if the inheritance is problematic.

This seems like it would be a good use for something akin to Simon's
@deprecatedInheritance idea... Map isn't going anywhere, but anyone
who uses a Map as-a Function1 should maybe get a warning.

Can annotations refer to types? e.g. @(deprecated @usageAsA[Function1])

-0xe1a

[Paul Phillips]

On Sat, Aug 4, 2012 at 8:36 AM, Alex Cruise <al...@cluonflux.com> wrote:

Can annotations refer to types?

They can - it is a powerful and as yet almost completely unexploited capability.

[√iktor Ҡlang]

Use CanBuildFrom and use the new .to[Function]?

Cheers,
V

[Paolo Giarrusso]

Martin Odersky already classified that behavior as a bug; in his
subsequent comment, he retracted, but it seems that it might be just
because there was _another_ bug hiding this in the specific example.
Anyway, the point is that it's a bug that might require special
attention. Can it be fixed in 2.10, or would the current behavior
require longer-term support?

Cheers,
Paolo

>
> -jason
>
> [1] https://github.com/scala/scala/blob/4e437f7/src/compiler/scala/tools/nsc/typechecker/Infer.scala#L1683
>
> [1] https://github.com/scala/scala/blob/4e437f7/src/compiler/scala/tools/nsc/typechecker/Implicits.scala#L310

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

[Jason Zaugg]

On Sun, Aug 5, 2012 at 3:27 AM, Paolo Giarrusso
<pgiar...@mathematik.uni-marburg.de>

>> Normal overload resolution [1] uses `followApply` before comparing the
>> candidates; this means that it compares two MethodTypes: Test.f2 and
>> Function1[String, Int]#apply.
>>
>> Implicit resolution [2] doesn't call `followApply, so it compares the
>> MethodType Test.f2 against the the result type of the nullary method,
>> Function1[String, Int]. This falls through the checks in
>> `Infer.isApplicable`.

>> I'd classify this as a bug. Implicit resolution should use something
>> like followFunction1Apply.
>
> Martin Odersky already classified that behavior as a bug; in his
> subsequent comment, he retracted, but it seems that it might be just
> because there was _another_ bug hiding this in the specific example.
> Anyway, the point is that it's a bug that might require special
> attention. Can it be fixed in 2.10, or would the current behavior
> require longer-term support?

As I see it, both implicit and explicit use of static overload
resolution between methods and nullary methods returning function
types is implementation specific and not covered by the specification.
The safest course of action is to avoid using it.

-jason

[Chris Marshall]

If function1-ness is being removed from Map/Set, you just broke all my Spring configured apps :-(

For example:

class TradeReporter(val mktsFilter: Market => Boolean)

Then:

<bean class="TradeReporter">
<constructor-arg>
<scala:set type="Market">
<entry>Nasdaq</entry>
<entry>NYSE</entry>
</scala:set>
</constructor-arg>
</bean>

Just because a change might theoretically not break existing code does not mean it doesn't break existing programs

Chris

[Bruno]

Thanks, Paolo!

[Paolo Giarrusso]

While I also would like this bug fixed, even though it doesn't bite me
especially, Scala seems to try to guarantee source compatibility by
using deprecation, and some people rely on it. Those people would also
probably like if Scala had a fixed policy up-front for these
decisions, to know what to expect. In other words, I think that having
a uniform policy for source compatibility is important.

Relying on this behavior _intentionally_ is clearly fragile. Instead
of relying on this, to force priorities it's better to follow the
LowPriorityImplicits pattern - so it doesn't seem even a clever
undocumented trick.
But as long as (say) type inference is (de facto) not spec'ed, there
is a lot of implementation-specific behavior one has to rely on,
intentionally and knowingly or not.

In this case, one can define an implicit val which should be ambiguous
but isn't, because another implicit is also imported in scope. In the
following example, if Other were part of some library and I defined
'implicit val f1: ...", I could easily miss the ambiguity. And the
example 'structure' seems quite plausible (see below). I'm not sure
how much source compatibility to expect from Scalac, and I personally
can live with what we have, but some people don't.

object Other {

implicit def f2(s: String): Int = 2
}

object Test {
import Other._

//Preferred:
//implicit val f1: String => Int = _ => 1
//Also preferred - you said so correctly, but the initial hypothesis
was in terms of val vs methods, so I was surprised.
//implicit def f1: String => Int = _ => 1
//With the change, the two above definitions would behave as the
following one - which is ambiguous:
implicit def f1(a: String): Int = 1

println(implicitly[String => Int] apply "")
}

<console>:18: error: ambiguous implicit values:
both method f1 in object Test of type (a: String)Int
and method f2 in object Other of type (s: String)Int
match expected type String => Int

println(implicitly[String => Int] apply "")

You could wonder why would I feel like writing f1 when f2 exists, one
can consider convoluted but realistic scenarios with evolution of
components.
For instance, we can assume that the author of Other didn't write f2,
the author of Test writes f1 and asks the library author to include it
and he does, but using a unary method.

Cheers