/dev/collective

This post is literate Haskell

Update: Almost immediately after posting this, I started receiving helpful comments that perhaps introducing multithreading is an overkill here. While I do like the notion of asynchronous message passing via MVars, the comments do have a strong point. Instead of changing the post, and thereby doing the commenters a disservice by invalidating their comments, I just put a non-threaded version of this on gist.github. Indeed, it is simpler than what is found on this page and even a little bit faster :)

I lurk on several mailing lists, one of them being the MochiKit list. One thing recently discussed there is a tool to let users of MochiKit create their own customized version of it. This entails a GUI that allows a user to select which module he or she needs, and the webapp takes care of including all the dependencies as well.

This led me to a fun exercise. Say we have a dependency graph, which by nature must by a directed acyclic graph (DAG), otherwise you could have circular dependencies. Now, if you have N modules with no interdependencies, then there are 2^N possible ways of choosing a subset. However, if you restrict yourself only to those subsets that work, i.e. those where all dependencies of included modules are also included, then that puts a limit on this number.

For example, if you have two modules Base and Sub, and the latter depends on the former, then you would not allow the set containing just Sub. In mathematical terms, you only allow closed subsets of modules, where closed means:

A subset S of modules is closed if and only if the following holds:

• If M is a module in S, and M depends on module P, then P is also in S

MochiKit contains around 15 modules and their dependency graph looks like this:

I wanted to know if it was feasible to pre-generate all legal combinations of modules, and the main factor of that is exactly how many are there. Clearly there are fewer than the roughly 16.000 which there would be if there were no dependencies. Generating all dependency-closed subsets seemed like a very classical graph theoretical problem so someone must have written an algorithm for it. I asked my friend and professor, Magnús Már, for some terms to put into Google. Instead he gave me a hint on how to solve this.

The hint is this: To every closed subset of modules, there is a distinct anti-chain of modules that represents that set. An anti-chain of modules is a collection of modules such that no two depend on each other, neither directly nor indirectly.

For example, say we want the modules Logging, DOM, Style, Selector and Visual. That means we have to take all the modules in the green area below. The anti-chain for this set of modules are the blue modules.

You can see how the set of the blue modules is the smallest set of modules needed to pull in all the modules that we want.

Since there is a one-to-one correspondence between anti-chains and legal subsets, then we need only find the anti-chains and we can generate the subsets.

First some preliminaries,

> module Main where
> 
> import Control.Concurrent (forkIO)
> import Control.Concurrent.MVar
> import Data.Maybe (fromJust)
> import Data.List (nub, intersect)

We then set up our data as a simple list of pairs, where the first element is the module name and the second is a list of its dependencies. This list must be ordered in topological order, meaning that a module may not appear before any of its dependencies. This is easy to do by hand by looking at the above picture.

> dependencies = [
>  ("Base",[]),
>  ("DateTime",["Base"]),
>  ("Format",["Base"]),
>  ("Iter",["Base"]),
>  ("Async",["Base"]),
>  ("DOM",["Base"]),
>  ("Style",["Base"]),
>  ("Color",["DOM", "Style"]),
>  ("Logging",["Base"]),
>  ("LoggingPane",["Logging"]),
>  ("Selector",["DOM", "Style"]),
>  ("Signal",["DOM", "Style"]),
>  ("Visual",["Color"]),
>  ("DragAndDrop",["Iter","Signal","Visual"]),
>  ("Sortable",["DragAndDrop"])
>  ]
> 
> -- For convenience, derive the list of module names 
> modules = map fst dependencies

The first thing we need to do is to generate all anti-chains. We will do this in a dedicated thread and feed the anti-chains as we find them, one by one, on an MVar. Note that the MVar holds a Maybe value, this is so that we can indicate the end by sending Nothing.

The algorithm is simple backtracking through recursion, we start with the empty set which is always an anti-chain. At each step, we do the following.

1. We check if the candidate element is dependent on any element in the anti-chain already. If it is not, we can add it and recurse.

2. Since the anti-chain is still valid without the element, we also recurse on the unchanged anti-chain but discard the candidate element.

The recursion bottoms up when there are no more candidate elements to consider. Note that the topological order of candidates is crucial here.

The helper function accepts determines if a candidate is allowed in a chain. This is simply done by closing the candidate (see later) and seeing if there is an overlap with the current anti-chain.

> antichains :: MVar (Maybe [String]) -> IO ()
> antichains channel = antichains' [] modules >> putMVar channel Nothing
>     where
>       antichains' :: [String] -> [String] -> IO ()
>       antichains' ac [] = putMVar channel (Just ac) >> return ()
>       antichains' ac (candidate:rest) =
>           do if ac `accepts` candidate
>                 then antichains' (candidate:ac) rest
>                 else return ()
>              antichains' ac rest
>       chain `accepts` candidate = null $ intersect (closure [candidate]) chain

