Writing a PhD dissertation in Latex

Writing a PhD dissertation in Latex

Having just finished writing my PhD dissertation using Latex, I'd like to share my experiences -- what was easy, what was hard, and some problems to watch out for.

Writing a PhD dissertation is a daunting task. Besides the actual content, we also need to worry about formatting, references, bibliographies, tables of contents, page numbering, figure layout, dedication pages, ... Using a good document preparation program can help you with these issues, leaving you free to focus on the science. A bad program can suck up your time on annoying, trivial details.

If you've never heard of Latex before, the short version is that it's a program used to create documents, much like Microsoft Word. I decided to use Latex to write my PhD dissertation because I didn't want to waste time on side issues, and I thought Latex would be able to handle those. (Also, I didn't know how to do those in Word, which would otherwise have been the default choice).

Why Latex?

In Latex, your document is plain text. This is advantageous because of the wealth of tools that work with plain text, such as git. I knew before starting that I wanted to manage my dissertation using git (due to its project management features such as tags to help me keep track of which versions I shared with my committee, ability to compare revisions with line-based diffs, and integration with cloud-hosting services such as bitbucket and github), and it's far more pleasant to work with text files than binary ones in git. Writing my dissertation in Latex is a natural fit for git.

Latex distributions are free, lots of people use them and contribute and test code and answers to the community. There's also lots of features both built-in and available through add-on packages to help build documents efficiently.

Latex's pleasant surprises

• the pdflatex program produces beautiful PDFs from your plain text Latex source files
• references are easy to manage and share. The Bibtex format is pretty standard and it's easy to get references in this format from most journals
• citing references from within the text is easy; Latex makes sure the citations are consistently numbered, formatted, and named
• Latex can automatically generate the bibliography
• Latex can automatically generate a table of contents
• Latex can automatically generate internal hyperlinks within a PDF
• beautiful rendering of mathematical equations
• can refer to figures, tables, and other sections of text using labels and anchors

There's a learning curve

If you're coming from Word, then learning to use Latex is going to take some time -- it does things differently, and you'll have to figure out a new approach to writing documents. I expected that I would spend a decent chunk of time learning how to use Latex, debugging and fixing my mistakes, and solving problems. This did indeed turn out to be the case.

You can also expect to face your fair share of standard problems (that you'll probably run into no matter what program you use). This includes finding a version of the program that runs on your platform, figuring out where to find add-ons and how to install them, and building a conceptual understanding of how the program works -- so that you understand why errors occur and how to fix them.

Problems and issues I encountered

More of my time than expected was spent managing Latex (instead of working on the content). While there's undoubtedly solutions for each of these problems, it's tough for a beginner. Here are some of the problems that I encountered:

• the error messages produced by pdflatex were pretty cryptic, which made it difficult to understand and google for the problem
• default settings and parameterizations are occasionally surprising, and often difficult to discover
• the built-in "report" document class did not exactly meet my university's formatting requirements -- that's okay, however, it took a lot of work to figure out how to fix the formatting
• there are multiple contexts, and some characters mean different things in different contexts
• conflicts between packages. Some Latex packages don't play nice with each other. Sometimes this means that you can't use certain packages together, other times it means that you'll silently get weird results. I believe there are also cases where packages have to be imported in a certain order to get them to work correctly
• entries in the bibliography had different capitalization in the output PDF than what I had put into the bibliography file
• it's hard to see where things start and end. Some commands aren't, delimited but are implicitly ended by later commands. Others have effects in some scope, which again is implicitly defined
• margins were routinely violated. I had assumed that the default behavior would be to respect margins, but this was not the case
• special characters. If you're not familiar with them, you may accidentally write something totally different from what you meant, without realizing it. Syntax-highlighting text editors are a big help here. Also, figuring out how to write a non-special version of the special characters
• I had to spend time manually checking the PDF to ensure that everything turned out correctly. Sometimes, there were surprising problems in the output that I wouldn't have found except by actually looking at the PDF (that is, there wasn't an error or warning generated by pdflatex)
• I had a very hard time finding complete, correct answers to problems. Many answers did not attempt to solve the problem, but rather argued with the premise of the OP. Many worked sometimes, but not in all contexts. Many others had unstated caveats, which later blew up in my face
• I was unable to find complete, precise documentation for packages, macros, document classes, and commands -- what they are intended to do, and how they are intended to be used. For instance, I needed to know what the "report" document class entailed and what its options meant, so that I could compare to my university's formatting requirements. I couldn't find this information anywhere
• it was difficult to choose between multiple competing packages solving the same problem -- it was hard to find good comparisons which included caveats, pros and cons, etc.
• I wasn't able to find resources to help me build a conceptual understanding of how Latex works. This meant that I wasn't able to understand why errors occurred

Conclusion: was using Latex the right decision for me?

Yes. I wanted to write my dissertation in plain text, manage it using git, and have my table of contents, references, and bibliography automatically generated. Latex had no trouble handling these. It was usually fun to use Latex, and the output from pdflatex was beautiful.

On the other hand, I spent much more time than expected troubleshooting, debugging, digging through old forums looking for answers, deciphering cryptic error messages, and wondering why things didn't work. Latex can be a very frustrating and complicated tool, and it's difficult to find help when you need it. I ran into numerous problems that I just couldn't solve and couldn't find solutions to using the internet. These left a bad taste in my mouth. I feel like a lot of Latex goes against standard principles of building robust software, such as encapsulation, abstraction, composition, and invariants.

Nevertheless, it was more than worthwhile to learn to use Latex for my dissertation. I think these issues are traps for beginners, but don't prevent advanced users from getting work done. I expect the downsides of using Latex shrink as one gains more experience using it.

Disclaimer: please keep in mind that I am only reporting my experience and my thoughts, and that it is certainly possible that my conclusions are flawed. I intended for this to be a fair portrayal of Latex.

Four different ways to inspect types and prototypes in Javascript

What is a type in Javascript?

