Author Archives: david

An introduction to implicit arguments

SBinary and Scalacheck are part of a small set of libraries that make extensive use of implicit arguments in a style very reminiscient of Haskell type classes. I’m hoping this style of programming will get more common in Scala – it’s a really useful technique and, in my completely unbiased opinion, both SBinary and Scalacheck are fantastic and you absolutely should use them. :-) But in order to do so you need to really understand how implicit arguments in Scala work.

This post is actually for work, as we’re using Scala there and this is a subject which has been confusing one of my colleagues.

As a starting point, in Scala you can declare a method to have multiple argument lists. This isn’t a fantastically useful feature, but here’s how it works:

scala> def foo(x : Int)(y : Int)
     | = x + y
foo: (Int)(Int)Int

scala> foo(1)(2);
res1: Int = 3

scala> foo(1, 2);
:6: error: wrong number of arguments for method foo: (Int)(Int)Int
       foo(1, 2);
       ^

scala> foo(1)
:6: error: missing arguments for method foo in object $iw;
follow this method with `_' if you want to treat it as a partially applied funct
ion
       foo(1)
       ^

i.e. “exactly the same as a single method parameter list but you have to use a different syntax for calling it”. Hurray.

This has one advantage though. You can declare the last parameter list of a function to be implicit. The syntax for this works as follows:

scala> def speakImplicitly (implicit greeting : String) = println(greeting)
speakImplicitly: (implicit String)Unit

scala> speakImplicitly("Goodbye world")
Goodbye world

scala> speakImplicitly
:6: error: no implicit argument matching parameter type String was foud.

scala> implicit val hello = "Hello world"
hello: java.lang.String = Hello world

scala> speakImplicitly
Hello world

So, we can call this as normal but, additionally, we can leave out the implicit argument list and the compiler will look for a value in the enclosing scope which has been marked as implicit. If we try to do that and there is no such value in scope then the compiler will complain.

Matching implicit arguments

Implicits are totally typesafe, and are selected based on the static type of the arguments. Here are some examples to show how things work.

Implicits of the wrong type

scala> def speakImplicitly (implicit greeting : String) = println(greeting)
speakImplicitly: (implicit String)Unit

scala> implicit val aUnit = ();
aUnit: Unit = ()

scala> speakImplicitly
:7: error: no implicit argument matching parameter type String was found.

Only an implicit of type String will be selected for an implicit argument of type String.

Implicits of the wrong static type

scala> def speakImplicitly (implicit greeting : String) = println(greeting)
speakImplicitly: (implicit String)Unit

scala> implicit val hello : Any = "Hello world"
hello: Any = Hello world

scala> speakImplicitly
:7: error: no implicit argument matching parameter type String was found.

Implicit selection happens on the *static* type of variables. It’s no use having something of the right dynamic type if the variable isn’t typed accordingly.

scala> def speakImplicitly (implicit greeting : String) = println(greeting)
speakImplicitly: (implicit String)Unit

scala> implicit val foo = "foo";
foo: java.lang.String = foo

scala> implicit val bar = "bar";
bar: java.lang.String = bar

scala> speakImplicitly
:9: error: ambiguous implicit values:
 both value bar in object $iw of type => java.lang.String
 and value foo in object $iw of type => java.lang.String
 match expected type String

If there are multiple implicit arguments of the same type, it will fail as it has no way of choosing between them. But…

Implicit arguments of subtypes

scala> def sayThings (implicit args : List[Any]) = args.foreach(println(_))
sayThings: (implicit List[Any])Unit

scala> implicit val nothingNiceToSay : List[Any] = Nil
nothingNiceToSay: List[Any] = List()

scala> sayThings

scala> implicit val hellos : List[String] = List("Hello world");
hellos: List[String] = List(Hello world)

scala> sayThings
Hello world

If you have an implicit argument of a subtype, it will also match as an implicit argument of this type. Moreover, if you have two implicit arguments which match and one is a subtype of the other, the more specific type will match.

Parameterized implicits

scala> def implicitly[T](implicit t : T) = t
implicitly: [T](implicit T)T

scala> implicit val foo = "foo"
foo: java.lang.String = foo

scala> implicit val aUnit = ()
aUnit: Unit = ()

scala> implicitly[String]
res2: String = foo

scala> implicitly[Unit]

Type parameters can quite happily take part in the implicits mechanism.

Defining implicit arguments

So, we know how to use defined implicit arguments now. But how can we define them? We’ve seen one way:

implicit val foo = "foo";

scala> implicitly[String]
res2: String = foo

If this was all we could do then it wouldn’t be that powerful a feature. A nice to have, but ultimately not *that* exciting. Fortunately there are a few more things we can do. For starters, Scala has the uniform access principle, so any (wait, no. That would be too general. We can’t have features without special cases. Sigh. Ok, let’s say most) things you can do with a val you can do with a def

implicit def foo = "foo"

scala> implicitly[String]
res2: String = foo

This def will be invoked each time we want the implicit. Here’s an example to demonstrate this

scala> implicit def aUnit : Unit = println("Hello world")
aUnit: Unit

scala> implicitly[Unit]
Hello world

scala> implicitly[Unit]
Hello world

scala> implicitly[Unit]
Hello world

In general, implicit defs shouldn’t have side effects. It can lead to some really counterintuitive behaviour. This is just for demonstration purposes.

Now, the ability to use defs opens up a bunch of possibilities. For example, they can have type parameters:

scala> implicit def emptyList[T] : List[T] = Nil;
emptyList: [T]List[T]

scala> implicitly[List[String]]
res9: List[String] = List(Hello world)
// Oops, we still had an implicit List[String] left over from an earlier example. Note how that was used in preference to the parameterized version. Let's try again.

scala> implicitly[List[Int]]
res10: List[Int] = List()

Moreover, implicit defs used in this way can themselves have implicit parameters. For example:

scala> case class Foo[T](t : T);
defined class Foo

scala> implicit val hello = "Hello"
hello: java.lang.String = Hello

scala> implicit def foo[T](implicit t : T) = Foo[T](t)
foo: [T](T)Foo[T]

scala> implicitly[Foo[String]]
res3: Foo[String] = Foo(Hello)

(Note: I originally tried to write this example with Option. It turns out there’s a bug with how covariant types are handled which made it not work)

The basic idea is that anything marked as implicit which you could write as a single identifier (possibly with a type signature to handhold the type inference system) is valid to be passed as an implicit argument.

Existential types in Scala

With 2.7 of Scala on the way, people are being exposed to Java wildcards more and more, which translate to Scala existential types. Unfortunately no one seems to understand these (including me at first!) and had previously let them go largely ignored, and now everyone is getting confused.

Here’s a brief introduction.

scala> def foo(x : Array[Any]) = println(x.length);
foo: (Array[Any])Unit

scala> foo(Array[String]("foo", "bar", "baz"))
:6: error: type mismatch;
 found   : Array[String]
 required: Array[Any]
       foo(Array[String]("foo", "bar", "baz"))

This doesn’t compile, because an Array[String] is not an Array[Any]. You can put 1 into an Array[Any], but not into an Array[String]. Nonetheless, it’s completely typesafe – we’ve only used methods in foo which would work for any Array[T]. How do we fix this?

Here’s one way:

scala> def foo[T](x : Array[T]) = println(x.length)
foo: [T](Array[T])Unit

scala>> foo(Array[String]("foo", "bar", "baz"))
3

We’ve parameterised the method by T in order to make it accept any T. But now we have a superfluous type parameter on our method. This may not seem like a big deal, and it’s usually not, but it can add up if you’re not careful (and can be particularly annoying when for some reason the type checker is no longer able to infer a single one of your type parameters and you have to supply all of them). It’s also not really what we mean – we mean “I want an Array, and I don’t care what type of things it contains”

This is exactly what existential types are for.

scala> def foo(x : Array[T] forSome { type T}) = println(x.length)
foo: (Array[T] forSome { type T })Unit

scala> foo(Array[String]("foo", "bar", "baz"))
3

This is quite verbose, I know. There’s a shorthand, Array[_], but this has some unfortunate unintuitive behaviour. I’ll explain this later.

Sometimes we want to act on a more specific type, but don’t care exactly what type it is. For example suppose we wanted this to work on any CharSequence and do something more complicated to each argument. e.g.

scala> def foo(x : Array[T] forSome { type T <: CharSequence}) = x.foreach(y => println(y.length))
foo: (Array[T] forSome { type T <: java.lang.CharSequence })Unit

scala> foo(Array[String]("foo", "bar", "baz"))
3
3
3

The type arguments in an existential type can have upper and lower bounds like normal type declarations. They can't have view bounds, presumably due to technical limitations.

So we've seen how these are used, and that was relatively nonconfusing (I hope!). Let's pin down exactly what these mean.

Suppose we have a type constructor M. In other words, for a type T, M[T] is a type, but M is *not* itself a type. M could be List, Array, Class, etc. M[T] forSome { type T; } is the type of all things for which there is some T such that they are of type M[T]. So an Array[String] is of this type, because we can choose T = String, as is an Array[Int], etc.

If we add bounds, all we do is restrict the range that T can lie in. An Array[String] is not an Array[T] forSome { type T <: Number; } because the only possible choice of T (String) is not a subtype of Number

Now, all you need to do in order to understand a given existential type declaration is to apply this rule rigorously. But this can be hard, especially because precedence matters in subtle ways! I'll walk you through some examples.

T forSome { type T; }

This is the type of all things for which there exists some T such they are T. Wha?

Think about it for a second. It's the type of all things for which there exists a type such that they are of that type. i.e. it's a long winded way of writing the type of all things, Any. This is important, and it often trips people up when they write subtly the wrong thing. Considering the following two types:

Array[T] forSome { type T; }
Array[T forSome { type T; }]

They look almost identical, but they're in fact very different. The first is the type of all arrays, whatever their type parameter. The second is Array[Any]

Let's take another example, because this is the one which seems to come up a lot. We have a Map. We want it to map classes to something. Let's say Strings. What type do we use?

Here. Pick one:

Map[Class[T forSome { type T}], String]
Map[Class[T] forSome { type T}, String]
Map[Class[T], String] forSome { type T}

Which did you pick?

The correct answer is "Map[Class[T] forSome { type T}, String]", or to save you searching for ]s, "the middle one".

Why? Well, the first one is a Map[Class[Any], String]. Class is invariant in its type parameters. So the only Class[Any] is in fact classOf[Any] (this is basically the same as Object.class in Java). So that's not very useful. Similarily, the third one is the supertype of all map types such that there is some T such that they are a Map[Class[T], String]. So again, we've got some fixed class type for keys in the map - it's just that this time we don't know what type it is. The middle one however has keys of type Class[T] forSome { type T }. That is, its keys are classes which are allowed to have any value they want for their type parameter. So this is what we actually wanted.

Now, the final confusing point. As I mentioned, we have this shorthand use of _ for wildcards. So we can write Array[_] to mean Array[T] forSome { type T}. That's nice. So what happens if we try to use this in the above and write Map[Class[_], String]? It turns out, we get "Map[Class[T], String] forSome { type T}". The wildcards always bind to the outermost level of the type expression. This is, unfortunately, almost never what you want in cases where it affects anything. There's been some discussion about changing it. I don't know if it will go anywhere.

Anyway, hopefully this has made some sense of things for you. It's a really confusing subject when you first encounter it, but once you've got it straight in your head it's not too bad. It would be nice if it could be simpler, but I'm not really sure what the best way to do this actually would be.

Formatting

I finally got sick of how much damage Blogger was doing to my posts with the excess of <br> tags it randomly felt like inserting, so I’ve turned it off. Unfortunately this appears to republish all existing posts. Sigh. So the formatting of old posts is going to look like crap. I’ll fix recent ones, and incrementally go around fixing older ones, but most of them will remain like that.

Open source project breakdown.

I realised today that I actually have a fairly large number of open source projects published online (all on google code. Another thing I realised is that I should fix that).

I also realised that some of these are totally defunct.

I thought this would be a good time to do a quick breakdown of them, explaining what’s there, what they do and what their current status is.

JTypebuilder

Code generator for creating immutable data structures in Java. The idea was to define simple datatypes with a record notation and get an immutable class from them with correct equality, hash code and toString implementations, getters for the properties and a builder class for generating instances.

Status: Very very dead. It was at best a weak idea, and I have no interest in pursuing it. Use Scala’s case classes instead.

Generators4j

A brief foray into functional programming in Java. Lazy generators with functions like map, filter, etc.

Status: So dead. I didn’t get very far before concluding that trying to do this in Java was unusably awful.

Lazy Strings

Experiments in efficient representation of String types, with the aim being to provide a drop in replacement for java.lang.String with a different set of performance characteristics. Started in Java, moved to Scala.

Status: Just resting its eyes. I’m not doing much with this at the moment, but I occasionally peek at it and will probably factor out some of the ideas and turn it into a more tightly focused library.

Ranged Types

Very small Scala library for statically checked numeric ranges.

Status: Awaiting a use case. I occasionally think about picking it up again, but then I wonder why. It’s a fun idea, but I don’t actually have anything I need to use it for and as far as I can tell neither does anyone else.

SBinary

A small library for binary serialization and deserialization of Scala data types, based on Haskell’s Data.Binary.

Status: Very much alive. I’ve just released version 0.1 RC1, am using it as a dependency in other things and am continuing to tinker with it to improve its usability.

Prefer Scala

A wrapper around the Java preferences API designed to be nicer to use from within Scala and support a wider variety of preferences in a typesafe way. Uses SBinary to serialize Scala types to and from the preference backing store. It’s been factored out of the code for Hector’s Reminder Service.

Status: Fledgling. I’ve only just released it. It’s very small, and I intend it to remain so, so I expect to push it towards a 1.0 fairly quickly and then have it enter maintenance mode where future updates are just to fix bugs and bring it into line with the latest versions of its dependencies.

Hector’s Reminder Service

Unlike the other ones, this one is an application. It’s a small cross platform status bar application based on QT which gives you reminder messages on a semi-regular basis. Designed to be unobtrusive and simple and intended for the occasional casual reminder rather than of specific events. Uses “Prefer Scala” for persisting of state between application runs.

Status: Again, quite recent. I have a semi-official version released which works and more or less does what I want. I’m intending to polish that, add a very small number of new features (currently planned are a more expressive way of specifying message intervals, the ability to temporarily suppress a message group and possibly a simple API for other programs to interact with him) and then declare it to be feature complete. Once it’s reached that point it will enter a similar state of “Updates are only to fix bugs and match new dependency versions”.

Hector’s Reminder Service: QT Jambi and Scala

Well, I spent a lot of today putting together the application I mentioned in my recent rant.

The program is called “Hector’s Reminder Service”. Basically it’s a taskbar reminder app. You specify a random lists of messages and their approximate frequency. It gives a little notification message (not a popup window!) on the task bar showing one of those messages about that often. You can configure as many different groups of messages as you like and they’ll be scheduled independently.

The code is available here. It’s GPLed, mostly because it depends on QT and I couldn’t be bothered to figure out the ramifications. Anything I consider reusable will be factored out into a library and released under a more moderate license. I have a few more things to sort out with it (mainly packaging) and will then release a version 0.1 of it.

Currently there’s no packaging system set up. If you want to build this you’ll need QT Jambi installed – both for the user interface file compiler and for the native libraries. It’s currently untested on anything except windows, but now that I’ve given up on Swing and switched to QT I expect it should by and large work on OSX or any X-windows setup with a compliant toolbar. No doubt there will be problems, but they should be surmountable. Give me a shout if you do want to build it and discover it doesn’t work on your platform. I’ll do my best to help.

Edit: Actually, unless you’re feeling brave you probably don’t want to build this. It depends on having Scala 2.7 and jerbil installed as well as the QT Jambi libraries. You can download a prebuilt version from http://hectorreminder.googlecode.com/files/hector.zip , but you’ll still need the QT Jambi libraries installed.

Edit 2: I can confirm that Hector does work properly under linux. You need to replace the qtjambi.jar in the lib directory with the one from your jambi install (turns out that’s windows specific. Oops). Other than that he works perfectly.

David R. MacIver