Above we mentioned closing a module, or more precisely a set of modules. This means to take a set of modules and adding all modules needed to make it closed with respect to dependencies. This is used both in the accepts helper above but also to map the anti-chains to what we ultimately want, the closed sets.

> closure :: [String] -> [String]
> closure ms = 
>     let missing = nub $ filter (not . flip elem ms) 
>                   $ concatMap (fromJust . flip lookup dependencies) ms
>     in
>       if null missing
>          then ms
>          else closure (ms ++ missing)

The anti-chain generator above feeds the anti-chains to an MVar. The following IO action is run in a second thread and it eats off the anti-chains from the MVar, closes them up and prints. We use a second MVar to notify the main thread when we are done.

> printer :: MVar () -> MVar (Maybe [String]) -> IO ()
> printer stop in_ = 
>     do v <- takeMVar in_
>        case v of
>          Just xs -> putStrLn $ show $ closure xs
>          Nothing -> putMVar stop ()
>        printer stop in_

Finally, to tie it all together, the main action creates the MVars for communication and sparks separate threads for the anti-chain generation and for the printing.

> main :: IO ()
> main = do chan <- newEmptyMVar
>           stop <- newEmptyMVar
>           forkIO $ printer stop chan
>           forkIO $ antichains chan
>           takeMVar stop
>           return ()

That’s it! The result: For the dependency graph of MochiKit above, there are only 817 legal combinations of modules. Actually - 816 if you discount the empty one :)

I’ll leave it up to someone else to answer the original question about feasibility of generating and storing that number of files.

I want to show you a neat trick method when constructing parsers with Haskell and Parsec.

While writing a parser for CCS, a process description language (don’t worry too much about it), I found I needed to parse constructs with a suffix operator. To provide a little context, the relevant grammar is this.

P ::= 0 | a.P | ... | P[f] | P \ S

where … indicates I’ve omitted some irrelevant stuff. Here, P is a process - the entity CCS is meant to describe. a is a so-called action label, just think of it as a generic label. a.P stands for a process that can perform an a action and then become the process specified after the dot. 0 (zero) stands for a special process that cannot do anything, the deadlocked process.

f is a mapping from such labels to labels, called a relabelling and is commonly specified with a list of pairs b/a,d/c,... which indicates that a maps to b, c to d etc. S is a set of such labels, represented in the normal manner with curly braces {a,b,c,...}. The construct P \ S is called a restriction, informally it means P cannot perform any of the actions in S.

In summary,

• a.a.0 is a process that can do two a actions and then stop
• P [b/a] is whatever P is, except any a performed by P will be changed to a b
• P \ {a,b} is whatever P is, except a or b actions are not allowed

Now, [f] and \ S can be considered postfix unary operators on processes, with some additional structure, the f and the S. Since they are postfix there is no need to define their relative precedence, their order is enough. I.e.

a.0 [b/a] \ {b} [d/c,e/d] \ {e,g}

is unambiguous. Our Haskell ADT to represent the abstract syntax tree looks like this,

type Action = String
type Relabeling = Map.Map Action Action
type Restriction = Set.Set Action
 
data Process
    = Null
    | Prefix Action Process
    | ...
    | Relabel Process Relabeling
    | Restrict Process Restriction
    deriving (Eq, Show, Ord)

We want the example above to be parsed into this value (indented for clarity),

