Monomorphic

As a little fun project, I developed some probabilistic cellular automata with Scala and very basic AWT graphics. I continue to become more proficient with Scala, and it feels increasingly natural to use. During this exercise I came up with something that I thought was particularly elegant, and that I am pretty sure would have been a lot less readable in Java. I will just reproduce the interesting bits. The basic idea is that I want cells on a 2D grid to take certain redrawing actions according to given probabilities. First, I define this utility function:

object Util {
 
	//sum of floats (probabilities) should be at most 1.0
	def multiAction(acts: Seq[Tuple2[()=> Unit, Float]]) = {
		val r = Math.random
		var soFar: Float = 0
		var acted = false
		for ((act,prob) <- acts) {
			soFar += prob
 
			if (soFar > r && !acted) {
				act()	
				acted = true
			}
		}
	}
 
}

The idea here is that we supply a list of tuples. The first element of each tuple is a function, and the second element is a float value between 0 and 1 representing the probability that each function is evaluated. Only one of the functions supplied is actually evaluated.

This is how I put it to use (excerpt from another class):

Util.multiAction(
  List( 
  (() => {
     cellsWrite(x, y-1) = cellsRead(x, y-1) + 0.01f;
     cellsWrite(x, y+1) = cellsRead(x, y+1) + 0.01f 
    }, 0.2f),
  (() => { 
     cellsWrite(x+1, y) = cellsRead(x+1, y) + 0.01f;
     cellsWrite(x-1, y) = cellsRead(x-1, y) + 0.01f 
    }, 0.1f)
 )
)

Once you take in the braces here it is actually quite simple. We have two anonymous functions taking zero parameters of two statements each. The first one has probability 0.2 and the second probability 0.1, meaning that there’s a 70% probability that nothing will happen. We can also make an arbitrarily long list of such functions on the fly.

To the best of my knowledge, the only way of reproducing this flexibility in Java would be to create anonymous inner classes and put them inside an array. Certainly that would be quite a bit more verbose than this.

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.