Well, I've been meaning to set up a site of my own for ages. I finally got around to it. I can now be found at http://www.drmaciver.com/
This blog will be moving to the "programming" category there. I'll update the various aggregator sites that have it on to point there instead.
I came up with a neat idea for changing the syntax for call by name parameters recently (it turned out that it's actually a reversion to an older syntax for it! The new one was there to resolve some problems, but I like the old syntax better so would rather resolve those problems directly). In the discussion of this some problems were pointed out and the feature list sortof spiralled out of control and collided head on with a previous proposal by Andrew Foggin. Here's a summary of the current state of the proposal.
This is kinda a "Well, duh" moment. It's obvious in retrospect, but I completely failed to spot it up front, so I thought I'd share.
I noticed that SBinary performance really really sucked. We're using it at work for saving application state, and reading and writing a file of only 900kb took about two seconds! This was bad.
Some quick performance testing suggested that this was almost entirely IO bound. Reading and writing the corresponding amount of data from a byte array took fairly little time - only about 200ms for writing, 300ms for reading. So, what was I doing wrong?
After a few seconds of head scratching I realised the problem. You see, RandomAccessFile implements the DataInput and DataOutput interfaces. This is useful for small things, but for doing non-trivial binary input and output? Not so much.
The problem is that the reads and writes for these implementations are totally unbuffered. This should have been obvious, but for some reason didn't occur to me. Oops. I'm now buffering reads and writes explicitly (currently in a pretty stupid way, but oh well). It's a lot faster now.
I'm thinking about changing the scope of some of the code for SBinary.
Specifically, you remember that part where I said "SBinary is only for serializing objects and manipulating binary data, and it's going to remain super minimal and specialised and this will never ever change!!"? I'm thinking of changing that. :-)
The reason for this change of heart is that I'm realising how incredibly generic the constructions you put together for SBinary are. You're basically creating a walker for deconstructing and reconstructing your entire object graph. That's pretty damn powerful. In particular I was thinking about how to modify formats to permit sharing (another post on that will be forthcoming) and suddenly thought "haaang on a minute. I've written this code before". It looks suspiciously identical to some Java code I wrote a while back for generic cloning of object graphs*. A simple rebinding of the backend to use a queue of objects rather than input and output streams would give a pretty efficient deep clone mechanism. I've also been thinking of creating a JCR backend which mostly works the same as the binary data (indeed, most data would probably be stored as binary blobs in the JCR), but allows for references to other nodes (and would use this for data sharing).
At the very least, this will result in ditching the explicit dependency on java.io. It will still be used extensively in the back end, but this is only visible in the API for the parts that actually need to interact with it. (most likely approach - have an Input and Output opaque type to replace DataInput and DataOutput. These will just be wrappers around the java.io types, but this won't be visible at first)
If I do do something like this, it would still be with making binary data the priority, and there would definitely be a specialised binary frontend which should be just as convenient as the current API. If it ever looks like feature creep is threatening to destroy that I'll separate out projects and/or cut out the idea entirely.
* In the unlikely event that anyone who worked on that project actually reads this blog, they will probably shudder in horror at the mention of that code. It was very fragile with regards to changes in the rest of the code. But that wasn't actually an issue with the cloning - it was an issue with the post-clone processing. The graph was of database mapped objects and it needed to be partially linearised in order to insert it back into the database due to constraint issues, and this never really worked right.
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.
Implicits are totally typesafe, and are selected based on the static type of the arguments. Here are some examples to show how things work.
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.
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...
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.
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.
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.
This should provide enough to get you started. Your next step should probably be to check out the documentation for Scalacheck and SBinary (the latter of which is... less than stellar at the moment. I'll fix that, I promise. :-)). If you're looking for some slightly more hardcore reading, Generics of a Higher Kind has some interesting examples. Other than that, the best thing to do is play with some code.
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.