[r-t] Scala, part one

[Mark Davies]

In my previous email I introduced the programming language Scala, and 
promised to show some examples of its utility in the field of composition.

This first article will focus on the functional programming style made 
possible in Scala. Functional programming will be familiar to those who 
have used languages such as Lisp, Forth, Clojure or Erlang, but is often 
alien to those of us brought up on C and Java. However, it is 
beautifully suited to many composing problems.

For instance, my first task in the Helixoid project was to generate some 
Helixoid methods. This is effectively a tree search, and it's very 
simple to write some functional Scala code to do the job.

First I created a function (just like a method in e.g. Java) called 
"search", like so:

def search(row: Row, pnSoFar: List[PN], rowsUsed: Set[Row]):
	List[Method] = { ...}

Variables are defined "back-to-front" compared to Java, so the search 
function here has three parameters, called "row", "pnSoFar", and 
"rowsUsed", which have types of "Row", "List[PN]" and "Set[PN]" 
respectively. The search method returns "List[Method]", which is nothing 
more than a List containing objects of type Method, and corresponds to a 
Java generic type such as List<Method>.

However, one key difference between the two languages is that, as in 
most functional languages, the default collection types are immutable. 
Hence, neither the set of place notation examined so far (pnSoFar) nor 
the set of rows produced in the lead so far (rowsUsed) can be modified.

This seems not very useful! But in fact it is exactly what we need in 
our search, to make sure separate branches of the search tree cannot 
overwrite each other's values. It means we have no need to "backtrack", 
as we must do with mutable data-structures, which dramatically 
simplifies our algorithm.

We can now implement the search using a simple recursive call:

def search(row: Row, pnSoFar: List[PN], rowsUsed: Set[Row]): List[Method] =
{
	if (rowsUsed.contains(row))
		return Nil
	else if (pnSoFar.size==HalfLeadLength-1)
		return new Method(pnSoFar.reverse)
	else
		AllPN.flatMap{ (pn)=> search(row.apply(pn),
			pn::pnSoFar, rowsUsed+row) }
}

We carry out a search for Helixoids by triggering the first recursive 
call, like so:

	search(Row("XXX....."), List(), Set())

And there we have a working tree-search algorithm. I hope you will agree 
this seems too simple to be true! Obviously we are relying on a little 
bit of support code: in particular classes Row and PN, which represent 
rows and place notations. However the main search is entirely embodied 
in the search function above.

Here's how it works.

The first thing to note is our initial row value: not rounds, but the 
masked string "XXX.....". A Helixoid must contain all 56 (=8x7) position 
of bells (123) within the 56-change half-lead, up to rotation of (123). 
Starting the search from "XXX....." and keeping track of which "rows" 
have been generated from this pattern is an easy way of enforcing the 
Helixoid rule. In fact, this starting pattern is the only thing which 
separates our search from a generic search for any method type.

The "rowsUsed" Set keeps track of which (XXX-style) rows we have 
generated in the current search branch. Every time we generate a new 
row, we create a new set (rowsUsed+row) and pass it to the recursive 
call of the search() function. Similarly, the pnSoFar List tracks the 
place notations generated in the current search branch, and we prepend 
the next pn before the recursive call, using the syntax pn::pnSoFar.

Because the Set and List instances are immutable, we create new 
instances on each call, and this means we don't have to worry about 
backtracking as we would normally need to do in a procedural language 
with mutable data structures. But wait! What about performance? Surely 
Scala is creating millions of new objects and cloning large 
data-structures on each call?

In fact, the immutable collection classes, which are part of Scala's 
standard library, are very clever and efficient. For instance, a Scala 
List is much more like a Lisp list than a java.util.List. Because it is 
singly-linked, very efficient head, tail and prepend operations are 
possible. If we already have a series of PN such as x18.1458.36, this is 
represented as a list of linked objects: x->18->1458->36->Nil. Scala can 
then add a new PN on the front simply by linking to the first "x", 
meaning the entire list does not have to be cloned. Millions of 
immutable list instances can be formed, each sharing the original tail 
of the list.

[Of course, we end up with the place notation for the half-lead the 
"wrong way round", with the final PN at the head of the list; but it's 
easy to reverse the list if we do find a valid Helixoid method, as you 
can see in the code above: new Method(pnSoFar.reverse).]

Another aspect of functional programming which is invaluable for our 
search is the idea of a "higher-order function". This is a function 
which takes as a parameter another function. Scala's collection classes 
use this idea heavily, for instance to implement map and filter 
operations on sets, lists and other collection types.

