My Diversions

A relative of mine has a recent HP Pavillion laptop. (I suggested that she get a Mac, but she was concerned about MS Office compatibility).

I was doing some telephone support trying to reattach it to her wireless network tonight. I was ultimately unsuccessful, but I did learn two reasons why HP laptops suck.

1. HP has their own ‘wireless assistant’ wizard, with a plethora of confusing options, so even my limited knowledge of Windows network configuration was useless.
2. The laptop has a wireless on/off switch on its front. This switch was in the off position, but the software couldn’t tell that. All it could say was ‘please check the network switch’ — and it didn’t show a picture giving the switch’s location. I had to Google and then describe the location over the phone. It’s a hardware switch when it should be a software switch, and to add insult to injury, its state isn’t even visible to the software!

Well at least my picture is:

Perhaps the Sudbury, Ontario municipal sculptor will use that photo as a reference when they erect a statue honoring Tom Davies…

I’ve recently found myself not blogging because I didn’t wish to inflict the posts on Planet Atlassian. So now anything non-technical which I don’t think is of interest to subscribers to this blog (Hi to both of you!) appears here.

Along with some colleagues I entered the ICFP programming contest this year.

You can read some more about our experience at Matt’s blog.

I thought the problem — guiding a Mars rover to a goal amongst obstacles — was very well chosen. It was possible to navigate the example maps with very simple software, so everyone could get the satisfaction of seeing their rover succeed. If you had the time and skills, there were a vast number of directions to go in to improve your rover’s performance. This compares favourably with last year’s problem. That problem was very clever, and I had a lot of fun playing with it, but I never got close to having a worthwhile submission because the threshold for even partial success was quite high. So kudos to the ICFP2008 team for creating a problem which has a low barrier to entry while still having the ‘dynamic range’ needed to challenge the top teams.

I’ll definitely participate next year. Among the lessons we learnt:

• Have all the team on the same premises, especially for the first few hours. When you are writing software this quickly you need to all be on the same page all the time.
• For developing geometry based heuristics visualisation is very important. You need to be able to see what your code is trying to do — where it is trying to go, what it thinks is blocking it, when it starts to turn and so on.

We wrote our entry in Java, but over the next few weeks I plan to produce something just as sophisticated in CAL. It is a functional programming contest after all

I’m much happier with the second version:

out3 a =
    let
        renderGroup g =
            let 
                char = head g;
                count = length g;
                renderChars :: Int -> String;
                renderChars n =
                    (fromChar char) ++
                    (if n >1 then  " " ++ (renderChars $ n-1) else "");
            in
                if count > 2 then
                    (renderChars 2) ++ 
                    " <span>" ++ (renderChars (count - 2)) ++ "</span>"
                else
                    renderChars count;
        concatWithSep list = (head list) ++ concatMap (\s -> " " ++ s) (tail list);
    in
        concatWithSep $ map renderGroup (group a);

This only uses one ‘exotic’ list function, group:

group :: Eq a => [a] -> [[a]]
    Splits the specified list into a list of lists of equal, adjacent elements.

My program is longer than Matt’s — roughly twice as long — but I think this version is easier to understand.

Matt’s Javascript for loop has some complicated state, contained in some loop variables which are modified in the body of the loop as well as in the for statement itself. I think that’s a recipe for confusion.

My colleague Matt Ryall wrote about this simple algorithm for marking up a series of letters — which is complex enough to be interesting.

I wrote a version in CAL:

arr = ['a', 'b', 'c', 'c', 'd', 'e', 'e', 'e', 'e', 'e',
          'f', 'e', 'f', 'e', 'f', 'a', 'a', 'a', 'f', 'f', 'f'];

data State = State string :: String current :: (Maybe Char) count :: Int;

out =
    let
        initial = State “” Nothing 0;
        f :: State -> Char -> State;
        f state char =
            let
                State s current count = state;
                charStr = fromChar char;
                appendSameChar = 
                    if count == 2 then
                        s ++ ” <span>” ++ charStr
                    else
                        s ++ ” ” ++ charStr;
                appendDiffChar =
                    if count > 2 then
                        s ++ “</span> ” ++ charStr
                    else
                        s ++ ” ” ++ charStr;
            in
                case current of
                    Nothing -> State (fromChar char) (Just char) (1 :: Int);
                    Just c ->
                        if c == char then
                            State appendSameChar (Just char) (count+1)
                        else
                            State appendDiffChar (Just char) 1;
            ;
        finalState = foldLeftStrict f initial arr;
    in
        finalState.State.string ++(if finalState.State.count > 2 then
            “</span>”
        else
            “”);

