Monthly Archives: March 2006

Match

When I first heard about Scala, the very first thing I did was find the specification and look up the details of pattern matching. I’m a big fan of pattern matching, something I apparently share with Martin Odersky, and I wanted to see if Scala used the same model as his previous language, Pizza. Unfortunately it does as far as I can see. The reason I think it’s unfortunate is that I think there is a great potential in introducing pattern matching in an object-oriented language but I don’t think Scala’s model quite reaches that potential.

Before getting to Scala’s mechanism I’ll start off by explaining why I think pattern matching is something you would want to have in an object-oriented language. Conventional wisdom says that in an object-oriented language you’re not supposed to decide which action to take based on the type of other objects. Scott Meyers says in Effective C++:

Anytime you find yourself writing code of the form “if the object is of type T1, then do something, but if it’s of type T2, then do something else,” slap yourself.

Instead of dispatching on an object’s type, you should use polymorphism. This rule is a good first approximation, but it’s not the whole story. Sometimes you’re not in a position to add methods to other objects. And even if you are, adding methods can be a bad idea because it often means polluting other objects with methods that may be convenient for you but are completely irrelevant to the object itself and anyone else who might use it. Case in point: in Squeak the Object class has over 400 methods including isSketchMorph, playSoundNamed and, the winner by unanimous decision, hasModelYellowButtonMenuItems. Encapsulation? We don’t need no steenkin’ encapsulation!

This is where a pattern matching mechanism can be really useful. If you have a reasonably fixed set of object types that you want to operate on it gives you a structured, simple and readable way of distinguishing between objects. Unfortunately Scala’s model, and Pizza’s before it, imposes some limitations on the objects involved that make it unnecessarily difficult to use.

Scala’s pattern matching mechanism is pretty simple: you can declare a class as a case class, which enables you to match against it:

class Expr
case class Var(x: String) extends Expr
case class Apply(f: Expr, e: Expr) extends Expr
case class Lambda(x: String, e: Expr) extends Expr

Given an Expr object, or any object really, you can match it against these three cases like this:

val e: Expr = ...
e match {
case Var(x) => ...
case Apply(f, e) => ...
case Lambda(x, e) => ...
}

This looks very similar to functional-style pattern matching as in ML and Haskell.

The most important problem with this mechanism is that a case is bound to a particular class. The Var(x) case only matches instances of the Var class and its subclasses. It’s fine to dispatch based on whether or not an object implements a particular interface, because any class is free to declare that it implements that interface, and implement it however they want. Requiring classes to have a particular superclass, on the other hand, dictates how the class should be implemented which is a bad thing indeed.

Here’s an example of why that’s a problem. Let’s say I’m implementing a linear algebra library with various functions that act on points, lists, matrices, etc. I have a basic Point class:

case class Point(x: Int, y: Int) {
// All sorts of numerical methods
}

Let’s say that my library turns out to be a bit slow and after profiling it I discover that one point in particular is used a lot, (0, 0), and a lot of the algorithms can be simplified considerable in that case. So I make a separate Origin class which represents (0, 0) and has its own simplified implementations of all operations (here in an imaginary case-extension syntax):

class Origin extends Object case Point(0, 0) {
// Methods specialized for (0, 0)
}

In Scala you can’t do that — Origin must be a subclass of Point if it wants to match as a point. In this case extending Point means that Origin gets two fields and a lot of methods, none of which it is interested in using. Bugger.

The second problem is that the values in the pattern can not be computed, they are always read directly from the object. You might want to optimize the numerical library by making some operations lazy, so you have a LazyPoint which is just like a point except that it doesn’t calculate its coordinates until they are requested. Unfortunately you can’t: the coordinates are read through an accessor, which is generated for you, that simply returns the value of a variable. Double bugger.

The last problem is that once a class has declared that it’s a case, subclasses can’t change or override that. An example from the post about equality was the class LinePosition, which represents a position corresponding to a particular line in a text file. A subclass of this class was CharacterPosition, which not only specifies the line in the file but also a particular character within that line. I would probably want LinePosition to match LinePosition(line: Int) and CharacterPosition to match CharacterPosition(line: Int, char: Int). Unfortunately I can’t because if one is a subclass of the other then they must match the same pattern. In this case, CharacterPosition must match as LinePosition(line: Int). Triple bugger.