It's hard to succinctly and accurately define `type` in Javascript. A couple of complications are Javascript's dynamic typing (meaning that variables don't have types), and that the tools that Javascript provides don't unambiguously and uniquely divide values in separate groups (meaning that there's overlap and differences between the various ways, and no one single way is more "right" than the others). Given these difficulties, let's forget about coming up with an unambiguous definition of "type" and also forget about what "type" means in other languages. Instead, let's just say that for the purposes of this article, "type" will mean "some way to group objects based on certain similar properties".

What are some of the properties that we can use to group Javascript's values? First, we can look at whether a value is an object or a primitive. We can further divide and group the objects by their prototype chains or constructors. We can divide the primitives into smaller groups based on their primitive types.

However, as I mentioned earlier, there are alternative, meaningful ways to group values. For instance, objects with identical prototype chains can be separated (`arguments` vs `{}`). There is also some overlap between primitives and certain objects -- some primitives are automatically converted to objects under certain circumstances, similar to Java's autoboxing.

This article will take a close look at Javascript's type-inspecting tools, and the different notions of "type" that they provide. Using a small amount of code -- and a large set of test cases -- we'll gather some data about each of the tools. This data will give us insight into the pros and cons of each tool -- and perhaps help to indicate when each should be used.

What are the tools at our disposal?

Object.getPrototypeOf

Can be used recursively to get the full prototype chain of an object. See the MDN docs. Related: Object.prototype.isPrototypeOf.

Object.prototype.toString

Used by Underscore for type inspection.

instanceof

Performs inheritance checks which respect the prototype chain.

typeof

Mostly useful for distinguishing between primitives and objects.

Array.isArray

A special method for checking if an object is an array. (Since this kind of method only exists for arrays, I won't use it in the rest of this article).

The code

We want to inspect as many different kinds of values as possible -- so let's make sure that we have each of the primitives, each of the commonly-used built-in object types, functions, user-defined types, `arguments`, object wrappers for primitives, and the root object for good measure. Remember, for each of these example values, we'll try each of the four previously-mentioned tools for inspecting types.

For each example, there's a meaningful string for display purposes, an expression that will evaluate to the desired value, and also a constructor function that we'll use for an `instanceof` check. The last part is pretty arbitrary -- I just use it to show that a given value can satisfy `instanceof` for multiple different constructors.

// put examples inside a function to get access to `arguments`
function getExamples() {
    var functionText = "new Function('x', 'return x + 1;')";
    return [
        // schema:  
        //   0: human-readable text
        //   1: expression to be inspected
        //   2: (optional) constructor for instanceof-checking
        ['undefined'        , undefined                         , null     ],
        ['null'             , null                              , null     ],
        ["'abc'"            , 'abc'                             , String   ],
        ["new String('abc')", new String('abc')                 , String   ],
        ['123'              , 123                               , Number   ],
        ['new Number(123)'  , new Number(123)                   , Number   ],
        ['Infinity'         , Infinity                          , Number   ],
        ['NaN'              , NaN                               , Number   ],
        ['true'             , true                              , Boolean  ],
        ['new Boolean(true)', new Boolean(true)                 , Boolean  ],
        ['function g(x) {}' , function g(x) {}                  , Function ],
        [functionText       , new Function('x', 'return x + 1;'), Function ],
        ["{'a': 1, 'b': 2}" , {'a': 1, 'b': 2}                  , null     ],
        ['new Object()'     , new Object()                      , null     ],
        ['new ObjectExt()'  , new ObjectExt()                   , ObjectExt],
        ['[1, 2, 3]'        , [1, 2, 3]                         , Array    ],
        ['new Array()'      , new Array()                       , Array    ],
        ['new ArrayExt()'   , new ArrayExt()                    , Array    ],
        ['/a/'              , /a/                               , RegExp   ],
        ["new RegExp('a')"  , new RegExp('a')                   , RegExp   ],
        ['new RegExpExt()'  , new RegExpExt()                   , RegExp   ],
        ['new Date()'       , new Date()                        , Date     ],
        ["new Error('!')"   , new Error('!')                    , Error    ],
        ['Math'             , Math                              , null     ],
        ['JSON'             , JSON                              , null     ],
        ['arguments'        , arguments                         , null     ],
        ['this'             , this /* the root object, right? */, Window   ]
    ];
}

Here's the code for setting up the three user-defined constructors. Each of Array, Object, and RegExp are extended:

// extend Array
function ArrayExt() {}
ArrayExt.prototype = [1, 2, 3];

// extend Object 
function ObjectExt() {}
 
// extend RegExp
function RegExpExt() {}
RegExpExt.prototype = /matt/;

Finally, the function used to grab an object's prototype chain. This throws an exception if `obj` is a primitive:

function getParents(obj) {
    var parents = [],
        par = obj;
    while ( true ) {
        par = Object.getPrototypeOf(par);
        if ( par === null ) {
            break;
        }
        parents.push(par);
    }
    return parents;
}

The data

Now we take each of the example values, and apply each of the four tests to it -- plus an extra `instanceof` test to show inheritance. For each expression "e", we'll do:

typeof e

Object.prototype.toString.call(e)

e instanceof Object

e instanceof [subtype]

getParents(e)

Here are the results. Especially surprising, inconsistent, and strange results are in red:

example	typeof	Object.prototype.toString	instanceof Object	instanceof subtype	prototype chain
undefined	undefined	[object Undefined]	false	--	--
null	object	[object Null]	false	--	--
'abc'	string	[object String]	false	String: false	--
new String('abc')	object	[object String]	true	String: true	String,Object
123	number	[object Number]	false	Number: false	--
new Number(123)	object	[object Number]	true	Number: true	Number,Object
Infinity	number	[object Number]	false	Number: false	--
NaN	number	[object Number]	false	Number: false	--
true	boolean	[object Boolean]	false	Boolean: false	--
new Boolean(true)	object	[object Boolean]	true	Boolean: true	Boolean,Object
function g(x) {}	function	[object Function]	true	Function: true	Function,Object
new Function('x', 'return x + 1;')	function	[object Function]	true	Function: true	Function,Object
{'a': 1, 'b': 2}	object	[object Object]	true	--	Object
new Object()	object	[object Object]	true	--	Object
new ObjectExt()	object	[object Object]	true	ObjectExt: true	ObjectExt,Object
[1, 2, 3]	object	[object Array]	true	Array: true	Array,Object
new Array()	object	[object Array]	true	Array: true	Array,Object
new ArrayExt()	object	[object Object]	true	Array: true	ArrayExt,Array,Object
/a/	object	[object RegExp]	true	RegExp: true	RegExp,Object
new RegExp('a')	object	[object RegExp]	true	RegExp: true	RegExp,Object
new RegExpExt()	object	[object Object]	true	RegExp: true	RegExpExt,RegExp,Object
new Date()	object	[object Date]	true	Date: true	Date,Object
new Error('!')	object	[object Error]	true	Error: true	Error,Object
Math	object	[object Math]	true	--	Object
JSON	object	[object JSON]	true	--	Object
arguments	object	[object Arguments]	true	--	Object
this	object	[object global]	true	Window: true	Window,EventTarget,Object

Notes:

• these results were obtained in Firefox, Javascript 1.5; Chrome, Javascript 1.7
• the results in the last row vary by implementation

The analysis

typeof

`typeof` distinguishes between primitives and objects. However:

• `typeof null` is "object"
• it returns "function" for functions, even though they are objects -- this is not wrong, just misleading
• for String, Number, and Boolean: `typeof` return "object" for wrapped values
• it doesn't distinguish between different objects -- arrays, dates, regexps, user-defined, etc.: all are just "object"

instanceof

`instanceof` checks whether a constructor's prototype property is in an object's prototype chain. However:

• the 2nd argument must be a constructor. The constructor is used to look up a prototype. This is a problem if creating objects with `Object.create` -- there is no constructor function (that you have access to).
• may not work if there are objects moving across frames or windows
• different results for corresponding objects and primitives
• doesn't tell you what the prototypes actually are

Object.prototype.toString.call(...)

This seems to differentiate between the built-ins correctly. See this for more information. However:

• it doesn't differentiate between corresponding objects and primitives
• it reports all primitives as objects
• doesn't seem to work for user-defined constructors and objects. Apparently, it depends on an internal [[Class]] property which can't be touched, according to this.

prototype chain using Object.getPrototypeOf

Gets the prototype objects. However:

• can't distinguish `arguments` from `Math`, `JSON`, and other objects. In fact, can't distinguish between any objects that share the same prototype chain.
• doesn't work on primitives -- even those which have corresponding objects
• may fail for passing objects between windows/frames -- like `instanceof` -- (not sure)

Conclusion

It appears that none of these approaches is capable of dealing with this problem by itself. I'm not even sure if it's possible to come up with a 100% accurate and unbreakable method for classifying Javascript values. However, using a combination of these tools will probably get you most of the way there. Good luck!

Simplifying a formal grammar using transformations and BNF extensions

Integer literals

A BNF grammar is a great way to specify a language, due to its concise and declarative nature. However, one major limitation of BNF is that it's not extendable -- which means if you identify a common pattern, you can't factor it out. You're stuck with repeating the boilerplate everywhere it occurs.

For an example of boilerplate making a grammar far more difficult to understand, let's take a look at the Java Language Specification While the specification is formal, it's rather verbose and it's difficult to intuitively see what language the grammar really generates -- especially the corner cases:

DecimalNumeral:
    0
    NonZeroDigit Digits(?)
    NonZeroDigit Underscores Digits 

Digits:
    Digit
    Digit DigitsAndUnderscores(?) Digit 

Digit:
    0
    NonZeroDigit

NonZeroDigit: one of
    1 2 3 4 5 6 7 8 9

DigitsAndUnderscores:
    DigitOrUnderscore
    DigitsAndUnderscores DigitOrUnderscore 

DigitOrUnderscore:
    Digit
    _

Underscores:
    _
    Underscores _

That's 7 rules on 21 lines of code (27 if you include blank lines), and describes the syntax for base 10 integer literals.

The challenge: can we transform this grammar into one that generates the same language, but is clearer and more concise? (We are allowed to extend BNF with additional operators, if necessary)

Three simple transformations

Repetitions: + quantifier

First, let's borrow some regex notation -- whenever we see this pattern:

RuleName:
    terminal
    RuleName  terminal

that means there's one or more repetion of "terminal", so we can instead use the "+" quantifier:

RuleName:
    terminal(+)

That pattern appears in two places, and after substituting our new shorthand for both of them, we now have:

DecimalNumeral:
    0
    NonZeroDigit Digits(?)
    NonZeroDigit Underscores Digits 

Digits:
    Digit
    Digit DigitsAndUnderscores(?) Digit 

Digit:
    0
    NonZeroDigit

NonZeroDigit: one of
    1 2 3 4 5 6 7 8 9

DigitsAndUnderscores:
    DigitOrUnderscore(+)

DigitOrUnderscore:
    Digit
    _

Underscores:
    _(+)

Factoring in

I use the "factor in" transformation when a rule is:

1. only used once
2. very simple
3. given a semantically void name such as "Underscores"

Here's the basic idea of factoring in (it's the opposite of factoring out repeated code):

// before -- need to look up `SubRule1` in order to understand `Rule1`
Rule1: 
    SubRule1

SubRule1:
    ... some pattern ...

// after -- no additional rule to look up, also shorter
Rule1:
    ... some pattern ...

Applying this transformation to "DigitsAndUnderscores" and "Underscores" yields:

DecimalNumeral:
    0
    NonZeroDigit Digits(?)
    NonZeroDigit _(+) Digits 

Digits:
    Digit
    Digit DigitOrUnderscore(+)(?) Digit 

Digit:
    0
    NonZeroDigit

NonZeroDigit: one of
    1 2 3 4 5 6 7 8 9

DigitOrUnderscore:
    Digit
    _

Which saves 4 more lines, and two meaningless names. This transformation can be easily abused, leading to grammars that are more difficult to read instead of less so. The trick is to decide when "factoring in" clarifies the grammar and when it obfuscates.

Character classes

This borrows more regex short-hand -- square bracket notation and character ranges. It means the rule must match any one of the characters in the given range. I'll apply it to shorten "NonZeroDigit":

DecimalNumeral:
    0
    NonZeroDigit Digits(?)
    NonZeroDigit _(+) Digits 

Digits:
    Digit
    Digit DigitOrUnderscore(+)(?) Digit 

Digit:
    0
    NonZeroDigit

NonZeroDigit:
    [1-9]

DigitOrUnderscore:
    Digit
    _

Okay, that didn't help much yet -- but we'll use it again shortly.

The plot thickens

Now we can start reusing those transformations we just covered. First, let's factor in "NonZeroDigit":

DecimalNumeral:
    0
    [1-9] Digits(?)
    [1-9] _(+) Digits 

Digits:
    Digit
    Digit DigitOrUnderscore(+)(?) Digit 

Digit:
    0
    [1-9]

DigitOrUnderscore:
    Digit
    _

Now, combine "Digit"s two alternatives, using the square bracket notation, factor it in to "DigitOrUnderscore", and then combine "DigitOrUnderscore"s two alternatives:

DecimalNumeral:
    0
    [1-9] Digits(?)
    [1-9] _(+) Digits 

Digits:
    Digit
    Digit DigitOrUnderscore(+)(?) Digit 

Digit:
    [0-9]

DigitOrUnderscore:
    [0-9_]

Now factor in both "Digit" and "DigitOrUnderscore":

DecimalNumeral:
    0
    [1-9] Digits(?)
    [1-9] _(+) Digits 

Digits:
    [0-9]
    [0-9] [0-9_](+)(?) [0-9]

The quantifiers "+" and "?", when used together, mean the same as "*":

DecimalNumeral:
    0
    [1-9] Digits(?)
    [1-9] _(+) Digits 

Digits:
    [0-9]
    [0-9] [0-9_](*) [0-9]

And we can get rid of the "?" quantifier using its definition, splitting an alternative into two:

DecimalNumeral:
    0
    [1-9]
    [1-9] Digits
    [1-9] _(+) Digits 

Digits:
    [0-9]
    [0-9] [0-9_](*) [0-9]

Closing steps

Let's now factor in "Digits" -- but we'll have to be careful since it has two alternative rules. This means the factored-in result we'll have two alternatives wherever "Digits" is replaced:

DecimalNumeral:
    0
    [1-9]
    [1-9] [0-9]
    [1-9] [0-9] [0-9_](*) [0-9]
    [1-9] _(+) [0-9] 
    [1-9] _(+) [0-9] [0-9_](*) [0-9] 

And now let's combine the first two alternatives:

DecimalNumeral:
    [0-9]
    [1-9] [0-9]
    [1-9] [0-9] [0-9_](*) [0-9]
    [1-9] _(+) [0-9] 
    [1-9] _(+) [0-9] [0-9_](*) [0-9] 

The final transformation requires a bit of intuition -- notice that underscores are only allowed in the interior of the numeral, never on the edges. Let's combine the last 4 alternatives:

DecimalNumeral:
    [0-9]
    [1-9] [0-9_](*) [0-9]

And ... voila! We've gone from 21 lines, down to 3 concise and simple ones. This makes it easier to see common error cases -- for example, a number cannot end with an underscore. Try it out on your Java compiler!

Conclusion

The length and complexity of the original grammar caused quite a few problems:

• more code means more chances for error -- misinterpretations, typos, omissions, etc.
• we couldn't tell what the code was saying. This makes it tough to write effective tests
• semantically void names -- "DigitsAndUnderscores" -- were distracting
• corner cases were not obvious
• difficult to maintain in the face of change

To deal with this, we defined several transformations, as well as extended BNF with a couple of new operators borrowed from regular expressions:

• the "+" repetition quantifier -- one or more
• square bracket notation and character ranges
• factor in simple rules, one-off rules, and poor names

We then used these transformations and extensions to transform the grammar, creating a clearer, more concise grammar.

Operator parsing

Operator parsing

Interested in simple, expressive, and efficient parsing algorithms? Ever heard of "Pratt", "operator precedence" or "top-down operator" parsing? It's a great technique, whose many advantages are described in Pratt's original paper as well as in excellent articles from more recent authors, including Douglas Crockford of Javascript fame. The chief advantages are:

• simplified description of the operator expression language portions
• simplified implementation of parser for operator expressions
• user extensibility of operator grammar

Despite its advantages, learning how the method works was very difficult for me. Although the papers were great resources, I found their explanations quite hard to grok. In particular, the original paper was confusing both in terminology and in explanation, while Crockford's implementation made heavy use of global variables, mutable state, and inheritance, and both lacked specific examples illustrating the key concepts and corner cases. They also used the same approach for parsing syntactic constructs that would not normally be considered as operators, which, although effective, did not help me to get "it".

In learning the method, I ended up using my own take on the algorithm and writing my own implementation in order to run examples. I ended up with something similar to work by Annika Aasa. Also, operator precedence climbing seems to be the same or similar.

With the help of this algorithm, I'd like to demonstrate:

• what operator expressions are
• what the problems with specifying and parsing operator expressions are
• the precedence/associativity solution to describing operator expressions
• the model used by my parser to parse operator expressions
• lots and lots of examples of the parser in action to point out corner cases and confusing scenarios

What are operator expressions?

Operators can be seen as a special case of functions, being called with a different syntax, argument order, and operator and operand positions. The main advantage of operator expressions is that they don't have to be fully parenthesized, making them more compact and (arguably) more convenient to read and write. Compare:

1 + !2 * -8 * ~3 ^ x ++

(1 + (((!2) * (-8)) * ((~3) ^ (x++))))

(+ 1 
   (* (! 2) 
      (* (- 8)
         (^ (~ 3)
            (post-++ x)))))

The first version is much shorter; is it easier to read as well?

There are four main types of operators that I'm going to focus on:

prefix:   !x             =>  (! x)
          not not x      =>  (not (not x))

infix:    x + 3          =>  (x + 3)
          a * b + c      =>  ((a * b) + c)

postfix:  y ++           =>  (y ++)

mixfix:   a ? b : c      =>  (a ? b : c)
          x if y else z  =>  (x if y else z)

Problems with specifying and parsing operator expressions

It's easy to write context-free grammars that describe operator expression -- a common example for specifying simple mathematical expressions is something like:

E  :=  E  '-'  E  |
       E  '*'  E  |
       E  '^'  E  |
       int

Unfortunately, the grammar is ambiguous; even simple expressions could be parsed multiple ways:

3 - 2 - 1         =>   (3 - (2 - 1))       or       ((3 - 2) - 1)  ??

4 - 5 * 6         =>   (4 - (5 * 6))       or       ((4 - 5) * 6)  ??

To express operator precedence, we can create a rule for each precedence level in the grammar:

E       :=  Factor  ( '-'  Factor )(*)

Factor  :=  Term  ( '*'  Term )(*)

Term    :=  int  ( '^'  int )(*)

It should be clear that this is a tedious and ugly solution. Plus, extending it to also deal with prefix, postfix, and mixfix operators further complicates things.

One last point to consider is whether the set of operators and their precedences are set in stone. With the above schemes, in which the grammar is fixed long before any actual parsing is done, the user will be not able to define new operators and their precedences.

Specification solution: precedence and associativity

Fortunately, there are better ways to specify operator grammars than using context-free grammars. One such way is to specify precedence and associativity of each operator. Then, when the parser needs to decide which operator an operand belongs to, it consults the precedence and associativity tables.

For an example, let's revisit the earlier problem of parsing `4 - 5 * 6`. The crux of the association problem is whether the `5` belongs with the `-` or with the `*`. As we know from math, the `*` has higher precedence, and so the expression is parsed as `4 - (5 * 6)`. That's precedence.

Using associativity, we can resolve the other example -- `3 - 2 - 1`. In this example, the association problem is whether the `2` belongs with the first or second `-`. Obviously, `-` has the same precedence as itself, so precedence won't help us here. However, infix `-` is left-associative, which means that `2` associates to the left, for a final result of `((3 - 2) - 1)`.

Precedences must also be specified for the other operator types -- prefix, postfix, and mixfix -- since each of these may participate in an association problem. The above two examples are infix/infix problems; here are the additional possible association problems:

prefix/infix:      !x + 3               =>    !(x + 3)               or    (!x) + 3

infix/postfix:     a * b--              =>    (a * b)--              or    a * (b--)

prefix/postfix:    - c ++               =>    - (c ++)               or    (- c) ++

mixfix/mixfix:     a ? b : c ? d : e    =>    (a ? b : c) ? d : e    or    a ? b : (c ? d : e)

prefix/mixfix:     ! a ? b : c          =>    (! a) ? b : c          or    !(a ? b : c)

mixfix/postfix:    a ? b : c ++         =>    (a ? b : c) ++         or    a ? b : (c ++)

infix/mixfix:      w + x ? y : z        =>    w + (x ? y : z)        or    (w + x) ? y : z

mixfix/infix:      n ? o : p + q        =>    (n ? o : p) + q        or    n ? o : (p + q)

Note that postfix and prefix operators can't be the first or second operator, respectively, in an association problem for obvious reasons.

As the above examples demonstrated, precedence handles cases between operators with different binding priorities, while associativity handles cases between operators with with equal priorities. Associativity can be right or left:

left associativity:    a + b + c    =>    ((a + b) + c)

right associativity:   d = e = f    =>    (d = (e = f))

Now what happens if we mix operators of equal precedence but opposite associativity? In the following examples, assume `+` and `=` have equal precedences but are left- and right- associative, respectively:

operator +  precedence 50, left-associative
operator =  precedence 50, right-associative

a = b + c    =>    (a = b) + c   violates associativity of `=`
                   a = (b + c)   violates associativity of '+'

d + e = f    =>    (d + e) = f   violates associativity of `=`
             =>    d + (e = f)   violates associativity of '+'

There's no good way to parse mixed-associativity expressions; systems can arbitrarily choose a parse, or report an error. My system chooses to report an error.

The most common way to define precedence is by assigning a number to each operator; the higher the number, the higher the precedence of the operator (or sometimes vice versa, confusingly). See Java and Python examples. Another approach is to define relative precedences between some (but not necessarily all) operator pairs, so that a total precedence order need not be defined.

Associativity is defined for each infix and mixfix operator, either as left-, right-, or non-associative. Prefix and postfix operators do not need associativities because they are always right- and left-associative, respectively. As can be seen in these examples, there is only one way to parse these operators expressions:

! ! ! ! x   =>   ! (! (! (! x)))

x ++ ++ ++  =>   ((x ++) ++) ++

A parsing algorithm

Now I'd like to deomonstate a parsing algorithm that works for prefix, infix, mixfix, and postfix operators of arbitary precedence and associativity.

First, I need to give a rough definition of the expression language we'll parse. Even though, as I mentioned before, BNF-like grammars are a poor means for defining operator expressions, I'll it a bit informally just to give a succinct outline what we'll be dealing with:

Expr        ::   PrePostfix  |
                 Infix       |
                 Mixfix

Infix       ::   Expr  InfixOp  Expr

Mixfix      ::   Expr  MixfixOp1  Expr  MixfixOp2  Expr

PrePostfix  ::   PrefixOp(*)  Operand  PostfixOp(*)

Operand     ::   Number  |  Variable

(Of course, this grammar is highly ambiguous, whereas our parser will be unambiguous.) Basically, this grammar says that we can do stuff like:

infix:        x * 123

add prefix
operators:    ! ~ x * 123

add postfix
operators:    ! ~ x ++ -- * 123

add infix
operator:     ! ~ x ++ -- * 123 & y

add mixfix
operator:     ! ~ x ++ -- * 123 & y ? 4 : p

We can have as many prefix and postfix operators as we want surrounding any operand, and infix and mixfix operator expressions recursively use the `Expr` rule.

The basic parsing algorithm needs five rules which must be repeatedly applied in order to parse the operator expressions: one for each type of operator, as well as one for finding operands. Since we're working left-to-right, there's a natural order in which the rules must be applied:

1. find prefix operators
2. find the operand
3. find postfix operators
4. find an infix operator, if possible, or ...
5. find the first part of a mixfix operator, an expression, and the second part, if possible

Applying these rules looks like this:

start:         ! ~ x ++ -- * 123 & y ? 4 : p

find prefix
  operators:       x ++ -- * 123 & y ? 4 : p     

find operand:        ++ -- * 123 & y ? 4 : p

find postfix
  operators:               * 123 & y ? 4 : p --

find infix
  or mixfix
  operator:                  123 & y ? 4 : p --

Now, if we found just an operand and postfix operators, we have a complete expression:

x ++   <-- complete expression

However, if we found any prefix operators, we may not yet have found the complete operand; using Python's rules:

not x      parse prefix operator 'not'
x          parse operand variable 'x'
-- done -- complete expression

not 3 + 2 + 1    parse prefix operator 'not'
3 + 2 + 1        parse operand number '3'
+ 2 + 1          parse infix operator '+'
2 + 1            tokens '2', '+', and '1' remaining
-- not done -- `not` has lower precedence than `+`, so we haven't yet found `not`s operand

If we found an infix or mixfix operator, we have found the left-hand operand, but we definitely haven't found the right-side operand(s):

3 + 4 * 5    parse operand number '3'
+ 4 * 5      parse infix operator '+'
4 * 5
-- not done -- we have not yet found `+`s right-hand operand

Introducing the Stack

To store the operators whose arguments we have not yet found, we'll use a stack. Each layer of the stack records the name, precedence, associativity, and any arguments already found of an operator. Of course, since it's a stack, layers are only added and removed from one end, representing where the parser is in the expression. Here's a prefix example:

tokens	stack	scratch space	action
! ~ x	[]		consume prefix operator
~ x	[]	!	prefix operator, so push
~ x	[(!, 110, right)]		consume prefix operator
x	[(!, 110, right)]	~	prefix operator, so push
x	[(!, 110, right), (~, 110, right)]

We can see that as each prefix operator is consumed, an entry is pushed on to the top of the stack. Notice that the associativity is 'right' for prefix operators, and that we haven't found any operands for them yet.

Now let's see what happens when we continue the above example. When we do find the operands, we can start popping stack entries. If we've consumed the entire input, we pop every stack level. Meanwhile, we're also maintaining a scratch value that is the operand which we pass to the next highest stack frame, after which the frame is popped and the process is repeated:

tokens	stack	scratch space	action
x	[(!, 110, right), (~, 110, right)]		consume operand
	[(!, 110, right), (~, 110, right)]	x	tokens empty, so pop
	[(!, 110, right)]	(~ x)	tokens empty, so pop
	[]	(! (~ x))	tokens and stack empty, so done

An infix example

The algorithm works similarly for infix, and mixfix operators, except that when an entry is pushed onto the stack for such an operator, the left-hand argument has already been found. Let's work through an example:

tokens	stack	scratch space	action
a + b * 3 - 4	[]		consume operand and infix operator
b * 3 - 4	[]	+, a	stack is empty, so push
b * 3 - 4	[(+, 80, left, a)]		consume operand and infix operator
3 - 4	[(+, 80, left, a)]	*, b	* > +, so push
3 - 4	[(+, 80, left, a), (*, 90, left, b)]		consume operand and infix operator
4	[(+, 80, left, a), (*, 90, left, b)]	-, 3	- < *, so pop
4	[(+, 80, left, a)]	-, (* b 3)	- == +, but is left associative, so pop
4	[]	-, (+ a (* b 3))	stack is empty, so push
4	[(-, 80, left, (+ a (* b 3)))]		consume operand
	[(-, 80, left, (+ a (* b 3)))]	a	input is empty, so pop
	[]	(- (+ a (* b 3)) 4)	input and stack empty, so done

The association problem is continually decided based on operator precedences and associativities, and is implemented through pushes and pops to the pending operator stack.

A postfix example

Postfix operators do not require stack pushes, but may require pops -- since their operands are always to the left, meaning that further parsing is not needed to find them. Here's a small example; assume the precedences of +, --, and @ are 80, 120, and 50 respectively:

tokens	stack	scratch space	action
x + y -- @	[]	(none)	consume operand and infix operator
y -- @	[]	+, x	stack empty, so push
y -- @	[(+, 80, left, x)]	(none)	consume operand and postfix operator
@	[(+, 80, left, x)]	--, y	-- > +, so apply -- to y
@	[(+, 80, left, x)]	(-- y)	consume postfix operator
	[(+, 80, left, x)]	@, (-- y)	@ < +, so pop
	[]	@, (+ x (-- y))	stack empty, so apply @ to arg
	[]	(@ (+ x (-- y)))	stack, input empty so done

To sum up how the algorithm works:

• use a stack to represent operators that we're not done parsing yet
• relative precedence and associativity of the current operator and the topmost operator on the stack tell us whether we need to push or pop
• use a scratch space to temporarily hold an operator and operand, if necessary
• prefix operators always push a stack frame
• postfix operators may pop stack frames
• infix and mixfix operators may pop 0 or more frames, followed by pushing a single new frame

Disambiguating ambiguities

It's great to be able to use `-` and `+` both as infix, binary operators and as unary prefix ones. Can this algorithm deal with those cases? Easily! Let's work through a short example:

tokens	stack	scratch space	action
140 - - 26	[]		consume operand and infix operator
- 26	[]	-, 140	stack empty, so push
- 26	[(-, 80, left, 140)]		consume prefix operator
26	[(-, 80, left, 140)]	-	prefix operator, so push
26	[(-, 80, left, 140), (-, 110, right)]		consume operand
	[(-, 80, left, 140), (-, 110, right)]	26	input empty, so pop
	[(-, 80, left, 140)]	(- 26)	input empty, so pop
	[]	(- 140 (- 26))	input and stack empty, so done

The algorithm handles the problem by reading the two `-` tokens in two different contexts: when it reads the first one, the algorithm is expecting an infix operator; once an infix operator is found, the algorithm looks for an operand. Since an operand can have prefix operators, it next looks for those.

Operators can also be used in both prefix and postfix contexts, or prefix and mixfix, without confusing the parser. However, using an operator as both postfix and infix/mixfix *will* screw things up, since the parser will no longer know when to stop parsing postfix operators and switch over to infix/mixfix.

User extensibility

One of the major advantages of operator parsing is its extensibility: to create brand new operators, you just need to add some entry to your operator tables giving the precedence and associativity (if necessary). This allows users to define their own operators. For an example, check out the Haskell programming language, which allows user-defined operators as described here.

Limitations

For simplicity, I intentionally chose an algorithm that is more limiting than the ones used by Pratt and Crockford. The problem is caused by the forced classification of operators into prefix, postfix, infix, or mixfix. If you have an operator that doesn't fit into one of those categories exactly, you will have to extend the algorithm to deal with it. An example is Python's `lambda` operator, since it requires a parameter list after the keyword and before the `:`, but is otherwise similar to a prefix operator.

In the Pratt & Crockford method, the tokens themselves are responsible for deciding what parse rules to use. This allows any grammatical rule to be parsed as an operator expression, but again, I find it more difficult to comprehend and demonstrate, precisely because it's so flexible.

Wrap up

Well, this has been quite a long article! I hoped you enjoyed reading it as much as I did writing it!

If you'd like to see the parser in action, you can find my implementation of the algorithm on github here. In addition to the actual code, there's a decent suite of tests to ensure that tricky corner cases are handled correctly. Might be worth a look!

Lastly, I'd like to mention again that this was all inspired by the works of Pratt and Crockford, which are excellent and definitely worth reading.

Parsing the NMR-Star format

The NMR-Star format

NMR, or Nuclear Magnetic Resonance, is a technique for studying molecules at the molecular level; it is also the technology behind NMR machines. The Biological Magnetic Resonance Data Bank is a great resource for archived NMR data, which can be access in text files using the NMR-Star format.

However, the NMR-Star format has a number of corner cases that I had to solve while writing the NMR-Star parser which were quite tricky. This article will discuss the problems and their solutions. The full code can be found on github in my NMR-Star parser project.

The parsing strategy

I used parser combinators supporting error reporting, backtracking, and line/column position, and added a a couple of extra phases for clean-up:

• scanner
• token clean-up. Discards whitespace and comment tokens, and classifies unquoted strings as keywords or values
• CST parsing. Builds a concrete syntax tree from the token sequence
• AST construction. Checks context-sensitive constraints while building an abstract syntax tree

Problem: whitespace/comments between tokens and semicolon-delimited strings

The NMR-Star format allows insignificant whitespace and comments between tokens. A standard parsing solution is to discard whitespace and comments after every token. However, the NMR-Star language defines semicolon-delimited strings to be opened by the sequence "newline, semicolon" and ended by the same sequence, which breaks the "munch junk after every token" rule, since newlines would be counted as whitespace and be discarded by the time a semicolon-string is tried. For example:

  ;abc  # <-- not a semicolon-string because preceding character is not a newline

;abc  # <-- semicolon-string because preceding character *is* a newline
def
; 

In my first solution to this problem, I pre-munched junk before every token. Semicolon-delimited strings got a special munching rule, which verified that the last junk character before the opening semicolon was indeed a newline. However, this had a couple disadvantages: 1) position reporting was much more difficult than with post-munching, since junk had to be parsed before finding the beginning of the next token, and 2) it was a special case, which complicated the specification and implementation.