Restrict (
    Relabel (
        Restrict (
            Relabel (
                Prefix "a" Null
            ) (Map.fromList [("a","b")])
        ) (Set.fromList ["b"])
    ) (Map.fromList [("c","d"),("d","e")]
) (Set.fromList ["e", "g"])

My initial attempt at writing a parser for these constructs was ugly and complex. I was trying in one rule to parse a bunch of relabellings and restrictions and construct the appropriate value from the process that had already been parsed, cluttering the rules for other constructs with this logic. I thus went to the best documentation of Haskell, the #haskellirc channel, and asked for opinions. Christophe Poucet (vincenz) showed me the light and pointed out that a parser could well return a function,

April 13th, 2008
15:24 < vincenz> Arnar: what about...
15:24 < vincenz> process_adapter :== relabeling | restriction
15:24 < vincenz> and have those return the type
15:24 < vincenz> Process -> Process

And therein lies the trick. Instead of constructing the correct value, I simply parse a sequence of adapters, each of which can be a relabeling or a restriction, in each step returning the function that wraps a process in the relevant constructors.

relabeling :: Parser Relabeling
relabeling = do rs <- brackets $ commaSep1 rename
                return $ Map.fromList rs
                where
                  rename :: Parser (Action,Action)
                  rename = do s1 <- lexeme action
                              symbol "/"
                              s2 <- lexeme action
                              return (s2,s1)
 
restriction :: Parser Restriction
restriction = do symbol "\\"
                 ss <- braces $ commaSep1 action
                 return $ Set.fromList ss
 
process_adapter :: Parser (Process -> Process)
process_adapter = do restr <- restriction
                     return (\p -> Restrict p restr)
                  <|>
                  do rel <- relabeling
                     return (\p -> Relabel p rel)

Very simple, very clean. Now, parsing a process followed by a sequence of such adapters is trivial. We then feed the process through the adapter functions in order, i.e.

adaptedProcess :: Parser Process
adaptedProcess = do p <- simpleProcess
                    adapters <- many process_adapter
                    return $ foldr (flip (.)) id adapters p

I especially like that last line, foldr (flip (.)) id adapters p. Remember adapters has the type [Process -> Process], i.e. a list of adapters. If this list is [f1,f2,...,fN], then

foldr (flip (.)) id adapters

will give us the composition of these in the correct order, namely

\x -> fN ( ... (f2 (f1 (id x))) ...)

All that’s left to do is to apply this on the original process and out pops a correctly wrapped one.

I think this is very neat and it showcases the power of first-class functions. If you don’t see the beauty here, feel absolutely free to write me off as eccentric ;o)

You can find the complete code and a PDF writeup of the CCS project right here.

I love Haskell. I love many things about it, but one of its main attractions for me is that it is lazy. I guess I like that because I’m lazy myself.

Lazyness in Haskell means that we get infinite lists (or streams) for free - i.e. they don’t need any special handling over finite lists. Granted, other languages have infinite lists, but in Haskell any regular list has the natural potential of being infinite so we don’t need any specific syntax or constructors for them.

So, when I read about a Rutgers graduate student named Eric Rowland that recently discovered a simple prime-number generating formula, I decided to try it out in Haskell. Turns out it is extremely simple.

The generating formula is based on the sequence a(n) that you get by setting a(1) = 7 and then for n ≥ 2:

a(n) = a(n-1) + gcd(n,a(n-1))

In Haskell, running in interactive mode (GHCi), we define this by

Prelude> let a' = (1,7) : (map ( \(n,x) -> (n+1, x + (gcd (n+1) x))) a')
Prelude> take 10 a'
[(1,7),(2,8),(3,9),(4,10),(5,15),(6,18),(7,19),(8,20),(9,21),(10,22)]
Prelude> let a = map snd a'
Prelude> take 23 a
[7,8,9,10,15,18,19,20,21,22,33,36,37,38,39,40,41,42,43,44,45,46,69]

Note that each element of a’ is a tuple of the index n and the value a(n). By taking differences between successive values of this sequence, you always get either the number 1 or a prime number (proving this is Rowland’s contribution).

Prelude> let d = zipWith (-) (tail a) a
Prelude> take 23 d
[1,1,1,5,3,1,1,1,1,11,3,1,1,1,1,1,1,1,1,1,1,23,3]

So far, so good. Now in one step we remove the 1-s by using filter and get rid of duplicates by using nub (which is defined in the List module).

Prelude> :m +List
Prelude List> let primes = nub $ filter (/= 1) d
Prelude List> take 23 primes
[5,3,11,23,47,101,7,13,233,467,941,1889,3779,7559,15131,53,30323,60647,121403,242807,19,37,17]

Neat! The list primes is of course infinite and we could pluck the values off it as long as we like, and Haskell’s laziness will make sure values are only computed on demand. Rowland’s paper contains the details of the math.

Note: This post is literate Haskell, you can copy the whole text to a .lhs file and compile it with GHC.

A friend of mine was showing me a very simple and elegant parser for JSON, written in Scala. As an excercise, I decided to write one in Haskell, using the Parsec parser combinator library. Here’s a quick walkthrough.

First we need some imports,

> import qualified Data.Map as Map
> import Control.Monad (liftM)
> import Text.ParserCombinators.Parsec
> import qualified Text.ParserCombinators.Parsec.Token as T
> import Text.ParserCombinators.Parsec.Language

Now, to represent a JSON value, we use an algebraic data type. For simplicity, we’ll only worry about integers and not floating point numbers. The definition of the type is simple, to be concise we use single letter constructor names (not a good idea if you want to publish a proper library).

> data JSON = S String 
>           | I Integer 
>           | B Bool 
>           | L [JSON] 
>           | O (Map.Map String JSON)
>           deriving Show