The conclusion here is that if I use case classes and pattern matching I’ve put a lot of restrictions on the way I can implement my classes. If I was to implement the linear algebra library I mentioned above and use pattern matching to distinguish between points, lists and matrices, I’ve severely limited the freedom to decide how to actually implement these objects. And the limitations are especially uncomfortable because they dictate how you should implement your objects: that superclass must be a particular class and that the internal state of the object, or at least part of it must be readable directly from variables.

What I’m saying is not that I think pattern matching in Scala was poorly designed — it’s more that I’m probably trying to use it to solve a problem it probably wasn’t designed to solve. But I don’t think it’s a fundamental problem with pattern matching. So without further stalling, here’s my suggestion for an alternative semantics that is much less restrictive.

There is already a well-known way to dispatch on the type of an object: the visitor design pattern. When you pattern match an object, you shouldn’t inspect the object “from the outside” to select the right case, you should instead let the object itself select the right case using double dispatch. If you were to write a double-dispatch version of the lambda example from before, without any syntactic sugar, the code would look something like this:

class Expr
class Var (x: String) extends Expr {
def match(m: Matcher) = m.var(x)
}
class Apply (f: Expr, e: Expr) extends Expr {
def match(m: Matcher) = m.apply(f, e)
}
class Lambda(x: String, e: Expr) extends Expr {
def match(m: Matcher) = m.lambda(x, e)
}

and a match expression would expand into something like:

val e: Expr = ...
e.match(new {
def var(x) = ...
def apply(f, e) = ...
def lambda(x, e) = ...
})

The match expression is packed into a Matcher object which is really a mini-visitor. The matcher is then given to the to the object being matched which calls back to select the case to match. Note that I’m not suggesting that you write the code like that. In simple cases the same syntax could be used as in Scala, in more complex cases you might need a more general syntax but I haven’t quite thought that through.

Using visitor-pattern-matching an object has full control over what and how it “matches”. In the Origin example this means that an Origin object is free to implement its match method so that it matches as a point. It also means that the lazy point object is free to calculate the coordinates before calling back to the Matcher. Finally, CharacterPosition can override the match method so it is no longer forced to match as a LinePosition. Nice!

Of course there are problems. If you want to be able to have default cases that match if no other cases do, the matcher object must be able to handle calls to methods it doesn’t implement — sort of like the way smalltalk does with doesNotUnderstand. Another problem is that the extra flexibility enables objects to abuse the Matcher object for instance by matching more than once or not at all. Finally, you don’t want to use regular method names like point since that’s a flat namespace — instead you would use some form of qualified names. But none of these problems are very difficult to solve.

Bottom line: I think visitor-ifying the pattern matching mechanism in Scala would make it much more flexible and useful but still provide, as a special case, the current mechanism. And oh, I almost forgot, it can also be used to solve the equality problem that I described in an earlier post but that will have to wait.

Update: I discussed this with some people from the scala group and they managed to convince me that visitors are just not a realistic implementation strategy. Bugger!

Reputation

Clearly, the whole cartoon controversy has done a lot of damage to Denmark’s reputation in the muslim world. This clip from the Daily Show gives an indication of how other western countries have come to view Denmark. Towards the end Michael Mandelbaum says that the reason other countries don’t oppose the US more actively, however exasperated they may be, is that they need it to play the role it does, and no other country can play that role. Jon Stewart’s comment on that is:

And that, not forgetting that Denmark could be out there, could be watching us right now. Cause those people don’t give a [beep].

Scary.

Equals

I recently discovered that if you look closely at the seemingly simple problem of comparing objects for equality it’s actually very hard, if not impossible, to solve satisfactorily. I looked around a bit to see if this was a well-known issue and it turns out that I’m certainly not the first person to notice this problem. See for instance here and here. This post introduces the problem (or one of the problems) of implementing object equality methods.