For example, suppose we had a set of rows (variable type Set[Row]) and 
wished to apply the same place notation to all of them. In Java we would 
need to write a loop to do this. In Scala, we just apply a "map" 
operation, like so:

	def applyPN(row: Row): Row = row.apply(pn)
	var newRows = oldRows.map( applyPN )

Here, the map() function returns a new set, comprised of every member of 
the old set, with the applyPN function applied to each.

We don't even need to explicitly declare the applyPN function. Scala 
supports "anonymous functions", which we can declare as follows:

	var newRows = oldRows.map( (row:Row) => row.apply(pn) )

The anonymous function is created by declaring its parameters in 
brackets (row:Row), then specifying the function literal => and finally 
the function implementation (row.apply(pn)).

Where the function passed has only one parameter, we can simplify this 
further, removing the parameter list and using "_" in place of the 
parameter name:

	var newRows = oldRows.map( _.apply(pn) )

Sometimes the code is clearer if we use the alternative brackets {} 
around the "higher-order" parameter:

	var newRows = oldRows.map{ _.apply(pn) }

I have used a higher-order function call in the search() function given 
above. Search() has three conditional branches, the first two of which 
are fairly self-explanatory, but here they are again with some comments:

	// Terminate recursion with a Nil (empty list) if we've already
	// had this (masked) row.
	if (rowsUsed.contains(row))
		return Nil
	// Otherwise, if we have a full half-lead's worth of PN, return
	// a List with a single Method in it, constructed from the PN.
	else if (pnSoFar.size==HalfLeadLength-1)
		return new Method(pnSoFar.reverse)

It is the third branch of the condition where the clever stuff happens:

AllPN.flatMap{ (pn)=> search(row.apply(pn), pn::pnSoFar, rowsUsed+row) }

"AllPN" is the set of all PN types we are interested in - for example, 
the minimal Set("x", "14", "58", "18") could be used, and does actually 
produce some useful Helixoids.

The "flatMap" call is a higher-order function defined on all collection 
types (including sets and lists), which works a little bit like the map 
function described above: the difference is that flatMap expects the 
function passed to it to return *another* collection of objects, and the 
results are "flattened" into a single master collection.

In diagramatic form, if the old set and the function parameter have 
these types:

	var oldSet: Set[X]
	def fn(x: X): Set[X]

then oldSet.map(fn) would give us a set of sets - Set[Set[X]] - but 
oldSet.flatMap(fn) gives us a plain old Set[X], because the individual 
sets returned from each call to fn() are combined.

This is just what we need for our search, because each recursive call 
can return zero, one or many valid Methods, and the flatMap operation 
will merge these together into a single list.

What about the function passed to the flatMap? It is an anonymous 
function, declared as:

	(pn)=> search(row.apply(pn), pn::pnSoFar, rowsUsed+row)

This takes a PN instance (one of those in the AllPN set) and then 
recursively calls the search function, with (a) a new row calculated by 
applying the pn to the current row; (b) a new pn list, created by 
prepending the current pn to the old list as described above, and (c) a 
new rowsUsed set, created by adding the old row to the old set.

[Notice how the anonymous function does not need to declare the type of 
the parameter, pn - Scala, although strongly-typed, has a sophisticated 
type inference system which means we can often leave it up to the 
compiler to work out the correct type. If in doubt, you can always 
specify the type, which we would do here by writing (pn:PN)=>... ]

Hence, the flatMap operation on AllPN effectively iterates through every 
PN possibility, recursively calling the search function on the results 
of each, and collating the results, all in a very neat, concise, 
easy-to-code way. Job done!

Well, not quite. With a 56-change halflead, the search space for 
Helixoids is reasonably large. The algorithm above needs some 
optimisation before it'll run in reasonable time. Again, Scala helps us 
here - we'll see more in the subsequent articles, where I hope to cover 
other interesting areas of the Helixoid project, but for now, let's keep 
looking at that recursive search function.

There are several things to note about the run-time behaviour of our search:

1. First, Scala code compiles down to (Java VM) bytecode. So, with a 
good modern JIT and heap manager, it's damn quick. I'm certain we could 
do still better with hand-optimised assembler or C, but I surely don't 
want to do that for a rapid, exploratory-style project such as this.

2. With one exception, we shouldn't be working the heap manager very 
hard with this code. Our maximum recursive depth is 56 (the length of 
the Helixoid half-lead), and we are generating a low number of 
relatively small objects at each stage, each of which will be free for 
collection once the call which allocated them has completed.