Now, to make our life somewhat easier, we’ll make use of the facilities in the ParsecToken module. This module provides us with ways to create functions for generic lexers, which deal correctly with whitespace (and comments) in a language. The first step is to create a language definition, in our case it only specifies how JSON comments are delimited. From the definition we create a token parser which we call lexer.

> ldef = emptyDef { commentStart = "/*"
>                 , commentEnd = "*/"
>                 , commentLine = "//"
>                 }
> lexer = T.makeTokenParser ldef

We can now pass lexer to the convenience functions of ParsecToken. As is common with such parsers, we rebind their names in our module to spare us referring to lexer every time we use them.

> symbol        = T.symbol        lexer
> stringLiteral = T.stringLiteral lexer
> integer       = T.integer       lexer
> squares       = T.squares       lexer
> braces        = T.braces        lexer
> commaSep      = T.commaSep      lexer

And now the parser itself. The basic element is a JSON value. From now on I’ll include the type signatures to make things easier to follow, but they are of course not necessary.

> value :: Parser JSON
> value = liftM S stringLiteral
>     <|> liftM I integer
>     <|> liftM B boolean
>     <|> liftM L list
>     <|> liftM O object

A value is simply a choice between each of the basic types, a string, an integer, a boolean, a list of values or an object (which is simply a mapping from strings to values). We defer each to its own parser, and simply lift the value constructors to the parser monad. We get parsing of strings and integers completely for free from the ParsecToken module, but the other three we need to handle ourselves. The boolean case is simple,

> boolean :: Parser Bool
> boolean = do symbol "true"
>              return True
>       <|> do symbol "false"
>              return False

Surprisingly, the list is even simpler, due to the helpers from ParsecToken.

> list :: Parser [JSON]
> list = squares $ commaSep value

Parsing objects is also fairly simple, basically just like list except that instead of parsing a comma seperated list of values, we parse a comma seperated list of key/value pairs. Such a pair is handled by the nested keyValue parser.

> object :: Parser (Map.Map String JSON)
> object = liftM Map.fromList $ braces $ commaSep keyValue
>          where
>              keyValue = do key <- stringLiteral
>                            symbol ":"
>                            val <- value
>                            return (key, val)

And that’s it! To test this easily, we finally add a main action that simply parses a JSON value from standard input.

> main = getContents >>= parseTest value

Testing the parser

A simple test, including a comment in the middle:

arnarb-macbook:tmp arnarb$ runhaskell json.hs 
[1,"two",false,{"one":1, /* a comment here */ "two":2, "list":[]}]
< here I pressed ctrl-d to insert an EOF, rest is output >
L [I 1,S "two",B False,O (fromList [("list",L []),(”one”,I 1),(”two”,I 2)])]

As an more complex test, we run it on the first example from json.org (newlines and indent added to the output for clarity).

arnarb-macbook:tmp arnarb$ runhaskell json.hs 
{
  "glossary": {
    "title": "example glossary",
    "GlossDiv": {
      "title": "S",
      "GlossList": {
        "GlossEntry": {
          "ID": "SGML",
          "SortAs": "SGML",
          "GlossTerm": "Standard Generalized Markup Language",
          "Acronym": "SGML",
          "Abbrev": "ISO 8879:1986",
          "GlossDef": {
            "para": "A meta-markup language, used to create markup languages such as DocBook.",
            "GlossSeeAlso": ["GML", "XML"]
          },
          “GlossSee”: “markup”
        }
      }
    }
  }
}
< here I pressed ctrl-d to insert an EOF, rest is output >
O (fromList [
    ("glossary",O (fromList [
        ("GlossDiv",O (fromList [
            ("GlossList",O (fromList [
                ("GlossEntry",O (fromList [
                    ("Abbrev",S "ISO 8879:1986"),
                    ("Acronym",S "SGML"),
                    ("GlossDef",O (fromList [
                        ("GlossSeeAlso",L [S "GML",S "XML"]),
                        (”para”,S “A meta-markup language, used to create markup languages such as DocBook.”)
                    ])),
                    (”GlossSee”,S “markup”),
                    (”GlossTerm”,S “Standard Generalized Markup Language”),
                    (”ID”,S “SGML”),
                    (”SortAs”,S “SGML”)
                ]))
            ])),
            (”title”,S “S”)
        ])),
        (”title”,S “example glossary”)
    ]))
])

Finally, we should note that many people have done this before :)

Edits:

• Added link to Scala version.
• Small revisisons, thanks to kpreid on #haskell for pointing out braces and squares.
• Stop lugging lexer around, thanks to Paczesiowa on reddit for useful suggestions.

For the impatient: Scroll down for the video.