I have a standard template for implementing the equals method in Java:

public class X ... {

// ... body of X ...

public boolean equals(final Object obj) {
if (this == obj) return true;
if (!(obj instanceof X)) return false;
final X that = (X) obj;
// X-specific comparison
}

}

Unfortunately it turns out that implementing equals using instanceof doesn’t work in general. Let’s say you have a class LinePosition which specifies a particular line in a text file. Two line positions are equal if they represent the same line:

public boolean equals(final Object obj) {
if (this == obj) return true;
if (!(obj instanceof LinePosition)) return false;
final LinePosition that = (LinePosition) obj;
return this.getLine() == that.getLine();
}

Now you might later want to create a subclass, CharacterPosition, which not only specifies a line but also a particular character in the line. Two character positions are equal if they specify the same line and the same character in that line:

public boolean equals(final Object obj) {
if (this == obj) return true;
if (!(obj instanceof CharacterPosition)) return false;
final CharacterPosition that = (CharacterPosition) obj;
return this.getLine() == that.getLine()
&& this.getCharacter() == that.getCharacter();
}

This might look reasonable but it doesn’t work: equals is required to be symmetric but in this case it isn’t:

final LinePosition a = new LinePosition(3)
final CharacterPosition b = new CharacterPosition(3, 5);
final boolean aIsB = a.equals(b); // true
final boolean bIsA = b.equals(a); // false

The problem is that b is more picky about who it considers itself to be equal to than a. Damn.

An alternative approach is to avoid instanceof and use getClass instead:

public boolean equals(final Object obj) {
if (this == obj) return true;
if (obj == null || obj.getClass() != this.getClass()) return false;
final X that = (X) obj;
// X-specific comparison
}

Using this technique to implement equals on the text position classes would cause a and b to be equally picky about who they considered themselves to be equal with so equals would be symmetric. Unfortunately, now the objects are so picky that they break Liskov Substitutability, which is a Bad Thing.

Here’s an example where that might hit you. Let’s say that during debugging you notice that instances of LinePosition turn up in places where you didn’t expect then. If I wanted to find out where these positions came from, I would probably make an empty subclass of LinePosition for each place where I instantiate them so each instantiation site uses its own class. That way, whenever I find a line position where I didn’t expect it, I can see where it was instantiated

But if equals has been implemented using class equality I can’t do that because even though I don’t change any methods, the behavior of my program has changed in a subtle way. One position can now only be equal to another position if they were created at the same place, which is very different from how the program behaved before. I’ve tried hunting bugs that occurred because a subclass behaved differently from superclasses merely because it had a different class. Bugs like that can be extremely evil because it’s so unexpected if your mind is warped the way object orientation usually warps people’s minds.

At the core, this problem is a question about when can you consider two objects to be of the same kind of objects. Having a common superclass does not imply that two objects are the same kind, as the LinePosition and CharacterPosition example demonstrates. On the other hand, sometimes objects should be considered to be of the same kind even if they have different classes. So how do you determine whether or not two objects should be considered to be the same kind of object? In Java, I don’t know. I think the getClass approach is the greater of two evils so I’ll probably keep doing things the way I’ve always done, using instanceof. Looking outside Java and java-like languages I have an idea for a solution using a mechanism that’s a combination of Scala-style pattern matching and the visitor design pattern. But that will be the subject of another post in the near future.

Hotswap

Gilad writes about JSR292 (Supporting Dynamically Typed Languages on the JavaTM Platform) and adding support in the JVM for updating a program’s code without stopping the program. Since hotswapping is part of the general “dynamically typed languages support” JSR, I guess the main focus is on the kind of updates required by a full implementation of languages like Python or Ruby, where a program can change the class of an object, add methods to a class, etc. In other words updates where a program itself changes its own structure.

What is most interesting to me in all this, though, is the kind of hotswapping that allows you to develop applications while they’re running, as demonstrated in this smalltalk screencast. When I spent a lot of time working on a particular corner of our IDE I tend to focus too much on the details and forget the big picture. Watching that video, I was reminded of what kind of system we should, and do, aim to make OSVM, and that’s probably the kind of interactive programming Gilad has in mind when he talks about how powerful and useful hotswapping is.

