In the River with Scala

Introduction

This post deals with my adventures in Scala and applying them to a real world problem. That problem is addressing some of the complexities that come with dealing with River services (previous “Jini” services).

For those who don’t know, River/Jini services are hugely powerful and customisable, but such things always come with a price. The price in this case is a reputation – probably deserved – that setting them up and using them is difficult and complicated. It’s my personal opinion that making a simple setup easy to configure and use is necessary to encourage adoption of what is a very smart and clever bit of kit.

This Scala work therefore addresses two problems. The first, making River services easy to use and the second? Getting some practical experience writing real Scala code.

This code is available in the Apache River skunk branch “easystart”.

Getting Started

River services reside in what we refer to as a djinn. This term, although present in the specification, isn’t used in the code; until now.

In the same “easystart” skunk branch are some helper classes for starting the infrastructure services that come with the River distribution. These are;

1. HTTP server
2. Lookup Service (reggie)
3. Java Space (outrigger)
4. Transaction Service (mahalo)

Look for the classes;

1. org.apache.river.extra.easystart.StartHttpServer

2. org.apache.river.extra.easystart.StartLookupService

3. org.apache.river.extra.easystart.StartOutriggerService

4. org.apache.river.extra.easystart.StartMahaloService

If using these classes as the basis for your djinn you will also need to supply the following VM arguments.

-Djava.security.policy=$RIVER_HOME/src-extra/policy.all
-Djava.rmi.server.RMIClassLoaderSpi=net.jini.loader.pref.PreferredClassProvider

At time of writing, the code in “easystart” is not tidy nor suitable for a real deployment, it began as a Proof Of Concept and hasn’t yet made it into sensible code.

Additional documentation can be found in the JavaDocs of these classes.

So you can either use the above or whatever other mechanisms you use to start your services. Remember, to continue you will need at least a HTTP server and one Lookup Service.

Accessing the Djinn

So now we need to access our djinn. Actually, we first need to know how we’re going to discover our djinn. Currently we have two options;

1. Multicast
2. Unicast

Multicast is easier to setup, we essentially just see what’s going on in our current subnet. Unicast isn’t that much more difficult, but it does require us to know where at least one lookup service (also known as a “Service Registrar” or by it’s implementation codename “reggie”) is. So let’s do that now in Scala.

Multicast
val djinn = new Djinn(new MulticastDiscovery)

Unicast
val locators
    = Array[LookupLocator] (
        new LookupLocator("jini://hostname"))
val djinn = new Djinn(new UnicastDiscovery (locators))

As you can see, there isn’t really much to it setting up our djinn. Both of these methods have now made available many of the methods available to us that we need to start using services.

Using the Djinn

We’re now in a position to start using our djinn. So what do we want to do? Maybe we want to write an entry into every space.

val spaces = new ServiceTemplate(
    null,
    Array[java.lang.Class[_]](classOf[JavaSpace]),
    null)