My second solution took advantage of the position information -- that the opening semicolon immediately follows a newline implies that it is in column 1 of its line. So, the parser must inspect the position before deciding to try parsing a semicolon-delimited string or not. This allowed one single rule for insignificant whitespace and comments, and also allowed me to use post-munching.

def _sc_rest(position):
    _, column = position
    # a semicolon-delimited string must be preceded by a newline -- thus, column must be 1
    if column == 1:
        return node('scstring',
                    ('open', sc),
                    ('value', many0(not1(_end_sc))),
                    ('close', cut('newline-semicolon', _end_sc)))
    return zero
    
scstring = bind(getState, _sc_rest)

Problem: semicolons inside semicolon-delimited strings

Since the newline/semicolon sequence closes semicolon-delimited strings, this means that semicolons can not be the first character on a line within a semicolon-string. For example:

; this ; starts the string
 this ; is *within* the string and does not end it
; # this ; ends the string, because it follows a newline
; # which means this is an extraneous ;

This problem is solved with a single character of lookahead: while parsing a semicolon-string, if a newline is encountered and the next character is a semicolon, end the string; otherwise, continue parsing the semicolon-string.

Problem: non-ending quotes of quoted values

NMR-Star has double-quoted values:

"abc 123"

Double-quotes can be within the string, as long as they are not followed by whitespace or EOF. Thus, this is a single, valid double-quoted value, since the second '"' is followed by '1':

