MarbleMice.com

One of the last things I was working on for SpiderSynth before deciding to start an effort to use Scala as the main programming language for it was a parser/calculator so you could type in you own expressions for the wave form. I had hand rolled some bits but was not entirely happy with the results, well more the size of the code.

Over the weekend I got familiar with the parser combinator library shipped with Scala. I have used a similar library in C++ (Spirit) so was quite looking forward to it. 60 odd lines gave me a basic parser which created a abstract syntax tree and then interpreted the tree to get the value. This will probably form the basis of a later blog entry. Tonight I extended this further to handle unary operators and built in commands like sin and cos, all useful stuff if it is to make it into SpiderSynth. By the end of tonight it was sitting at about 100 lines. All looking very concise and way better looking than the Java code. I have a few SpiderSynth specific code that needs adding but after that is should just slot in.

As a little aside in learning Scala I took some time to write a fairly general implementation of the Hill Climbing optimisation algorithm. I thought it would make good topic for a blog entry.

It would take too long to introduce mathematical optimisation and hill climbing methods in this entry so I am going to assume you have a general idea of what they are, besides the topic has been introduced far better than I could do here and here

The basic algorithm we are going to implement is

1. current = random state
2. do
3. Generate Neighbours(current)
4. Find best score of neighbours
5. if(neighbour score > current score) current = best neighbour
6. else exit
7. loop

So a pretty easy to understand algorithm really. What I wanted to do was produce a reusable frame work for this technique to solve many different problems, hopefully learning a little bit of Scala along the way.

We define a simple interface from which we can create concrete classes that allow us to forumalate the optimisation problems we want to solve. Based on the pseudo code above we can define the HillClimbInterface trait as follows

trait HillClimbInterface[T] {
  type State = T
  def neighbours(state:T, rand:Random):List[T];
  def randomState(rand:Random):T;
  def eval(state:T):Double;
}

The first line creates a state type, we shall see later this could be as simple as a Double or something more complex. The three functions are then fairly obvious, neighbours will generate the neighbours of the current state, randomState will generate a random state to initialise the whole process and finally eval with return a score for the state, the higher the better.

Before we actually get onto the Hill Climbing implementation lets take a look at a very simple HillClimbInterface concrete class We are going to create a class that uses the Hill Climbing algorithm to find the maximum value of a sin wave. The answer is ofcourse 1, knowing the answer helps us to check we have our Hill Climbing algorithm correct.

class SinWave() extends HillClimbInterface[Double] {
  val delta = 0.00001
  override def neighbours(state:State, rand:Random) = List( if(state>=delta)       state-delta else state,
                                                            if(state<=2*Math.Pi - delta) state+delta else state
                                                           );
  override def randomState(rand:Random) = rand.nextFloat;
  override def eval(state:State):Double = Math.sin(state)
}

Our state type is a Double, the position at which we want to evaluate the sin function. To work out the score we just take the sin of the state as shown in out eval function. The random state if just some random value between 0.0 and 1.0 and the neighbours is a list of two values one slightly larger than the current state and one slightly less. We clamp the values between 0 and 2 Pi for no particular reason other than I want to work in that range and demonstrate how to apply simple contraints.

The class SinWave is effectively a controller for the hill climbing algorithm, I use this term below when defining the Hill climbing algorithm. Here is the class.

class HillClimb[T]{
  val rand = new Random()

  def optimise(controller:HillClimbInterface[T]) ={
    climb(controller)
  }

  private def climb(controller:HillClimbInterface[T]) = {
    def climbImp(controller:HillClimbInterface[T], best:T, atMax:Boolean):T = {
      atMax match {
        case true => best
        case false => {
          var atMax = true
          var newBest = best
          val newStates = controller.neighbours(newBest, rand)
          var bestScore = controller.eval(newBest)
          for(state <- newStates) {
            val newScore = controller.eval(state)
            if(newScore > bestScore){
              atMax = false
              bestScore = newScore
              newBest = state
            }
          }
          climbImp(controller, newBest, atMax)
        }
      }
    }
    climbImp(controller, controller.randomState(rand), false)
  }
}

Class HillClimb is parametised by the state type. In the case of sin wave this is a Double. The public functions are quite simply the function optimise which does what it says on the tin. The private function climb is where the action is, well actually the local function in that does all the work. I could have written this using a more procedural way which would be closer to algorithm we specified at the top but as I am trying to learn more functional way of thinking I decided to use tail recussion. I am of course open to suggestions on how to improve this code.
As the algorithm closely follows the pseudo algorithm above I won’t bother to discuss it here, just think recussively and all is well!

To use this class with our SinWave controller we could write this

val sinWave = new SinWave()
val hillClimb = new HillClimb[sinWave.State]
println(hillClimb.optimise(sinWave))

Pretty simple I hope you would agree. I am not totally happy with the sinWave.State part when creating the hillClimb value but struggled to figure out a better way to do this. 