The 2008 world championship in General Game Playing is currently on. AI bots from various universities around the world compete in playing games they’ve never seen before. The bots act as web servers to which a game master connects and uploads a game description, a first-order logic description of game rules in a special language called GDL. The games can be single- or multi-player, but must be perfect information games.

I am proud to say that the world champions of last year (2007) are my friends and colleagues at RU, Hilmar Finnsson and Yngvi Björnsson. Their team, which now includes Gylfi Þór Guðmundsson, and their bot CADIAPlayer, are quite busy these days defending the title.

Update July 18th: The RU team succeeded in defending the title and CADIA Player is the 2008 General Game Playing champion.

CADIAPlayer relies on an implementation of the UCT algorithm. I’m not qualified to explain it here but if you are interested, Hilmars M.Sc. thesis has all the gory details. This weekend, me, Hilmar and Stefán Freyr did a little experiment with a very interesting piece of software called Ubigraph. Ubigraph is basically just a application that fires up a 3D window and starts listening for XML-RPC requests over HTTP. Through its XML-RPC API, client applications can create graph nodes, edges and alter their styles and Ubigraph lays them out in 3D with a powerful multi-core algorithm and displays it in the window. The user can then zoom and move around the graph. Updates to the graph are rendered in real-time.

To see the CADIAPlayer in action, Hilmar added commands to the code to log to a file whenever it created new nodes (representing game states), when nodes were deleted and when the player made an actual move. Me and Stefán cobbled together a small Python script, which Hilmar then tweaked some more (source below), that eats this log and sends the relevant commands to Ubigraph at a fixed rate. The result is a beautiful display of how the algorithm works and shows how it explores areas of the search graph that look interesting before deciding on a move.

Of course, words are useless here so here’s a video of it in action, playing a game of Othello. The video is quite long (18 minutes) so I recommend skipping around in it, the action starts after 13 seconds and the middle and the ending are also interesting. At about 3:50 you start to see loops forming, meaning two different lines of play reach the same state, and the tree actually becomes a graph.

The nodes represent states and edges represent a legal game move. As old nodes are removed from memory, you can see how their child nodes become disconnected, they snap away from the tree (chasing all child nodes for deletion is too expensive) but they are cleaned up in subsequent deletion phases. The pink node represents the current state of the game and the growth in the tree shows where CADIAPlayer is exploring and evaluating possible moves. The numbered nodes represent the actual playout so far and the numbers are the players confidence values, the closer they are to 100, the more optimistic it is about winning the game.

The log file is quite simple, the first character of a line determines the entry type. For the main purpose we have two types, "C 123 456" means create a new node with id 123 as child (successor) of node 456, and "D 123" which simply means delete node 123. There are other commands, but those are the main ones. The Python program that feeds this to Ubigraph looks like this,

    # -*- coding: utf-8 -*-
    import sys
    import time
    import xmlrpclib
    import itertools
    import gradient
 
    NPS = 100  # nodes per second
    server_url = 'http://127.0.0.1:20738/RPC2'
 
    playercolors = itertools.cycle(['#ff00ff', '#ffd9ff'])
 
    weight_colors = [ (0.0,   (1.0, 0.0, 0.0)), # red
                      (50.0,  (0.0, 0.0, 1.0)), # yellow
                      (100.0, (0.0, 1.0, 0.0)), # green
                    ]
 
    def weight2color(w):
        c = gradient.piecewise_interpolate(weight_colors, w)
        return '#' + ''.join(map(lambda x: ("%02x" % int(255*x)), c))
 
    if __name__ == '__main__':
 
        server = xmlrpclib.Server(server_url)
        G = server.ubigraph
 
        G.clear()
 
        current = None
        interval = 1.0/NPS
 
        seen = {}
        path = set()
 
        log = file(sys.argv[1], 'r')
        for line in log:
            line = line.strip()
            if not line:
                continue
            params = line.lower().split()
            cmd = params[0]
 
            if 'c' == cmd:
                new, parent = map(hash, params[1:])
                if new in seen:
                    if parent not in seen[new]:
                        G.new_edge(parent, new)
                        seen[new].append(parent)
                else:
                    seen[new] = [parent]
                    G.new_vertex_w_id(new)
                    G.set_vertex_attribute(new, 'color', weight2color(50))
                    if params[2] == '0':
                        current = new
                        G.set_vertex_attribute(new, 'color', playercolors.next())
                        path.add(new)
                    else:
                        e = G.new_edge(parent, new)
                        G.set_edge_attribute(e, "oriented", "true")
                    time.sleep(interval)
 
            elif 'd' == cmd:
                if hash(params[1]) not in path:
                    # Uncomment this next line and comment second next one if you want
                    # deleted nodes to be coloured gray instead of being nuked.
                    # G.set_vertex_attribute(hash(params[1]), 'color', '#666666')
                    G.remove_vertex(hash(params[1]))
                    time.sleep(interval)
 
            elif 'u' == cmd:
                n, w = hash(params[1]), float(params[2])
                G.set_vertex_attribute(n, 'color', weight2color(w))
                G.set_vertex_attribute(n, 'label', "%0.2f" % w)
 
            elif 'n' == cmd:
                new = hash(params[1])
                G.set_vertex_attribute(new, 'color', playercolors.next())
                current = new
                path.add(new)

