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.

After 13 months and 51 posts, my experiments in blogging continue, although they are perhaps better described as polymorphic than monomorphic. Maybe it’s time for some reflections.

On the whole blogging in this format and at this frequency has been a pretty fun and fulfilling process. I get to practice writing free-form, nonscientific texts, and even if many of them might not be read by so many people, the idea that they might be turns it into a useful exercise.

Recently Flattr buttons were added to this blog, which allows users who use the service to donate money and show appreciation for my texts (some such people indeed exist – thanks a lot, all two of you!). Initially I had a single button for the entire blog, but now I am trying out a format where I have one button per post.

I’ve noticed, on this blog and elsewhere, that I can’t quite decide if I should write with British or American English. I feel culturally uncertain as a writer of this language. But recently I’ve come to think that I should embrace my European background, so more of the British variety in the future is a likely prospect.

Topics have been varied. The tag and category systems have been used in an attempt to bring some order to the table, but they’ve become too chaotic to be useful. A restructuring is perhaps in order during the next 13 months.

One of the most popular topics I’ve written about has been the Scala language. People tend to google Scala a lot, and it’s actually really uplifting to see the interest in it (since I hold it to be a way forward). If you are a blogger who wants to get a billion page views, write about Scala. I don’t want to consciously pander to the readers too much, so in itself it is not a reason for me to write about the topic. I will write about Scala when I want to say something about it. (A difficult principle to really practice.)

I’ve tried out some different WordPress themes occasionally, but so far I haven’t found anything I like better than this “Infinimum” theme. It feels very clean, functional and modern.

That will be enough of the reflections for now.

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))

Today, Java is one of the most popular programming languages. Introduced in 1995, it rests on a tripod of the language itself, its libraries, and the JVM. In the TIOBE programming language league charts, it has been at the top for as long as the measurements have been made (since 2002), overtaken by C only for a brief period due to measurement irregularities.

Yet not all is Sun-shine in Java world. Sun Microsystems is about to be taken over by Oracle, pending EU approval. (EU is really dragging its feet in this matter but it seems unlikely they would really reject the merger). Larry Ellison has voiced strong support for Java and for Sun’s way of developing software, so maybe this is really not a threat by itself. But how far can the language itself go?

The Java language was carefully designed to be relatively easy to understand and work with. James Gosling, its creator, has called it a blue collar language, meaning it was designed for industrial, real world use. In a world where C++ was the de facto standard for OO programming, Java was a big step forward in terms of ease of development, with its lack of pointers and strong type system – to say nothing of its garbage collection. Many classes of common programming errors were removed altogether. However, in the interests of simplicity and clarity, some tradeoffs were made. The language’s detractors today point to problems such as excessive verbosity, the lack of closures, the limited generics, and the checked exceptions.

For some time there has been a lot of exciting alternative languages available on the JVM. Clojure is a Lisp dialect. Scala, the only non-Java JVM language I have used extensively, mixes the functional and object oriented paradigms. Languages like JPython and JRuby basically exist to allow scripting and interoperability with popular scripting languages on the JVM.

Today it seems as if the JVM and the standardized libraries will be Java’s most prominent legacy. The language itself will not go away for a long time either – considering that many companies still maintain or develop in languages like Cobol and Fortran, we will probably be maintaining Java code 30 years from now (what a sad thought!), but newer and more modern JVM languages will probably take turns being number one. The JVM and the libraries guarantee that we will be able to mix them relatively easily anyway, unless they stray too far from the standard with their custom features.

So in hindsight, developing this intermediate layer, this virtual machine – and disseminating it so widely –  was a stroke of genius. Will it be that in future programming models we have even more standardized middle layers, and not just one?

Meanwhile, there’s a lot of debate about the process being used to shape and define Java. For a long time, Sun employed something called the Java Community Process, JCP, which was supposed to ensure openness. Some people proclaim that the openness has ended. To take one example, very recently, Sun announced that there will be support for closures in Java 7, after first announcing that there would be no support for closures in Java 7. The process by which this decision has been managed has been described as not being a community effort. Some aspects of Java are definitely up in the air these days.

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’ve started experimenting with the programming language Scala. I’ve been wanting to get back into functional programming for some time, but I’ve found it impractical for the time being to dive right into something like ML, Haskell or Scheme. Scala has gained notoriety since Twitter announced that they’ve rewritten their engine in it. Some of its benefits are:

• Mixes multiple paradigms, including imperative, functional and actor programming
• Runs on the Java VM – interop with Java libraries and frameworks is trivial
• Lightweight syntax

There is much to like in this. I’m hoping that it will turn out to be useful as a rapid prototyping language for trying things out, especially since so many third party tools are available in Java world.

For now I am using exercises from Project Euler as a means to experiment with and learn it. This works surprisingly well.

Also see this list of the most popular programming languages - Scala is now number 27, ahead of Prolog, Erlang, Haskell and ML.