Monomorphic

Academics and practitioners, having rather different goals in life, tend to approach software development in quite different ways. No doubt there are many things each side of the fence can learn from the other, but I think academics in particular could often benefit quite a lot by adopting some of the practices used in industrial development. And not just computer science academics!

A common misconception is that these techniques only are useful with large projects and large teams. I find, though, that they can help reduce much of the growth pains even in small projects, helping them reach maturity much faster.

Use version control. Classical, but invalid, counter arguments include “it’s a hassle and too much work to set up”, or “there’s only one person working on this project anyway”. Even if it’s only you, you will benefit massively from being able to undo your changes far back in time. It will let you experiment safely. Plus, setup is no longer an issue with free and easy-to-use services like github and bitbucket. My tool of choice is now Mercurial, and I used to use SVN. And there are many other good choices.

Use a debugger. If there is a debugger available for your language, and there most certainly is, then you should use it to find nontrivial errors, rather than extensive printf style testing.

Don’t optimise prematurely, but when you need to, use a profiler. Profilers tell you where a program’s performance bottlenecks are. You can profile things like heap usage (what classes use most space in Java, for instance) and CPU usage (which functions use the most CPU time). For Java, I’ve discovered that the NetBeans IDE has a very good built in profiler. Eclipse also has one, but it didn’t work on Mac last time I checked. For C/C++, GProf used to be good and probably still is.

Use unit testing wisely. All of the above apply even to very small projects, but I think some projects are too small to need unit tests, at least initially. You be the judge. I find that unit tests can have a lot of benefit when applied to the fragile, complicated parts of a system, where many different things interlock. If you are ambitious you can also write tests first and code later — test driven development.

Use a good IDE if you can. For a language like Java, where you have to type a lot of code to get something done and spread out your code across lots of files, a good IDE that can generate boilerplate code and navigate quickly can really speed up your work. It’s beneficial for other languages too. But I have no problem with people who use pure vim or emacs, after all these are practically IDEs.

I believe that honing your software development skills as an academic can pay off. Also see: Daniel Lemire on why you should open source your projects. (I will get around to doing this eventually, I promise )

Scala is a little wonderland sprinkled with useful things you can mix and match as you like to improve your coding experience while staying on the Java platform. The Option classes, the structural case matching, the compact declarations, lazy evaluation… the list goes on. But at the heart of it is the decision to mix freely the functional and imperative programming styles.

How does this work in practice?

• Statements can have side effects, like in Java
• The final statement evaluated in a function is its return value by default
• Every statement evaluates to a value, even control flow statements like if… else, unlike in Java

The bottom line is that some problems call for a functional programming style, and others for an imperative one. Scala doesn’t force you into a mold, it just gives you what you need to express what you’d like to express. This can lead to very compact code. Here’s a function that recursively finds all files ending in .java starting in a given directory. The File class here is the standard Java java.io.File!

Remember, the last expression evaluated is the return value.

 def findJavaFiles(dir: File): List[File] = {
    val files = dir.listFiles()
    val javaFiles = files.filter({_.getName.endsWith(".java")})
    val dirs = files.filter({_.isDirectory})
    javaFiles.toList ++ dirs.flatMap{findJavaFiles(_)}
  }

But we can write it even more compactly at the expense of some clarity:

 def findJavaFiles(dir: File) = {
    val files = dir.listFiles()
    files.filter(_.getName.endsWith(".java")).toList ++
 files.filter(_.isDirectory).flatMap{findJavaFiles(_)}
  }

Now write this function in Java and see how many lines you end up with.

The Scala collections library (in version 2.7.7) has a MultiMap trait for mutable collections, but none for immutable ones. I hacked something up to use while waiting for an official version. I’m finding this to work well, but I don’t have much experience with collections design, so it’s likely to have some flaws. Also, this is a class and not a trait, so you can’t use it with any map you like. And from a concurrency perspective, maybe it’s sometimes better to use backing collections other than the HashSet and the HashMap.

 
import scala.collection.immutable._
 
/**
A multimap for immutable member sets (the Scala libraries 
only have one for mutable sets). 
*/
class MultiMap[A, B](val myMap: Map[A, Set[B]]) {
 