Oh, and that gradient module is one that often comes in handy, here it is for sake of completeness.

# -*- encoding: utf-8 -*-
 
def interpolate(c1, c2, t):
    """
    Interpolates between two colours c1 and c2 by the variable t.
    t should be in the range [0.0, 1.0]. interpolate(c1,c2,0) will return
    c1 and interpolate(c1,c2,1) will return c2. interpolate(c1,c2,0.5) will
    return the color in the middle.
 
    The colours c1 and c2 should simply be number triplets (for example RGB values).
 
    Example:
 
    >>> c1 = (1,2,3)
    >>> c2 = (11,12,13)
    >>> t = 0.5
    >>> interpolate(c1,c2,t)
    (6.0, 7.0, 8.0)
    """
 
    if t <= 0: return c1
    if t >= 1: return c2
 
    ipol = lambda a, b, t: (1.0-t)*a + float(t)*b
 
    return (ipol(c1[0], c2[0], t),
            ipol(c1[1], c2[1], t),
            ipol(c1[2], c2[2], t))
 
    # equivalent:
    # from itertools import starmap
    # return tuple(starmap(ipol, zip(c1,c2,(t,t,t))))
 
def piecewise_interpolate(stops, t):
    """
    Gives a piecewise linear interpolation of values in stops by t.
    stops should be a list (or an iterable) of paris of the form (value,colour)
    where colour is a numerical triplet. t should be a real number.
 
    The function returns an interpolation of the colours in stops determined
    by the parameter t. If t falls out of the range of specified values, the
    appropriate end colours will be returned
 
    Examples:
    >>> stops = [ (0.0, (1.0, 0.0, 0.0)), # red
    ...           (3.3, (1.0, 1.0, 0.0)), # yellow
    ...           (6.7, (0.0, 1.0, 0.0)), # green
    ...           (10.0, (0.0, 0.0, 1.0)),# blue
    ...         ]
    >>> piecewise_interpolate(stops, 0.0)
    (1.0, 0.0, 0.0)
    >>> piecewise_interpolate(stops, 1.0)
    (1.0, 0.30303030303030304, 0.0)
    >>> piecewise_interpolate(stops, 5)
    (0.5, 1.0, 0.0)
    >>> piecewise_interpolate(stops, 10.0)
    (0.0, 0.0, 1.0)
    >>> piecewise_interpolate(stops, 11.0)
    (0.0, 0.0, 1.0)
    >>> piecewise_interpolate(stops, -1.0)
    (1.0, 0.0, 0.0)
    """
    stops = stops[:] # copy for sorting
    stops.sort()
    values, colours = zip(*stops)
    if t <= values[0]: return colours[0]    # below range
    if t >= values[-1]: return colours[-1]  # above range
 
    # find which "bin" t falls in
    bin = 0
    while t > values[bin]: bin += 1
 
    # normalize t in the interval (0,1]
    normalized_t = (t - values[bin-1]) / (values[bin] - values[bin-1])
 
    return interpolate(colours[bin-1], colours[bin], normalized_t)
 
def _test():
    import doctest
    doctest.testmod()
 
if __name__ == "__main__":
    _test()

One of the most tedious and tricky things a web developer does is designing good form validation. It poses interesting challenges in UI design, but also in not being a hurdle for interested users. One of the most common thing I experience when signing up for stuff is this.

And the reason… is this

(not my actual phone number) The problem here is that Iceland doesn’t use area or city codes - there is one uniform set of seven-digit phone numbers across the whole country. However, Apple doesn’t make room for that, it assumes all phone numbers must have an area code. In this case it is easy enough to get past this, I just move the first digit to the area code.

Another common error is in validating e-mail addresses. Many websites assume an email address has to be xxx@yyy.zzz where the x, y and z must be alphabetical or numerical or perhaps a dash (-) and a period(.). However, e-mail addresses in general are not constrained to that. A useful feature of GMail is that you can add a plus (+) after your username, followed by any string you want. For example user+aha@gmail.com gets routed to user@gmail.com, but the owner of that mailbox can filter on the +aha part if she wants. This is very handy when registering for something, you can indicate where you are registering in the address and set up filters to route messages to that address directly to a tag (such as the trash). The problem is that many (most?) websites don’t allow you to register an address containing the +.

