/dev/collective

In the previous post, Arnar wrote about how to do a JSON parser in Haskell using parsec. He also mentioned that I had shown him a similar parser written in Scala, but I must admit that I stole it from the upcoming book Programming in Scala. The book is very good and I recommend it to anyone that is interested in learning Scala.

Before I get on with the post, I’m gonna spend a few words on explaining Scala. It is a strictly typed language with a very powerful type inference system. Scala runs on the Java Virtual Machine, a port or the .NET CLR is available. It is a mix between functional and object oriented languages and is almost fully interoperable with Java. Scala replaces some of the constructs and mechanisms that you normally have in Java with more general things. Rather than using anonymous classes you have closures, there are no interfaces, but you have traits and so on. Scala also adds implicit conversions, operator overloading, mutable and immutable types and some more goodies.

Scala access to all of the class libraries that come with Java and everything you throw into its classpath. It also comes with its own class library which has collections, tuples, parsers, xml types, etc etc. Relevant for this post, maps are written as Map(key -> value), tuples as (first, second, third) and lists as List(1, 2, 3).

The first thing that is going to look weird is that the type of things appears after the name or definition and there is a keyword in front.

val i = 3
val j: Int = i
 
def hello: String = "Hello world"

The val keyword placed in front of the variables is to tell the compiler that an immutable value is coming up and var is the mutable counterpart. Methods are defined with the def keyword. The first two lines show the type inference system at work, since you have the number 3 it can only be an integer. If there is any doubt about the type during compilation, the compiler will complain and exit. The same goes for the return type of the “hello” method, the type String is specified but can be omitted. Since the method is a oneliner the = "Hello world" is a short hand for { return "Hello world" }.

Back to the JSON parser, the parsing combinator package has to be imported

import scala.util.parsing.combinator._

In Scala _ is a sequential any reference, or like in this case as * in Java imports. The parser itself is a token based parser, and extends from a trait called JavaTokenParsers which includes parsing for identifiers, numbers and strings.

class JSON extends JavaTokenParsers { 
        def obj: Parser[Map[String, Any]] = 
                "{"~> repsep(member, ",") <~"}" ^^ (Map() ++ _) 
 
        def arr: Parser[List[Any]] = 
                "["~> repsep(value, ",") <~"]" 
 
        def member: Parser[(String, Any)] = 
                stringLiteral~":"~value ^^ 
                        { case name~":"~value => (name, value) } 
 
        def value: Parser[Any] = ( 
                obj 
                | arr 
                | stringLiteral 
                | floatingPointNumber ^^ (_.toInt) 
                | "null" ^^ (x => null) 
                | "true" ^^ (x => true) 
                | "false" ^^ (x => false) 
                ) 
}

The root of the parse tree is defined in the method value which returns a Parser[Any]. Since the short hand notation is being used and it expects are Parser[Any], it uses implicit conversions for the Parser class and from there you get the ( ... | ... ) notation which provides you with parser alternatives. The weird ^^ thing is result conversions, so floatingPointNumber ^^ (_.toInt) means, take that floating number and return it as an integer using the wildcard _. repsep is a shorthand for interleaved repitition. Lastly the wavy dudes with ~, <~ and ~> denotes sequential composition and with the less and more than symbols it keeps to the left or right.

To run the parser and do something meaningful with it we read in a file pass it on to the parser and print the output

import java.io.FileReader 
 
object JSONTest extends JSON { 
        def main(args: Array[String]) { 
                val reader = new FileReader(args(0)) 
                println(parseAll(value, reader)) 
        } 
}

Different from Java, Scala does not have static types per se but allows you to do static like things by using a object instead of a class. Also notice how the FileReader is being imported directly from the Java class libraries.

After we’ve compiled the code and run it on the same file JSON file as Arnar provided in his example, we are presented with

