I read two theory related blog posts at the weekend which I thought were very interesting.
The first was by Laurence Tratt on the subject of parsing, and suggests that we are getting to the stage where we’d like to embed DSLs into standard programming languages, raising the question of how we compose the two grammars. The post raises a lot of interesting points, and also links to a load of interesting papers on parsing PEGs and boolean grammars. PEGs look really interesting to me and demonstrate the advantages of functional thinking – if we remove the ambiguity of a grammar by ordering the rules for a non-terminal symbol, then we can regard the parser as a pure function with inputs the current character positions and the non-terminal that we expect to start at this position and which outputs a parse tree representation. We can therefore apply memoisation, a standard functional programming trick, to these parsing functions to get a parser that works in linear time.
The second was by Chris Smith on the subject of “Why Do Monads Matter?”. This essay compares and contrasts the views of mathematicians and computer sciences in the way that they look at monads. He looks at the problems represented by the four horsemen of the catapocalyse and considers how these problems relate to categories. In so doing, he gives a very good motivation for the inclusion of monad-based datatypes in languages such as Haskell.