	def this() = this(new HashMap[A, Set[B]])
 
	def +(kv: Tuple2[A, B]): MultiMap[A, B] = {
	  val set = if (myMap.contains(kv._1)) {
		  myMap(kv._1) + kv._2
	  } else {
		  new HashSet() + kv._2	     	   
	  }
 
	  new MultiMap[A, B](myMap + ((kv._1, set)))
	}
 
	def -(kv: Tuple2[A, B]): MultiMap[A, B] = {
	  if (!myMap.contains(kv._1)) {
	    throw new Exception("No such key")
	  }
	  val set = myMap(kv._1) - kv._2
	  if (set.isEmpty) {
	    new MultiMap[A, B](myMap - kv._1)
	  } else {
		  new MultiMap[A, B](myMap + ((kv._1, set)))
	  }
	}
 
	def entryExists(kv: Tuple2[A, B]): Boolean = {
	  if (!myMap.contains(kv._1)) {
	    false
	  } else {
	    myMap(kv._1).contains(kv._2)
	  }
	}
 
    def keys = myMap.keys
 
     def values: Iterator[Set[B]] = myMap.values
 
    def getOrElse(key: A, elval: Collection[B]): Collection[B] = {      
      myMap.getOrElse(key, elval)
    }
 
    def apply(key: A) = myMap(key)
 
 
 
}

Usage:

 
   var theMultiMap = new MultiMap[String, Int]()
 
   theMultiMap += (("george", 1))
   theMultiMap += (("george", 3))
   theMultiMap += (("bob", 2))
   theMultiMap -= (("george", 1))

Programming languages are more about people and less about machines.

Programming languages are about staying inside the limitations of people’s minds and their ability to keep track of and work with abstractions. If people had no such limitations, they could code in assembly language all the time.

Programming languages and supporting tools and environments are the interface between people and the raw instruction set of a computer (or a bigger entity, like a network of computers). When we design programming languages, we must take into account not only what the machine environment will do and how it changes, but also how people create the software, how they modify it, how they think about it. Maybe programming languages should even be designed with business processes in mind, in some cases.

But this is also a question of what kind of programmer we want to cultivate. The language shapes the programmer, too.

Programming with actors was a new concept to me until I tried it out in Scala. It’s appears to be one of Scala’s most celebrated features, judging by the official blurb. Actors was a daunting word at first but it really ends up being a very simple concept.

Actors are a programming model for concurrent programming. With conventional mutex/monitor based programming in Java, say, programmers hold and release locks (the synchronized keyword) to achieve safe concurrency. Condition variables are used for thread communication (the wait and notify family of functions on java.lang.Object). Communication is synchronous: a typical case would be that you change some condition, invoke notifyAll to wake up threads waiting on that condition, and then they can take over the relevant lock and proceed to do some processing.

An actor is a unit of execution with an asynchronous message queue. Actors can receive messages from other actors or send messages to other actors at any time, however, the messages wait in the receiving actor’s “mailbox” until the actor has time to receive it.

As a simple example, let’s develop a program that converts text files to upper case using actors. The program will have an “Input” actor, an “Output” actor, and a number of “UpperCase” actors that do the processing. First the Input actor:

import scala.actors._
import java.io._
 
class Input(in: BufferedReader) extends Actor {
	def act() {
	  while(true) {
	    receive {
	      case Next => { sender ! Line(in.readLine()) }
	    }
	  }
	}
}

It’s worth noting that the Actor system is implemented completely in the libraries, outside of the core language. Actors are not first class constructs, but sometimes look as if they were. The act method is where actors begin their execution. The receive method causes them to block and wait for a message, which we may pattern match on. The sender variable corresponds to whoever sent the last message received, and the ‘!’ operator sends a message. So whenever this actor receives the Next message, it will respond with the next line from a buffered reader.

Then, the UpperCase actor:

import scala.actors._
 
case class Next
case class Line(x: String)
 