"abc"123"

This is easily solved using a single character of lookahead: '"' followed by whitespace, end the string; '"' followed by not whitespace, consume the '"' and continue parsing the string.

NMR-Star also has single-quote values which work in the same way.

Problem: keyword vs. unquoted value

The lexical definitions of keywords and unquoted values in the original Star grammar is ambiguous; this is resolved with an additional rule stating that unquoted values can not be keywords. For example:

loop_  # <- 'loop_' is a keyword, so it can not be an unquoted value
 _a _b
 loop_1  # <- 'loop_1' is not a keyword, so it can be an unquoted value
 loop_2 
stop_

An alternate definition, and the one which I used in my parser, is to match the longest string of the unquoted value pattern; then classify the string as either a keyword or an unquoted value in the token clean-up phase. This avoids unnecessary grammatical ambiguity and more clearly captures the intent of the specification.

unquoted = node('unquoted',
                ('first', not1(special)),
                ('rest', many0(not1(space))))

Problem: context sensitive rules

There are a number of constructs in the NMR-Star format that are context-sensitive, meaning that they cannot be parsed correctly using a context-free grammar/parser:

• no duplicate save frame names
• no duplicate identifiers in save frames
• no duplicate identifiers in loops
• framecode references
• the number of values in a loop must be an integer multiple of the number of identifiers

