That Fibonacci function in detail…

Posted by – May 3, 2016

Some time ago I gave an answer on StackOverflow is to a question about producing a Fibonacci sequence, which asked if there is an “elegant way to do this in Scala”.

My solution was this:


val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

Funnily enough, none of the comments on this confusing-looking snippet of code asked exactly how it worked. Maybe people are too embarrassed to ask. But I don’t think it’s really very obvious, so here’s an explanation. I’ll type slowly…

The short answer:

The result of scanLeft is by definition a sequence consisting of the accumulator at each step of the calculation, starting with its initial value.

For each step, the accumulator and an element of the collection are combined using the supplied function, producing a new accumulator value that is used in the following step.

In our function, calculating element ei will take element ei-2 (since we already have the first two values from the 0 provided, and 1, the initial accumulator), and combine with the current accumulator. The current accumulator has been output by scanLeft as ei-1, hence in effect we are adding the previous two elements together to provide the following one.

In detail…

The Fibonacci sequence

In case you don’t know, the Fibonacci sequence is a sequence of numbers that crops up in nature and mathematics. The important thing about it for our purposes is that it’s easy to define: start with the numbers 0 and 1, then each subsequent term is the sum of the previous two. So the next one would be 0 + 1 = 1, then 1 + 1 = 2, then 1 + 2 = 3, then 2 + 3 = 5, then 3 + 5 = 8, and so on, creating the following:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

The solution

Let’s break the code up and describe what each word does. Simple bits first. Skip ahead if you know it already.

val means we’re defining a value (a variable as it’s known in other languages, except here it’s immutable, so “variable” wouldn’t be such a great bit of terminology), which we’re calling fibs.

: precedes a type annotation, where we describe the type of fibs. Type annotations are for showing anyone reading the code the type without having to look at the definition, and also as a sanity check on your definition. Normally this is optional, but because this value is recursive (fibs also appears on the right hand side of the = sign), the compiler requires the extra help.

Stream[Int] is the actual type of fibs. A Stream is like an everyday linked List, except it’s lazy, i.e. we only know what the first element (the head) is, and the rest (the tail) will only be calculated as far as needed if and when we access it. This allows us to describe infinite sequences (though Streams can also be of finite length). The [Int] part is the Stream’s type parameter, required because there is a type parameter in the class definition. It lets us and the compiler know the type of the elements in the Stream.

0 is just a plain old Int literal: the first element of our Stream.

#:: is the Stream cons operator. It’s the equivalent to :: in List, i.e. it’s a prepend method to insert an element at the start of the Stream. Because it ends in the character ’:’, it’s right-associative, so it’s called on the object to the right (here, a Stream, since that’s what Stream’s scanLeft method returns), with the argument being the 0 to the left.

Actually… it’s a bit more complicated than this, since if you check the Stream documents, there’s no mention of a method called #::. The method is supplied via an implicit conversion to a class called ConsWrapper. Why? Because if it wasn’t, the Stream would itself need to be evaluated before we can call the prepend method, which would mean our resulting Stream (our 0 plus the result of scanLeft) now has at least the first two elements calculated, which is not what we want. This implicit conversion method is found on the Stream companion object:

implicit def consWrapper[A](stream: ⇒ Stream[A]): ConsWrapper[A]

It’s in scope because companion objects are one of the places that the compiler looks for implicit conversions.

So our snippet above is converted by the compiler to:

val fibs: Stream[Int] = 0 #:: Stream.consWrapper(fibs.scanLeft(1)(_ + _))

Importantly, the parameter “stream” in the implicit conversion is by-name, indicated by the “=>” before its type. This means that the argument is not actually evaluated, but only its name is passed – which is effectively a function that evaluates and returns the value each time it is used. Hence in the following:

def foo(x: ⇒Int) = {
  Thread.sleep(100)
  println("Start")
  Thread.sleep(100)
  println(x)
  Thread.sleep(100)
  println(x)
}
foo({println("Evaluating"); 42})

The output is:

Start
Evaluating
42
Evaluating
42

Notice:

1) Evaluation of the {code block} does not occur before it passed to foo, as method arguments normally would be. It’s first evaluated at the first place in the receiving method foo where the value x is used

2) Each time it is used, it is re-evaluated

So the consWrapper method can be called without actually evaluating its “stream” parameter, which is the behaviour we need.

fibs.scanLeft(1)(_ + _):

Let’s get the (_ + _) out of the way first. That’s your everyday anonymous function placeholder syntax, and is exactly equivalent to ((b,a) => b + a), which hopefully you’ll recognize as a function literal that takes two values that we declare as b and a on the left hand side of the =>,  and adds them together. Such repetition of the value names is avoided by using the underscore _ for each instead. The types of b and a are known from the context, i.e. the type of function scanLeft is expecting, given the types of the elements in the Stream, and the type of the first argument (1 in this case).

scanLeft is a method that is available on all Traversables, i.e. anything in the Scala collections library, which includes Streams such as our fibs here. First, what does it do? To quote the documents, this method is to

create a new stream which contains all intermediate results of applying the operator to subsequent elements left to right. scanLeft is analogous to foldLeft.

For a Stream[A], the method signature is:

final def scanLeft[B, That](z: B)(op: (B, A) ⇒ B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That

Ouch! Let’s ignore the clever generic bits (that allow us to spit out a collection of some other type, if we so desired), and state it more simply as

def scanLeft[B](z: B)(op: (B, A) ⇒ B): Stream[B]

So we see that scanLeft takes two parameter lists, with one parameter in each.

  • The first, z, is some value of type B, which gives the initial value of the “accumulator”, i.e. a value that is used for storing the accumulated value of a fold function, the “current total”, if you like.
  • The second, op, is a function value which takes a B and an element A, and combines them into a new B (meaning, how to add an element to the current total). At the end we’re left with a Stream of Bs.

Let’s remind ourselves what foldLeft does, and see how this compares to scanLeft, using a List for simplicity:

val xs = List(2,3,4)
xs.foldLeft(10)(_ * _)

res5: Int = 240

We start with an accumulator, with value 10, then this is multiplied by 2, to give 20, which is our new accumulator value. So this is then multiplied by 3, to give 60. Finally, 60 is multiplied by 4, and the result 240 is returned. The list folds left to right into the accumulator like a concertina.

Now let’s change foldLeft to scanLeft:

xs.scanLeft(10)(_ * _)

res6: List[Int] = List(10, 20, 60, 240)

As you can see, scanLeft is very similar, except all the intermediate values of the accumulator are output. Note that the initial value is included. So it’s pretty simple: scanLeft is just a foldLeft that shows its working.

So now we understand the elements of this snippet, WHY does this yield a Stream of Fibonaccis?

To start with, we can see that the first element must be 0, because that has been tacked onto the start. fibs is

Stream.consWrapper(…).#::(0)

where the “…” is a Stream, but it’s not evaluated yet, because it’s passed by-name. This returns

Stream(0, ?)

Scala uses the ‘?’ in its toString representation to show the parts that haven’t yet been evaluated.

Now, let’s force it to evaluate some more of fibs. (We might do this using the “take” method to give us the first n elements.) To get the second value, we need to evaluate the “…”, which is the scanLeft part, fibs.scanLeft(1)(_ + _)

Remember that scanLeft returns a Stream, and (from the definition of scanLeft) the first element of that Stream is just the initial accumulator, which is 1. At this point,

fibs = 0 #:: Stream(1, ?)

For the third element of fibs, and second element of the scanLeft result, we use the (_ + _) function to combine the accumulator, 1, with the first element of fibs. This is 0, and readily available without evaluating scanLeft, as we saw above. 1 + 0 = 1.

fibs = 0 #:: Stream(1, 1, ?)

For the next element, remember how scanLeft works, from our demo with List above. Each element of the result is the value of the accumulator at each step in the calculation. We take the second element of fibs, 1, and combine it with the accumulator that we just calculated – which was the third element of fibs, also 1. 1 + 1 = 2.

fibs = 0 #:: Stream(1, 1, 2, ?)

Carrying on, because scanLeft by definition appends each accumulator value to the resulting Stream, we can see that each new value also is added to the fibs Stream, which means it’s available two steps later when we need to reference the next value of fibs. So in our next step, the third element of fibs, 1, is combined with the accumulator, which is what we just worked out.

fibs = 0 #:: Stream(1, 1, 2, 3, ?)

When the scanLeft method references the next value of fibs, it does not need to re-calculate each time, since Streams cache their results.

So as we can see above, the current accumulator value in scanLeft is the final element of fibs calculated so far, and the value of fibs being folded into the accumulator is always the value one element behind, which was the previous accumulator value. These are summed using (_+_), giving the new accumulator value, which is added on the end. Effectively, we’re continuously adding the last two values in the Stream to yield the following one. And that’s the definition of the Fibonacci sequence!

Food for thought

  1. Is it possible to use a List instead of a Stream in this solution, to give a Fibonacci sequence of a finite length?
  2. Is it possible to use foldLeft, rather than scanLeft, to return a single value at position n in the sequence?
  3. Why doesn’t Stream’s scanLeft method enter an infinite loop, given that the input Stream is infinite? How must the implementation on this method differ from the implementation on List?

Give your answers in the comments!

Conway’s Game of Life in Scala

Posted by – September 2, 2012

… or, Cool Uses of flatMap and Sets

Via Hacker News I found a blog post about  Conway’s Game of Life in Scala, claiming to solve it in 10 lines. The author’s aim was to translate from a short piece of Clojure. The result is… well, take a look at that blog and judge for yourself.

Now this might be the inevitable result of trying to translate from a dynamic syntaxless language made up of S-expressions (whatever the heck they are), but surely Scala is capable of something more comprehensible. So, stepping into my Code Golf slacks and wielding the book of Wikipedia, here’s what I came up with:

def vicinity (p: (Int, Int)) = for { dx <- Set(-1,0,1)
                                     dy <- Set(-1,0,1) } yield (p._1 + dx, p._2 + dy)

def next (ps: Set[(Int, Int)]) = ps flatMap vicinity filter { p =>
  val ns = vicinity(p) - p count ps
  ns == 3 || ns == 2 && ps(p)
}

def display (width: Int, height: Int, ps: Set[(Int, Int)]) =
  Seq.tabulate(height, width) { (y, x) => if (ps(x, y)) 'X' else '.' } map (_.mkString)

Not optimized, but hopefully that’s not too unreadable (and it’s only like 5 lines, if my lines were as long as Original Blogger’s). Some explanation, if required:

vicinity takes a grid point and returns the 3×3 set of points centred on that one.

next takes a Set of points and outputs the next set. Instead of looking at every point on our infinite plane, we just consider the ones surrounding our set of points (since these are the only ones that can have neighbours), which is `ps flatMap vicinity`.

The points alive in the next generation are determined by the number of neighbours (ns), which is the points in the vicinity minus itself (`vicinity(p) – p`), counted if they were alive in the previous generation. See how we can use the Set `ps` as a function, since Set extends Function. If there are 3 neighbours, the point is alive. If there are 2, the point is alive only if it was already alive. Otherwise the point is dead (filtered out).

display just turns a set of points into something displayable, a sequence of Strings

Now, this isn’t exactly equivalent to the other version, since that requires you to supply functions for the number of neighbours, whereas I’ve already incorporated them. (It would be easy enough to do it like that – exercise for reader etc – but I didn’t really see the point.)

Anyway, by now I’m sure you’ve pasted the above into your REPL and are disappointed that no gliders have yet started whizzing around your screen. Worry not, young Grasshopper! You just need to supply some data and iterate:

  val g = Set((2, 0), (2, 1), (2, 2), (1, 2), (0, 1))
  val frames = Seq.iterate(g, 100)(next)
  frames foreach { f => display(25, 25, f) foreach println; println(); Thread.sleep(100) }


Recognise that? Yes, it’s a glider, the universal symbol of people with too much time on their hands.

Now, go and build a GUI.

Scala need-to-knows

Posted by – July 13, 2012

You know Java. You’ve heard Scala is some awesome lean-and-mean, pure-OO, functional version of the language, but are daunted by its perceived complexity and all those underscores. The good news is that it’s really not that hard, at least, not when you understand these morsels of knowledge:

use the REPL

Once you’ve added the SCALA_HOME directory to your path, you can load the REPL by typing “scala” at the command line. Use it!

the apply method

foo(...)
//
// is short for
//
foo.apply(...)

This is one bit of syntactic sugar that you just have to know.

It’s useful because now the syntax for applying a function is the same as the familiar syntax for calling a method, and the distinction between methods and functions begins to melt away.

functions are objects

Functions in Scala are objects just like Strings or Ints; their type depends on their “arity”, in other words how many arguments they take. For example a function that takes an Int and returns a String is of type `Function1[Int, String]`, which can be written as `Int => String`. A function that takes an Int and a String and returns a Char is type Function2[Int, String, Char], aka `(Int, String) => Char`.

There’s often confusion between what is a “function”, “method”, “function object” or “function literal”. In Programming in Scala they refer to “functions” and “methods” interchangeably; however the community consensus is that “method” should be used for `def`s, and `function` reserved for function objects as described above.

Methods can be used as functions: if you write a method name where a Function object is required, the compiler will create a Function object for you.

expressions everywhere

In functional languages, almost everything is an expression, i.e. it evaluates to something. This is incredibly useful. Important examples are if-expressions, try-catch-finally, and for-expressions:


val x = if (true) 42 else 101  // x is now 42

val y = try io.Source.fromFile("somefile.txt") catch { case _ => sys.error("ZOMG") }

val z = for (i <- 1 to 3) yield i * 2 // z is Vector(2, 4, 6)

singletons / companion objects

In Java, everything must be declared within a class or enum. In Scala, we have classes, but also the `object` keyword, which is used for declaring singleton objects. Use objects for declaring what would have been static methods in Java, static data, enumerations, implicits, factory methods, your main method, anything that you might want to import into another scope, basically.

vals and vars

`val` and `var` are used to declare values / variables (in a method), or properties (in a class / object). `val` values are immutable; `var` variables are not. Always use `val` unless you have a good reason not to; mutability is A Bad Thing.

object Foo {
  val size = 42  // constant property, with getter of same name
  var age = 33   // variable property, with getter and setter of same name
  def foo = {
    val n = 100  // final local variable
    var i = 0    // non-final local variable
  }
}

def vs val vs lazy val

Each of these defines a value.

`def` will re-evaluate every time it’s called, and can take parameters, so it’s like a method in Java when defined on an object, but it can also be defined locally within methods.

`val` is eagerly evaluated only once.

`lazy val` is lazily evaluated (i.e. not before it’s actually called) once, and is useful, say, when it makes an expensive calculation that won’t always be used. Also often useful in recursion. Think of it as a no-arg method that caches itself.

the meaning of _

_ is Scala’s wildcard character, similar to * in Java. It has a number of meanings, detailed here, most of which are quite advanced and you don’t need to know them… just yet anyway. :)