3. The exception is the result list. This is a major problem with the 
simple implementation given above: we are collating all our results into 
a big List, which we won't get to look at until the search is finished. 
We'll be waiting a long time, and there's a real danger we'll run out of 
memory trying to store all the results.

4. We're possibly doing a bit more work than we should in the "inner 
loop" of the recursion. For instance, we are calculating explicit PN 
permutations between rows; a standard composition technique is to 
pre-build a table of nodes, representing the entire search space, in 
order to avoid this overhead. By using a "masked" row of XXX.... we have 
avoided some of the cost - we only have a single "row" to generate in 
each node - but not all.

5. Finally, and most importantly, there are ways to prune the branches 
of our search tree. Pruning is the single most important optimisation 
for any tree-search algorithm. Here, we can note that, because of our 
use of a "masked" row, at each step in the recursion there may be 
several PN possibilities which give us the same effective result row. 
For example, from "rounds" (XXX.....) the place notations x, 56, 58, 
1256 and 1258 all give us the same result (XX.X....). These place 
notations will certainly generate different methods, but they will all 
have the same pattern for bells (123) and (45678). In other words, they 
will be trivial variations, and we really only need to list (and search 
for) one of them. There are plenty of other pruning possibilities, too: 
we can restrict the list of place notation (AllPN), and we could look 
for more restrictive method types, such as right-place methods, or 
Double methods.

In the remainder of this article we'll look at points (3) and (5). I'll 
discuss the node table idea in point (4) in the next article.

So, point (3) is the easiest to deal with. My initial design for the 
search() function was intended to show off some functional programming 
with ideas like the flatMap higher-order function. But Scala allows us 
to mix procedural programming with the functional stuff, so we can do 
something really simple here: let's not return anything from our 
function, and simply print each method we find. We get this:

def search(row: Row, pnSoFar: List[PN], rowsUsed: Set[Row])
{
	if (rowsUsed.contains(row))
		return
	else if (pnSoFar.size==HalfLeadLength-1)
		println(new Method(pnSoFar.reverse))
	else
		AllPN.foreach{ (pn) => search(row.apply(pn),
			pn::pnSoFar, rowsUsed+row) }
}

Here the return type (and the =) of the function definition have been 
removed; we use println (the concise Scala equivalent of Java's 
System.out.println) to output methods as we find them; and flatMap() is 
replaced by foreach(), another higher-order function which simply 
applies a function to all members of a collection, discarding any results.

We could have stayed "pure functional" by, for example, passing in a 
function which would be called when each Helixoid is found, however for 
our quick-and-dirty search a hard-wired println() is fine.

Scala does have a very neat and powerful "for" loop, which can be used 
to rephrase the higher-order functions such as filter, map and foreach, 
so we could write the following code instead, which might look more 
familiar than the "foreach":

	for (pn <- AllPN)
		search(row.apply(pn), pn::pnSoFar, rowsUsed+row)

Here we have two ways of expressing the same thing, but it is a nice 
demonstration of how naturally Scala combines the procedural and 
functional paradigms.

Now to address point (5). If we can solve this, we've got some chance of 
exhausting the search space in a reasonable length of time.

The first thing to do is to avoid place notations that give a trivial 
variation of a notation we have already tried. One way to do this is to 
use a mutable Set to keep track of all the result rows we have seen so 
far, thus:

	// Declare an empty mutable set of Rows
	val rowsSeenThisTime = mutable.Set[Row]()
	for (pn <- AllPN)
	{
		val newRow = row.apply(pn)
		if (!rowsSeenThisTime.contains(newRow))
		{
			rowsSeenThisTime+= newRow
			search(newRow, pn::pnSoFar, rowsUsed+row)
		}
	}

Alternatively we could have used an immutable Set, and instead of using 
a "constant" variable (defined with "val", and the equivalent of Java's 
"final" keyword), we could use a re-assignable variable (defined with 
"var"):

	// Declare an empty immutable set of Rows
	var rowsSeenThisTime = Set[Row]()
	for (pn <- AllPN)
	{
		val newRow = row.apply(pn)
		if (!rowsSeenThisTime.contains(newRow))
		{
			rowsSeenThisTime+= newRow
			search(newRow, pn::pnSoFar, rowsUsed+row)
		}
	}

Note how the rest of the code does not change at all! The operator += is 
the equivalent of saying
	rowsSeen = rowsSeen+newRow
if rowsSeen is an immutable Set, but changes to just
	rowsSeen.+(newRow)