For example, the following loop follows the context-free rules but has duplicate keys:

  loop_

    _a _b _a

    v1 v2 v3
    v4 v5 v6

  stop_

What we'd like to have the parser do is report an error including location in the input and the nature of the violation.

One way to solve this problem is to use a context-sensitive grammar formalism; however, I've never tried this approach. One important disadvantage is that it would prevent context-free parsing of files that violate the context-sensitive rules -- which may be a pain if you have invalid data.

A second approach is to parse the input according to the context-free rules and generate a concrete syntax tree. Then, run a second pass over the CST to produce the abstract syntax tree. The second pass is now responsible for implementing the context-sensitive rules. This is the method I used and seems to work well in practice. It also seems to be easier to maintain due to better separation of concerns.

Wrap up

As far as formats go, the NMR-Star format is relatively clear and succinct. However, as I've shown, it does have a few pitfalls for the unwary, as well as some redundancies.

Scannerless Parsing: a JSON case study

Scannerless parsing

Scannerless parsing is not a very popular or well-understood approach to building parsers. So many parsing tools out there take for granted that parser implementors want/need/accept separate scanning and context-free parsing phases, that it's hard to get good information on the how, what, and why of scannerless parsers. That is, one would like to know:

• What is 'scannerless parsing'?
• What's so different about it?
• How are scannerless parsers implemented?
• What are some of the advantages?
• What are some of the drawbacks, pitfalls, and difficulties?

I will explore these issues using a parser that I recently built, for the JSON data format, as a case study. I hope this will provide some practical insight into scannerless parsers!

What is scannerless parsing?

A scannerless parser is a parser that does not arbitrarily separate parsing into lexical and context-free phases; instead, these are combined into a single phase, as we'll see in the rest of this section.

Programming and data languages are often defined by grammars; parsers are programs that implement grammars; they read in strings and: 1) decide whether the string is part of the language; 2) build a structure representing the input; and 3) report any problems with the input.

Common tools for converting grammars to executable parsers (see the Wikipedia page for examples) often enforce an artificial separation of parsing into two stages. In the first stage, often called lexing (or tokenization or lexical analysis), the input string is broken up into a sequence of tokens. These tokens are then used as the input for the second stage.

I'm not sure what the next stage is called; I've seen it called context-free parsing, hierarchical parsing, and simply parsing. But the important point is that in this stage, the tokens are assembled into syntactic units to build some kind of parse tree which represents the structure that was recognized in the input string.

Each phase has its own separate grammar to describe what language it accepts. In a typical parser, the lexical grammar is (or tries to be) regular in the formal sense, and may require only minimal lookahead and/or backtracking; these characteristics help the tokenizer to do its job faster. The grammar for the second phase is context-free, and its terminals are tokens. Sometimes the grammars are ambiguous (meaning some strings can be parsed multiple ways); ambiguities are often resolved using additional rules outside the grammar.

This separation of parsing into two phases is completely arbitrary; it is perfectly possible to create a single-phase parser that accepts the exact same language as a two-phase parser. After all, it's quite easy to combine the regular token grammar into the hierarchical context-free grammar. Advantages of the two-phase approach are that it's familiar, tools implementing it are often quite fast, and the separate grammars may be simpler than a single combined grammar.

On the other hand, there are also important disadvantages when splitting parsing into two phases:

• Artificially constraining the token grammar can create unnecessary ambiguities. See the lexer hack for an example. These types of ambiguities are not inherent in language itself, but are caused by the technology. Another example occurs with Java's templates; see this question. It's solved by reinterpreting the token stream during the second phase, if necessary.
• More phases means more glue code between phases. Information such as token type and position must pass from the lexer to the parser; data may also be passed back to the lexer as in one resolution of the lexer hack. Also, error reporting and handling between the phases must be accounted for.
• Language composability may be reduced.
• Language description is more complicated. Two parallel grammars must be maintained, and the interactions between them well understood in order to effectively make changes.
• Two tools and all their idiosyncracies, as well as the interface between them, must be mastered.

Parser combinators

The parsers will all be built using parser combinators; if you've worked with parser combinators before, it should be straightforward to follow along (aside from any idiosyncracies of my approach). If you've never used them, there are plenty of libraries in every language which are easy to download, or you can check out my library. I prefer using parser combinators because:

• they are powerful -- they parse not only regular and context-free, but also context-sensitive grammars
• they are expressive -- parsers are approximately as long as the grammar they implement
• as they are expressed within a programming language, they benefit from that language's ecosystem, including functions, classes, unit testing libraries and tools, build tools, type systems, runtime, JIT compiler, etc. This also means that they can be extended when new patterns are identified.
• they are composable. Parsers are built by successively combining parsers into ever-large parsers; combinator libraries come with a rich set of functions for combining parsers.
• they are easy to test. Since each parser -- no matter how small -- is an object, it can be tested independently. This is a big win for me -- if I'm not confident that I have the little things right, I know I have no chance of getting the big things right.
• easy to deploy and use. Since both parsers and the combinators are libraries, one needs only to import them, then hand them data to get started.
• results, such as parse trees, are easy to build while parsing
• they allow good, meaningful error messages to be produced

The combinators I'll use support four computational effects:

1. backtracking. This allows choice between alternatives.
2. error reporting. Errors will not be created using exceptions, but rather through a special datatype.
3. state(1). The token sequence.
4. state(2). This will be used to keep track of the position (line and column) in the input that the parser is at.

The how of scannerless parsers

Now let's get started! I'll point out problems that I faced, then describe how my scannerless parser solved them. The full code can be found on github here.

Problem: whitespace/comments between tokens

Many languages, including JSON, allow insignificant whitespace between tokens. This means whitespace must be discarded before and after tokens. One solution is to implement a parser for each token, and then wrap them with a combinator which runs the token parser and discards junk before or after the parser. Should we pre-munch or post-munch the junk? I found two advantages of post-munching: 1) after parsing a token, the parser always stops at the beginning of the next token, making it easy to report position; 2) if the parser must backtrack on a token, it will not have to re-parse the junk, only to discard it again. Of course, pre-munching before the very first token is still necessary.

This implements a `whitespace` parser and a `tok` combinator:

whitespace = many0(oneOf(' \t\n\r'))

def tok(parser):
    return seq2L(parser, whitespace)

The `tok` combinator implements post-munching by running its parser argument and then running the whitespace parser; its result is that of the parser argument. Note that the whitespace parser can't fail, since it matches zero or more whitespace characters -- this allows there to not be any whitespace after tokens.

Parsing a single token

By getting rid of the scanning phase, we haven't thrown the baby out with the bathwater, have we? Of course not! Since context-free grammars are more powerful than regular ones, it is no problem to express token patterns. One can simply create a parser for each token type. Since the JSON specification defines lexical syntax as a regular language, the token parsers simply don't use the more powerful features of CFGs.

The implementation uses the `literal` combinator:

os = tok(literal('['))

Which matches a given character exactly; this parser is then passed to `tok` to allow for optional trailing whitespace, which is post-munched.

Problem: position tracking

Keeping track of the line and column number while parsing allows position-specific errors to be reported, and also construction of a parse tree that includes position information. The latter is useful if you need to link later analyses to positions in the file.

One method for tracking position is to pre-process the input, converting a sequence of characters into a new sequence of annotated characters, including both the original character and the calculated position. This approach seems to work okay, but has a couple of drawbacks. First, many of the combinators have to be updated to deal with matching annotated characters, which means they are no longer compatible with simple characters, so you need two versions. Second, you have to extract the underlying characters; like the first problem, it's not a big deal but is certainly annoying. Third, you can only look at the position by monadically pulling a token into scope, which means: 1) extra parameters to pass around, and 2) you can't look at the position if the token sequence is empty.

A separate approach is to track the position using monadic state. This has the advantages that the parser combinators work the exact same way and do not need to be updated, the values don't have to be muddled with to extract out the underlying characters, and you can look at the position whenever necessary using the appropriate combinator. One disadvantage is that under backtracking, position calculations may be repeated.

Problem: parsing complex syntactic structures

The JSON format defines several multi-token syntactic structures -- key/value pairs, arrays, and objects. Again, for each of these I implemented a single parser. However, these parsers don't touch the token sequence directly, but only indirectly through the token parsers. In other words, each structural parser is implemented as a combination of token parsers.

This is similar to how the two-phase parsing strategy works. However, there is a key difference -- the structural parsers use only the token parsers because they *choose* to; it is no problem to use a different tokenization strategy at any time if necessary.

The syntax rules for array, object, and value are mutually recursive; however, Python's variable-binding semantics are not let-rec compatible, so a little trick is used to mock a forward declaration:

array = error('unimplemented')

value = alt(jsonstring, number, keyword, obj, array)