The ShotGun Method.
One problem with Hill Climbing is it can get stuck at local maximums. More complicated optimisation algorithms exist to get around this although a very simple approach to try to mitigate this is to run the Hill climbing algorithm many times with random initial states. This is often call the Shot Gun method for obvious reasons. It is pretty easy to create a function in HillClimb that implements this.

def shotgunMethod(controller:HillClimbInterface[T], numIters:Int) = {
    def shotgunImp(controller:HillClimbInterface[T], iter:Int, best:T) : T = {
      iter match {
        case 0 => best
        case _ => {
          val latest   = climb(controller)
          val newBest = if(controller.eval(latest)> controller.eval(best)) latest else best
          shotgunImp(controller, iter-1, newBest)
        }
      }
    }
    shotgunImp(controller, numIters, controller.randomState(rand))
  }

We can specify the number of iterations. Again it uses tail recurrsion rather than procedual loops. Basically we keep calling the climb function and storing the best result so far until the value iter is zero at which point we return the best result so far. To use the Shot Gun approach we would use this code.

val sinWave = new SinWave()
val hillClimb = new HillClimb[sinWave.State]
println(hillClimb.optimise(sinWave))
println("With shotgun" + hillClimb.shotgunMethod(sinWave, 10))

The KnapSack Problem.
So far we have not really stressed tested framework. Finding the largest value of a sin wave does not exactly contain many local minima so lets try a more difficult problem. Packing items into a rucksack to maximise the value of the items while being constrained by the cost of the items. This problem is taken from here a genetic algorithm library written in Scala. Here is the code to implement it using our hill climbing algorithm. To get the max value you need to use the shotgun method.

// Max Cost: 17
// Best Value is 24 the last two added together 11.0 + 13.0
// see http://code.google.com/p/jiva-ng/wiki/KnapsackProblem
class KnapSack extends HillClimbInterface[Array[Boolean]] {
  val costToValues= Map(3.0->4.0, 4.0->5.0, 7.0->10.0, 8.0->11.0, 9.0->13.0)
  val costs = Array(3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 4.0, 7.0, 7.0, 8.0, 8.0, 9.0)

   def stateCost(state:State):Double = {
      val setStates = costs.zipWithIndex.filter(x=> state(x._2)==true)
      val currentCosts = setStates.map(x =>(costs(x._2)))
      currentCosts.foldLeft(0.0)(_+_)
    }

  override def neighbours(state:State, rand:Random) = {
    val maxNeighbours = 5
    var neighbours = List[State]()

    for(i <- 0 to maxNeighbours) {
      var arr = state.toArray
      arr(rand.nextInt(arr.length)) = true
      while(stateCost(arr) > 17) {
        arr(rand.nextInt(arr.length)) = false
      }
      neighbours = arr::neighbours
    }
    neighbours
  }

  override def randomState(rand:Random) = {
     var s = new State(13)
     for(i <- 0 until 10){
       s(i) =  rand.nextBoolean
     }
     // this state may not be valid, so generate neighbours that are guarenteed valid
     neighbours(s, rand).head
    }
  override def eval(state:State):Double = {
     val setStates = costs.zipWithIndex.filter(x=> state(x._2)==true)
     val currentCosts = setStates.map(x =>(costToValues(costs(x._2))))
     currentCosts.foldLeft(0.0)(_+_)
  }
}

This time our state variable is an array of bools and our randomState function just fills it and array with random boolean values. As this could state may not be valid (have a cost > 17) we generate neighbours from it which are guaranteed to be valid and take the head of it. I make a fair amount of use of the built in processing functions such as map, zip and filter but found the neighbours function just looked better using more procedural idioms. Obviously suggestions are welcome to add clarity.
Here is the code to run it

val knap = new KnapSack
val climber = new HillClimb[knap.State] 

val res2 = climber.shotgunMethod(knap, 20)
println(res2.deepToString)
println("Cost is:"+knap.eval(res2));
println("State cost is:" +knap.stateCost(res2))

Using the shotgun method we get the expected value of 24.

Conclusions
I wrote this code about a month ago but have only just got round to posting it and it compile under Scala 2.72RC1. I would certainly change a few things now, like using a List rather than an Array for the State in the KnapSack container and changing the name of HillClimbInterface to HillClimbController. I am not sure if the whole map, filter and zip add to the clarity of the KnapSack implementation, perhaps reworking to use for loops would be better? As always I welcome any comments as I am still learning Scala.
Here is the complete code for the HillClimb class.

import scala.util.Random

trait HillClimbInterface[T] {
  type State = T
  def neighbours(state:T, rand:Random):List[T];
  def randomState(rand:Random):T;
  def eval(state:T):Double;
}
// Hill climbing optimasation
class HillClimb[T]{
  val rand = new Random()

  def optimise(controller:HillClimbInterface[T]) ={
    climb(controller)
  }