class UpperCase(input: Actor, out: Actor) extends Actor {
	def act() {
		while(true)
		{
			input ! Next
			receive {
			case Line(x:String) => { out ! x.toUpperCase() }
			}
		}
	}
}

This actor is created with in- and output actors as its constructor parameters. It continually asks the input actor for a new line, converts it to upper case, and sends it to the output actor. Also note the case classes here, which are for pattern matching only. They are a bit like algebraic data types in Haskell.

Finally, the Output actor:

import scala.actors._
 
class Output extends Actor {
	def act() {
		while(true)
		{
			receive {
			case x:String => { println(x) }
			}
		}
	}
}

And then we have to tie it all together:

import java.io._
 
object Demonstration {
 
  val reader = new BufferedReader(new InputStreamReader(System.in))
 
  def main(args: Array[String]) {
 
    val in = new Input(reader)
    in.start
 
    val out = new Output()
    out.start
 
    1.to(5).foreach(x => {
      val tr = new UpperCase(in, out)
      tr.start
    })
  }
}

Here I abuse the foreach notation slightly to create 5 parallel text processors. Each actor runs on its own thread (though there are ways to prevent this if one wants very large numbers of actors). Now of course, the lines will probably be output in the wrong order. Another obvious shortcoming is that there is no clean shutdown protocol that terminates all the actors when the input stream is fully read. Solving these problems is outside of the scope of this article.

Some other interesting resources on actors: the official tutorial, the papers (slightly more academic but accessible to the monomorphic reader, I imagine). Debasish highlights how actors can be used to get threadless concurrency, Erlang-style.

I’m now going to share some of the results of my recent experiments with the Scala programming language. In May I wrote that I had started looking at it. I’ve been using it to make some support tools that I needed for research work since.

First a disclaimer: It’s been 4+ years since I did serious work with a functional programming language (Haskell, in first year of university), so my style is imperative-sprinkled-with-functional rather than the opposite. Also, since I haven’t spent that much time with this language yet, I’m bound to be making obvious mistakes. That said, I’m happy to be able to recommend Scala to pretty much anyone at this point. The learning curve is not steep if you know Java, and it allows for a variety of approaches depending on who you are.

For this particular tool, I needed to parse XML files, edit the contents of certain tags, and spit the data back out again. I’d like to show what I ended up with and point out some of Scala’s powerful features. Let’s first look at some interesting parts, and then the entirety.

1
2
3

object XMLTool {
  val interLink = """\[\[(.*)\]\]""".r
}

Scala lets you define objects as well as classes. Objects are singletons and can be referred to by name. Otherwise they are like classes; they participate in the type hierarchy.
Scala has three kinds of declarations: val, var and def. Values are evaluates once and cannot be reassigned. Vars are variables which can be reassigned. Defs are definitions and can as such be functions or values. My understanding is that they are lazily evaluated. The type of this val declaration is inferred by the highly powerful type system automatically using Hindley Milner type inference. One of my biggest surprises with Scala is how little type information the programmer has to provide, yet how powerful the static checking is. Incidentally, the .r at the end is a shortcut for turning the string into a regular expression object.

1
2
3
4
5
6

def main(args : Array[String]) : Unit = {
 
    val p = new XMLEventReader().initialize(Source.fromFile(args(0)))
    p.foreach(matchEvent)
 
  }

This function is the analogue of Java’s public static void main() and actually compiles to the same bytecode. Unlike in Java, types come after the variable name, separated from it by a colon. We can tell that we’re dealing with a functional language when we see foreach being applied to a function which I’ll declare next:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def matchEvent(ev: XMLEvent) = {
    ev match {
      case EvElemStart(_, "text", _, _) => { 
        readingText = true
        print(backToXml(ev))
      }
      case EvElemStart(_, _, _, _) => { print(backToXml(ev)) }
      case EvText(text) => {
        if (readingText) print(filterText(text)) else print(text) 
      } 
      case EvElemEnd(_, "text") => {
        readingText = false
        print(backToXml(ev))
      }
      case EvElemEnd(_, _) => { print(backToXml(ev)) }
      case _ => {}
    }
  }