val writeEntry = { si: ServiceItem => //code to write in a space
val writeInAll =
    { sis: List[ServiceItem] => Some(sis map writeEntry) }

djinn filter spaces flatMap writeInAll

It’s really that simple, we take our djinn, filter it looking for spaces and then we execute “writeInAll” on every space. The only slightly confusing bit here is the call to “flatMap“.

Of course, we can use filter with a more specific ServiceTemplate to return a more specific kind of service that we want to do something interesting with.

Or maybe we want to shut down all the services.

val terminate = (si:ServiceItem) =>
    ...//code to terminate a service
djinn foreach terminate

RemoteExecution

As you’re probably aware, every time you do something to a River service there is the possibility of a java.rmi.RemoteException of being thrown. I’ve chosen to adopt something similar to Scala’s Option to hide this away.

So when you call functions on a djinn you’ll actually get back a RemoteExecution[A] with “A” being of a type you’re looking for. RemoteExecution can either be a Result or a Problem. Take a look at the source code for these things and it’s fairly obvious what’s going on inside them. I decided not to just have djinn function return Option‘s because in the case of an exception being thrown we potentially want to know what the exception was.

To complicate things slightly further. A Result itself can contain an Option thus indicating whether something or nothing was returned. We need this additional complexity because when we search for a service (for example) one of three things might happen.

An exception might get thrown, in which case we’ll receive a RemoteExecution.Problem with the exception inside it. Nothing might be returned, in which case we’ll get a RemoteExecution.Result.None. Finally, we might actually get the service we were looking for, so we’ll get a RemoteException.Result.Some(…).

Talking to the Djinn

When writing “pure” River code it’s possible to register listeners to your discovery mechanism so you know when services are made available, destroyed or changed. This is possible when using a djinn as well. We do this slightly differently in Scala.

djinn.handleNewService(
    {event: ServiceDiscoveryEvent => println("New Service")})
djinn.handleRemovedService(
    {event: ServiceDiscoveryEvent => println("Removed")})
djinn.handleChangedService(
    {event: ServiceDiscoveryEvent => println("Changed")})

All we do for a djinn is register functions to be called on each event. The function needs to have the signature (f: ServiceDiscoveryEvent => Unit), and that’s all there is to it.

Finishing

Shutting down a djinn follows the same approach as everything else in River.

djinn terminate

Conclusion

At the time of writing, these classes are obviously incomplete. The Scala ones in particular are pretty raw and I’m sure that there are Scala based optimisations and patterns that I’ve missed when writing them. We all have to start somewhere though.

Please drop a message onto the dev@river.apache.org mailing list with any comments, requests or suggestions for improvement.

Playing With Python

What?

This is just a quick post documenting my recent forays into Python programming and the kinds of things I managed to (quickly) do with it. You might ask “Why?”, well aside from the fact that learning new languages is fun and can keep you on your development toes, I’m seeing a lot of job adverts asking for skill sets which include scripting languages such as Ruby and Python. Since I’ve done a spot of Ruby in the past, I figured why not spend some time messing around with Python.

Do What?

This is the problem to solve. Given a triangle of numbers, find the shortest path from the top of the triangle to the bottom. So consider the triangle;

      9
    8  5
  5  10  7
13  4  12 11

Moving between rows can only be done by going to the ‘root’ of any particular number. (Here, “root” in relation to trees not Maths). So, if we were are number 10 in the second to last row, our only options of moving to the final row are to select 4 or 12.

For this triangle, the shortest path is “9, 8, 5, 4″ which has a total weight of 26.

Starting from the top of the triangle will lead to a lot of messy backtracking, which, although doable, is a bit more complex than I want it to be. Another top-down solution might be to start lots of threads and start them exploring the triangle[1]. Again, this is a potential solution, but there is a much simpler approach we could take.

Starting at the bottom of the triangle, we can easily work out the cheapest way to get from row-1 to row. With that data, we can move up the triangle, working out the cheapest way to get from the row below, to the current row until we get up to the top, in which case we would have calculated the shortest path.

Because we care about the path and not just it’s weight, I created a class to represent both the path and the weight.

Classes

class Path:
  def __init__(self,v):
    if isinstance(v,int):
      self.path = [v]
      self.weight = v
    else:
      self.path = list(v.path)
      self.weight = v.weight

  def append(self, num):
    self.path.append(num)
    self.weight += num

  def weight(self):
    return self.weight

  def __repr__(self):
    str_list = ['Path:',`self.weight`,'\t',`self.path`]
    return ''.join(str_list)


The only interesting part of the code above, I think, is the use of ‘isinstance’ to provide a form of constructor overloading.

Accepting the input

Accepting command line input from Python was also very easy, as it is in most scripting languages.

def readInput():
  triangle = []

  while True:
    l = raw_input()
    if l == 'EOF':
      break
    else:
      row = buildRow(l);
      triangle.append(row)

  return triangle

def buildRow(line):
  numRow = []
  strRow = line.rsplit(' ')
  for s in strRow:
    numRow.append(int(s))
  return numRow

This code accepts the input from the command line and returns us our triangle represented as a list of lists. Using the same example as above, we get the list;

[[9], [8, 5], [5, 10, 7], [13, 4, 12, 11]]

Note, that I didn’t bother with any checking or validating that the input formed a correct triangle.

Then I needed a method to be able to convert a [int] to a [Path]. As I was beginning to expect, this was going to be a simple matter.

def convertToPaths(row):
  paths = []
  for n in row:
    paths.append(Path(n))
  return paths

Being able to return tuples is also a very nice feature in Python and one I miss in Java after having spent time writing Haskell. I used this feature when working out the parents of a particular number in the triangle. In Java, I’d be forced to either create a “Parents” class which contained two numbers or return some kind of array or Collection which introduces a lot of places for errors and misuse. Tuples here keep things very plain and simple.

def parents(cIndex, row):
  left = row[cIndex]
  right = row[cIndex+1]
  return (left,right)

I’m now ready for the algorithm proper. Converting the bottom row of the triangle in a [Path] gives me a starting point. Looking at the row above, I can calculate the cheapest way to get to it, knowing the current Path back to the bottom.

Put another way, I take the bottom two rows of the table (one which is a [Path] and the one above which is a [int]) and merge them together to make a new row, of type [Path] but which is of the same length as the [int] row. I repeat this process until there is only one row left, which should have only one element in it; a Path.

Here’s the code.

def calcPaths(base, row):
  newBase = []
  for i in range(0, len(row)):
    (l,r) = parents(i, base)
    if l.weight < r.weight:
      new = Path(l)
    else:
      new = Path(r)
    new.append(row[i])
    newBase.append(new)
  return newBase

def calcShortestPath(triangle):
  row = len(triangle)-1
  base = convertToPaths(triangle[len(triangle)-1])
  while len(base) != 1:
    base = calcPaths(base, triangle[row-1])
    row -= 1
  return base.pop(0)

triangle = readInput()
shortestPath = calcShortestPath(triangle)
print shortestPath

Then What?

The algorithm I chose, merging one row of the triangle into the row above, looks very much like a fold. (I can’t express who pleased with myself I was when such a functional solution magically popped into my brain when thinking about this problem). I couldn’t find a fold function in Python, luckily, writing my own was very simple.

def foldl(f, a, l):
  if 0 == len(l):
    return a
  else:
    head = l.pop(0)
    a = f(a,head)
    return foldl(f,a,l)

As you can see this is a left fold. This is not intended to be introduction into folds, but basically it works by accepting as arguments a function, an accumulator and a list. It then applies the function to the accumulator and the head of the list. It then recursively calls itself with the same function, the updated accumulator and the rest of the list until the list is empty.

So my main method now a bit more simple, with it’s intention more simply expressed by use of the fold method.

triangle.reverse()

def merge(paths, roots):
  if 0 == len(paths):
    return convertToPaths(roots)
  else:
    return calcPaths(paths,roots)

shortestPath = foldl(merge,[],triangle)
print shortestPath[0]


Although finding the shortest path is now expressed a bit more elegantly. We have to reverse the triangle. This is because we received the input in such a way as the ‘base’ of the triangle is the last element of the list, but we need to processes the bottom of the triangle first.

So What?

The thing that surprised me the most about programming Python was how easy it was. And it was really easy. The language syntax is simple and followed the same rules as most of the other languages I’ve picked up.

I particularly likes the way that everything, including functions, are objects and so can be passed around as arguments. I first encountered passing functions as parameters in Haskell, and since picking up that trick have often been frustrated that Java hasn’t offered me a simple way of doing the same thing.

The only thing that put me off was the convoluted way of “overloading” a constructor. Due to the way Python handles it’s types, overloading as we understand it in Java wasn’t possible. I think that’s a pretty small price to pay for the simplicity and power that Python programming provides.

[1] I’ve taken this problem from an tech test for an interview I had recently which I failed. The reason being that I’d spent many weeks prior to this particular interview reading about multi-threading at the new concurrency packages available in Java 5/6. Whilst all that is great and important, because I’d become so immersed in that kind of programming, I forgot to look for the simple solution first. My bad. I guess when you spend a long time studying hammers, new problems instantly present themselves as nails. There’s a lesson I won’t be forgetting in a hurry. Interestingly, my multi-threaded approach just wasn’t per formant enough for large triangles (more than 60 rows) because it found more and more work to do the longer the algorithm ran. With the above approach, the algorithm actually gets less work to do the closer it comes to a solution.

Simple Cell Automata in Haskell

Introduction

To further help me improve my Haskell skills I’ve started writing an implementation of Conways Game of Live. The rules here are simple;

• The cells are laid out in a grid – my implementation assumes a square
• If any cell is “alive” and it has more than three neighbours, then the cell dies
• If any cell is “alive” and it has fewer than two neighbours, then the cell dies
• If any cell is not alive and it has between two and three neighbours, then it comes to life

I also wanted my cell automata to be nicely visible so I decided to use Glade and Gtk2Hs to make a nice GUI for it.

Getting Everything Installed

I already had GHC installed, so all I need to install was everything else. Firstly, use the package manager to install Glade. This was easy, the rest is easy to but involves using cabal.


cabal install alex
cabal install gtk2hs-buildtools
cabal install gtk
cabal install glade


To use your Glade/GTK stuff with GHC you need to use this incantation;


ghc -package gtk --make MyProgram


Also, when using Glade the project file format needs to be changed from “GtkBuilder” to “Libglade”.

The Code

My code can be found in BitBucket here; Cell Automata

The cell automata algorithm works okay see the “evolve” method. I’m currently stalled on trying to make it work nicely in the GUI.

I got stuck when trying to calculate the square root of an integer (and receive a rounded/truncated integer as the result). I couldn’t make that work so I borrowed/stole some code from
http://haskellsolutions.blogspot.com/2009/02/integer-square-root-of-positive-integer.htm
to work that bit out for me. I couldn’t make the Haskell sqrt work properly.

Edit: I got this fixed. To get an integer square root of an integer, the following incantation is used

floor (sqrt (fromIntegral (length xs)))

In the above, xs is the list containing my cells world. This is safe to do because in my implementation the size of the world is always a square number. I’ve yet to run hlint over my code to check that it is sensible. Edit ends.

If anyone can offer any insights into how to create a kind of animation thread (for want of a better phrase) to handle the rendering the evolution of the world I’d be very grateful!

Comments always welcome.

Edit: I finally got it all working, including a UI in HOpenGL. The biggest problem I’m facing now is that there GOL algorithm is very ineffecient for large world sizes, I’m guessing this is because it does a lot of list traversals per cell.

I should also mention the following three sites which proved to be invaluable.

1. Michi’s blog which I “borrowed” the majority of the OpenGL code and module layout from
2. Andre W B Furtado tutorial for the IORef help
3. My Awesome Blag – which appears to be the only place on the Internet which shows how to use the timer callback

Safety is not the same thing as patronizing

I hate cars and the lawmakers who govern their use. Speed limits hinder my progress; if I think it’s safe to do 100mph along some road, I should be allowed to. Seat belts, urgh! Don’t get me started on how uncomfortable and restrictive they are. I think it’s patronizing for car makers to fit new cars with airbags. What kind of moron is going to drive into something that will necessitate an air bag? Like the rest of the population, I consider myself an above average driver. So I can get out of difficult situations without crashing, I can make fast progress safely and avoid all the obstacles. Also, the car manufactures restrict the type of fuel I can put in the car. Obviously, they don’t realise that sometimes one kind of fuel is cheaper than the other. Who are they to dictate to me what kind of fuel I should use?

Except that..

…I can’t avoid all crashes. Sure, more times than not, I’m a perfectly safe driver, regardless of what speed I’m doing or the road conditions or other situations. But there are two very good reasons why I need all those safety features.

1. Sometimes, I’m an idiot
2. Everyone else is also sometimes an idiot

This little rant is in response to a couple of articles that have been bugging me recently. Namely; Patronizing Language Design and Steve Yegge’s Java/Wikileaks article.

Now, I don’t know either of those other authors. The only thing I know about them is that they are both probably way more clever than me. They’ve probably forgotten more great stuff than I’ll ever know. Steve Yegge’s article in particular seems like it’s written as a comedy piece, but like all good comedy there’s a degree of truth hidden inside it. I’ve not had a sense of humor amputation, I laughed and smiled about it as much as the next programmer. However I do take issue the two premises that appear in these articles.

1. Programming languages should allow any programmer to do whatever they want, and it’s the programmers responsibility to be safe
2. Object Orientated design, particularly in Java, forces developers to only use certain software components in known ways and that’s a restrictive and bad thing

Patronizing Programming Languages

Preventing programmers from doing ‘more complicated’ things is just a kind of seat belt. Or maybe a better analogy is that of a speed-limiter as fitted to most trucks and vans these days. (At least, in the UK.) Think back to all the programmers you’ve ever worked with, all the WTF articles you’ve read. Aren’t you kind of glad that some of those developers weren’t driving a lot faster when they crashed? Particularly if it was you they crashed into!

The first article claims that even with more difficult language features available, an increase in program crashes has not been seen. I don’t have access to his data so I can’t verify that claim. My gut tells me though that this just can’t be the case. If you took all the programs written in so-called ‘safe’ languages and rewrote them in ‘un-safe’ ones, I’m convinced that you’d see an increase in the number of nasty crashes.

I’d be interested to visit an alternative reality and see what some of the enormous Java software projects that l’ve worked on look like when written in some less ‘patronizing’ language.

The phrase “enough rope to hang yourself with” comes to mind. Sure, you can hang yourself in ‘safe’ languages such as Java, C# etc. But that’s about it. Introduce language features that give you even more rope and you could probably tie up and hang the entire town. Neither outlook is pretty, but the differences in scale can’t be ignored. Obviously, I’m not saying that this always going to happen, but I would argue that the occurrences of it happening would be greater – and messier.

Doing Whatever You Want To Do

I think that’s it’s fair to say that most of us write programs that are difficult or impossible (at least, according to our individual skill sets) to formally reason about. This means that testing the behaviour of our software is limited to testing it in way we think that it’s going to be used – with some additional edge/exception cases thrown in for good measure.

In my opinion, the gripe about Java programs hiding implementation with final and non-public modifiers is more a gripe about Object Orientated design than about Java specifically. (And goodness knows, I’ve moaned about Java enough!) I just can’t get away from the fact that it is appropriate for some software components to be hidden away; other people may well want to use them in ways that they were not intended.

Ideally, any given class can be extended and have it’s non-private members overridden with predictable results. Hopefully, such things are tested or at least well enough documented to allow other developers to not break anything else. Opening up everything inside every class places an enormous burden of testing on the original developer; how can they possibly verify that if any of the internal code changes (because it has been overwritten) that the rest of the code will behave in the same expected manor.

You just have to ready any “How/Why Do I Do OO?” book or article to see why we encapsulate and hide data/functionality. If you really really need some functionality which is private or final then the correct solution is to petition the vendor and ask for an API change. (Good luck with that!) To me, the Java/Wikileaks article should be more targeted at bad API design and less about abolishing final/private in any particular language.

Programming is not just about design-test-code, whatever language or silver bullet you’re using right now. It’s also about support. Making every possibly software component open to use (and abuse) is just asking for a support nightmare. I would hazard a guess that the response to most support tickets would be closed with phrases like “Your computer caught fire because you overrode this method and you didn’t do something which the original method did” or “You lost £1,000,000 in business because you used that method which is not designed to be used in such a way”.

My car manufacturer says I should only put diesel in my particular car. They’ve left the choice on whether or not I keep that restriction up to me, although it has to be said that they have not documented the repercussions of disobeying them very well in the car handbook. I’m also not holding my breathe for any free support or fix if I do disregard their rules. Now obviously, as a sensible person, I wouldn’t put unleaded, water, Lucozade or anything else in my fuel tank, but there is nothing physically stopping me. But what happens one day when I’m day-dreaming whilst filling up and accidentally pick up the wrong pump? After I’ve paid the expensive bill to get my car fixed, I bet that I wished that there was some physical restriction stopping me from doing the wrong thing. Even though I’d never made that kind of mistake before!

Remind me again why physical restrictions against accidental (or idiotic) mistakes are a bad thing. Remind me again why an API designer hiding certain things from my code is a bad idea.

Summary

You might currently work only with brilliant people, but remember that not everyone does. Every few months (or weeks) a new article is released about how education and training in this country or that is going down the tubes. The bar to entry of the Programming Profession is already pretty low and seems to be getting lower. Keeping ‘difficult’ things away from the majority of those programmers, to me, seems like a good idea.₁ I don’t let my kids play with sharp knives, but as they grow and move onto different meals (i.e. programming projects) different sets of cutlery (i.e. tools, languages, language features) will be introduced and they’ll be taught to use them. But only if I consider their aptitude sufficient enough to wield them safely. Even though some companies have very stringent hiring and interview practices, bad programmers still get jobs!

Programmers should lock their APIs down to a handful of known places which makes sense. Then they can predicate what their users are going to do and help them do that. Some programmers are going to complain that because of those restrictions they can’t do this or that with your API. That complaining is okay. Making everything open is just asking from trouble. Not from you, the reader, obviously. You’re an above-average programmer who doesn’t make mistakes. But restrictive APIs are designed to protect software against programmers like me; you know, the human ones who do make mistakes.

₁ Either that, or raise the bar to entry a bit more!

Finding All the Paths In a Graph With Haskell

Here’s an interesting problem…

Given an undirected graph, find all the paths (not just the shortest) between two nodes that are less than some given length.

I decided to attack this problem using Haskell. Simply because I’ve been trying to get to grips with the language and felt that this was a nice “real” problem for me to practice my fledgling skills on. I’ve chosen to model a graph as a list of edges which are described as a simple pair (see the end of the following source code). I have therefore made the following assumptions in the code;

• An entry in the list (‘a’,'b’) explicitly states that an edge exists between the nodes ‘a’ and ‘b’ and further this implies that the edge (‘b’,'a’) exists since the graph is undirected.
• An entry (‘a’,'a’) implies that a node ‘a’ exists that does not have any edges, rather than an edge exists that self-references the node ‘a’. Nodes are not allowed to have edges to themselves.

The following code does work, and returns the correct number of paths given my test data and the requests I make of it. I can’t escape the feeling, though, that my Haskell could be made more simple and efficient. I just don’t know Haskell well enough yet to work out how!

The Solution

Edit 1: code to apply Hlint comments

• Only HLint error: use of “not (elem …)” rather than “notElem …” has been fixed
• HLint warning: use of “[p] ++ (some list)” rather than “p : (some list” has been fixed
• HLint warning: unnecessary parenthesis used in a few places, most of these have been fixed

Edit 2: corrected some cut and paste mistakes


import Data.List

-- finds all the paths with length <= l from u to v in g
findAllPathsTo l u v g
    = filter endsAt (findAllPaths l u g)
        where
        endsAt ps = (last ps) == v

-- finds all the paths with length >= l from u in g
findAllPaths l n g
    | notElem n (allNodes g) = []
    | otherwise  = allPaths' l g [[n]]

-------------------------------------------------------------------------------
-- Supporting functions below
-------------------------------------------------------------------------------

appendNeighboursToPath l p g
    = append ns p
        where
        ns = neighbours n g
        n = last p
        append [] _ = []
        append (n:ns) p = flatten (appendToAll l [p] n) : append ns p

neighbours a g
    = reverse (foldl step [] g)
        where step acc (u,v)
           | u == a    = v : acc
           | v == a    = u : acc
           | otherwise = acc

allNodes :: (Eq a) => [(a,a)] -> [a]
allNodes [] = []
allNodes [(u,v)] = [u,v]
allNodes ((u,v):gs) = nub (u : v : allNodes gs)

allPaths' l g acc
    | length acc == length paths = acc
    | otherwise = allPaths' l g (nub (acc ++ paths))
      where
      paths = nub (appendNeighboursToPaths l acc g)

appendNeighboursToPaths l [] _ = []
appendNeighboursToPaths l (p:ps) g
    = p : nub (appendNeighboursToPath l p g ++ appendNeighboursToPaths l ps g)

appendToAll l [] _ = []
appendToAll l (x:xs) y = maybeAdded : appendToAll l xs y
    where
    maybeAdded  | elem y x = x
                | length (x) > (l-1) = x
                | otherwise = x ++ [y]

flatten = foldl (++) []

-------------------------------------------------------------------------------
-- Test code below
-------------------------------------------------------------------------------

test=do putStr "\n"
putStr "Simple tests to check return length of path lists\n"
putStr "1 == length (findAllPaths 100 'a' g0)? " ;
print (1 == length (findAllPaths 100 'a' g0))
putStr "5 == length (findAllPaths 100 'a' g1)? " ;
print (5 == length (findAllPaths 100 'a' g1))
putStr "9 == length (findAllPaths 100 'a' g2)? " ;
print (9 == length (findAllPaths 100 'a' g2))
putStr "9 == length (findAllPaths 100 'a' g3)? " ;
print (9 == length (findAllPaths 100 'a' g3))
putStr "4 == length (findAllPaths 100 'a' g4)? " ;
print (4 == length (findAllPaths 100 'a' g4))
putStr "21 == length (findAllPaths 100 'a' g5)? " ;
print (21 == length (findAllPaths 100 'a' g5))
putStr "\n"
putStr "2 == length (findAllPathsTo 100 'a' 'f' g5)? " ;
print (2 == length (findAllPathsTo 100 'a' 'f' g5))
putStr "1 == length (findAllPathsTo 6 'a' 'f' g5)? " ;
print (1 == length (findAllPathsTo 6 'a' 'f' g5))
putStr "0 == length (findAllPathsTo 100 'a' 'z' g5)? " ;
print (0 == length (findAllPathsTo 100 'a' 'z' g5))
putStr "\n"
putStr "Has all paths [\"abcdf\",\"abcjklmnf\"] in (findAllPathsTo 100 'a' 'f' g5)? " ;
print (checkSameContents (findAllPathsTo 100 'a' 'f' g5) ["abcdf","abcjklmnf"])
putStr "Has all paths [\"abcdf\"] in (findAllPathsTo 6 'a' 'f' g5)? " ;
print (checkSameContents (findAllPathsTo 6 'a' 'f' g5) ["abcdf"])

g0=[('a','a'),('b','b'),('c','c')]
g1=[('a','b'),('b','c'),('c','d'),('d','e')]
g2=[('a','b'),('b','c'),('c','d'),('c','e'),('d','f'),('e','f')]
g3=[('a','b'),('b','c'),('c','d'),('c','e'),('d','f'),('e','g'),('g','h'),('h','i')]
g4=[('a','b'),('b','c'),('b','d')]
g5=[('a','b'),('b','c'),('c','d'),('c','e'),('d','f'),('e','g'),('g','h'),('h','i'),('c','j'),('j','k'),('k','l'),('l','m'),('m','n'),('n','f')]

checkSameContents     :: (Eq a) => [a] -> [a] -> Bool
checkSameContents a b
    = (length a == length b) && (length b) == (length (takeWhile f a))
        where
        f x = elem x b

Playing with Servos and SUN SPOTS

Introduction

I’ve managed to find some time recently to get playing with my SUN SPOTs again, so I figured I’d start by wiring up one of the servos from my ancient remote control cars to it. Although, there seems to be a lot of information about doing this on the web (mostly the wiring diagrams) I hit a snag with getting the full motion range out of my servo. So I figured I’d put something up here in case anyone else encounters the same.

Scenario

To control my servo I wrote a very quick GUI that allowed me to send float values through the connected base station to the free range SUN SPOT. That SPOT was wired up to a battery pack and servo and the servo moved when I hit the GUIs button. Simple, but a nice first step.

The Setup

I mostly copied the wiring of the servos from “Fantastic Kobe” and this offical SUN blog. There’s not a lot to the wiring, as you can see from this picture.

Shows the wiring from the battery pack and SUNSPOT to the Servo

I not going to go into detail about what connects where, because that information can easily be found on either of the above two links.

Setting the Servo Bounds

One of the things I found was using the setPosition(float p) method on Servo wasn’t giving me the full range of motion. To fix this you need to set the bounds of your particular servo. I didn’t know the ‘correct’ way to do this, so instead I went with a trial-and-error approach.

private int servoPin = EDemoBoard.H1;

private void initServo() {
servo = new Servo(EDemoBoard.getInstance().getOutputPins()[servoPin]);
// for(int i=250; i<2300; i+=10) {
// servo.setValue(i);
// out("value="+i);
// Utils.sleep(100);
// }
servo.setBounds(250, 2300);
}

In the above code, the starting value of “i” was originally zero and the end value was 10000. Then, by using changing these values so that when initServo() was called the servo didn’t groan in protect, I was able to set the bounds as shown. Having done that, servo.setValue(0.5); puts the servo in the middle as expected. With values of 0 and 1.0 taking the servo to its extremes.

I expect that most people’s servos are going to be different. Mine is a Futaba FP-S148. And now I can move a servo around, I can start to do something useful (or at least fun) with it!

The Code (Free Range SPOT)

There is only one class in the application that sits on the free range SPOT.
import java.io.IOException;

import javax.microedition.io.Connector;
import javax.microedition.io.Datagram;
import javax.microedition.io.DatagramConnection;
import javax.microedition.midlet.MIDlet;
import javax.microedition.midlet.MIDletStateChangeException;
import com.sun.spot.sensorboard.EDemoBoard;
import com.sun.spot.sensorboard.peripheral.Servo;

public class MainApplication extends MIDlet {
    private final String BASE_STATION_ID = "0014.4F01.0000.103E";

    private int servoPin = EDemoBoard.H1;
    private Servo servo;
    private DatagramConnection toBaseStation = null;

    protected void destroyApp(boolean arg0) throws MIDletStateChangeException {}

    protected void pauseApp() {}

    protected void startApp() throws MIDletStateChangeException {
        initComms();
        initServo();
    }

    private void initComms() {
        try {
            toBaseStation = (DatagramConnection) Connector.open("radiogram://" + BASE_STATION_ID + ":100");
            startListenerThread();
        } catch (IOException ex) {
            out("EXCEPTION: "+ex.getMessage());
        }
    }

    private void initServo() {
        servo = new Servo(EDemoBoard.getInstance().getOutputPins()[servoPin]);
        servo.setBounds(250, 2300);
// for(int i=200; i<2300; i+=10) {
// servo.setValue(i);
// out("value="+i);
// Utils.sleep(100);
// }
    }

    private void startListenerThread() {
        Thread t = new Thread(new Runnable() {
            public void run() {
                while(true) {
                    listenForMessage();
                }
            }
        });
        t.start();
    }

    private void listenForMessage() {
        Datagram dgIn = null;
        try {
            dgIn = toBaseStation.newDatagram(toBaseStation.getMaximumLength());
            toBaseStation.receive(dgIn);
            handleMessage(dgIn.readUTF());
        } catch (IOException ex) {
            out("EXCEPTION LISTENING: "+ex.getMessage());
            ex.printStackTrace();
        }
    }

    private void handleMessage(String message) {
        out("NEW MESSAGE ["+message+"]");
        if(message.startsWith("SERVO:")) {
            handleServoMessage(message);
    } else {
            handleUnknownMessage(message);
        }
    }

    private void handleUnknownMessage(String message) {
        out("UnknownMessage ["+message+"]");
        sendMessage("UNKNOWN MESSAGE ["+message+"]");
    }

    private void handleServoMessage(String message) {
        int cutAt = message.indexOf(":")+1;
        String txtValue = message.substring(cutAt);
        try {
            float value = Float.valueOf(txtValue).floatValue();
            if(value 1.0) {
                sendMessage("SERVO VALUE REJECTED. OUT OF BOUNDS 0.0-1.0 ("+txtValue+")");
            } else {
                servo.setPosition(value);
                sendMessage("SERVO: New Value Set="+servo.getValue());
            }
        } catch (NumberFormatException nfe) {
            sendMessage("SERVO VALUE REJECTED. NOT A VALID FLOAT ("+txtValue+")");
        }
    }

    private void sendMessage(String message) {
        out("Sending: "+message);
        Datagram dgOut = null;
        try {
            dgOut = toBaseStation.newDatagram(toBaseStation.getMaximumLength());
            dgOut.writeUTF(message);
            toBaseStation.send(dgOut);
        } catch (IOException e) {
            out("EXCEPTION SENDING TO BS: "+e.getMessage());
        } finally {
            if(null != dgOut) {
                dgOut.reset();
            }
        }
    }

    private void out(String msg) {
        System.out.println(msg);
    }

}

The Code (Base Station)

The code on the base station is simple enough, in fact too simple to warrent posting and spending the time formatting it here. The only interesting bit is the following line which is one of the first lines in the public static void main(String[] args) method;

OTACommandServer.getInstance().start();

The rest of the code is either UI/Swing code or normal Java/SUN SPOT code. In fact, the initComms, sendMessage, startListenerThread and listenForMessage methods are identical to those that run on the free range SPOT. The only difference is the SPOT address that the DatagramConnection is opened with. Obviously, on the free range SPOT it is opened with the address of the base station, and the reverse for the code on the base station.

Aside

Disclaimer: Obviously, soldering is dangerous to yourself and the components you’re working on/with. Any damage or injury you sustain following this advice is entirely at your own risk and I accept no responsibilty for it.

…that being said; if you don’t have a decent breakout board for your SUN SPOTs (and you’re in the UK) then Maplin do some PCB socket connector things* that you can buy and solder into your SUN SPOT. This gives you the ability to use bread board connector cables to easily connect up different sockets from the SUN SPOT without having to do any resoldering. The soldering its self is a bit fiddly, so I recommend getting a decent magnifying glass and a soldering iron with a fine tip. I’m definitely not the worlds best solder-er but I managed it okay.

* – I forget the actual name or catalogue reference, they’re pretty cheap (less than a pound I think) and are sold in rows of about 20 or so. You just snap off two rows of 10 each and get on with it.

Useful Links

• SUN SPOT API Doc

Playing with the Sun SPOT Radio

I have recently been lucky enough to borrow a set of very cool Sun SPOTs, so I immediately began thinking of all the amazingly clever and brilliant things I could do with them. However, with the exception of making the LEDs light up like a Cylon’s eyes (or Knightrider’s Kit as per your preference), all my ideas required one spot to be able to talk to another.

So what I figured the first thing to do would be to create a simple way to do this. Basically, each SPOT you want to talk to another instantiates a Buddy object and asks it to look for another buddy (myBuddy.lookForPair()) this will then start the buddy broadcasting and looking for a fellow.

It’s probably important to note at this point that I have not tested this code with more than two SPOTs, I certainly haven’t tested any edge cases where multiple SPOTs start up and all start looking for buddies on different ports. This is code is for my own use, I’m very happy for anyone to download, modify and use it (it is GPL’d) as long as you remember that it only works for the nicest of use cases.

Once two buddies (on different SPOTs) have connected you can send a message from one to the other by typing;

myBuddy.sendMessage("my message");

Recieved messages are handled by a BuddyListener which your SPOT application should have given to it’s Buddy instance. Recieved messages come in from the following method on that interface;

void messageRecieved(String message);

There’s lots of ways this code could be improved, for example the initial broadcast port is hardcoded into the Buddy code itself, this should really be parameterised. Also, the sleeps and waits that the Buddy endures while trying to connect to another one and so on. These should probably be pulled out to fields so that they can be tweaked more easily.

The good thing about this code is that it makes paired communication very simple (although you do have to be careful with the threads that are listening to incoming messages). You can also use your own language/protocol that the SPOTs will interpret on top of this Buddy mechanism very easily.

radio.Buddy – This is the meat of the project. To easily connect two SPOTs each must have an instance of one of these. Once connected to each other sending and recieving messages between the two is very easy.

/* 
 * This program is free software; you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation; either version 2 of the License, or 
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU General Public License along 
 * with this program; if not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
package radio;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;

import javax.microedition.io.Connector;
import javax.microedition.io.Datagram;
import javax.microedition.io.DatagramConnection;

import com.sun.spot.io.j2me.radiogram.RadiogramConnection;
import com.sun.spot.io.j2me.radiostream.RadiostreamConnection;
import com.sun.spot.peripheral.radio.RadioFactory;
import com.sun.spot.util.IEEEAddress;
import com.sun.spot.util.Utils;
import com.sun.squawk.util.StringTokenizer;

public class Buddy {

	private static final String NEED_BUDDY = "BUDDY_REQ";
	private static final String I_WILL_BE_YOUR_BUDDY = "BUDDY_ACK";

	private long thisAddressAsNumber = RadioFactory.getRadioPolicyManager().getIEEEAddress();
	private String addyStr;

	private RadiostreamConnection listenOn;
	private RadiostreamConnection sendOn;

	private DataInputStream listenOnInputStream;
	private DataOutputStream sendOnOutputStream;

	private int portOut;
	private int portIn;

	private BuddyListener buddyListener = new NullBuddyListener();

	private int initialBroadCastPort;

	private boolean foundBuddy = false;

	private RadiogramConnection broadcastConnectionIn;
	private DatagramConnection broadcastConnectionOut;

	private int MAX_BROADCAST_SIZE;

	public Buddy(int broadcastPort) throws IOException {
		this.initialBroadCastPort = broadcastPort;
	}

	public void lookForPair() throws IOException {
		IEEEAddress addy = new IEEEAddress(RadioFactory.getRadioPolicyManager().getIEEEAddress());
		addyStr = addy.asDottedHex();

		System.out.println("I am " + addyStr);

		broadcastConnectionIn = (RadiogramConnection) Connector.open("radiogram://:" + initialBroadCastPort);
		MAX_BROADCAST_SIZE = broadcastConnectionIn.getMaximumLength();
		broadcastConnectionOut = (DatagramConnection) Connector.open("radiogram://broadcast:" + initialBroadCastPort);
		startListenForPartnerResponseThread();
		startLookForBuddyThread();
	}

	public void setBuddyListener(BuddyListener bl) {
		
		if(null != bl) {
			buddyListener = bl;
		} else {
			buddyListener = new NullBuddyListener(); //allows us to reset the currently loaded BuddyListener
		}
		
	}

	public void sendMessage(String message) {
		if (null != sendOn) {
			try {
				if (null == sendOnOutputStream) {
					sendOnOutputStream = sendOn.openDataOutputStream();
				}
				sendOnOutputStream.writeUTF(message);
			} catch (IOException ioe) {
				System.out.println("IOException sending message on partner stream");
				ioe.printStackTrace();
			}
		} else {
			throw new IllegalStateException(
					"Cannot send message.  No buddy found yet.");
		}
	}

	private void startLookForBuddyThread() {
		Thread t = new Thread(new Runnable() {
			public void run() {
				lookForBuddy();
			}
		});
		t.start();
	}

	private void lookForBuddy() {
		try {
			while (!foundBuddy) {
				Datagram dg = broadcastConnectionOut.newDatagram(broadcastConnectionOut.getMaximumLength());
				dg.writeUTF(Buddy.NEED_BUDDY + " " + initialBroadCastPort);
				broadcastConnectionOut.send(dg);

				Utils.sleep(1000);
			}
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
	}

	private void startListenForPartnerResponseThread() {
		Thread t = new Thread(new Runnable() {
			public void run() {
				try {
					while (true) {
						Datagram dg = broadcastConnectionIn.newDatagram(MAX_BROADCAST_SIZE);
						broadcastConnectionIn.receive(dg); // blocking call

						String message = dg.readUTF();

						String otherAddress = dg.getAddress();
						long otherAddressAsNumber = IEEEAddress.toLong(otherAddress);

						if (thisAddressAsNumber != otherAddressAsNumber) {
							handleIncomingBroadcastMessage(dg, message,	otherAddress);
						}
						if (sendOn != null && listenOn != null) {

							System.out.println("Buddy status achieved, no longer going to listen to broadcasts");
							System.out.println("Partner port to send on: " + sendOn.getLocalPort());
							System.out.println("Partner port to listen on: " + listenOn.getLocalPort());

							startListenOnPartnerStreamThread();
							break;
						}
					}

				} catch (IOException ioe) {
					System.out.println("Exception when listening for buddy response");
					ioe.printStackTrace();
				}
			}
		});
		t.start();

	}

	private void handleIncomingBroadcastMessage(Datagram dg, String message, String otherAddress) throws IOException {
		if (message.startsWith(Buddy.NEED_BUDDY)) {
			if (null == sendOn) {
				int otherPort = Integer.valueOf(separateStrings(message)[1]).intValue();
				Datagram response = offerToBeBuddy(otherPort, otherAddress);

				response.setAddress(dg);
				broadcastConnectionIn.send(response);
			}
		} else if (message.startsWith(Buddy.I_WILL_BE_YOUR_BUDDY)) {
			buddyInviteAccepted(message, otherAddress);
		}
	}

	private void buddyInviteAccepted(String message, String otherAddress)	throws IOException {
		foundBuddy = true;

		portOut = Integer.valueOf(separateStrings(message)[1]).intValue();
		sendOn = (RadiostreamConnection) Connector.open("radiostream://" + otherAddress + ":" + portOut);

		portIn = portOut - 1;
		listenOn = (RadiostreamConnection) Connector.open("radiostream://" + otherAddress + ":" + portIn);
	}

	private Datagram offerToBeBuddy(int otherPort, String otherAddress) throws IOException {
		foundBuddy = true;

		portOut = otherPort;
		portIn = portOut + 1;

		System.out.println("Offering to be a buddy to " + otherAddress + "\nSending on " + portOut + "\nListening on " + portIn);

		sendOn = (RadiostreamConnection) Connector.open("radiostream://" + otherAddress + ":" + portOut);
		Datagram response = broadcastConnectionIn.newDatagram(MAX_BROADCAST_SIZE);

		response.writeUTF(Buddy.I_WILL_BE_YOUR_BUDDY + " " + portIn);
		listenOn = (RadiostreamConnection) Connector.open("radiostream://" + otherAddress + ":" + portIn);
		return response;
	}

	private void startListenOnPartnerStreamThread() {
		Thread t = new Thread(new Runnable() {
			public void run() {
				while (true) {
					listenForIncomingMessage();
				}
			}
		});
		t.start();
	}

	private void listenForIncomingMessage() {
		if (null != listenOn) {

			try {
				if (null == listenOnInputStream) {
					listenOnInputStream = listenOn.openDataInputStream();
				}

				String message = listenOnInputStream.readUTF();
				buddyListener.messageRecieved(message);

			} catch (IOException ioe) {
				System.out.println("IOException recieving message on partner stream");
				ioe.printStackTrace();
			}
		} else {
			// Maybe we haven't found a partner yet, so don't spin the processor
			Utils.sleep(100);
		}
	}

	private String[] separateStrings(String msg) {
		StringTokenizer stk = new StringTokenizer(msg, " ");
		String[] result = new String[stk.countTokens()];
		for (int i = 0; stk.hasMoreTokens(); i++) {
			result[i] = stk.nextToken();
		}
		return result;
	}
}

radio.BuddyListener – Classes wishing to have a buddy must have (or be) one of these and give it to the buddy instance

/* 
 * This program is free software; you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation; either version 2 of the License, or 
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU General Public License along 
 * with this program; if not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
package radio;

public interface BuddyListener {
	void messageRecieved(String message);
}

radio.NullBuddyListener – It might be that two buddies are connected and one could be chatting to the other which doesn’t have a BuddyListener attached, in which case this is used instead.

/* 
 * This program is free software; you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation; either version 2 of the License, or 
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU General Public License along 
 * with this program; if not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
package radio;

public class NullBuddyListener implements BuddyListener {

	public void messageRecieved(String message) {
		System.out.println("Warning!  NullBuddyListener being used and messages are getting recieved");
	}
}

radio.RadioFun – This is included for completeness. It’s the app that got run when I was testing the Buddy connections. I don’t think it makes a lot of sense for any one else to use this class except to see how to talk/listen to the buddy.

/* 
 * This program is free software; you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation; either version 2 of the License, or 
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU General Public License along 
 * with this program; if not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
package radio;

import java.io.IOException;

import javax.microedition.midlet.MIDlet;
import javax.microedition.midlet.MIDletStateChangeException;

import com.sun.spot.peripheral.radio.RadioFactory;
import com.sun.spot.util.IEEEAddress;
import com.sun.spot.util.Utils;

public class RadioFun extends MIDlet {

	private Buddy buddy;
	
	public RadioFun() {
	}

	void start() {
		try {
			buddy = new Buddy(60);		
			buddy.setBuddyListener(new BuddyListener() {
				public void messageRecieved(String message) {
					System.out.println("recieved=["+message+"]");
				}
			});
			buddy.lookForPair();
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}

		IEEEAddress addy = new IEEEAddress(RadioFactory.getRadioPolicyManager().getIEEEAddress());
		String addyStr = addy.asDottedHex();
		
		while (true) {
			try {
				buddy.sendMessage("Hello from "+addyStr);
			} catch (IllegalStateException ise) {
				System.out.println("Failed to send message ["+ise.getMessage()+"]");
			}
				
			Utils.sleep(500);
		}
	}

	protected void destroyApp(boolean arg0) throws MIDletStateChangeException {
	}

	protected void pauseApp() {
	}

	protected void startApp() throws MIDletStateChangeException {
		RadioFun rf = new RadioFun();
		rf.start();
	}
}