Perhaps the silliest example was the one that this guy fell victim to, a checkbox that said “uncheck this box if you don’t want us to email you”, but then the form wouldn’t validate unless the box was checked. Ingenious.

I’m writing myself a small website, with basic contact info and perhaps a blog. For the fun of it, I’m using Django (for those not in the know, Django is a Python web application framework).

Edit: My website is up and running although there is no code content yet to show off the stuff discussed below.

Now, I don’t like most WYSIWYG editors at all. I think they only help you remove the semantic structure from your documents and makes you focus on visual layout instead. I find it best to either predesign the visual stuff and then not worry about it - or write my document first and then see what visual layout fits the semantic structure.

For this reason, I like markup languages, such as Markdown which I’m using right now to write this entry. However, for my website/blog I wanted something a little more powerful and extendable. Since I’m a Python programmer by trade, what better language to use than reStructuredText, the language often used for inline documentation of Python code?

I don’t want to waste your time by deitailing my preferences, what I do want to write about is how easy it is to extend reStructuredText with custom code. In my case, I wanted to be able to write inline LaTeX formulas on my site and have them automatically converted to PNGs for display in the browser. There is a WordPress plugin but a custom version seems to in effect on the public Wordpress.com blog host as well. The following is my account of quickly implementing this in Python and plugging it into my website as a rST (reStructuredText) extension.

LaTeX rendering

First step is to throw together a script to render the LaTeX formulas into a PNG. For this I shamelessly stole the idea from the LatexRender, the WordPress plugin mentioned above. First off, we need some imports and a function to wrap a formula in a proper document. The preamble shown here corresponds to the one from LatexRender, but of course you can use your own.

import tempfile
import os
import hashlib
import shutil
 
def wrap_formula(formula, font_size, latex_class):
    return r"""\documentclass[%(font_size)spt]{%(latex_class)s}
               \usepackage[latin1]{inputenc}
               \usepackage{amsmath}
               \usepackage{amsfonts}
               \usepackage{amssymb}
               \pagestyle{empty}
               \newsavebox{\formulabox}
               \newlength{\formulawidth}
               \newlength{\formulaheight}
               \newlength{\formuladepth}
               \setlength{\topskip}{0pt}
               \setlength{\parindent}{0pt}
               \setlength{\abovedisplayskip}{0pt}
               \setlength{\belowdisplayskip}{0pt}
               \begin{lrbox}{\formulabox}
               $%(formula)s$
               \end{lrbox}
               \settowidth {\formulawidth}  {\usebox{\formulabox}}
               \settoheight{\formulaheight} {\usebox{\formulabox}}
               \settodepth {\formuladepth}  {\usebox{\formulabox}}
               \newwrite\foo
               \immediate\openout\foo=\jobname.depth
                   \addtolength{\formuladepth} {1pt}
                   \immediate\write\foo{\the\formuladepth}
               \closeout\foo
               \begin{document}
               \usebox{\formulabox}
               \end{document}""" % locals()

Now we need a function that given a formula and a destination directory, invokes the necessary commands to make a PNG and saves it in that directory. For efficiency, we take the MD5 sum of the formula and use it as a name for the PNG, so we can simply skip it if one exists already (taking our chances on hash collisions).

def render_formula(formula, folder, font_size=11, latex_class='article'):
    hash = hashlib.md5(formula).hexdigest()
    if os.path.exists(os.path.join(folder, hash + ".png")):
        return hash + ".png"
 
    tempdir = tempfile.mkdtemp()
    curpath = os.getcwd()
    os.chdir(tempdir)
 
    f = file('formula.tex', 'w')
    f.write(wrap_formula(formula, font_size, latex_class))
    f.close()
 
    status = os.system("latex --interaction=nonstopmode formula.tex")
    assert 0==status, tempdir
 
    status = os.system("dvips -E formula.dvi -o formula.ps")
    assert 0==status, tempdir
 
    status = os.system("convert -density 120 -trim -transparent \"#FFFFFF\" formula.ps formula.png")
    assert 0==status, tempdir
 
    os.chdir(curpath)
 
    shutil.copyfile(os.path.join(tempdir, "formula.png"), os.path.join(folder, hash + ".png"))
    shutil.rmtree(tempdir)
 
    return hash+".png"

Now, this is all very quick n’dirty - there is no error checking or recovery, as the point is to show of how easy it is to plug this into rST. The code so far I saved in latexrender.py.

Defining rST directives and roles

In Django, I’m using the template_utils application for quick access to some Markup languages and follow the lead of James Bennet from his blog application - i.e. my Django model simply contains a text field that on each save is formatted with a markup processor and the resulting HTML is stored in another field. Quite simply, the model looks like this