Here we see pattern matching in action. We can match on lots of things, including types, partially instantiated types, strings and regular expressions. This style of programming is encouraged in FP languages, unlike in imperative ones. By matching on something like EvElemStart(_, "text", _, _) I’m looking for XML tags whose name is “text”, and I don’t care about their namespace or attributes. _ is a wildcard character.

Incidentally, it’s perfectly fine for me to leave out the return type of this function. Scala will infer that the return type is Unit (which vaguely corresponds to void in Java).

Here’s the whole thing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import scala.xml._
import scala.xml.pull._
import scala.io.Source
 
object XMLTool {
  val interLink = """\[\[(.*)\]\]""".r
  var readingText = false
 
  def main(args : Array[String]) : Unit = {
 
    val p = new XMLEventReader().initialize(Source.fromFile(args(0)))
    p.foreach(matchEvent)
 
  }
 
  def matchEvent(ev: XMLEvent) = {
    ev match {
      case EvElemStart(_, "text", _, _) => { 
        readingText = true
        print(backToXml(ev))
      }
      case EvElemStart(_, _, _, _) => { print(backToXml(ev)) }
      case EvText(text) => {
        if (readingText) print(filterText(text)) else print(text) 
      } 
      case EvElemEnd(_, "text") => {
        readingText = false
        print(backToXml(ev))
      }
      case EvElemEnd(_, _) => { print(backToXml(ev)) }
      case _ => {}
    }
  }
 
  def backToXml(ev: XMLEvent) = {
    ev match {
      case EvElemStart(pre, label, attrs, scope) => {
        "<" + label + attrsToString(attrs) + ">"
      }
      case EvElemEnd(pre, label) => {
        "</" + label + ">"
      }
      case _ => ""
    }
  }
 
  def attrsToString(attrs:MetaData) = {
    attrs.length match {
      case 0 => ""
      case _ => attrs.map( (m:MetaData) => " " + m.key + "='" + m.value +"'" ).reduceLeft(_+_)
    }
  }
 
  def filterText(text: String) = {
    val matches = interLink.findAllIn(text)
    if (matches.hasNext) matches.reduceLeft(_+_) else ""
  }
}

So the purpose of this program is to read the XML, remove everything inside <text> tags that doesn’t match the interLink regular expression, and output the XML again. Towards the end, note how pleasant map and reduceLeft are for string processing – in Java I can’t really think of a succinct way of expressing the same notion.

Another couple of disclaimers: someone brought to my attention that there’s a very compact way of doing XPath queries in Scala, which probably makes my pattern matching on EvElemStart unnecessarily verbose. (Here’s a blog post on the xpath technique) Also, there was no particular reason for me to use pull parsing – push parsing might have been more natural, but I started down that path and this is what I ended up with. It works.

You can tell that I still have an imperative style from the way I use the readingText state variable to keep track of what the program is doing. A much more functional style program is probably hiding behind this one. Fortunately Scala is very forgiving towards people who mix styles like this.

My experience has been that it’s quite easy to get started and do useful things with Scala, once you get past the initial ideas (such as the difference between objects and classes, traits, val/def/var, declaration syntax). I would recommend it to anyone doing things with the JVM.

I now break the longstanding tradition of not posting code on this blog. I just wanted to share what I believe to be a somewhat unusual pattern in Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public IMethod findMethod(String name, String[] types) {
		outer:
		for (IMethod m: m_methods)
		{
			if (m.getName().equals(name))
			{
				int i = 0;
				for (IType t: m.getArgList().getTypes())
				{
					if (! t.getName().equals(types[i]))
					{
						continue outer;
					}
					i++;
				}
				return m;
			}
		}
		return null;
	}

On line 2, there’s a label outer: which identifies a location in the code. Normally this feature is used with keywords like the hotly debated goto in C. Java has goto as a keyword, but doesn’t support the feature. However, you can still use the labels with statements like continue above (line 12), which in this case starts a new iteration of the outer loop rather than the inner one.

I can’t remember ever having had to use this feature of any C-like language before (perhaps once) so it was intriguing when it popped up. It’s possible that a neater implementation of this would put the inner loop in a matchesSignature method in the IMethod interface instead.