  private def climb(controller:HillClimbInterface[T]) = {
    def climbImp(controller:HillClimbInterface[T], best:T, atMax:Boolean):T = {
      atMax match {
        case true => best
        case false => {
          var atMax = true
          var newBest = best
          val newStates = controller.neighbours(newBest, rand)
          var bestScore = controller.eval(newBest)
          for(state <- newStates) {
            val newScore = controller.eval(state)
            if(newScore > bestScore){
              atMax = false
              bestScore = newScore
              newBest = state
            }
          }
          climbImp(controller, newBest, atMax)
        }
      }
    }
    climbImp(controller, controller.randomState(rand), false)
  }
  // Uses many random initial states to try to avoid
  // local minimums.
  // numIters specifies the how many random states that will be considered
  def shotgunMethod(controller:HillClimbInterface[T], numIters:Int) = {
    def shotgunImp(controller:HillClimbInterface[T], iter:Int, best:T) : T = {
      iter match {
        case 0 => best
        case _ => {
          //var bestScore = controller.eval(best)
          val latest   = climb(controller)
          val newBest = if(controller.eval(latest)> controller.eval(best)) latest else best
          shotgunImp(controller, iter-1, newBest)
        }
      }
    }
    shotgunImp(controller, numIters, controller.randomState(rand))
  }
}

Well it is not hard to see that SpiderSynth has stalled a little bit in its developement. This is in part due to it being summer and having had a new arrival to the family not that long ago. Now winter is approaching my mind is turning to the developement of SpiderSynth. In truth another reason for slowed development is the codebase was starting to get messy and if I am honest my motivation with using Java has started to wane.

For me Java just does not quite have a large enough delta into higher level languages (from C++) and feels  to verbose. There are a lot of good points and plenty of people are highly productive. The tooling is amazing compared with C++. Although I think the final nail in the preverbial coffin was discovering Scala. This is not the topic for the entry so I will leave it there.

The codebase of SpiderSynth is fairly messy mainly because it was used to learn how to code in Java and how to best use the various libraries like swing.

So I was left with what to do with SpiderSynth. Well mulling it over for a few days I came up with these possible options

1. Abandon the project. Perhaps open source it, but no real java programmer was going to touch it
2. Continue using Java with decreasing motivation. This would mean very slow progress.
3. Rewrite it in either Scala or C++. Well I was thinking more Scala. It would take me a long time to get back up to the functionality I already have.
4. Mix Scala into the Java code. All new code done in Scala and a gradual conversion of  Java code to scala.

I actually enjoy coding SpiderSynth so abandoning it was not really on the cards. Continuing with it as a Java project would in truth be equivalent to abandoning it as my motivation would be so low to work on it not much would get done.

Rewrites never seem to work out for me, I tend to get side tracked somewhere along the way whenever I try it. Perhaps it is the pysocolgical effect of going back to square one. Which really left only  option 4.

SpiderSynth used Netbeans as it Editor/Project manager but the scala plug in for that does not allow mixing Scala and Java in the same project. The Eclipse Scala plug in does. I thought this was going to be one major pain to convert over. Infact it took less than two minutes to convert. Just create the project and import the files. I was suprised.

I then experimented in re-writing some of the very small classes with scala and everything went smoothly.  I was a bit suprised how smoothly that part went as well. Sure the eclipse scala plug in does have some rough edges but it is improving at a reasonable pace.

Because it is probably going to be a little while yet before I get a new release up to the website I have built a final version of the just java code with an extended beta period (1 year) before it starts nagging you to get the latest version. That is not to say I expect it to be anywhere near a year before the next release.

So I have gradually come to the conclusion that it is better to only use software tools that have reached version 1.0 or higher in their stage of development. This has been hammered home by the two main Scala editors (Netbeans and Eclipse) both not really provided a solution that is really productive. I seem to spend a great deal of time fighting with them rather than them letting me get on with interesting stuff. Both are improving although I am slightly worried for the Netbeans scala plug as it is very dependent on a single person. In general it is not a slur on any of the programmers working on these projects more a comment that the project are just at an early stage so don’t expect a smooth ride.

Scala swing is also at a very early stage. I spent some time playing with it and it was pretty good. Higher level than basic swing. As I started to write more complex stuff it started to become apparent that not all swing components are wrapped (JTree for instance seems to be missing) and some components seem to be missing some functionality that they have in unwrapped swing.

The key word in the past paragraph is “seem” as there seems (there I go again) to be no documentation on scala-swing. None at all. If you download the source code you can find a few examples but not much else. Again a great project but not quite there yet. The plus side, I did manage to learn some more about swing.

I guess that is the price you pay for using a programming language that is still in its’ infancy. On a positive not the vector of change has a large magnitude and is pointing in the right direction. Given a year or two the tool side of things should have improoved a great deal.

This is not a I am fed up with Scala, in fact the opposite I seem to be quite enjoying actually programming with it and more fun than java to code. Then again at the moment I am really enjoying programming in C++ as well – probably because I have been using templates a fair amount to refactor code into something much nicer.

So my current feeling is I have had enough of using tools that are in an early stage of development and should/when I come to learn a new programming language/skill I shall not do so until enough of the tool set is up to version one.

Beaking the Tower, Best way to describe it is a single screen version of settlers. Quite addictive although you will probably only play through once, unless you get addicted to how fast you can complete it.

Requires a very recent version of Java.