My Diversions

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.

written by Tom Davies

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!

written by Tom Davies

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?

written by Tom Davies

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.

written by Tom Davies

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!

written by Tom Davies

I’ve been interested in GWT as a way of building rich Internet applications since it appeared, and I’m very pleased to see it getting better and better.

So it’s natural that I’d want to try using it with CAL, a functional language quite similar to Haskell which runs on the JVM.

I used a similar approach to marshalling Javabeans to CAL algebraic types as I used before, but this time I haven’t used any bytecode manipulation — as the Java classes are needed at compile time for the GWT client there isn’t any point in generating them at runtime (although generating them as a separate build step might be useful). I’ve also extended the previous work to include mapping a Java 5 enum to a CAL algebraic type which has constructors with zero parameters.

So in our GWT client we can write:

CaltestServiceAsync service = GWT.create(CaltestService.class);
((ServiceDefTarget) service).setServiceEntryPoint(
    GWT.getModuleBaseURL() + "CaltestService");
service.processPerson(
    new Person(Salutation.MR, "Jim", "Earl", "Jones"), new MyAsyncCallback(...));

and call the CAL function:

public processPerson p =
    let Person s f m l = p; 
    in Person s (toUpperCase f) (lift toUpperCase m) (toUpperCase l);

where the types are:

data Salutation = MR | MRS deriving Inputable, Outputable;
data Person =
    Person salutation :: Salutation 
              firstName :: String 
              middleName :: (Maybe String) 
              lastName :: String 
    deriving Inputable, Outputable;

All this is done via three different annotations, and a special subclass of the GWT RemoteServiceServlet.

The first annotation, @Cal is applied to the GWT service interface, and indicates the CAL module to map the functions on the interface to:

@Cal(workspace = "myworkspace.cws", module = "TDavies.GwtTest")
public interface CaltestService extends RemoteService {
    @Cal
    Person processPerson(Person p);
...

The CAL types Person and Salutation need to be mapped to Java classes:

Person is a simple Javabean with getters and setters for each attribute:

@CalBean(workspace = "myworkspace.cws", module = "TDavies.GwtTest",
    constructorName = "Person")
public class Person implements IsSerializable {
    private Salutation salutation;
    private String firstName;
    private String lastName;
    private String middleName;
...

Note that middleName has the type Maybe String in the CAL type. A value of null maps to Nothing while a value of "x" maps to Just "x".

Salutation is an enum:

@CalEnum(workspace = "myworkspace.cws", module = "TDavies.GwtTest",
    type = "Salutation")
public enum Salutation {
    MR, MRS
}

The names of the enum’s values must be identical to the names of the CAL constructors.

A subclass of RemoteServiceServlet checks for the annotations and transforms the values in both directions.

The source code for this experiment is available via anonymous svn from http://tgdavies.beanstalkapp.com/eddy/browse/trunk/cal. Please note that this repository contains various other half-baked and half-finished experiments! Look at the build.xml file to see how to set up an environment — you’ll need to supply OpenQuark, GWT and Jetty.

In my next post I’ll describe how to persist information on the server.

written by Tom Davies \\ tags: GWT

Fuel additives seem to be the most popular science-based scam outside of alternative medicine.

I’m not sure whether the promoters primarily make their money from investors or customers, but it seems that there’s enough money in it to keep a steady stream of ‘inventions’ coming.

The press (or ‘mainstream media’ as us bloggers call it) loves the ‘Aussie innovation’ angle, so I’m pleased that the Sydney Morning Herald has got a grip and has published a series of many critical articles.

Firepower have now threatened to sue blogger Daniel Rutter, a step which I think they will find counterproductive in the age of Google.

The Herald has treated another magic fuel additive completely differently — again, see Dan for the details. An initial uncritical puff-piece, followed by a mysterious two-stage withdrawal of the article, with no real description of the reasons for doing so.

written by Tom Davies

Apple ships good developer documentation with OS X, and Xcode provides a good UI for searching it, but as I’m a beginner I like to read the conceptual documentation all the way through.

I don’t like reading long documents on a screen, so I print out the documents I want to read 2-up on single sided A4.

This means that I end up with an unordered pile of dog-eared pages.

I have always been interested in the publish on demand idea, so I decided to get hard copies of some of the Apple documentation from http://www.lulu.com — this is permitted by Apple’s terms and conditions, as I read them.

So I concatenated a few documents, converted to Postscript and back to PDF to embed the fonts, and uploaded the result to Lulu. I photoshopped a cover with a Leopard desktop wallpaper image, and it was all ready to go. I had a 712 page book with a spiffy looking colour cover!

The best part was that the indicated cost was $18.77.

Of course once I got to the checkout I was unpleasantly unsurprised to see that shipping was more than double the cost of the book itself.

I don’t want to spend that much money, so I put this experiment on hold for now.

There’s certainly a cost to not living in the US. Perhaps I’ll just wait for the AUD to appreciate a little more against the USD…

written by Tom Davies

Last week a colleague pointed my at this post by Steve Yegge. It discusses ‘code’s worst enemy’ (size) and asks which new language, by being more expressive, can reduce line count.

Dijkstra said (via Overcoming Bias):

“If we wish to count lines of code, we should not regard them as ‘lines produced’ but as ‘lines spent’: the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger.”

Less expressive languages mean that algorithms need to be duplicated to be applied to different data structures. Yegge doesn’t give any examples, but he’s presumably thinking of things like the paradise benchmark which requires that you can write a function which increases salaries for all employees of a company, without any knowledge of the complicated data structure which represents the company other than the type which represents a Salary.

Steve wants a language which runs on the JVM, which is entirely reasonable. It gives you immediate cross-platform consistency, and the potential to use the thousands of libraries written for Java, if the language has been written to support it.

He rejects JRuby because his colleagues don’t like it and chooses the next generation of Javascript, EcmaScript 4. This has an optional type system which looks as though it is a little less expressive than Java 5’s, and of course has the usual Javascript dynamism.

Many of the comments to Steve’s post suggest Scala, a functional/object oriented language with an advanced type system. I have looked at Scala in the past, but have never been able to ‘get into it’. I think this is because it is too much like Java in syntax, and supports the OO paradigm. In Haskell, by contrast, all you have are functions, algebraic types, and type classes, so you just have to get on with it. Scala left me not knowing where to start.

To remedy that I’ve forked out hard cash for the PDF+printed version of Odersky et. al.’s “Programming in Scala”. I hope that the combination of having spent money, and having a physical book will motivate me to learn the language.

written by Tom Davies

My choice for the highlight of OS X 10.5, Leopard, is that Spotlight is worth using. It’s fast enough that it’s replaced Quicksilver (I was never a power Quicksilver user) as my application launcher.

I’ve also found it useful for general searching for emails, contacts, PDF documents and so on.

This inspired my second current spare-time project, a Spotlight importer and Quickview generator for Confluence.

There are two parts to this project, one which is easy and fun and another which is difficult and (relatively) dull. Of course I’ve only done the first part!

The fun part is getting Spotlight (and Quickview) working with Confluence data. Spotlight provides search results at the file level, so each distinct entity you want to be able to find must be represented by a file on your disk. To index a Confluence instance, all you do is crawl a space via the Confluence remote API (OS X has a good XML-RPC library), and create a file for each page/blog-post. The file contains enough information for the Spotlight indexer (which comes along after the file has been created and extracts metadata for the index) to do its job, plus what Quickview needs to create thumbnails and previews in the Finder:

• Page metadata such as creator, editor, creation date, modification date, labels, title and so on.
• The page markup.
• A pre-generated thumbnail — this is just a ’screenshot’ of the page being rendered. This is shown in the finder’s coverflow mode. (In fact it is shown in list mode too, but I think that may be a bug in the finder)
• The HTML Confluence renders for the page, plus all the images shown on the page, so that Quickview can produce an HTML preview view without making any requests to Confluence.
• The original URL the page is at, so that opening the file opens the original page in your default browser.

The Confluence demonstration space looks like this in the Finder’s Coverflow mode:

And previews of pages look like this:

The previews are accessible off-line, but the links all point to the original Confluence instance. A useful enhancement would be to send them through a helper application which determined whether the server was available, and if it was not, opened the locally stored preview HTML.

The duller part is making the process efficient enough that many users can keep their Spotlight indexes up to date without imposing too much load on the Confluence server.

I plan to achieve this using a plugin which provides a specialised RPC service which returns only the data required, in the minimum number of requests, and shares some of the work done between clients by caching. As I have an irrational dislike of XML I’m writing the plugin using the Hessian protocol, which uses a binary encoding, and is available for Objective C. At present the plugin does not do any incremental updates, and doesn’t share data between clients — it just dumps the contents of a space. It also assembles the entire response in memory, rather than streaming it back, so I won’t be installing the plugin on confluence.atlassian.com any time soon

How should the plugin work? I plan to host the data on Amazon S3, with base data produced each night and incremental data produced every few minutes. Each set of data will comprise a file for each ‘level’ of Confluence authorisation. That is, there will be a file containing the data visible to an anonymous user, then a file for each group containing data visible to a member of that group, but not visible to an anonymous user and finally a file for each user containing the data they can see by virtue of their identity, rather than their membership of a group. The user files are likely to be mostly empty.

Files stored in S3 are either private to the account owner, or publicly visible, so data will be encrypted with symmetric encryption. The client requests the keys to which it is entitled from the Confluence instance before downloading the data files from S3.

The advantage of using S3 is that the load on the IT infrastructure hosting Confluence is reduced. If this is not an issue the files could be placed on any available http server.

written by Tom Davies