from django.db import models
from template_utils.markup import formatter
 
class Page(models.Model):    
    key = models.CharField(max_length=30, primary_key=True)
    body = models.TextField()
    body_html = models.TextField(editable=False, blank=True)
 
    class Admin:
        fields = (
            ('Meta', { 'fields': ('key', 'title', 'page_title', 'page_subtitle' )}),
            ('Body', { 'fields': ('body',), 'classes': 'monospace' }),
        )
 
    def save(self):
        self.body_html = formatter(self.body)  # <-- that's basically all it takes...
        super(Page, self).save()

Now, I may be abusing the Django settings file a little, because from it I import a module rstextensions (the contents of which we’ll see shortly), the relevant part of my settings.py looks like this,

import rstextensions
MARKUP_FILTER = ('restructuredtext', {})
LATEX_IMG_DIRECTORY = '/Users/arnarb/Documents/Projects/django/arnar/static/latex'
LATEX_IMG_URL = '/static/latex/'

And now for the whole point, how to define rST extensions. rST has two main extension mechanisms, directives, for block-level content, and roles for inline content and we’ll use both. All code appearing from now on forms the contents of rstextensions.py. First some imports and a simple function to take a formula string, pass it to latexrender and return the corresponding URL, using the LATEX_IMG_* settings from above.

from docutils import nodes, utils
from docutils.parsers.rst import directives, roles
from django.conf import settings
import latexrender
 
def get_latex_img(formula):
    fname = latexrender.render_formula(formula, settings.LATEX_IMG_DIRECTORY)
    return settings.LATEX_IMG_URL + fname

To define an rST directive, we define a handler function and register it.

def latex_directive(name, arguments, options, content, lineno,
                    content_offset, block_text, state, state_machine):
    url = get_latex_img('\n'.join(content))
    return [nodes.raw('', '<img class="formula" src="%s" />' % url, format='html')]
 
latex_directive.content = 1
directives.register_directive('latex', latex_directive)

What is happening here is we define a function with a standard signature (refer to the relevant documentation) and tell docutils that we want it to be a handler for the latex directive. On seeing such a directive, the rST processor will call our function with the block text in content, which will be a list of the lines in the block. We simply generate the PNG and the corresponding URL and plug it into a <img> tag and return it as a raw document node. (Note: the proper thing here would have been to return a nodes.image object, but it didn’t work right away and this served my purposes well)

Now I can write rST code like this

Check this out:
 
.. latex::
 
   e^{i\pi} - 1 = 0
 
Regular text continues here.

and the rST processor correctly generates the PNG and replaces the block with the appropriate <img> tag. Excellent!

Now, since I also want to use inline math expressions, let’s define a rST role as well. Roles are text strings of the form role:`some content` within a paragraph. Defining one is equally simple to defining a directive, just a different signature and another registering function.

def latex_role(name, rawtext, text, lineno, inliner, options={}, content=[]):
    src = rawtext.split('`')[1].replace('\\\\','\\')  # Restore escaped backslashes
    url = get_latex_img(src)
    return [nodes.raw(rawtext, '<img class="inlineformula" src="%s" />' % url, format='html')], []
 
roles.register_canonical_role('latex', latex_role)

Since the rST parser hands role handlers a interpreted version of the context in the text parameter, we must use the rawtext one instead. That one contains the whole unparsed role text, including the role name and the backticks. We fish out the part between the ticks and since rST has been kind enough to double up all backslashes, we need to reverse that before passing it to LaTeX. This function must now return two lists, one with the nodes to be injected (like the directive one did) and a list of system messages that will be injected right after the block that contains the inline element (see the relevant docs for details). Notice how the <img> tag has a different class name, so we can style inline formulas differently in our CSS.

Now I’m a happy camper as I can write rST code like this

The transition :latex:`\right< X,s \left> \Rightarrow \right< X^\prime, s \left>` is contrived!

and all is well :o)

A handy feature of rST is the default role. The default role is a global role that is applied to all strings enclosed in backticks if there is no preceding role name. So, if I have a text with lots of formulas, I can set the default role with a command like this one

.. default-role:: latex

and from then on, I only have to wrap inline LaTeX expressions in a pair of backticks.

My instructor sent me this list of interesting epigrams in programming by Alan J. Perlis. It is a long list of good quotes, some are famous,

A language that doesn’t affect the way you think about programming, is not worth knowing.

some are humorous,

Syntactic sugar causes cancer of the semicolon.

but this one takes the cake for me:

Computer Science is embarrassed by the computer.

Why? Because it is true.

Click here for the complete list