# Author:

## Introduction

Posted by – February 9, 2019

Chapter 1 of CLRS (which I may also refer to as ItA, since it’s easier to remember) is about “The role of algorithms in computing”. An algorithm is defined as any well-defined computational procecedure that takes an input and produces an output. Sounds to me a lot like a mathematical function, though I imagine an algorithm referring to the machinery that performs the computation, whereas a function is a description of a relationship. I also imagine it would be difficult to express many algorithms fully in mathematical symbols. But the distinction between an algorithm and the computer code of a function is less clear. The algorithm is the procedure, while the actual code will depend on the language you’re programming in.

More formally, an example is given where the Input and Output are stated, and the algorithm is correct if for every input instance, it halts with the correct output. (I like the sound of halting. It makes me think of the kind of computer Babbage would use, with clunking gears that finally stop and the dials come to a stop showing a number for the answer.)

Problems in the real world where algorithms are applied include:

• The Human Genome Project (sequencing, data storage, abalysis) – using human and machine resources efficiently
• The Internet – routing of data; search
• Cryptography for e-commerce
• Industry: placing oil wells, assigning crew to flights, political campaigning etc (these are Linear Programming)

ItA then talks about efficiency, and mentions that for some problems, no efficient solution is known. There is a subset known as NP-complete, for which no efficient algorithm has been found, but no-one knows if an efficient algorithm exists or not. If it does, then it’s been shown that all have an efficient solution. And many NP-complete problems are very similar to some problems for which we do have efficient solutions. NP-complete problems (e.g. the travelling salesman problem) come up very often, and while a “solution” might not be entirely efficient, it is possible to come up with “approximation algorithms”.

Example of different complexities is given in the form of insertion sort and merge sort. The former is O(n^2) while the latter is O(n lg n). Insertion sort is faster for small n, but there will always be a crossover point above which merge sort is the more efficient.

Finally, we’re asked to compute the largest size of n (the number of items the problem is applied to) that can be computed in different spaces of time, if an algorithm takes f(n) microseconds (millionths of a second) to complete. I spent a while using Excel’s “solver” to compute the answers numerically (which was difficult when using some of the huge numbers!), since I’m not sure an analytical way of solving some of these even exists. Doing the whole thing would be just a bit too tedious, since Excel only lets you solve one thing at a time, so I just did 1 second, 1 day, and 1 century, to various levels of precision. :)

## Let’s learn algorithms!

Posted by – February 2, 2019

In Scala, of course… a new series of articles begins

Back in the day (circa 2011), I cut my teeth on Java participating in algorithm competitions on a site called TopCoder. There was a cool little applet you would download, and you used it to navigate problems, enter your code, run tests, check out other people’s solutions, etc. I wrote a parser for the problems in the form of a Swing application that would spit out fully formed Scala test scripts and code templates, which allowed me to tackle the problems in Scala as well, which was rather neat… if I say so myself. I wasn’t very highly rated, and by “participating”, I mean mainly tackling the problem sets post facto in my own sweet time, but it was good fun, somewhat addicitive, and a way to keep the coding skills sharp. I must have done hundreds of them.

Well, applets went out of fashion, and TopCoder went into terminal decline (they have their problems on a website now, but it er… doesn’t really work). Fortunately there are a bunch of similar sites that have sprung up in the meantime, one of the best of which is CodeForces. Its interface is a bit less friendly for JVM programmers (everything’s done in strings via the standard in and out, which requires a bit of rather tedious parsing and formatting kerfuffle, rather than filling the gaps in a method with a provided signature and return type), but it does support a wider range of languages including Scala, and some more “out-there” ones like Rust, Kotlin, and Node.js. So I’ve been playing around with those competitions lately instead.

Now I seem to do okay on the easier problems, like the ones tagged “brute force” or “implementation”, but I’ve been struggling a bit with the more advanced ones, for instance requiring use of data structures. One that had me scratching my head recently required the use of a “segment tree”. Since you don’t get to use any libraries beyond the standard one, you have to program it yourself during the course of answering the question (or, I guess, if you’ve done it before, cut-and-paste one from your bag of tricks). Lacking a formal computer science education, I’d never heard of a segment tree, which makes it kind of tricky. So far I’ve counted on pretty much working things out myself from first principles each time I see something new – but, given the limited time we have on this planet, and the time it would take to re-invent computer science in my own head, I thought maybe it would be an idea to knuckle down and learn algorithms properly.

“Introduction to Algorithms” (pictured), aka “CLRS” after its authors, is a highly regarded reference book. So I’ve got hold of my own copy, but at over 1200 densely packed pages it’s not something I’m going to fly through in a weekend. I will work through it; one interesting challenge will be to try to implement any exercises in functional style, i.e. without side-effects or mutable state. In the book, the examples are in a Python-esque pseudocode with variables and loops a-go-go.

Another reference for this blog series, will be cp-algorithms.com, which I’m going to call “CPA”, and as the name suggests is a guide to competetive programming algorithms. It is itself a translation of a Russian site (as everyone knows, the best competitors are mostly Russian – they love their C++ out there). There are a LOT of topics, which are listed in alphabetical order rather than from simplest to most complex, so I’ll use CLRS as a guide to learning order, and CPA for some juicy and pertinent examples to tackle in Scala.

There only seem to be a handful of people currently using Scala in these competitions, and their style is mostly imperative. Let’s see if we can take the world of algorithm competitions by storm writing idiomatic Scala. It will be a journey!

## 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”.

```
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 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.

### 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) = {
println("Start")
println(x)
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 `B`s.

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?

## 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 it = list.iterator  //good
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)
```

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

private class QuickTimer implements Runnable {

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

public void go(){
rateChecker.start();
}

public void doWork(){
}

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 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) {
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;
}
});

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

public void start(){
if(!isRunning) {
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 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();
}
});
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();
}

}

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

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 =>
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++) {
}
} 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++) {
}
} 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++) {
}
} 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++) {
}
} 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!