array.parse = node('array',
                   ('open', os),
                   ('body', sepBy0(value, comma)),
                   ('close', cut('close', cs))).parse

The `value` rule then refers to the `array` object; later, we replace the `parse` attribute of `array` with the actual parsing function that we want. Ugly, but effective. As for the rest of the parser, note how it doesn't touch the characters directly -- it is built in terms of the token parsers (and `value`).

Problem: keyword matching

There are three literal keywords in the JSON spec. Using the `string` parser, which matches a sequence of tokens exactly, a keyword is matched:

_keyword = node('keyword', 
                ('value', alt(*map(string, ['true', 'false', 'null']))))

If the keyword is matched, then the appropriate keyword is presented as the return value.

Strings: hex escape sequences

The JSON spec allows four-digit hexadecimal escape sequences in string literals, opened by the sequence '\u', and followed by four hexadecimal digits (case-insensitive):

_hexC = oneOf('0123456789abcdefABCDEF')

_unic = node('unicode escape',
             ('open', string('\\u')),
             ('value', cut('4 hexadecimal digits', quantity(_hexC, 4))))

What's missing

This article doesn't cover the details of error-reporting, which was extremely complicated. While correctly reporting the where and why of malformed input is critical in a real parser, the JSON spec does not explicitly say what is an error (it's implied) it is difficult to know what should be reported. This article also doesn't cover the design, implementation, and combinators of the parsing library. If you would like to see more about either of these topics, check out the code on github!

Monad Transformers: Constructive Stack Order

What are Monad Transformers?

Monad Transformers provide a modular solution to combining monads, in which a combined monad can be viewed as an ordered stack of layers -- each layer implements the semantics of a single monad. Here's a small stack:

top:     State
bottom:  Maybe

And here's a bigger one:

top:     State
         Maybe
         Error
         Maybe
         Writer
bottom:  Reader

As I mentioned, the stack is ordered -- and one of the problems that people run into when learning how to use monad transformers is what difference the stack order makes, figuring out what the semantics of a given stack are, and coming up with a stack that meets some given criteria.

Does stack order matter?

Yes! For example, let's compare State/Maybe to Maybe/State using the standard transformers. First, we create a stateful computation that increments the state by 1 -- this shows how many times it's executed -- then we create a computation that runs `inc`, fails, and runs `inc` again:

import Control.Monad.State          (StateT(..), MonadState(..))
import Control.Monad.Trans.Maybe    (MaybeT(..))
import Control.Applicative          (Alternative(..))
import Data.Functor.Identity        (Identity(..))

inc :: (Num s, MonadState s m) => m ()
inc = get >>= (put . (+ 1))

calc :: (Num s, MonadState s m, Alternative m) => m ()
calc = (inc >> empty) <|> inc

Here we create our two stacks, differing only in order, and functions for unwrapping the stacks from all the constructors:

type Type1 s a = StateT s (MaybeT Identity) a
type T
ype2 s a = MaybeT (StateT s Identity) a
run1 :: Int -> Maybe ((), Int)
run1 s = runIdentity $ runMaybeT (runStateT calc s)

run2 :: Int -> (Maybe (), Int)
run2 s = runIdentity $ runStateT (runMaybeT calc) s

And the results?

*Main> run1 32
Just ((),33)

*Main> run2 32
(Just (),34)

Different! Apparently the first example only ran `inc` once, while the second ran it twice -- but why?

Calculating stack order

In order to figure out the underlying types of transformer stacks, we need two things: first, the types of monads to which they are applied:

Maybe         /\  a.  Maybe a
State         /\s a.  s -> (a, s)
List          /\  a.  [] a
Identity      /\  a.  a
Either        /\e a.  Either e a
Reader        /\r a.  r -> a
Writer        /\w a.  (a, w)
Cont          /\r a.  (a -> r) -> r

and second, the types of the transformers. Working from Haskell's mtl monad transformer library, I've pulled out the types:

MaybeT        /\  m a.    m (Maybe a)

StateT        /\s m a.    s -> m (a, s)

ListT         /\  m a.    m [a]

IdentityT     /\  m a.    m a

ErrorT        /\e m a.    m (Either e a)

ReaderT       /\r m a.    r -> m a

WriterT       /\w m a.    m (a, w)

ContT         /\r m a.    (a -> m r) -> m r

Now to start building complicated stacks, there are two approaches that I use. The first I find simpler: starting from simple monads, successively add layers, with the result of each step being a more complicated monad that could be placed in the bottom of a monad transformer stack. In other words, what we're doing is:

1. simple monad, or monad(1)
2. transformer + monad(1) = monad(2)
3. transformer + monad(2) = monad(3)
4. ... etc. ...

And an example using StateT as the transformer and Maybe as the monad:

• Step 1: write down the types that the transformer and monad represent
• transformer: /\s m a. s -> m (a, s)
• monad: /\a. Maybe a
• Step 2: substitute the monad into the transformer type, taking the place of type variable `m`
• /\s m a. s -> Maybe (a, s)
• unbind type variable m, bind all type variables except the last (`a`) from the monad
• /\s a. s -> Maybe (a, s)

Let's also do it the other way around: MaybeT and State:

• Step 1: /\m a. m (Maybe a) and /\s a. s -> (a, s)
• Step 2: /\m a. s -> (Maybe a, s)
• Step 3: /\s a. s -> (Maybe a, s)

So we've built some 2-layer monads which can themselves be passed to transformers. For example, with ErrorT as the transformer and Maybe/State as the monad:

• Step 1: /\e m a. m (Either e a) and /\s a. s -> (Maybe a, s)
• Step 2: /\e m a. s -> (Maybe (Either e a), s)
• Step 3: /\e s a. s -> (Maybe (Either e a), s)

And applying ErrorT to State/Maybe:

• Step 1: /\e m a. m (Either e a) and /\s a. s -> Maybe (a, s)
• Step 2: /\e m a. s -> Maybe (Either e a, s)
• Step 3: /\e s a. s -> Maybe (Either e a, s)

The third step is just to tidy things up, making sure the right type variables are in scope and that unused ones are not in scope. The second approach is to combine a transformer with another transformer to create a two-layer transformer. It works similarly to the first approach, except that the resulting transformer can be placed anywhere in a monad stack, instead of just at the bottom.

Semantic differences from stack order

So why is Maybe/State `s -> (Maybe a, s)` different from State/Maybe `s -> Maybe (a, s)`? In Maybe/State, the state is outside of the Maybe, which means that even if the computation fails, you'll still get a (possibly modified) state output; in State/Maybe, if the computation fails, you won't get a new state.

What this means is that the state in Maybe/State is not subject to Maybe's effects; if you're using Maybe for backtracking, as we were in the examples, any modifications to the state won't be undone by backtracking. Since the state is subject to Maybe's effects in State/Maybe, backtracking did prevent the effect of the first `inc` from being reflected in the final output. It's important to note that both orderings are useful in practice, albeit for different things.

On the other hand, for other combinations the order doesn't matter. Examples are Maybe/Error and State/Writer. I don't know of any rule to figure out which pairs are order-dependent and which aren't, so I'm stuck looking it up on a little table of combinations!

A classy approach to parser combinators

Parser combinators

Parser combinators serve as a great introduction to Functional Programming, and are one of the most-studied topics in the field. Nevertheless, they are a very complex and broad topic, covering concepts such as non-determinism, monads, and higher-order functions.

What people may not get as much exposure to, at least in my experience, is many of the Haskell type classes and their relationship to parsers. As we'll see in this article, the most common and useful combinators are actually parser-specific versions of more widely useful generic operations.

Type classes