[22.2] parsed: 
    Map("glossary" -> 
        Map("title" -> "example glossary", "GlossDiv" -> 
            Map("title" -> "S", 
                "GlossList" -> 
                Map("GlossEntry" -> 
                    Map("Acronym" -> "SGML", 
                        "Abbrev" -> "ISO 8879:1986", 
                        "GlossSee" -> "markup", 
                        "GlossTerm" -> "Standard Generalized Markup Language", 
                        "ID" -> "SGML", 
                        "GlossDef" -> 
                            Map("para" -> 
                                "A meta-markup language, used to create markup 
                                languages such as DocBook.", 
                                "GlossSeeAlso" -> List("GML", "XML")), 
                        "SortAs" -> "SGML")))))

I am to lazy to format this output nicely, but you get the picture. :) I noticed also that this JSON parser does not handle comments, which I leave as an exercise to my good readers.

I have been meaning to write something on Scala for quite some time now and now I was forced to since Arnar mentioned my crazy ranting. In the coming weeks I am hopefully going to show you some more niceness of Scala, such as implicit conversions, XML types, its functional nature, etc.

Guðmundur Bjarni Programming JSON, Parsing, Progrmaming, Scala

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.

Arnar Programming Haskell, JSON, Parsing, Programming

Earlier this week, Arnar wrote about silly form validation techniques. He specifically mentioned problems with providing Icelandic phone numbers in forms, which fail validation due to the lack of area or city codes. I agree with Arnar that form validation is surprisingly hard to get right and if not done properly it can annoy your users, possibly to the point where they cancel their registration.

However, in addition to improving the form validation code, I suggest (and I am by no means the first to propose this) that we stop requesting so much information in user registration forms, and focus on information that is relevant to the application. For instance, it is very rational to ask for a username and a password that the user wishes to have. It is also rational to ask for an email address which can be used to verify the registration, as well as provide a way to handle forgotten passwords.

On the other hand, I see no reason to require phone numbers, age and so on. In Arnar’s post there is a screen shot from Apple, where they fail to validate the phone number. Why does Apple require you to register your phone number in the first place? What if I do not, under any circumstances, want Apple to call me? If they really need to reach me, they can do so via e-mail. I’m also curious how often Apple actually uses this information, has anyone received a phone call from Apple after signing up for an Apple ID?

The form that led to this post is the account creation form at Digg. I saw an article that I wanted to bump up, an action that requires a Digg account. However, after I viewed the registration form I decided not to sign up.

In addition to the standerd username, password and email address, Digg requires you to provide your first and last name, gender, birthday, and full address. They provide no rational explanation for requesting this information, so I can only assume that they use it to improve their profiling. If I ever feel so strongly about a submitted story on Digg that I feel compelled to sign up, I will most certainly register with false information.

So to wrap this up: request only the information you need in order to provide the service. It leads to simpler form validation, better privacy and less annoyed users. Sounds like a win/win situation to me.

Einar Uncategorized

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()

Arnar Programming AI, Programming, Python, Visualization

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.

Arnar Programming Programming, Rants, Web development

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.

Arnar Programming Django, LaTeX, Programming, Python

A classical problem with the way Computer Science is taught is that it does not connect the dots between the different layers of abstractions which build up modern computer applications. Now I am talking about everything from the hardware components up to multi layered software. People tend to focus on one of upper-most parts of the cake and get really good at that, without understanding what happens beneath. Some people are really good at writing code and solve complex domain problems without realizing why their application performs like a drunk mule. For example:

• Doing some computationally intensive tasks, not understanding how CPU caches and memory architectures work.
• Using fancy built in data structures in their favorite language, without knowing anything about the different implementations, like the difference between ArrayList vs. LinkedList.
• Dive into multi-threading, thinking it is easy as one-two-three.
• Thinking that by having garbage collection means no memory leaks.
• …

The courses I have had in my education have tackled each of the layers in a computer very well, but have generally lacked a focus on what the bigger picture is and how things relate. Therefore I got really interested and excited when I saw this clip where Shimon Schocken from Efi Arazi School of Computer Science explains a course and book he came up with along with Noam Nisan. The point of the course is to have students learning about all the different abstractions by starting at building logic gates from nothing but Nand components and ending up with a computer game like Tetris. I highly recommend everyone to take a look at this video, and as a bonus, the entire thing can be done for free with the tools and exercises from their homepage.

Guðmundur Bjarni Programming