Predef and pre-imported stuff

By default the following are imported:

scala._
scala.Predef._
java.lang._

So if you are wondering how your code already knows what a “Seq” is, or where “->” or “println” comes from, it’ll be in one of these, which you can browse in Scaladoc.

for-loops

Scala doesn’t have for-loops corresponding to

for (int i = 0; i < 10; i++) { ... }

But this is to be celebrated, because a) they’re a pain to write, and b) in Java you should be using an “enhanced-for” (i.e. for each) loop most of the time anyway. Scala goes further and nudges you away from using loops at all, because they’re inherently imperative.

// Using while-loop
var i = 0
while(i < 10) {
  ...
  i += 1
}
// Using Scala for-loop
for (i <- 1 to 10) {
  ...
}
// Using collection functions
1 to 10 foreach { i => ... }

The while-loop might be faster than the for-loop or foreach, as of Scala 2.9, but optimizations are apparently forthcoming. But if you use functional patterns, you shouldn’t need these often, except maybe for I/O.

functional style

All you need to do to write in a functional style is to always use immutable variables and datastructures. That’s it.

Don’t mutate an object by changing a property: return a new copy, just like you did with String in Java. Paradoxically, this is sometimes more efficient than updating an existing structure, since immutability means that most of the existing structure can be re-used.