In my experience you don’t need full hotswapping for it to be useful. Eclipse, for instance, only supports relatively limited updates — all you can do, more or less, is change the implementation of existing methods. It is still very useful, though, and far preferable to always having to restart everything after every little change. Even if they fall short of a general solution, any steps they can take in the right direction will be great.

Wow, that sounded a lot like me being positive. That’s so unlike me.

Implementing support for this in OSVM was, to say the least, non-trivial. And our VM is not only very simple but was also designed with this kind of use in mind. As for implementing this in the JVM… as they say, good luck with that. But of course this JSR doesn’t have to be ready until Java SE 7 so they have a few years to get it done.

Fortran

I found an article at dusty decks about the original Fortran I compiler. This is interesting because the designers of the fortran compiler were the first to solve a whole bunch of interesting problems. Being a parser geek, I think their solution to operator precedence parsing especially neat.

The goal of operator precedence parsing is to take an expression such as

2 * x + y / 8

and group it according to a set of precedence rules such as “* and / bind tighter than +“, in this case producing

((2 * x) + (y / 8))

Today this problem is well-understood and there is a bunch of algorithms for solving it; the algorithm used in tedir is shift/reduce expression parsing. The fortran guys, on the other hand, had to solve this problem from scratch.

The way they did it was to scan through the expression and expand it in various places with a sequence of parentheses. In the simple case for a language with only +, -, / and *, the algorithm would do the following:

  • Insert (( at the beginning of the expression and )) at the end
  • For each + and - insert ))+(( and ))-(( respectively.
  • For each * and / insert )*( and )/( respectively.

And that’s it! Once the expression has been expanded using these rules it will be correctly parenthesized. For instance

  1. 2*x+y/8
  2. ((2*x+y/8
  3. ((2)*(x+y/8
  4. ((2)*(x))+((y/8
  5. ((2)*(x))+((y)/(8
  6. ((2)*(x))+((y)/(8))

It might not be obvious that this works in all situations, and inserting unmatched parentheses should make any programmer feel queasy. But it does work (Knuth says so) and it generalizes nicely, you just have to insert additional parentheses. Of course, once you get above 5 levels of precedence you might want to investigate ways to optimize the algorithm to avoid inserting endless amounts of parentheses. And once you do that the algorithm starts looking a lot like more “modern” algorithms like shift/reduce parsing. Which was, coincidentally, invented just a few years later by Knuth who also wrote about this algorithm.

Moved

I’ve moved the blog to my own domain: quenta.org.

Using

Argh, this whole “neptune looks like C#” thing is self-perpetuating. After we first noticed the similarities between the languages I looked into C# a bit more, and having that at the back of my head as we’re discussing the language only paves the way for new C#-like constructs and so the hideous circle continues.

Example. And this is where smalltalk programmers should look away or at least read the disclaimer before continuing. The example is about synchronization and locking. In java, all objects can be used as monitors and you usually guard a critical section by synchronizing on some object:

final Object lock = ...;
synchronized (lock) {
// critical section
}

That’s pretty readable even though it’s somewhat warped that all objects can be used as monitors. But that’s beside the point. In smalltalk it’s even neater since you can use blocks and so don’t need a special synchronized statement, you can just call a method on a Monitor or Mutex:

mutex acquireDuring: [
// critical section
].

In neptune, being derived from smalltalk, we also have blocks (they’re called functions) and until recently we used the exact same technique as smalltalk for synchronization:

Mutex mutex = ...;
mutex.acquire_during(fun {
// critical section
});

Yeah I know, it doesn’t look very good. It’s exactly the same as in smalltalk except that method calls are written as mutex.acquire_during(...) and that the block syntax has changed into fun { ... }.

It turns out that you use acquire_during all over the place so we really want a more concise syntax. The idea is to add a special purpose syntax for acquiring a resource, for instance a mutex or a file, in a particular scope that makes sure the resource is released properly. It’s an old idea we’ve had floating around but it never really got anywhere because we couldn’t find the right syntax.

This afternoon we ended up discussing this problem again and it seems like we finally have a strawman: the using statement:

Mutex mutex = ...;
using (mutex) {
// critical section
}

C# programmers will find this very familiar — C# has a construct with a very similar purpose and a very similar syntax. It is important, though, to point out that we haven’t taken the whole construct from C#, only the name of the keyword. But that’s a pretty important part of the construct.

As with all out shorthands, the using statement is just syntactic sugar for a simpler construct, in this case a method call:

mutex.using(fun {
// critical section
});

Any object is free to implement the using operator so it’s a much more general construct than synchronized in Java. A using statement can also define variables, for instance when acquiring a resource produces a result:

File my_file = ...;
using (InputStream stream : my_file) {
// read file
}

Will this be a popular statement? I think that probably depends on how we use it in the libraries. But that goes for most of the language constructs, if we don’t use them in the libraries they probably won’t be used by others either. We’ll see.


Disclaimer: I cannot be held responsible for any discomfort felt by smalltalkers while reading this post. To a smalltalk programmer the following probably seems like utter insanity since smalltalk already has a great solution to the problem in this example, and the people who are designing this language are all smalltalk programmers. I’m trying to find the courage to write a post about why we’re moving away from smalltalk and I’m not quite there yet.

Brevity

Ted Neward compares a handful of different languages (Java, C#, VB, Scala and Ruby) with respect to how much code it takes to express a simple person concept:

A Person has a first name, a last name, and a spouse. Persons always have a first and last name, but may not have a spouse. Persons know how to say hi, by introducing themselves and their spouse.

Of course, I couldn’t help but compare it with neptune which (sigh of relief) compares favorably:

class Person {

readable String first_name, last_name;
readable Person spouse;

Person(String -> first_name, String -> last_name,
Person -> spouse = null);

String to_string() {
if (spouse==null) return "Hi, my name is ${first_name} ${last_name}";
else return "Hi, my name is ${first_name} ${last_name}"
", and this is my spouse ${spouse.first_name} ${spouse.last_name}"
;
}

}

Personally, I think that is more readable than both scala and ruby but of course I’m biased. Here’s a short run through of what’s going on in this code.

The modifier readable means that the field is given a read accessor. So instead of writing

readable String first_name;

you would get the exact same result if you wrote

String first_name;

String accessor first_name {
return first_name;
}

In the Person class above, unlike C, C++ and Java, spouse.first_name does not just read the field first_name in spouse directly but calls the read accessor called first_name. In neptune, hidden or no modifier defines a field but doesn’t create accessors, readable gives it a read accessor, writable gives it a write accessor and visible gives it both 1.

The Person “method” is the constructor. The arrow notation means “assign this argument directly into the specified field” and the = null specifies a default value for a parameter (as in C++). The constructor above could be written alternatively as the following, which is completely equivalent but, I think, a lot less clear:

Person(String _first_name, String _last_name, Person _spouse) {
first_name = _first_name;
last_name = _last_name;
spouse = _spouse;
}

Person(String _first_name, String _last_name) {
this(_first_name, _last_name, null);
}

If you want to go completely nuts you can even expand the constructors into two static new operators and an instance initializer. And once you’ve done that it’s pretty easy to see that basic neptune is almost just smalltalk with a warped syntax. But I digress…

By the way, if you’re not into the whole type thing you’re free to leave out the types

class Person {

readable var first_name, last_name, spouse;

Person(-> first_name, -> last_name, -> spouse = null);

to_string() {
if (spouse==null) return "Hi, my name is ${first_name} ${last_name}";
else return "Hi, my name is ${first_name} ${last_name}"
", and this is my spouse ${spouse.first_name} ${spouse.last_name}
;
}

}

[1]: Why didn’t we use public and private instead of visible and hidden? Well, our modifiers mean something different from Java or C++’s do in almost all positions where they occur. We thought that it was important to avoid misleading people by emphasizing the similarities, which I think we would have if we had used public and private, and instead emphasize the differences by choosing completely different keywords.

C# 3.0

Pretty early on in the development of the neptune language we noticed that if you want syntax coloring when editing neptune source in editors that didn’t know about the language, a syntax coloring mode for C# is usually the closest approximation. That may not be a coincidence: I don’t actually know C# very well, I don’t think anyone in our group do, but for some reason neptune has drifted in C#’s direction.

Amazingly, the C# also seems to be drifting towards neptune: the new C# 3.0 spec describes the new constructs in C# 3.0 and a few of them are very similar to constructs in neptune.

One new construct in C# 3.0 is implicitly typed local variables. For instance, you can write

var i = 5;
var s = "Hello";

and the compiler will infer the variable types for you from the initializer and understand the code above as if you had written

int i = 5;
string s = "Hello";

In neptune you can also declare variables without specifying the type, using the exact same syntax:

var i = 5;
var s = "Hello";

In neptune, however, the type is not inferred but left undefined — neptune has optional typing and you are always free to leave out the types. So where this is illegal in C#:

var x = 5;
x = "Hello";

since x is inferred to be an integer, it is perfectly legal in neptune. You are also free to leave out the initializer in neptune, since we don’t need it to infer the type as they do in C#. So the constructs are a little different when you look closely but still pretty similar.

Another new construct in C# 3.0 is collection initializers. You can now write

new List<int> { 1, 2, 3, 4, 5 }

which gives creates a new list containing the five specified numbers. In neptune you can do exactly the same (except that we don’t have generic types) and, again, with exactly the same syntax:

new Vector { 1, 2, 3, 4, 5 }

Not only do the two constructs have the same syntax, the coding convention used in the spec is the exact same as I use in my code: a space after the class name, before the first element and after the last.

There is a subtle difference in what the code means in C# and neptune, but it makes almost no difference in how the constructs works, only how efficiently it can be implemented. In C# the expression above is implemented by adding the elements to the list:

List<int> list = new List();
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);
list.Add(5);

In neptune collections have a special collection constructor and the elements are given to the collection constructor in a special “primitive” collection:

var raw_elements = #{1, 2, 3, 4, 5} // "magic" primitive collection
Vector.new{}(raw_elements)

Our model has the advantage that we can optimize the allocation of the primitive collections which can often be pre-allocated and, if necessary, placed in ROM on small devices. It also means that collections are given all the elements at once and are hence free to implement new{} in smart ways. In C#, new List<int> { 1, 2, ..., 1000 } must be implemented using 1000 .Adds, whereas new Vector { 1, 2, ..., 1000 } in neptune can be implemented extremely efficiently no matter how many elements are added. (How? By using the primitive collection as a backing store and using copy-on-write if the vector is modified. And you can be much smarter than that if performance is an issue).

Unlike C#, this syntax can also be used to initialize mappings in neptune:

new TreeMap { 1 -> "one", 2 -> "two" }

On the other hand, C# allows this syntax to be used to initialize arbitrary objects:

new Point { X = 12, Y = 16 }

Considering that we knew nothing of these constructs in C# and the C# people of course didn’t know what we were doing (the spec came out before we even started working on neptune) it’s interesting how alike they are. I’m optimistic take it as a sign that maybe we’ve hit a design that will feel natural for people used to C-like languages.

For the technically minded, Ted Neward writes about the gory details of the new C# features. For an overview of all the new features a good place to look is the Code Post.

Kurdistan

Michael J. Totten is traveling in the Kurdish northern part of Iraq and blogging about it. Very interesting stuff, with lots of pictures.

Whatever food and beverage item you might want to buy (including booze), the Kurds have it. You want Red Bull? They got it. They also have Blue Ox, whatever that is. People looked at me funny when I took these pictures. Why on earth is that guy taking pictures of the Red Bull? He’s American, hasn’t he seen this shit a million times already back home? What I think they don’t understand is that what’s normal in the Middle East somehow amazes (and comforts) people who have never been here. So I took pictures of the grocery store. It’s not all burkhas, camels, and caves out here.