if it is mutable. [Observe that "+" is a method, which does exactly the 
same as the "add" method when applied to a mutable Set:
	rowsSeen.add(newRow)
Scala does not in fact have operators: everything is a method! We can 
define methods with symbolic names, like + or ::, and use them with 
either infix notation, a + b, or dotted notation, a.+(b). We can also 
use the infix syntax for "normal" methods with one parameter: a add b. 
This flexibility may seem frightening to start with - but fear not!]

Whether we code this with mutable or immutable sets, we are likely to 
end up with something pretty quick, since Scala's collection library 
provides super-efficient hard-wired collection classes for instances 
with low member sizes.

One final improvement to make to the algorithm in this article: let's 
implement a right-place search. To do this, we simply need to filter the 
list of PN candidates to ensure, if a cross was rung in the last change, 
places are made in the next, and vice versa. This little helper function 
sums that up:

	def isRightPlace(thisPN: PN, prevPN: PN): Boolean =
		thisPN.isCross != prevPN.isCross

Here we are relying on the "isCross()" method from the PN class, which 
we can assume is a library routine. The interesting thing to spot here 
is that, if a function takes no parameters, the () brackets are 
optional, so we write "pn.isCross" instead of "pn.isCross()".

We can now apply some more functional magic by filtering our AllPN list 
using the higher-order filter() method of Scala's collection library:

	for (pn <- AllPN.filter{ isRightPlace(_, pnSoFar.head) })

We have made a slight modification to just one line of code, and as if 
by magic a right-place search algorithm has popped out!

Well, we do need to be a little careful here: we probably want to make 
sure the search starts with a x change, and you may have noted the call 
"pnSoFar.head", which might not work if the pnSoFar list is initially empty.

These objections could be handled within the search loop, but in fact it 
is easier just to modify the way we initiate the recursion. Since there 
is no choice of first PN, let's jump immediately to the second change:

	search(Row("XX.X...."), List(PN("x")), Set(Row("XXX.....")))

Here is the complete implementation of our search (with a small bit of 
refactoring to make it neater; in particular we now expect the rowsUsed 
set to contain the row parameter already, and in doing so the 
rowsUsed.contains check can be combined with rowsThisTime.contains):

object HelixoidSearcher
{
	val HalfLeadLength = 56
	val AllPN = Set(PN("x"), PN("14"), PN("58"), PN("18"))

	def main(args: Array[String])
	{
		val rounds = Row("XXX.....")
		val startPN = PN("x")
		val row2 = rounds.apply(startPN)
		search(row2, List(startPN), Set(rounds, row2))
	}

	def isRightPlace(thisPN: PN, prevPN: PN): Boolean =
		thisPN.isCross != prevPN.isCross

	def search(row: Row, pnSoFar: List[PN], rowsUsed: Set[Row])
	{
		if (pnSoFar.size==HalfLeadLength-1)
		{
			println(new Method(pnSoFar.reverse))
			return
		}
		val rowsThisTime = mutable.Set[Row]()
		for (pn <- AllPN.filter{isRightPlace(_, pnSoFar.head)})
		{
			val newRow = row.apply(pn)
			if (!rowsThisTime.contains(newRow) &&
				!rowsUsed.contains(newRow))
			{
				rowsThisTime+= newRow
				search(newRow, pn::pnSoFar,
					rowsUsed+newRow)
			}
		}
	}

}

With the four place notations specified, the program above runs to 
completion in a few seconds, searching half a million possible 
rows/place notations, and producing the following output:

-14-18-14-18-58-18-58-58-58-18-18-14-14-18-58-58-18-18-14-14-14-18-14-18-58-18-58- 
-14-18-14-18-58-18-58-18-18-18-58-18-14-18-14-14-14-18-18-18-18-18-18-14-14-18-18- 
-18-14-14-58-58-14-58-18-18-14-18-58-18-18-18-14-18-58-18-18-14-58-14-14-58-58-18- 
-18-14-14-18-18-14-14-18-18-18-14-58-14-18-58-14-58-18-18-18-58-58-18-18-58-58-18- 
-18-14-14-18-18-18-18-14-18-14-18-18-58-18-14-18-14-18-18-18-14-18-58-18-58-14-18- 
-18-58-14-18-14-18-58-18-18-18-58-18-58-18-14-18-18-58-18-58-18-18-18-18-58-58-18- 
-18-18-58-58-18-18-18-18-18-18-58-58-58-18-58-18-14-18-18-18-14-18-14-18-58-18-58- 


Hopefully this introductory article has demonstrated some of the power 
and expressibility of Scala. It really is a very quick and elegant way 
of bolting together composing programs.

I'll examine its application to some more sophisticated algorithms in 
the next article.

MBD