The definitions of the type classes used are based on both the standard Haskell classes of the same name (minus the '), and Brent Yorgey's Typeclassopedia. I've added a ' to the end of each of their names to indicate that they're not identical to the standard Haskell classes, and in some cases are quite different. I've also added one type class of my own -- Switch' -- which represents the ability to convert a failing computation into a successful one with a default value, and to convert a successful computation into a failing one. I wasn't able to find a type class providing this functionality on Hoogle.

Parser definition and basic combinators

Following convention, parsers are modeled as functions that operate on token streams, either producing a result paired with the rest of the token stream, or failing. A convenient choice for representing possible failure is the Maybe data type.

newtype Parser t a = Parser { 
        getParser :: [t] -> Maybe ([t], a) 
    }

run :: Parser t a -> [t] -> Maybe ([t], a)
run = getParser

In addition, we'll use these basic parsers repeatedly throughout the examples to build bigger and more exotic parsers:

-- succeeds, consuming one token, as
--   long as input is not empty
getOne :: Parser s s
getOne = Parser (\xs -> case xs of 
                        (y:ys) -> pure (ys, y);
                        _      -> empty)

-- runs the parser, and if it succeeds,
--   checks that its result satisfies a predicate
check :: (a -> Bool) -> Parser s a -> Parser s a
check f p = p >>= \x -> 
  guard (f x) >> 
  pure x

-- consumes one token if the token
--   satisfies a predicate
satisfy :: (a -> Bool) -> Parser a a
satisfy p = check p getOne

-- builds a parser that only
--   matches the given token
literal :: Eq a => a -> Parser a a
literal tok = satisfy (== tok)

Alternation and failure

Alternation and failure are covered by the semigroup and monoid classes, respectively. Semigroups are characterized by an associative, binary, closed operation.

The parser interpretation of semigroups is choice: given two parsers, use the first one if it succeeds, but use the second one if the first fails.

class Semigroup' a where
  (<|>)  :: a -> a -> a

instance Semigroup' (Parser s a) where
  Parser f <|> Parser g = Parser (\xs -> f xs <|> g xs)

This implementation exploits the fact that the Maybe datatype can also form a left-biased semigroup.

Monoids are semigroups whose binary operation has an identity element; for parsers, this means that applying the choice operator to any parser plus the identity parser will always return the result of the first parser, regardless of whether it fails or succeeds. The identity parser always ignores its input and fails:

class Semigroup' a => Monoid' a where
  empty :: a

instance Monoid' (Parser s a) where
  empty = Parser (const Nothing)

Here are some examples:

-- combining two parsers with choice:  succeeds if either parser succeeds
a :: Parser Char Char
a = literal 'a'
b :: Parser Char Char
b = literal 'b'
ab :: Parser Char Char
ab = a <|> b

$ run ab "babcd"
Just ("abcd",'b')
$ run ab "abcd"
Just ("bcd",'a')

-- the empty parser always fails
fail :: Parser Char Char
fail = empty

$ run fail "abcd"
$ Nothing

-- the empty parser is both a right and a left identity
a_ :: Parser Char Char
a_ = a    <|>  fail
_a :: Parser Char Char
_a = fail <|>  a

$ run a_ "abcd"
Just ("bcd",'a')
$ run a_ "babcd"
Nothing
$ run _a "abcd"
Just ("bcd",'a')
$ run _a "babcd"
Nothing

We're not limited to combining two parsers at a time, of course; there is also the 'mconcat' combinator:

mconcat :: Monoid' a => [a] -> a
mconcat = foldr (<|>) empty

$ run (mconcat []) "abcde"
Nothing

digits :: [Parser Char Char]
digits = map literal ['0' .. '9']

$ run (mconcat digits) "4hi!!"
Just ("hi!!", '4')

'mconcat' combines a list of monoids using the binary operation, and the identity element as the base case. This means that using 'mconcat' on an empty list will generate a parser that always fails.

Success

Similarly to the parser that always fails, we have a parser that always succeeds. This is captured by the pointed class, which is the 'pure' part of the Applicative class in the standard Haskell libraries. This class allows you to lift a value into a context; for parsers, we build a parser that always succeeds, with the specified value as its result, and consuming zero tokens.

  
class Pointed' f where
  pure :: a -> f a

instance Pointed' (Parser s) where
  pure a = Parser (\xs -> Just (xs, a))

Examples:

pass :: Parser Integer String
pass = pure "Hello, world!"


$ run pass []
Just ([],"Hello, world!")

$ run pass [1,100,31]
Just ([1,100,31],"Hello, world!")

The parser 'pass' always succeeds, even with empty input; it simply returns its input token stream along with its value.

Mapping and sequencing

It's also useful to have access to a parser's value for further processing; a common use case is building up a parse tree. This concept is captured by the Functor class, which lifts a normal function to a function that operates on the result value of a parser. The parser interpretation is that, given a function and a parser, if the parser succeeds, map the function over its results; whereas if the parser fails, just propagate the failure.

class Functor' f where
  fmap :: (a -> b) -> f a -> f b

instance Functor' (Parser s) where
  -- one 'fmap' for the Maybe, one for the tuple
  fmap f (Parser g) = Parser (fmap (fmap f) . g)

The Applicative class enables not just lifting, but application in which both the function and its arguments are in contexts. It allows parsers to be run in sequence, where the first parser is run, and if it fails, the whole chain fails; if it succeeds, the rest of the token stream is passed to the next parser and its result is collected, and so on. This implementation makes use of the Monad instance of Maybe, although it could also be implemented without such an assumption.

class Functor' f => Applicative' f where
  (<*>) :: f (a -> b) -> f a -> f b

instance Applicative' (Parser s) where
  Parser f <*> Parser x = Parser h
    where
      h xs = f xs >>= \(ys, f') -> 
        x ys >>= \(zs, x') ->
        Just (zs, f' x')

Here are some examples:

one :: Parser Char Char
one = literal '1'
oneInt :: Parser Char Int
oneInt = fmap (\x -> (read :: String -> Int) [x .. '9']) one

$ run oneInt "123"
Just ("23",123456789)

two :: Parser Char Char
two = literal '2'
twelve :: Parser Char (Char, Char)
twelve = pure (,) <*> one <*> two

$ run twelve "123"
Just ("3",('1','2'))

$ run twelve "1123"
Nothing

The first example shows a Char parser ('one') that is converted into an Int parser using 'fmap' and a function of type 'Char -> Int'. The second example applies the '(,)' function within an Applicative parser context, tupling the results of the parsers 'one' and 'two'. The third example shows that parsers run in sequence must all succeed for the entire match to succeed; although the '1' is matched, the '2' cannot be.

The power of Applicative parsers can also be harnessed to create parsers that ignore the results (but not the effects!) of some or all of their parsers:

(*>) :: Parser t a -> Parser t b -> Parser t b
l *> r = fmap (flip const) l <*> r 

(<*) :: Parser t a -> Parser t b -> Parser t a
l <* r = fmap const l <*> r

Both '(*>)' and '(<*)' will only succeed if both of their arguments succeed in sequence; the difference is that '(*>)' only returns the result of the 2nd parser, while '(<*)' only returns the result of the 1st parser. Examples, using the 'one' and 'two' parsers defined above:

$ run (two *> one) "212345"
Just ("2345",'1')

$ run (two <* one) "212345"
Just ("2345",'2')

Combining Applicatives with Semigroups, we can create repeating parsers:

many :: Parser t a -> Parser t [a]
many p = some p <|> pure []

some :: Parser t a -> Parser t [a]
some p = fmap (:) p <*> many p

(note that 'some' and 'many' are mutually recursive). 'many' tries to run its parser as many times as possible, progressively chewing up input; it always succeeds since it's fine with matching 0 times. On the other hand, 'some' matches its parser at least once, failing if it can't match it at all, but other than that is identical to 'many'. Examples (using 'one' from above):

$ run (fmap length $ many one) "111111234"
Just ("234",6)
$ run (many one) "23434593475dkljdfs"
Just ("23434593475dkljdfs","")

$ run (fmap length $ one) "111111234"
Just ("234",6)
$ run (some one) "23434593475dkljdfs"
Nothing

Negations

Oftentimes, parsing conditions are easier to state in the negative than in the positive. For instance, if you were parsing a string, you might look for a double-quote character to open the string, and another double-quote to end the string. Meanwhile, anything that's *not* a double-quote which comes after the opening will be part of the string. To capture this pattern, I created the 'Switch' class:

class Switch' f where
  switch :: f a -> f ()

instance Switch' (Parser s) where
  switch (Parser f) = Parser h
    where h xs = fmap (const (xs, ())) $ switch (f xs)

This converts a failing parser to a successful one and vice versa. Importantly, it consumes no input from the token stream -- it acts as a negative lookahead parser, which allows us to build flexible parsers on top of it. Examples:

not1 :: Parser t b -> Parser t t
not1 p = switch p *> getOne

dq :: Parser Char Char
dq = literal '"'

not_dq :: Parser Char Char
not_dq = not1 dq

dq_string :: Parser Char String
dq_string = dq *> many not_dq <* dq

$ run dq_string "\"no ending double-quote"
Nothing

$ run dq_string "\"I'm a string\"abcxyz"
Just ("abcxyz","I'm a string")

The 'not1' combinator takes a parser as input, runs that parser, and if it succeeds, 'not1' fails; if that parser fails, 'not1' then tries to consume a single token (any token). In other words, it's like saying "I want anything but ".

The 'not_dq' parser matches any character that's not a double-quote; the string parser matches a double-quote followed by any number of non-double-quotes, followed by another double-quote; it throws away the results of both double-quote parsers, only returning the body of the string.

Running many parsers in sequence

Traversable is an interesting type class. It allows you to 'commute' two functors; i.e. if you have '[Maybe Int]', it allows you to create 'Maybe [Int]' (that is, turn a list of 'Maybe Int's into a 'Maybe' list of Ints. This is also useful for parsing, where it allows one to convert a list of parsers into a (single) parser of lists. In this case, we don't need to supply an instance for 'Parser' because the Functor in question is lists:

class Functor' t => Traversable' t where
  commute :: (Pointed' f, Applicative' f) => t (f a) -> f (t a)

Here are some examples (using 'digits' from above):

six_fours :: [Parser Char Char]
six_fours = replicate 6 (literal '4')

$ run (commute digits) "0123456789abcxyz"
Just ("abcxyz","0123456789")

$ run (commute six_fours) "4444449999999"
Just ("9999999","444444")
$ run (commute six_fours) "44444 oops that was only 5 fours"
Nothing

Monads

What parsing article could be complete without mentioning monads? Monads are similar to applicatives, but add the extra ability to have computations depend on the result of previous computations. Here's the class definition and parser implementation:

class (Applicative' m, Pointed' m) => Monad' m where
  join :: m (m a) -> m a 

instance Monad' (Parser s) where
  join (Parser f) = Parser h
    where
      h xs = f xs >>= \(o, Parser g) -> g o  

A good example of putting this extra power to work is this combinator:

twice :: Eq a => Parser a a -> Parser a a
twice p = p >>= \x ->
  literal x

It runs its input parser, and if it succeeds, attempts to match the *same* output a second time. Thus, the second match depends on the results of the first. We can't build such a parser using applicatives (although we can build less general versions by enumerating multiple cases). Here's an example showing how it's different from an Applicative version, using the 'ab' parser from earlier:

ab_twice :: Parser Char Char
ab_twice = twice ab

-- using monads
$ run ab_twice "aa123"
Just ("123",'a')
$ run ab_twice "ab123"
Nothing

-- using applicatives
$ run (pure (,) <*> ab <*> ab) "aa123"
Just ("123",('a','a'))
$ run (pure (,) <*> ab <*> ab) "ab123"
Just ("123",('a','b'))

In the first example, which uses monadic parsing, 'ab_twice' parses the first input and fails on the second. However, the second example -- with applicatives -- successfully parses both inputs. It sees the two parsers as being totally independent of each other and thus isn't able to require that the second one match the same tokens as the first one.

Relationship to BNF grammars, regular expressions, etc.

Of course, all of these useful parsing combinators have also been applied in other parsing approaches, such as grammars and regular expressions. Here's a quick correspondence:

BNF/regex	combinators
|	<|> of semigroups
sequencing	<*> of applicatives
*	many
+	some
grouping	always explicitly grouped

What's next & further reading

There are a few topics that weren't covered in this article. First and foremost, good error detection and reporting is a key component of a parser library that's friendly and easy to use. Second, although I chose to use the Maybe data type to model the results, this could be extended to use any arbitrary monad -- resulting in a much richer set of parsers. Two examples are the list monad, to allow non-deterministic parses, and the state monad, two allow context-dependent parses.

If you're interested in learning more about parsing, Philip Wadler, Graham Hutton, and Doaitse Swierstra have published some excellent papers over the years on the topic; reading their papers was what really helped me to understand parsing. And of course there's also the powerful Parsec tool, a Haskell-based library for parser combinators which illustrates these ideas in a practical context.

A Haskell library for relational algebra

Why Haskell? Why relational algebra?

If you've never heard of Haskell before, and you like programming languages, you might want to check it out. It's a functional, statically-typed, type-inferred, elegant language in the ML family. The most important benefit that I've received from working with Haskell is a much better understanding of the static typing discipline, and the practice of designing a program or a library by figuring out a few concepts, capturing them as types -- either data or functions -- and building the rest of the code around them.

Relational algebra (RA) is a powerful mathematical tool for working with sets and functions on sets. Most common database products implement some flavor of SQL, a practical and standard language which contains many constructs from RA. Using SQL, a programmer can easily accomplish many complex data querying, manipulation, and transformation operations.

Unfortunately, applying RA often necessitates the use of a database. For whatever reason, there seem to be very few 'pure' RA libraries available for common languages. However, there are enormous benefits to be gained from integrating RA, instead of using a database: 1) not coupled to a database product, or its failure modes; 2) one less dependency for a deployed program; 3) code can mix RA with general purpose code, enhancing the effectiveness and efficiency of RA.

This post discusses the basic design and implementation of an RA library in Haskell.

Data model

The basic data types in RA are tuples, fixed-size units of n primitive values, and relations, or unordered sets composed of multiple named n-tuples of the same type. To distinguish RA tuples from Haskell tuples, I'll call them 'rows' for the rest of this post. Here's an example:

(first name: "Matthew", country: "USA", age: 25) <-- a named 3-tuple

a relation:

 first name | country | age   <-- the schema
-----------------------------
 "Matthew"  |  "USA"  |  25   <-- a tuple
  "Jimbo"   | "Spain" |  32   <-- another tuple of the same type
 "Jessica"  |  "USA"  |  27   <-- a third compatible tuple

However, the Haskell data model is a little bit different. Instead of restricting our row representation to just Haskell n-tuples, we'll let *any type* be a row, as long as we can compare any two instances of it for equality and ordering. And instead of using sets, we'll use lists -- Haskell has a large number of functions for working with lists, so it's a lot more convenient to use them than sets (although lists are intrinsically ordered, and do allow duplicates. We can ignore the first problem by never assuming the ordering is meaningful, but the second is more dangerous potentially). So what we have is:

-- the type of a relation:
:: (Eq a, Ord a) => [a]

-- and some examples of relations:
r1 :: Num a => [a]
r1 = [1,2,3]

r2 :: Num a => [(String, a)]
r2 = [("Matt", 1), ("Kevin", 14)]

r3 :: [a]
r3 = [] 

r4 :: [[String]]
r4 = [["abc", "xyz"], ["ghi"], []]

Note how the types of the rows can be almost anything -- numbers, Haskell tuples, polymorphic, or even lists.

Primitive RA operators

Rename: change attribute names, without changing any values. This operator is meaningless in the Haskell version, since it's not restricted to named tuples.

(name: "Matt", total: 32) -> (first name: "Matt", sum: 32)

Projection: apply a function to each tuple in a relation. Unfortunately, this could result in duplicates for either of two reasons: 1) the input contained duplicates, or 2) the mapping function created duplicates. The 2nd case has to be dealt with.