Instead of looping, perform a map or fold operation on a collection, or recursion if need be. Now you’re 90% of  the way there!

operator-style method calls

// "Infix" notation
obj.method(argument)
// can also be written
obj method argument

This also works if your method doesn’t take an argument (“postfix notation”), but is discouraged since it can interfere with semicolon inference:

obj.method
// can also be written
obj method

Why use these? It can make your code read more clearly, particularly when your methods have operator character names. For instance, 1 + 2 is clearer than its equivalent 1.+(2) .

right-associative methods

Methods that end with a : character are right-associative when you use them without the dot. e.g.


1 :: List(1,2,3)
// is the same as
List(1,2,3).::(1)

Here, :: is a method on the List, with 1 as the argument.

optional parentheses on method calls

If a method takes no arguments, then the empty parentheses can be omitted. This reduces clutter.

There is a convention whereby parentheses are included when a method has side-effects (i.e. the method does something, rather than return a value), for instance the next() method on an iterator.

val list = List(1,2,3)
val a = list.toString   //good
val b = list.toString() //bad
val it = list.iterator  //good
val c = it.next         //bad
val d = it.next()       //good: has side effects (changing the state of the iterator)

operator characters

Scala allows you to use symbols for identifiers (i.e. your variable / class names). Some characters are classed as alphanumeric (e.g. a1£$), some as operators (<+&*). Some you can’t use at all ([`;.). See here for the guide. The catch is, you can’t mix operators and alphanumerics in a given identifier (unless separated by an underscore).

rich types

You’ll see things like “1 to 10”, and after a while you’ll figure out that “to” is a method being called on “1” with a “10” argument. So you check out the Scaladocs, and find that “Int” has no “to” method. What’s going on? Well, it tells you in little letters at the top that there is an implicit conversion to RichInt, so you’ll need to look there instead. Here are some such implicit conversions that are useful to know about:

Int    -> RichInt
Char   -> RichChar
// etc for all primitives
Array  -> ArrayOps
String -> StringOps

Also, you won’t find `String` in the documentation, except for a type definition that tells you it’s really `java.lang.String`. So you’ll need to keep a link to the Java docs handy if you need to look up its methods (if you’re on Windows, this download is super-useful).

what are implicits?

Implicit values allow you to take values from the present scope as input into a function without having to specify them explicitly (i.e. type them out) in the function call. There can only be one of any given type in scope at a time (else, you get a compile error telling you of the ambiguity when you try to use it). The compiler looks for implicit values that are a) imported (in the default imports or by you), b) in the class’s companion object, or c) in a bunch of other places (which you can google).

An example is the `sorted` method on a `List`, which takes and implicit `Ordering[A]` argument. Say you want to sort List(1,2,3). Its `sorted` method requires an `Ordering[Int]` object to be in scope.

Implicit conversions are applied by the compiler when it finds an object of type A in a context where it requires one of type B, i.e. as an argument, or as an object where the method being called is only available on B. If there is an implicit function A => B in scope, this will automatically be applied. This can be very useful, for simulating extension methods and in DSLs, but generally should be avoided in everyday code since it can make code confusing to read and maintain.

methods of unit type

`Unit` is Scala’s equivalent of the `void` return type. You generally won’t use these when programming in a functional style, except perhaps in a `main` method. You can write them in two ways:

def doSomething: Unit = println("this method returns nothing")
// or
def doSomething {
  println("this method returns nothing")
}

function syntactic sugar

This is perhaps one of the most confusing things for the Scala novice, coupled with the fact that there are multiple ways to declare functions.

Let’s take a simple example of a function that adds 1 to an Int.


def addOne(x: Int) = x + 1

But wait! Didn’t we just say that this is a method, not a function? Yes, but the compiler will automatically convert this method to a function object if we use its name in such a context (e.g. as an argument). We can also manually turn this into a function object using an underscore, which represents the missing arguments:

val f = addOne _ 

Now let’s try defining the same thing the long way:

val addOne = new Function1[Int, Int] { def apply(x: Int) = x + 1 }

That’s quite verbose, so here’s where the `=>` keyword comes in; the following is exactly equivalent to the new object declation above:


val addOne = (x: Int) => x + 1

But we can do better! The repeated `x` is unnecessary; we can use an underscore:


val addOne = (_: Int) + 1

If the compiler can infer the type, we don’t need the type annotation. This could be in a situation where we’re entering an anonymous function as an argument, or if we’re simply supplying the information on the left hand side:

val addOne: Int => Int = x => x + 1
// or
val addOne: Int => Int = _ + 1

Which of these to use? Generally I use `def`, since the syntax is more familiar, and they can be type-parameterized (think generics) which makes them more flexible.

“as varargs” : _*

When using a method that takes varargs, i.e. a sequence of arguments of unspecified length, but you have a collection object that you want to enter, you can put : _* after it, to “type” it as individual elements:


Vector(1,2,3) // Vector's apply method takes varargs

val xs = List(1,2,3)

Vector(xs) // Vector(List(1,2,3)) - a Vector with a single List element: NOT what we wanted!

Vector(xs: _*) // = Vector(1,2,3)

imports

Imports are much more flexible than in Java. You can have an import anywhere, not just at the top of a file, and it’s confined to that scope. You can even import the methods on a variable!

val xs = List(1,2,3)
import xs._
reverse // = List(3,2,1)

scaladocs at the ready

First, find the docs on your hard drive (somewhere along the lines of “scala2.9/doc/scala-devel-docs/api/index.html”). Bookmark this page and leave it open in your browser.

To find a class, object, trait or package, type its name into the box in the top-left.

Often classes / traits have a companion object containing utility methods: to to switch, click on the circle next to the name in the main window that looks like it’s peeling off, or on the little blue “o” next to the class name in the search column.

All methods from supertypes are shown by default, which is generally useful, but experiment clicking the “ordering by inheritance” button.

To search for a method by name where you don’t know the class, click on the appropriate letter of the alphabet under the search box.

Big improvements to Scaldoc are apparently coming in Scala 2.10!

A more precise timer for Java

Posted by – August 2, 2011

I was trying to benchmark a Swing app I’d written, but found I was reaching a ceiling at 1000 frames per second. The source of this ceiling turns out to be the fact that, on Windows at least, there’s no way to set up a timer for less than 1 millisecond. I tried the 2-argument version of Thread.sleep(), I tried Object.wait(), I tried java.util.concurrent.locks.LockSupport.parkNanos(), I tried constructing a Timer with 0 initial delay… still no joy. There’s no problem timing things with System.nanoTime(), but there’s no way to control things… until now!

I knocked together the following extremely dirty solution in about 10 minutes:

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.Timer;

public class NanoTimer {

    public final int TARGET_DELAY_NS = 200;
    public final int POLL_FREQ_MS = 1000;
    private int updates = 0;
    private int cycles = 500 * TARGET_DELAY_NS;

    private Timer rateChecker = new Timer(POLL_FREQ_MS, new ActionListener() {

        @Override
        public void actionPerformed(ActionEvent e) {

            double delay = POLL_FREQ_MS * 1000.0 / updates;
            double ratio = delay / TARGET_DELAY_NS;
            cycles /= ratio;
            updates = 0;
        }
    });

    private class QuickTimer implements Runnable {

        @Override
        public void run() {
            while (true) {
                updates++;
                doWork();
                for (int i = 0; i < cycles; i++) {
                    double x = i/7;
                }
            }
        }
    }

    public void go(){
        new Thread(new QuickTimer()).start();
        rateChecker.start();
    }

    public void doWork(){
        // Add your work here
    }

    public static void main(String[] args) {
        new NanoTimer().go();
    }
}

Can you see how it works? If you’re old enough to remember the 8-bit computers of the early ’80s, you may know that a common technique for pausing in languages (i.e. BASIC) with no PAUSE command, was to loop a large number of times (how many exactly was left to trial and error). And that’s what we do here, except the computer does the trial and error for us and dynamically updates the number of cycles in the loop.

It’s not quite as bad as it sounds, because on a multi-core processor this will only take up one core, leaving your actual application run in the other(s). My test application running on full burn slowed down by only about 18%. Here it is repainting a GUI at over 5000 frames per second:Adding some bell and whistles to allow things like stopping it, changing the delay and poll freqency, adding constructors, getting it to behave more like the standard Swing Timer (i.e. throwing out ActionEvents) complicates things a bit, but here goes anyway:

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.Timer;

public class NanoTimer {

    private double TARGET_DELAY_NS;
    private int POLL_FREQ_MS;
    private long updates = 0;
    private int cycles;
    private int cyclesLast = 0;
    private boolean isRunning = false;
    private boolean stopping = false;
    private boolean doneInitializing = false;
    private double dummy;
    private final PublicTimer PUBLIC_TIMER = new PublicTimer();

    // Swing's Timer class's method to fire events is protected, so we need to extend it
    // to fire off events manually
    private class PublicTimer extends Timer {

        private PublicTimer(){
            super(Integer.MAX_VALUE, null);
        }

        public void fireActionPerformedPublic () {
            fireActionPerformed(new ActionEvent(NanoTimer.this, 0, ""));
        }
    }

    private class QuickTimer implements Runnable {

        @Override
        public void run() {
            while (!stopping) {
                updates++;
                if(doneInitializing) {
                    PUBLIC_TIMER.fireActionPerformedPublic();
                }
                for (int i = 0; i < cycles; i++) {
                    dummy = i/7;
                }
            }
            stopping = false;
            isRunning = false;
            doneInitializing = false;
        }
    }

    private Timer rateChecker = new Timer(POLL_FREQ_MS, new ActionListener() {

        @Override
        public void actionPerformed(ActionEvent e) {
            cyclesLast = cycles;
            double delay = POLL_FREQ_MS * 1000.0 / updates;
            double ratio = delay / TARGET_DELAY_NS;
            cycles /= ratio;

            float cyclesRatio = ((float) cyclesLast) / cycles;
            if(cyclesRatio < 1.1 && cyclesRatio > 0.9)
                doneInitializing = true;
            updates = 0;
        }
    });

    public NanoTimer(int delayNanos) {
        this(delayNanos, null);
    }

    public NanoTimer(int delayNanos, ActionListener al) {
        this(delayNanos, 100, al);
    }

    public NanoTimer(int delayNanos, int pollFreqMillis, ActionListener al){
        if(pollFreqMillis * 1000 / delayNanos < 10) {
            throw new IllegalArgumentException("Poll frequency must be 10 times or greater than the delay");
        }
        TARGET_DELAY_NS = delayNanos;
        POLL_FREQ_MS = pollFreqMillis;
        rateChecker.setDelay(POLL_FREQ_MS);
        cycles = (int)(500 * TARGET_DELAY_NS);
         addActionListener(al);
    }

    public void start(){
        if(!isRunning) {
            Thread nanoThread = new Thread(new QuickTimer());
            nanoThread.start();
            rateChecker.start();
            isRunning = true;
        }
    }

    public void stop(){
        if(isRunning) {
            stopping = true;
            rateChecker.stop();
        }
    }

    public int getPollMs() { return POLL_FREQ_MS; }
    public void setPollMs(int POLL_FREQ_MS) {
        if(POLL_FREQ_MS * 1000 / TARGET_DELAY_NS < 10) {
            throw new IllegalArgumentException("Poll frequency must be 10 times or greater than the delay");
        }
        doneInitializing = false;
        this.POLL_FREQ_MS = POLL_FREQ_MS;
        rateChecker.setDelay(POLL_FREQ_MS);
     }
    public double getDelayNs() { return TARGET_DELAY_NS; }
    public void setDelayNs(double TARGET_DELAY_NS) { this.TARGET_DELAY_NS = TARGET_DELAY_NS; }
    public void addActionListener(ActionListener al) {PUBLIC_TIMER.addActionListener(al); }
    public void removeActionListener(ActionListener al) {PUBLIC_TIMER.removeActionListener(al); }
} 

It’s far from perfect: in particular:
– changing poll frequency while running sometimes stops events altogether
– it’s not thread-safe: strange things might happen due to methods accessing the instance variables as they’re changed by the setter methods
– the initialization period before events are fired could be made a lot shorter, perhaps using System.nanoTime

However it does a pretty good job under a normal conditions. Firing a million events per second? No problem. Here’s a test class which you can play around with:

class NanoTimerTest {

    public static void main(String[] args) {
        NanoTimer n = new NanoTimer(200);
        final TestListener tl = new TestListener();

        Timer t = new Timer(1000, new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                tl.getUpdate();
            }
        });
        n.addActionListener(tl);
        t.start();
        n.start();
        sleep();
        System.out.println("Change poll");
        n.setPollMs(50);
        sleep();
        sleep();
        System.out.println("Change delay");
        n.setDelayNs(2);
        sleep();
        System.out.println("stopping");
        n.stop();
        sleep();
        System.out.println("starting");
        n.start();
        sleep();
        System.out.println("removing ActionListener");
        n.removeActionListener(tl);
        sleep();
        System.out.println("adding ActionListener");
        n.addActionListener(tl);
    }

    static void sleep() {try{Thread.sleep(3000);}catch(Exception e){}}

}

class TestListener implements ActionListener {

    private int count = 0;
    private long t0 = System.currentTimeMillis();

    @Override
    public void actionPerformed(ActionEvent e) {
        count++;
    }

    public void getUpdate() {
        long t1 = System.currentTimeMillis();
        System.out.printf("TestListener received %d events in %.2f seconds%n", count, (t1 - t0) / 1e3);
        count = 0;
        t0 = t1;
    }
}

Let me know if you find this useful for anything!

Composition vs Inheritance: Converting Java’s Swing Timer class to Scala

Posted by – July 27, 2011

I’ve been having a look at using Swing in Scala. Java’s Swing is messy, verbose, buggy, and unintuitive. Scala sweetens things a bit, although if we’re to believe the rumours from the EPFL, the Observer Pattern, around which Swing is based, is more of an anti-pattern and should be deprecated. So maybe Swing’s days are numbered, but in the current absence of anything better, I’m diving in.

Scala has cleaned up some of the names and classes to make things a bit simpler, but there are some things missing, and Timer is one of them. This isn’t too much of a big deal, because you can still just use the Java version, but it would be nice if you could treat it in the same way as you do button clicks, using a Publisher / Reactor model, rather than Java’s Listeners (more details here).

So to bring up a Frame with a coloured background that changes according to a Timer, I did this:

import swing._
import java.awt.{Graphics, Color}
import java.awt.event.{ActionEvent, ActionListener}
import javax.swing.Timer

object ColorPanel extends SimpleSwingApplication {
  var c: Color = new Color(0)

  def top = new MainFrame {
    title = "Flash!"
    contents = p
  }

  val p = new Panel with ActionListener {
    preferredSize = new Dimension(200, 200)

    override def paintComponent(g: Graphics2D) {
      g.setColor(c)
      g.fillRect(0, 0, size.width, size.height)
    }

    def actionPerformed(e: ActionEvent) {
      c = new Color((c.getRGB() + 1000) % 16777216)
      repaint
    }
  }

  val timer = new Timer(100, p)
  timer.start()
}

That should be pretty simple to understand. Our application is a SimpleSwingApplication, which requires the top window to be specified in a method called top. We then define a Panel, and override the paintComponent method, just as in Java. We implement ActionListener‘s actionPerformed method, and here goes what we want the panel to do when it receives an event (i.e. change colour and repaint). Finally we specify the Timer and start it.

In Scala Swing, to react to an event, you listenTo a Publisher. So we want to make a Java Timer into a Publisher.

I started by making my ScalaTimer a Component, because you get Publisher / Reactor functionality for free. (This doesn’t really make sense, and actually all we need to do is to implement the Publisher trait.) The other way I thought of was to directly extend Java’s Timer class – although I wasn’t convinced this was the way, because the provided classes don’t seem to subclass their Java peers (they do some kind of wrapping with a peer value, which I don’t understand). Unsure which is best, I tried both.

1) Wrapping it (composition)

case class TimerEvent (source: AnyRef) extends swing.event.Event

class ScalaTimer(delayTime: Int) extends swing.Publisher {
  outer =>

  private val t = new javax.swing.Timer(delayTime, new java.awt.event.ActionListener {
    def actionPerformed(e: java.awt.event.ActionEvent) {
      publish(new TimerEvent(outer))
    }
  })

  def addActionListener(listener: java.awt.event.ActionListener) {t.addActionListener(listener)}
  def fireActionPerformed(e: swing.event.ActionEvent) {publish(e)}
  def actionCommand: String = t.getActionCommand
  def actionListeners: Array[ java.awt.event.ActionListener ] = t.getActionListeners
  def delay: Int = t.getDelay
  def initialDelay = t.getInitialDelay
  def listeners[A <: java.util.EventListener](listenerType: Class[A]) = t.getListeners(listenerType)
  def coalesce: Boolean = t.isCoalesce
  def repeats: Boolean = t.isRepeats
  def running: Boolean = t.isRunning
  def removeActionListener(listener: java.awt.event.ActionListener) {t.removeActionListener(listener)}
  def restart() {t.restart()}
  def actionCommand_=(command: String) {t.setActionCommand(command)}
  def coalesce_=(flag: Boolean) {t.setCoalesce(flag)}
  def delay_=(delay: Int) {t.setDelay(delay)}
  def initialDelay_=(initialDelay: Int) {t.setInitialDelay(initialDelay)}
  def repeats_=(flag: Boolean) {t.setRepeats(flag)}
  def start() {t.start()}
  def stop() {t.stop()}
}


object ScalaTimer {
  import javax.swing.Timer
  def getLogTimers: Boolean = Timer.getLogTimers
  def setLogTimers(flag: Boolean) {Timer.setLogTimers(flag)}
}

If that’s confusing, here are some explanations:

  • outer => is an alias which is a self-reference. It’s like this, except this isn’t always in scope, i.e. in inner classes, so we need to define an alias for the outer scope specifically
  • We instantiate a private Timer t, giving it an anonymous ActionListener, which publishes a TimerEvent whenever it gets an ActionEvent from t
  • We have to make our own Event type, because Scala’s ActionEvents require a Component to be specified as their source, and ScalaTimer isn’t a Component
  • I used fully qualified names to help avoid confusion, since there are both Scala and Java ActionEvents
  • I changed the method names to fit the Scala conventions, so instead of myTimer.getDelay(), we have myTimer.delay, and instead of myTimer.setRepeats(true), we state myTimer.repeats = true. Personally I think the _= syntactic sugar for setters can be confusing, since it’s syntactically the same as assigning a value to a field, so while you might think you’ve set a field to equal your object, it’s almost certainly done something else, like copying values.
  • We have a companion object at the end which allows us to include Timer’s static methods

Overall this was pretty straightforward, once I’d found out how to use aliases, although it involved quite a bit of typing, copying the methods from Timer’s javadoc.

2) Extending javax.swing.Timer (inheritance)

class ScalaTimer2 (delay: Int)
      extends Timer(delay, new ActionListener { def actionPerformed(e: ActionEvent) {} })
      with swing.Publisher {
  outer =>

  removeActionListener(getActionListeners.apply(0))

  addActionListener(new ActionListener {
    def actionPerformed(e: ActionEvent) {
      publish(new TimerEvent(outer))
    }
  })
}

object ScalaTimer2 {... same as ScalaTimer ...}

OK, this was a little tricky. Coming from a Java background, Scala’s constructors are a bit weird. If the base class constructor contains arguments, you have to pass these in your subclass signature, and the only values you have available are from the subclass’s arguments. Timer has only one constructor, which takes two arguments, an integer delay and an ActionListener. So we need to supply an ActionListener either by taking one in the main argument list, or generating one, as above.

Unfortunately neither a reference to self or the publish method will be available to pass in, because the object doesn’t yet exist. So above, we pass a dummy ActionListener which we then remove, then add a real one containing the publish method.

I also did a version using an auxiliary constructor taking just an Int, which I shortened to the above. Then I made the primary constructor private, similar to the example below.

Postscript: Actually it’s easier than this. The Timer you send to the Java constructor can be null. So all you need is:

class ScalaTimer2 (delay: Int) extends Timer(delay, null) with Publisher {
  outer =>
  addActionListener(new ActionListener {
    def actionPerformed(e: ActionEvent) {
      publish(new TimerEvent(outer))
    }
  })
}

Just add a companion object containing those pesky static methods, and that’s it!

3) Extending Timer, but using a factory method

Notice that adding a dummy ActionListener is a workaround rather than a solution, and in the general case, such methods won’t be available. Instead, we can avoid the constructor and use a factory method. Kipton Barros on StackOverflow showed me how to do this, using the companion object’s apply method, so a new timer can be invoked just like with a constructor, except without the new keyword.

class ScalaTimer3 private (delay: Int, listener: java.awt.event.ActionListener)
      extends javax.swing.Timer(delay, listener) with swing.Publisher {
  // no body!
}

object ScalaTimer3 {
  def apply(delay: Int): ScalaTimer3 = {
    lazy val ret: ScalaTimer3 = new ScalaTimer3(delay, new java.awt.event.ActionListener {
      def actionPerformed(e: java.awt.event.ActionEvent) {
        ret.publish(TimerEvent(ret))
      }
    })
    ret
  }
  // + static methods here
}

This cleverly uses a lazy val, which (for reasons not entirely understood) allows reference to itself within the inner class.

Note also I’ve added the private keyword to the primary constructor, so that only the object’s apply method is available.

Conclusion

So which solution is best? Well, given infinite time and patience, I would favour the first solution, where we compose rather than inherit. It’s the most flexible, and allowed us to alter the method names, and indeed change method implementation where desirable (as you might notice I did with the fireActionPerformed method, taking a Scala ActionEvent rather than a Java one). I don’t really expect these precise challenges with the constructors to come up often, but it was an instructive exercise. Oh, and here’s the ColorPanel example updated with the new Timer:

import swing._
import java.awt.Color

object ColorPanel extends SimpleSwingApplication {

  def top = new MainFrame {
    title = "Flash!"
    contents = p
  }

  val timer = new ScalaTimer(100)

  val p = new Panel {
    var c: Color = new Color(0)
    preferredSize = new Dimension(200, 200)
    listenTo(timer)
    reactions += {
      case e: TimerEvent => {
        c = new Color((c.getRGB + 1000) % 16777216)
        repaint
      }
    }

    override def paintComponent(g: Graphics2D) {
      g.setColor(c)
      g.fillRect(0, 0, size.width, size.height)
    }
  }

  timer.start()
}

Garbage collection in Java while references still exist

Posted by – July 24, 2011

Who would have thought it, my first meaningful post is on garbage collection!

There’s a common misconception that objects can only be garbage-collected when there no longer exist any references to those objects. Actually, HotSpot goes one better, and garbage collects when it determines you’re not going to use those references again. Which might be in the middle of a method while your variables are still theoretically in scope.

Here’s how I know this? I’m unable to concentrate long enough to read any actual documentation on the garbage collector, but I found some surprising results from this experiment, which simply attemepts to add 17 million Foos to a list 4 times, catches out of memory errors, and prints its results:

import java.util.ArrayList;
import java.util.List;

public class Foo {

    public static void main(String[] args) {
        test1();
        test2();
    }

    static void test1() {
        List<Foo> a = new ArrayList<Foo>();
        try {
            for (int i = 0; i < 17000000; i++) {
                a.add(new Foo());
            }
        } catch (OutOfMemoryError e) {
            System.out.println("a: out of memory");
        }
        System.out.println("Created " + a.size() + " foos");
        
        List<Foo> b = new ArrayList<Foo>();
        try {
            for (int i = 0; i < 17000000; i++) {
                b.add(new Foo());
            }
        } catch (OutOfMemoryError e) {
            System.out.println("b: out of memory");
        }
        System.out.println("Created " + b.size() + " foos");
    }

    static void test2() {
        List<Foo> a = new ArrayList<Foo>();
        try {
            for (int i = 0; i < 17000000; i++) {
                a.add(new Foo());
            }
        } catch (OutOfMemoryError e) {
            System.out.println("a: out of memory");
        }
        System.out.println("Created " + a.size() + " foos");
        
        List<Foo> b = new ArrayList<Foo>();
        try {
            for (int i = 0; i < 17000000; i++) {
                b.add(new Foo());
            }
        } catch (OutOfMemoryError e) {
            System.out.println("b: out of memory");
        }
        System.out.println("Created " + b.size() + " foos");
        a.size(); // <-- IMPORTANT: REFERENCE TO a
    }
}

In test1() we get the results
Created 17000000 foos
Created 17000000 foos

indicating that there was sufficient memory to create a second list of 17000000 Foos.
In test2() we get
Created 17000000 foos
b: out of memory
Created 3392918 foos

The only difference is that in test2(), we needed to keep hold of List a, in order to evaluate a.size() at the end. And we ran out of memory, which indicates the memory must have been freed during the method in test1().

Welcome

Posted by – July 17, 2011

It is with great pleasure that I announce the launch of LuigiP.com!

Please be sure to check back in the future, when there is some content!