Positive proof that you can write verbose, confusing code in any language — but at least this code had no bugs — once it compiled it worked correctly first time.

As a follow up to this I will try to do better!

This site has potential to be quite interesting, depending on the quality of the instructions.

It may also self select an interesting group of people — I wonder what a version of Slashdot which only those people knew about would be like?

The launch of Google’s AppEngine has given me the obligation to find out what it’s all about, and the opportunity to learn a bit more about one of our products, Crowd — and, of course, pick up some Python along the way.

I began by working through Google’s Guestbook example, and then replaced its use of Google’s Users API with single sign on via Crowd.

Crowd Single Sign On

A Crowd client application authenticates via SOAP calls to a Crowd server. The sequence looks like this:

Duck Punching httplib for SOAP

I used the soaplib Python SOAP library to talk to Crowd. This library uses httplib to talk to the SOAP server, which is a problem as AppEngine only allows applications to use Google’s HTTP request mechanism.

I adapted soaplib to use Google’s fetch function by ‘Duck Punching’, also known as ‘Monkey Patching’. This globally overrides a library class with a class of your own:

import httplib

class AppEngineHTTPConnection(object):
... delegate the functions called by soaplib to Google's fetch ...

class Crowd(object):
def __init__(self, path, applicationName, applicationPassword):
    # do some monkeypatching
    httplib.HTTPConnection = AppEngineHTTPConnection

Simple, and safe in this case, as we want any client of httplib to use our replacement.

By default, soaplib puts an empty namespace on strings and arrays, so I cut, pasted and renamed these classes, changing them to explicitly set the correct namespace. A Pythonista could probably duck-punch their way out of that with less duplication

My modified Guestbook application adds login and logout URLs which authenticate with Crowd and create the appropriate cookie.

Caveats and Conclusions

AppEngine doesn’t support SSL, so your username and password are transmitted unencrypted to the application. To avoid this you could write a small authentication application to be hosted with your Crowd server under SSL.

Your Crowd server and your Google AppEngine application need to be on the same domain, in order to share the Crowd SSO cookie. This should be possible by assigning your domain to a Google Apps account, but I haven’t managed to add my Google Apps domain to my Google AppEngine application yet.

Python

I strongly dislike weakly typed languages such as Python. IDEs can’t sensibly provide code completion, and I found that I made many errors which were only caught at runtime. Most of these were in code which could easily have been type checked at compile time.

The sooner type inference is added to Python or AppEngine supports JVM languages, the happier I’ll be. I expect the latter to happen first.

Code

The code for this AppEngine app can be found in my crowd-appengine Git repository. As usual, get a snapshot if you don’t have a git client installed.

aka, attack of the TLAs.

This webapp’s architecture is depicted below:

• The browser runs a Javascript thick client compiled from Java by GWT. Some of the classes have CAL annotations. These don’t affect the client, but allow the server side of the GWT RPC protocol to call CAL functions.
• The CAL functions store persistent data using Software Transactional Memory. This is a simple Java implementation based on the description in Composable memory transactions. It is given a CAL interface similar to a subset of Haskell’s Control.Concurrent.STM.
• Each STM TVar stores its value as a key-value pair in a Berkeley DB Java Edition database.

Any data structure can be built on top of TVars — and each TVar is a mutable reference, these are not functional data structures.

In this application a simple hashmap is used. Skiplists and relaxed balance btrees are other data structures which might allow reasonable concurrency too, while also providing features like in-order traversal.

This illustrates the relationship between the CAL objects in the CAL ExecutionContext and key-value pairs in the BDB:

The root of the persistent data structure is a TVar with a ‘well-known’ id — 1 in the example, which is created by a constant applicative form function. This TVar will retrieve its value from the BDB when it is created, or if no value exists for its id, it will be initialised with a default value, which in the case of a hashmap is an array of TVars, each containing an empty list of key-value pairs. A value stored in a TVar is persisted to the BDB by serialising it using CAL’s default output function and Xstream, which can serialize and deserialize instances which are not serializable and do not have accessible constructors.

TVars themselves have transient values, so only the id is persisted — the value is lazily loaded when required, using the id. So even though a TVar may persist a complicated tree of CAL algebraic values, this stops at the first TVar. (The root TVar is never persisted itself — only its value is stored).

You can get a snapshot here — just unpack it and run ant run, then point your browser at http://localhost:8080/caltest.html. Or browse the source.

The ant build script includes a target run-tests which runs some Selenium tests. Stop the server before running that target.

Note that the source code includes various bits of half-baked rubbish, in addition to that described above!