June 27, 2008
Coding challenge
Update: I posted a wrap-up here.
Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.
For example, part of the output would be:
- 8, 9, 10, 12 (11 is not valid)
- 98, 102, 103 (99, 100 and 101 are not valid)
- 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)
- Display the biggest jump (in the sequences above, it's 4: 98 -> 102)
- Display the total count of numbers
- Give these two values for max=10000
Post your solution in the comments or on your blog. All languages and all approaches (brute force or not) are welcome.
I'm curious to see if somebody can come up with a clever solution (I don't have one)...
June 24, 2008
Are Scala's case classes a failed experiment?
A long time ago, Bertrand Meyer, the creator of Eiffel, made a very strong statement against the use of switch and case. He argued that these constructs were not object-oriented and made future maintenance difficult. And to make his point crystal clear, he decided that Eiffel would not support these statements.
This decision didn't go well with Eiffel users and Meyer eventually gave in and added switch> and case to his language.
Meyer's initial position was certainly extreme but I think the foundation of his argument still stands, and I was reminded of this age old debate just today while attending Martin Odersky's Jazoon keynote, and more specifically, when he described Scala's "case classes".
Ever since I first read about case classes, I have been confused about their utility, and my puzzlement has not abated. Either I am missing something big or this feature is something that has been vastly overhyped and that should be avoided as much as possible
Let's see why.
Here is the example used in the official Scala documentation:
def printTerm(term: Term) {
term match {
case Var(n) =>
print(n)
case Fun(x, b) =>
print("^" + x + ".")
printTerm(b)
case App(f, v) =>
Console.print("(")
printTerm(f)
print(" ")
printTerm(v)
print(")")
}
}
This code is part of a hypothetical parser: it does different things depending on whether we just encountered a variable, a function or an application.
I have two strong objections to this kind of approach:
- It ties this class very tightly to all the classes described in the various cases.
- It makes evolution problematic.
The second claim is a bit more subtle but is actually the most important.
Obviously, this parser is quite incomplete: what happens if I want support for import clauses?
First, I am probably going to create at least one new class Import and second, I need to remember to add it to this code. Worse: all this code does is print out the type of Term it just parsed. Obviously, we will be needing more logic to actually do the work, such as a function to verify that the Term is syntactically correct (say verify(), and also a function to generate the code or the abstract information related to that term (generateCode()). Each of these methods will also feature a match structure, which will need to be updated for each new class.
In summary: every time that I add a new class, I need to remember to update three functions located somewhere in my code base.
Now we can see why Meyer dislikes switch statements so much...
The preferred way to solve these two problems is to make sure that each class encapsulates its own logic for all these operations:
interface Term {
void print();
void verify();
void generateCode();
}
public Var implements Term {
public void print() {
print(n)
}
public void verify() { ... }
public void generateCode() { ... }
}
// same for Fun and Expr
Here is how we print a term with case classes (from the Scala documentation, again):
Term t = ...; printTerm(t)And with proper encapsulation:
Term t = ...; t.print();With the OO approach, the code shown at the very top is simply no longer needed! If you need to print the content of a Term, you just invoke print() on it. If you add a new class to your parser, all you need to implement is conveniently summarized in the Term interface: no need to go hunting through your entire code base for switch statements. Not only do we have clean encapsulation, but we also have locality.
When I exposed the crux of this argument to a few Scala experts, they overall agreed about the point and responded by pointing out that case classes were more useful as an alternative to the Visitor pattern.
Before turning our attention to this specific case, it's important to note that at this point, we are now looking at solving a niche problem. And quite a rare one, in my experience. If this is really the reason why case classes were invented, I am really left scratching my head about the decision to include such a big feature inside a language to solve such a small class of problems.
Anyway, let's take a look at the Visitor angle.
In a nutshell, Visitors are used to emulate multiple dispatch in languages that don't support it natively. In some way, you are extending virtual invocation to apply to the runtime type of parameters passed to your functions.
I'm not going into a deep discussion of the pros and cons of this approach, but I'll just observe that even in the few cases where I have had such a need, an approach similar to the encapsulation explained above usually turns out to be preferable to a switch statement. In other words, if you need to have different operations depending on whether your function is being invoked with parameters of types A or B is better implemented by hiding this particular detail inside the class handling this dispatch, and not in a global switch.
From my understanding of Scala's history, case classes were added in an attempt to support pattern matching, but after thinking about the consequences of the points I just gave, it's hard for me to see case classes as anything but a failure. Not only do they fail to capture the powerful pattern matching mechanisms that Prolog and Haskell have made popular, but they are actually a step backward from an OO standpoint, something that I know Martin feels very strongly about and that is a full part of Scala's mission statement.
To be fair, Scala navigates in very rough waters: finding a good compromise between running seamlessly on an existing OO platform and inventing a language that will not only accomodate fundamental functional programming paradigms but also leave the door open for advanced dynamic concepts such as open classes is no easy feat, and overall, Scala has done a very good job at finding the right balance. But unfortunately, not with case classes.
Or am I missing something?
June 19, 2008
Jazoon'08
Here is the description:
A lot of new languages have emerged to challenge Java these past years: Ruby, Scala, Groovy, Erlang, etc... Can Java survive? In this presentation, I will do a quick analysis of these various languages and explain why, despite its old age, Java is in the best position to face the challenges that await software developers for the next decade. I will cover topics such as dynamic and duck typing, functional programming, concurrency, distribution and much more.As you can see, the topic is very broad and the main challenge will be to keep the presentation within the allotted time. Hopefully, we'll be able to carry on the discussion over beers or dinner.
See you all in Zurich.
June 11, 2008
The Fan programming language
I just came across a language that I never heard of before: Fan.
Here is a quick snippet:
// find files less than one day old
files := dir.list.findAll |File f->Bool|
{
return DateTime.now - f.modified < 1day
}
// print the filenames to stdout
files.each |File f|
{
echo("$f.modified.toLocale: $f.name")
}
After a few hours surveying the language, I have to say that Fan seems to get a lot of things right. Here is a short list of its features:
- Reuses the C# syntax for properties.
- Optional static typing and type inference. Use "." to enable static typing, "->" for dynamic typing. Non-existent methods are sent to a catch-all "trap" method, which is the equivalent of Ruby's method_missing. It is also possible to create types at runtime, which Fan calls -- a bit confusingly albeit accurately -- "dynamic types".
- Currying with the & operator.
- Closures. I also like the fact that closures and Fun functions can be transparently converted to methods (think "delegates") via currying. See below for an example.
- override and virtual keywords (as opposed to Java, Fan methods are not virtual by default).
- Untyped annotations (called Facets). Facets are pairs of (key, value) and they can be introspected at run time. The system reserves a few facet names for itself, such as @transient or @serializable.
- Immutability (classes can be created const and objects can be made immutable).
- Mix-ins (represented by interfaces that can have implementation). Fan mix-ins can have properties, although these need to be abstract (an approach that I find less restrictive than Scala's).
- Runs on both the JVM and .Net (wow!).
- Uses := for assignment. I remember liking this symbol a lot when I was programming in Pascal and Modula 2, but I haven't used it in about twenty years, so it might be a bit disconcerting at first.
- Interesting approach to modularity leveraging REST URI's to denote namespaces. This area is still in development, but here is a quote that summarizes Fan's approach:
Java and .NET to a lesser degree separate the concepts of namespace and deployment. For example in Java packages are used to organize code into a namespace, but JAR files are used to organize code for deployment. The problem is there isn't any correspondence between these concepts. This only exacerbates classpath hell - you have a missing class, but the class name doesn't give you a clue as to what JAR file the class might live in.
- "once" methods (a feature I can only remember ever seeing in Eiffel).
- Constructor declarations need to be prefixed with the keyword "new" but can take any arbitrary name, although the prefix "make" is commonly used. Constructing an object is done by invoking that constructor as a static method on the type (like Ruby), which I find intuitive.
- Good-looking web site with extended documentation.
Constructor
class Point
{
new make(Int x, Int y) { this.x = x; this.y = y; }
Int x
Int y
}
// make a point
pt := Point.make(30, 40)
Properties
class Person
{
Str name
Int age { set { checkAge(val); @age = val } }
}
In the code above, @age is used to refer to the actual field and not the property.
Facet
@version=Version("1.2")
@todo=["fix it", "really fix it"]
class Account
{
}
You can pass methods when closures are expected. For example, Thread.make expects a closure that takes a Thread in parameters and returns an Obj:
new make(Str name := null, |Thread -> Obj| run := null)You don't need to create an object to invoke that method:
static Void readerRun(Thread t) {
// ...
}
reader := Thread.make("reader", &readerRun).start
Here are some of my pet peeves about Fan:
-
The typing syntax. I would have preferred "f: File->Bool" instead of "File f->Bool" so that formal parameters and the type of the closure can be more easily told apart.
-
No generics. All successful languages eventually get there, so I hope Fan will as well, but the creators seem to be hostile to the idea:
Our philosophy is that generics are a pretty complicated solution to a fairly insignificant problem.
I'm sure they will change their mind in due time, and in the meantime, List, Map and Func offer a limited type of genericity. -
There doesn't seem to be any IDE support. I'm not sure how old Fan is, but the documentation states that it is approaching v1.0, so I'm hoping that the Fan developers will learn from Groovy's mistakes and focus their attention on IDE support as soon as possible.
-
I prefer for constructors to have a fixed name instead of one arbitrarily chosen by the developer. While class declarations make it easy to pinpoint which methods are constructors (just look for "new"), it's not as easy to tell when you are on the call site, since a constructor invocation cannot be differentiated from a static call. From that respect, I still find that Ruby's approach (Person.new) represents the best of both worlds, although I think it could be perfected even further by eliminating the duality "new"/"init" completely.
For example, instead of:
// Valid Fan class Point { new make(Int x, Int y) { this.x = x; this.y = y; } Int x Int y } p = Point.make(2, 3)Why not:// Invalid Fan class Point { new(Int x, Int y) { this.x = x; this.y = y; } Int x Int y } p = Point.new(2, 3)? (the same remark can be made about Ruby)
Overall, it looks like Fan is being driven by motivations that are very similar to what started Groovy: pick the best features of the current popular languages and try to blend them into a coherent set. I find myself particularly fond of Fan because I happen to agree with a lot of the choices that the designers made, which is exactly how I felt about Groovy in the beginning. Of course, Fan has the advantage of hindsight and it borrows from a few additional languages than Groovy did (namely, C#, Scala and a bit of Erlang), so I find the result quite promising.
June 08, 2008
The future of mobile user interfaces
It's a very impressive demo, but as opposed to the author of the article, I really don't think that much more can be done with this kind of technology. People are quick to point out that we could write fantastic games or develop great applications with this technology, but the fact that you need to keep the screen visible (and at a reasonable angle) as you tilt the phone severely limits the range of what you can actually do.
Recently, I have also started encountering limitations in what you can do with touches on a phone screen. Touch interaction allows for great-looking devices that are not encumbered by ugly-looking keyboards, but it also takes a toll on user interaction in two ways:
- The widgets need to be much bigger so that fingers can accurately tap them, thereby limiting the amount of information that can be shown on the screen.
- When you tap on a widget, your entire finger will mask a significant portion of the screen, including the very widget you are tapping on.
There is no doubt that touch and accelerometers are here to stay, but in my opinion, the most revolutionary applications that we are likely to see in phones in these coming years will come from features that don't require any user interaction, such as camera, compass and GPS.