$ project (length . fst) [("Matt", 30), ("Bob", 22), ("Jimbo", 39), ("Sarah", 28)]
[4,3,5]

Row selection: select some rows, discarding the rest; none of the rows are changed.

$ rfilter (\(name, age) -> age >= 30) [("Matt", 30), ("Bob", 22), ("Jimbo", 39), ("Sarah", 28)]
[("Matt",30),("Jimbo",39)]

Cartesian product: combine two relations of size m and n rows respectively, resulting in a relation of size (m * n) rows, where an output row consists of a row from each of the input tables glued together. SQL and RA typically restrict result sets to *flat* tuples; since we've already gotten rid of this restriction, we're free to allow this to produce nested tuples.

$ rproduct "abc" [1..4]
[('a',1),('a',2),('a',3),('a',4),('b',1),('b',2),
 ('b',3),('b',4),('c',1),('c',2),('c',3),('c',4)]

Union: given two relations of the same type with m and n rows respectively, combine them by removing duplicates, resulting in a new relation of the *same* type with no more than (m + n) rows.

$ union [1..10] [5..15]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

Difference: given two relations of the same type, remove all elements found in the second relation from the first relation.

$ difference [1..10] [5..15]
[1,2,3,4]

Here are the Haskell implementations (note that these are by no means as efficient as possible):

project :: Eq b => (a -> b) -> [a] -> [b]
project f = nub . map f

rfilter :: (a -> Bool) -> [a] -> [a]
rfilter = filter
    
rproduct :: [a] -> [b] -> [(a, b)]
rproduct = liftM2 (,)

intersect :: Eq a => [a] -> [a] -> [a]
intersect xs ys = filter (\x -> x `elem` ys) xs

union :: Eq a => [a] -> [a] -> [a]
union xs ys = nub (xs ++ ys)

difference :: Eq a => [a] -> [a] -> [a]
difference r1 r2 = filter (\x -> not $ elem x r2) r1

Extending the library with some useful SQL operators

Inner, outer and left (outer) joins: these combine a cartesian product operation with a filtering operation. Outer joins are augmented inner joins, in that there is one additional result row for each unmatched row on one or both sides. Requires a default value of each row type to combine with the unmatched rows -- we're avoiding 'NULL's (although we could use Just/Nothing instead).

predicate l r = fst l == fst r
left = [(1, "Matt"), (2, "Jackie"), (3, "Gilligan")]
right = [(1, "hammer"), (1, "saw"), (1, "screwdriver"), (3, "boat"), (4, "wrench")]

$ innerJoin predicate left right
[((1,"Matt"),     (1,"hammer")),
 ((1,"Matt"),     (1,"saw")),
 ((1,"Matt"),     (1,"screwdriver")),
 ((3,"Gilligan"), (3,"boat"))]

$ leftJoin predicate (0, "nothing") left right
[((1,"Matt"),     (1,"hammer")),
 ((1,"Matt"),     (1,"saw")),
 ((1,"Matt"),     (1,"screwdriver")),
 ((2,"Jackie"),   (0,"nothing")),    <--- an extra row!!
 ((3,"Gilligan"), (3,"boat"))]

$ outerJoin predicate (0, "nobody") (0, "nothing") left right
[((1,"Matt"),     (1,"hammer")),
 ((1,"Matt"),     (1,"saw")),
 ((1,"Matt"),     (1,"screwdriver")),
 ((2,"Jackie"),   (0,"nothing")),
 ((3,"Gilligan"), (3,"boat")),
 ((0,"nobody"),   (4,"wrench"))]    <--- another extra row!!

Grouping, group processing, and aggregation: it's often useful to separate a relation into groups based on values of certain attribute(s), and then to continue processing with the grouped data.

-- group some words by their length
$ let g1 = groupBy length $ words "this is an article for my blog that I hope is interesting"
[(1,["I"]),       (2,["is","my","an","is"]),
 (3,["for"]),     (4,["hope","that","blog","this"]),
 (7,["article"]), (11,["interesting"])]

-- the first letters of words, in each group
$ groupLift (project head) g1
[(1,"I"), (2,"ima"),
 (3,"f"), (4,"htb"),
 (7,"a"), (11,"i")]

-- the number of words, in each group
$ groupLift length g1
[(1,1), (2,4),
 (3,1), (4,4),
 (7,1), (11,1)]

-- the unique letters, in each group
$ groupLift (nub . concat) g1
[(1,"I"),       (2,"ismyan"),
 (3,"for"),     (4,"hopetablgis"),
 (7,"article"), (11,"intersg")]

-- aggregation ignoring groups
$ aggregate (length . snd) sum g1
12

-- aggregation within groups
$ groupLift (aggregate (ord . head) sum) g1
[(1,73),  (2,416),
 (3,102), (4,434),
 (7,97),  (11,105)]

And the implementations:

innerJoin :: (a -> b -> Bool) -> [a] -> [b] -> [(a, b)]
innerJoin f ls rs = rfilter (uncurry f) (rproduct ls rs)

leftJoin :: forall a b. (a -> b -> Bool) -> b -> [a] -> [b] -> [(a, b)]
leftJoin p null rl rr = concatMap f rl
  where 
    -- go through all the a's 
    --   match each a with all b's
    --   if no matches, match it with the default
    --   otherwise keep all matches
    f :: a -> [(a, b)]
    f a = map ((,) a) $ addNull $ filter (p a) rr
      where
        addNull :: [b] -> [b]
        addNull [] = [null]
        addNull bs = bs

outerJoin :: (Eq a, Eq b) => (a -> b -> Bool) -> a -> b -> [a] -> [b] -> [(a, b)]
outerJoin p anull bnull as bs = union left right
  where 
    left = leftJoin p bnull as bs
    right = project swap $ leftJoin (flip p) anull bs as

groupBy :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
groupBy f rel = toList grouped
  where
    grouped = foldl f' (fromList []) rel
    f' mp next = addRow (f next) next mp
    -- check whether the key's already in the map:
    -- if it is, stick 'next' on the existing list
    -- if not, create a new, single-element list for that key
    addRow :: Ord k => k -> v -> Map k [v] -> Map k [v]
    addRow k v mp = case lookup k mp of    
                        (Just oldval) -> insert k (v:oldval) mp;  
                        _ -> insert k [v] mp;  

groupLift :: ([a] -> c) -> ([(b, [a])] -> [(b, c)])
groupLift f = map (fmap f)  

aggregate :: (a -> b) -> ([b] -> c) -> [a] -> c
aggregate proj f = f . map proj

Some notes about the design goals of the library

was shooting for flexibility, simplicity, and minimality, not efficiency. thus, it lacks many 'composite operators' that SQL has, for instance: in a SQL join, you both join and project all in one operation. in this library, instead, you'd do the join, then the projection separately ... maybe less efficient, but more expressive and compositional. another example, is that it lacks things like equi-joins that would make joining more efficient; it doesn't have them b/c that's covered by inner joins.