Wednesday, September 13, 2006

Erlang in 5 seconds.

There was recently a thread on erlang-questions that discussed how you would present Erlang in 5 seconds. In an unrelated thread it is possible Richard Carlsson managed to nail it:

In most respects, Erlang _is_ a concurrent, nondestructive Lisp with a Prolog-inspired syntax that focuses on pattern matching and rules.

For my own reference he original email:

Nick Linker wrote:
I wonder why Erlang is not Lisp? I mean why inventors of Erlang chose
to create its own language instead of creating just ERTS-specific
library for LISP (or at least Scheme)?

Here are some reasons why Lisp might not be a perfect match to
the problem they wanted to solve:
 - no built-in concurrency
 - destructive updates abound (in Scheme, too)
 - no pattern matching

And if you're going to fix those things, you might as well use a syntax
that feels more comfortable to you. In particular, pattern matching
makes function definitions and selective receives much more readable,
which I assume was an important goal for the kind of industrial
applications that Erlang was created for.

In most respects, Erlang _is_ a concurrent, nondestructive Lisp with
a Prolog-inspired syntax that focuses on pattern matching and rules.


The Monad Laws

Every now and then I come across a post that explains a concept so clearly it is inspiring. I'd like to thank Albert Lai for just such a post. Re: [Haskell-cafe] Monad laws

Deokhwan Kim  writes:
>What is the practical meaning of monad laws?
>  1. (return x) >>= f == f x
>  2. m >>= return == m
>  3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

I offer to re-write the laws in do-notation.  (Please view with a
fixed-width (non-proportional) font.)

1. do { x' <- return x            do { f x
      ; f x'               ==        }

2. do { x <- m             ==     do { m
      ; return x }                   }

3. do { y <- do { x <- m          do { x <- m
                ; f x                ; do { y <- f x
                }          ==             ; g y
      ; g y                               }
      }                              }

                                  do { x <- m
                    using 3.14       ; y <- f x
                           ==        ; g y

I think in this notation everyone sees the laws as plain common sense.
If you do write a monad that doesn't follow some common sense, the
dire consequence (practical or theoretical) is obvious.

Just in case it is still not obvious to somebody...

When we see a program written in a form on the LHS, we expect it to do
the same thing as the corresponding RHS; and vice versa.  And in
practice, people do write like the lengthier LHS once in a while.
First example: beginners tend to write

  skip_and_get = do { unused <- getLine
                    ; line <- getLine
                    ; return line

and it would really throw off both beginners and veterans if that did
not act like (by law #2)

  skip_and_get = do { unused <- getLine
                    ; getLine

Second example: Next, you go ahead to use skip_and_get:

  main = do { answer <- skip_and_get
            ; putStrLn answer

The most popular way of comprehending this program is by inlining
(whether the compiler does or not is an orthogonal issue):

  main = do { answer <- do { unused <- getLine
                           ; getLine
            ; putStrLn answer

and applying law #3 so you can pretend it is

  main = do { unused <- getLine
            ; answer <- getLine
            ; putStrLn answer

Law #3 is amazingly pervasive: you have always assumed it, and you
have never noticed it.  (To put it into perspective, you hardly notice
yourself breathing, but this only makes the practical meaning of
breathing more profound, not less.)

Whether compilers exploit the laws or not, you still want the laws for
your own sake, just so you can avoid pulling your hair for
counter-intuitive program behaviour that brittlely depends on how many
redundant "return"s you insert or how you nest your do-blocks.

It is also worth reading apfelmus' followup for further elaboration on the intuition behind the monad laws.

Deokhwan Kim wrote:
> But what practical problems can unsatisfying them cause? In other words,
> I wonder if declaring a instance of the Monad class but not checking it
> for monad laws may cause any problems, except for not being qualified as
> a theoretical monad?

This question is likely to be a result of an unlucky introduction to
monads where they are introduced top down: "Hear ye, a monad, this is
some mystic thing obeying the spiritual laws 1.,2. and 3.", isn't it?
It is this way that monads get the attribute "theoretical".

Asking what the practical meaning of the monad laws might be is like
asking what the practical meaning of the laws for natural number
addition could be: what does
i)  a + (b+c) == (a+b) + c mean?
How can i understand
ii)  a + 0 == a ?
What does
iii)  a + b == b + a signify?

These question are unlikely to arise because you have an intuition of
what a natural number is: a number of bullets in sack, coins in your
pocket, people in the mailing-list etc. With this knowledge, you will
most likely not have any problems explaining the laws i),ii),iii) to
somebody else and most likely you will have not doubt about *why* they
must be true.

For monads, my intuition is as following: a value of type (M a) is an
action, something producing a value of type  a  and (or by) executing a
side-effect like drawing on the screen or screwing up the hard drive.

With the operator >>=, I can execute such actions in a specific
sequence. For the sequence, it is of course unimportant how i group my
actions: i can group actions act1 and act2 first and then postpend act3,
or i can group act2 and act3 first and then prepend it with act1.

To simplify writing down a formular corresponding to this fact, we
introduce the operator >> defined by
    act1 >> act2 = act1 >>= \x -> act2
which sequences actions but for simplicity discards the computed value x
of type a. It is only the side-effect of act1 we are interested in.

Now, the thought about grouping written does as formular is just
    (act1 >> act2) >> act3  ==  act1 >> (act2 >> act3)
and this is the simplified version of law 3. Of course, we know that
this is coined "associativity".

The actual law 3 is just a formulation for >>= that takes proper care of
the intermediate calculation result x.

With  return x , we can create an action which computes the value x but
 has absolutely no side-effects.
This can also be stated in formulas, as Mr "return" explains:
1. "if i am prepended to guys doing side-effects, i give them the value
x but do not take any responsibility for side-effects happening"
   (return x) >>= (\y -> f y) ==  f x
2. "if i am postponed to an action which computes a value x, i don't do
any additional side-effects but just return the value i have been given"
   m >>= (\x -> return x)  ==  m
which is of course equivalent to
   m >>= return  ==  m

So to answer your question:
> In other words, I wonder if declaring a instance of the Monad class
> but not checking it for monad laws may cause any problems, except for not
> being qualified as a theoretical monad?
A thing you declare to be an instance of the Monad class, but one that
does not fulfill the three laws above, simply does not match the
intuition behind a monad. I.e. your definitions of (>>=) and (return)
are most likely to be void of the intended meaning.

Friday, September 01, 2006

Why I prefer LALR parsers

I was asked on a mailing list why I prefer LALR to LL based parser generators. I ended up spending enough time on it to justify posting it here. Summary: "Reduced complexity in the semantic analyser is well worth the 'cost' of thinking bottom-up in the parser."

How come you prefer LALR? What about LR(k)?

I haven't really found the need for the added expressiveness of LR(k); this combined with the dearth of good GLR and LR(k) generators for many languages means that I haven't ended up using one for a project yet. When people write production generators (as opposed to experimental), they seem to be either LL(k) or yacc+.

I'm not surprised at the popularity of LL, as you say, if you're going to write your parser by hand you're going to use top-down, recursive decent - ie LL. Consequently for people coming to the problem of parsing for the first time, they are much easier to visualise, and as you point-out consequently to debug. I recently had to assist a colleague with a couple of sablecc[0] bugs that were a direct result of visualising the parse top-down, while using a bottom-up parser.

However once you've written a handful of parsers, the expressive limitations of LL(k), and the software engineering challenges top-down imposes on semantic analysis quickly teach you to appreciate LALR. Consequently I do not voluntarily use LL parsers in new projects.

I prefer LL(k) as it generates code similar to that you'd write yourself (top down parser) and that's useful when you are debugging. LL(k) is quicker :).

You're right, debugging of the parser is simpler with LL(k). That of course is beside the point, as I mentioned in my original email, the parser is the easy stage - the hard part is the semantic analysis, and LL makes this tougher. Simplifying the parser at the expense of the SA is false economy.

The added complexity derives from two places. The first derives from the additional information available with non-terminal productions in bottom-up parsers. Because bottom-up parsers reduce non-terminals after their children are fully parsed. This additional information makes using S or L-attribute grammars feasible for the first stage of SA. When working with LL I have come across three ways of dealing with this:

  1. Don't use attribute grammars, and use gradually (ie. most of the time, partially) initialised parser-global mutable state.
  2. Use nested parsers as accumulators.
  3. Use a eulers walk to convert top-down into bottom-up by attaching the SA to the post-order events.
In my experience the general approach is a combination of 1 and 2 - and they both cause serious structural problems in the resulting code, which all manner of coupling and structural aliasing between the parser and the SA that complicate ongoing maintenance. 3 wastes alot of memory (although admittably that is less of a problem now), but more importantly you have thrown away the very reason you went LL(k) in the first-place - top-down parsing.

The second source of complexity is the consequence of losing access to left-recursive grammars - which has two key impacts.

  1. Elimination of left-recursion replaces one simple rule with two coupled rules.
  2. This elimination is achieved by converting left-recursion to right-recursion; which will always[4] convert an S-attribute grammar into an L-attribute grammar; and seriously complicate any L-attribute grammar.

This causes problems analogous to the interaction of non-associative operators with foldr.
Consider the following grammar (where n is a terminal matching {digit}+ )

E -> E - n | n
converted[1] becomes
E -> nT*
T -> - n
"10 - 5 - 3" is then parsed:
  • L-recursive : (((10) - 5) - 3)
  • R-recusive : (10 (- 5 (- 3)))
Now of course SA can evaluate the R-form correctly, it just takes more work[2]; less intuitive code[3]; greater coupling; greater complexity.

LL parsers can't handle the L-recursive grammar, LR parsers can.

Reduced complexity in the SA is well worth the 'cost' of thinking bottom-up; seriously, it's not that difficult to do.

[1] The kleene star simplifies this a bit, using e for the empty match the classic conversion is

    E -> nE'
    E' -> - nE' | e
See Aho et al for details.

[2] The L-recursive SA is a trivial S-attribute grammar defined as

E -> E' - n { E.val := E'.val - n.val }
E -> n      { E.val := n.val }

[3] In this case the L-recursive form is so trivial that the resulting R-form produces a trivial accumulator based SA. However note that even at this basic level, we have converted a simple declarative form into a recursive form that is fundamentally more complex. In cases where the L-form is naturally recursive, the resulting R-form invariably introduces mutable shared state, with it's attendant complications.

[4] I'm reasonably certain this is the case, I don't however have time to double check this. Presumably someone will correct me if I'm mistaken here.

Friday, April 21, 2006

Open Recursion: a definition.

I've been asked a couple of times now about my use of "open recursion". It's covered in some detail by Pierce in "Types and Programming Languages"; I've included the one paragraph definition he gives below.

Open recursion. Another handy feature offered by most languages with objects and classes is the ability for one method body to invoke another method of the same object via a special variable called self or, in some langauges, this. The special behavior of self is that it is late-bound, allowing a method defined in one class to invoke another method that is defined later, in some subclass of the first.

Types and Programming Lanauges, Benjamin C. Pierce, 2002, MIT Press, pg 227.

Thursday, April 20, 2006

What is Object-Oriented Programming

Ok, so I've spent the past few days ragging on various applications of object-oriented programming. So what do I consider OOP good for? Well the answer naturally depends on what you consider OOP to be. So before I attempt to ask "What is it good for?", I will prepare the way by looking at "What is Object Oriented Programming"?

The biggest problem with giving a definition for object-oriented programming is that there are so many to choose from. Worse, the vast majority consist of little more than vague handwaving giving little or no thought to the existence of non-OO techniques. Consider the list of features listed by Johnathan Rees on Paul Graham's site.

Consider the first example. Encapsulation is not a distinguishing feature of OOP. Not only is it common in numerous non-OO languages, but it is not supported by many OO languages including both Smalltalk and Python! Moreover encapsulation is a friendly name given to existentially quantified types, which are the underlying theory used to understand Modules. Ie. when you see a feature offering encapsulation, what you are really seeing is a module/package system (possibly in disguise). Yes that does mean that Java/C#/C++ classes are doing double duty as both a type definition AND a module system. Yes that is the cause of several problems you are probably experiencing. No it doesn't have to be that way, there are languages that successfully seperate the two orthoginal concepts.

I make use of theory here because it allows me to avoid handwaving. Specifically it allows me to avoid the trap of promoting specific language features to the status of paradigm definition just because they are favoured, or even common in OOP languages. Using this approach I can quickly eliminate Encapsulation, Protection, Ad hoc Polymorphism, Parametric Polymorphism, and Sum-of-Product-of-Function from Ree's list. This leaves us with only "Everything is an object", "All you can do is send a message", Specification Inheritance, and Implementation Inheritance to consider. So lets map these to theory and see what we have left:

Everything is an object
This is literally a meaningless phrase as either it is strictly a matter of syntax (2.add(3) vs. 2 + 3); or it is a matter of purity, at which point it begs the question.
All You can do is send a message
Message Passing. You can take your pick of various algebras and calculi to model this. CSP was popular for a while; Process Algebra has its admirers; but my favourate is the pi-calculus.
Specification Inheritance
This is subtype-polymorphism using subsumption.
Implementation Inheritance
Open Recursion. Not alot of use if you don't have subtype-polymorphism as well, and proves difficult to model when you do. The simplest treatments use a least-fixed-type operator applied to a 'self' abstraction.

Ultimately the above three concepts coalese into two conceptualisations of OOP.

The first focuses on the 'object', considering them as identifiable, autonomous, finite automatons communicating via message-passing. Conceptually we are talking about highly concurrent actor based models. This approach is the once taken by Simula, Erlang, Pick, and friends. However while it corresponds closest to the original conception of OOP, it is barely recognisable in modern mainstream OOP languages. In fact these languages are more likely to be described as concurrency-oriented than object-oriented.

The second focuses on the 'class', considering OOP in terms inheritance and subtyping. Conceptually we are talking about languages that provide records containing function typed attributes that are parametised by a recursive 'self' parameter that provides for 'late-binding'. The conventional way to model this theoretically is via Abardi and Cardelli's Object Calculus (or you could try one of the papers available online ie A Theory of Primitive Objects (second order systems) or An Imperative Object Calculus). Representitive languages include all the usual suspects: Java, C++, C#, Smalltalk, etc.

While concurrent agents with message passing might be the original definition of OO, as mentioned above most programmers who consider themselves OO wouldn't recognise this as OO; certainly almost none of the languages traditionally considered OO would fit this definition. So it is pointless to pursue it further. That leaves us with a single definition.

Object Oriented Programming is any programming based on a combination of subtype polymorphism and open recursion

Translated back into more common terms - programming based on a combination of

  1. Polymorphic functions that accept as actual parameters values of any subtype of their formal parameters, and
  2. Late binding, based on a distinguished 'self' parameter to functions that provides access to attributes of a record/object based on its runtime type.
Which is consise, precise, and coincides with our intuition --- even if it does leave out a few 'traditional' aspects commonly included in definitions of OOP. Now to produce an object oriented language you need to add at least the idea of functions and function application without which you are not turing complete and you will need records, without which you can't define subtyping. These don't belong to any paradigm rather they are what it means to be a programming language. You probably want to add a store and references, but again these do not belong to OO rather they belong to the super-paradigm Iterative Programming. There are all sorts of features you can add to your language but only two, subtype-polymorphism and open recursion, make you Object Oriented.

Wednesday, April 19, 2006

Interpreter Pattern and Structural Recursion

I have previously discussed the flaws and limitations of the Visitor Pattern; criticised the Singleton Patterm as a global variable in disguise; and dismissed all but one of the rest as kludges to work around the GoF's languages-of-choice. That leaves the Interpreter.

This is a critically important pattern, if you only learn one pattern, make it this one! It is so fundamental to what we do to be different in kind from the other patterns in the book. In fact it is so critical that Gamma et al would probably have been better off ignoring the other patterns and writing their book exclusively on the Interpreter. In a very real sense this is exactly what Daniel Friedman did in "Essentials of Programming Languages" (EoPL).

If nothing else, the fact that you can comfortably write an entire book introducing the basics of the Interpreter Pattern is a good sign we're dealing with a different beast here to the rest of the GoF. Can you imagine writing a 300 page book introducing the basics of the factory-method?

The reason why the interpreter pattern is so important is that it amounts to designing a language, and language is our primary tool as programmers. We solve problems with computers, ultimately we do so with sequences of opcodes passed to the execution unit of our cpus; but the number of concepts we can express in a single sentence in machine code is limited, and the amount of detail we can choose to ignore when it is irrelevant to our solution is minimal. The act of climbing the language stack, (machine code -> symbolic assembly -> macro assembly -> C -> libc -> [java, Scheme, ML, etc]) is an exercise in increasing these two measures. Note I included libc in that list. I did that because language is the core abstraction being invoked in library, module, and macro systems as Kernighan and Pike discuss in "The Practice of Programming".

Now for the bad news. Yes the interpreter pattern is all goodness and light, but the unfortunately the sample implementation provided by GoF is crap. It's crap for exactly the same reason the visitor pattern is an inappropriate approach for parse-tree manipulation. This is a symbolic transformation, and as a problem is decidedly non-object-oriented. I'll go into exactly what an object-oriented problem looks like another time, but suffice to say that there is a good reason why LISP has survived 50 years, and the applicability of functional programming techniques to symbolic programming is a major part of it.

The solution offered in Design Patterns is an excelent piece of OO design. The problem: You have an AST you wish to execute. The solution: encapsulate the knowledge of how each different node-type should be evaluated in an 'evaluate' method on each node-type's associated class. Below is an example calculator implemented in Java using this exact design:

$cat test/*.java

 * test/
package test;

public class Add implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Add(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;

  public int calc() {
    return this.lhs.calc() + this.rhs.calc();

 * test/
package test;

public class Div implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Div(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;

  public int calc() {
    return this.lhs.calc() / this.rhs.calc();

 * test/
package test;

public interface Expression {
  public int calc();

 * test/
package test;

public class Main {
  public static void main(String[] args) {
        new Mul(
          new Sub(new Num(6), new Num(2)),
          new Add(new Num(2), new Num(3))).calc()));

 * test/
package test;

public class Mul implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Mul(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;

  public int calc() {
    return this.lhs.calc() * this.rhs.calc();

 * test/
package test;

public class Num implements Expression {
  private int num;

  public Num(int num) {
    this.num = num;

  public int calc() {
    return this.num;

 * test/
package test;

public class Sub implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Sub(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;

  public int calc() {
    return this.lhs.calc() - this.rhs.calc();
and indeed this does print '20' as expected.

Compare this with the ML code below, or the far more complex interpreter on page 74 of EoPL, and the problem is immedately clear. With symbolic transformation we are invariably performing 'structual recursion'. We have a data-structure, that is indeed a structure, defined recursively that is then processed by following the structure of the data, possibly performing an operation at each step. Consequently it is the structure that is important in comprehending the code, and ensuring a perfect match between data-structure and code-structure that is required to get it right. By scattering the code across multiple files, it makes it much more difficult to understand the structure of the code, and impossible to verify that this matches the structure of the data without signifigant effort.


(* Calculator *)

type expression =
  | Num of int
  | Add of expression * expression
  | Sub of expression * expression
  | Mul of expression * expression
  | Div of expression * expression ;;

let rec calc expr =
  match expr with
    | Num n -> n
    | Add (e1, e2) -> calc e1 + calc e2
    | Sub (e1, e2) -> calc e1 - calc e2
    | Mul (e1, e2) -> calc e1 * calc e2
    | Div (e1, e2) -> calc e1 / calc e2

let main () =
  print_int(calc(Mul(Sub(Num 6, Num 2), Add(Num 2, Num 3))));
  exit 0 ;;
main() ;;
and it is now trivial to inspect the code and the data and verify that the structures are identical. In fact it is so trivial the compiler will warn us of our mistake.
$ diff 15c15
<     | Mul (e1, e2) -> calc e1 * calc e2
> (*    | Mul (e1, e2) -> calc e1 * calc e2 *)
$ ocamlc -o calc-broken 
File "", line 11, characters 2-199:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Mul (_, _)
$ ./calc-broken
Fatal error: exception Match_failure("", 11, 2)
Now if you are stuck in an OO-world then the closest you can get to the above is to use either the visitor pattern or dynamic double dispatch. Not as neat, and a scary amount of boilerplate, but it works, and it is definately preferable to the example given in GoF; and when the time comes that you are not compelled to consign yourself to the OOP-only gulag you now know that there is something worth escaping to.

Tuesday, April 18, 2006

Back working on Kowari.

I am very grateful that I have been able to obtain another contract to work full-time on Kowari, so we should be seeing several fixes, changes, and enhancements flow into kowari over the next 3 months. The first installment is an enhancement to iTql to permit the convenient expression of compound constraints and existentials within the query.

{ s p1 o1 : p2 o1,o2 in m}
  is expanded to 
s p1 o1 in m and 
s p2 o1 in m and 
s p2 o2 in m

[ p1 o1 : p2 o1,o2 in m ] 
  is expanded to 
$av__X p1 o1 in m and 
$av__X p2 o1 in m and 
$av__X p2 o2 in m ; 

for some value of X
This syntax is derived directly from N3/SPARQL, with the only exception being that we use colons instead of semicolons to separate predicates because kowari uses ';' as a query seperator.

Anyone doing large conjunctions on custom resolvers will be particularly pleased to see this, and this is my first step towards better custom resolver support in general.

In other news I feel I should point people at the Netymon Public Repository which is currently home to any kowari improvements made by Netymon until such a time as the future of the sourceforge project is determined.

The perils of avoiding heresy (or "What are Design Patterns")

My last two posts have been rather critical of the Visitor Pattern as described in "Design Patterns" more commonly known as GoF (Gang of Four). So the question is reasonably asked, do I consider the other patterns similarly flawed? If anyone is interested in the answer, it's yes. In fact rather than being subtitled "Elements of Reusable Object-Oriented Software", it should have been "21 reasons C++ sucks; 1 embarassment; and an Abstract Syntax Tree".

First the embarassment: Singleton.
This is a global variable. It should be treated in your design as a global variable; a useful hack sometimes, but always undesirable. Singleton is more honestly described as "Abusing your languages class system to provide namespacing for global variables". Just say no.

Regarding the 21 other patterns, let me just add that most of them apply to Java equally to C++, but Java simply wasn't a serious contender when the book was written; and of course the examples are mostly C++ (all of them except a few in smalltalk). Ponder this question: Why isn't 'Constructor' a creational pattern? Then ask yourself, why are the OO-community the only programming community to name the Factory Method, or Command patterns? The answers are simple, but the ramifications profound.

In a language with first-class constructors, the Factory Method Pattern consists of

factory = MyClass.constructor
In a language with closures the Command Pattern consists of
menuItem.clicked = lambda : stuff...
In a langauge with constructors, the Constructor Pattern consists of
obj = new MyClass()

The final pattern is the OO version of the fundamental 'design pattern', elsewhere known as 'language'. The Interpreter Pattern was first applied, in it's non-OO form, during the 1950's, most famously in the development of symbolic assembly language, FORTRAN and Lisp. Since then it has found wide application being used in such diverse domains as database-querying, and printf format strings. The pattern is simultaneously both the most signifigant, cross-language, powerful pattern in Computer Science, and the biggest 'DUH' in the GoF's book. Of course, as with Visitor, the pattern in GoF is a near perfect example of the results of trying to shoehorn a non-OO problem into an OO-design; however I'll leave analysis of that for another time.

So if the book is predominately a catalogue of unfortunately necessary kludges around the semantic weaknesses of mainstream OO-languages, why do I still highly recommend it to new programmers?

Well for starters, precisely because it is a catalogue of necessary kludges. The book does capture (with the exception of Singleton) good work arounds for the weaknesses a programmer is going to face when working with C++/Java/C# (and to a lesser extent Python/Ruby/Smalltalk/etc). We all find ourselves needing to work in these languages from time to time, and it is well worth knowing cleaner kludges.

Secondly, along with "Refactoring" by Martin Fowler, GoF provides the reader with a solid introduction to good OO design. Combined, these two books will guide the new programmer into a solid understanding of classic object orientation. Given OO is the dominant paradigm behind all the current mainstream languages (unless you consider VB mainstream), this is worthwhile. That there are far better, cleaner, and safer alternative designs available outside the mainstream is beside the point when a new programmer is going to face Java or C# (or heaven forbid C++). Where a skilled programmer will translate these alternatives into a clean non-OO implementation within a mainstream language (see previous discussion regarding Visitor pattern and parser generators); this is simply not a reasonable expectation of a new programmer who is still mastering their first or second language.

Read them, learn them, even use them. Still you should always remember, these are kludges, and there are generally better alternatives available - the proof of you skill as a programmer is you understanding of what they are.

Thursday, April 13, 2006

More on the visitor pattern

The primary reason I started this blog was that I occasionally spend non-trivial amounts of time contributing to mailing lists discussions. Some of those emails approach short articles and I got fustrated having them disappear into list-archives, sometimes never to be seen again (even when I've gone looking for them).

Not surprisingly my recent blog entry, and associated post to the kowari mailing lists has led to a need to respond with a more carefully reasoned, and less emotional defense than yesterdays rant.

First it has been pointed out that I used the term Abstract Syntax Tree when it would be more correct to refer to the output of sablecc as a Concrete Syntax Tree. I acknowledge this, although I have always found the distinction vague. It always seems to rely on the semantics of the grammar not the syntax. The closest I've come to definition that doesn't make reference to semantics is: "An AST is a CST missing some bits"; which of course implies CST is a subtype of AST forall values of some == none.

However as this post is not dealing specifically with sablecc, but rather with parser generators in general, and with their interaction with the visitor pattern in particular, I will continue to use the more general term AST as it is more appropriate given the existence of tools such as javacc that permit the definition of an AST directly within the grammar file.

I was pointed at for a discussion of new features in sablecc to make the use of the visitor pattern more palateable. Indeed these features are going to be useful, however they only demonstrate my point.

Defining the abstract syntax tree and writing transformations from to concrete to abstract tree is quite an effort, and then you have to write your own visitor classes to process that tree.
Exactly the same argument applies if what you are wanting is 3-address code, or a rmi-enabled Query object (which is want Kowari is generating). What the author of sablecc is slowly learning is that the authors of cups, yacc, and antlr whose products he dismissed so casually in his thesis actually did know what they were doing.

Ultimately the Lex -> Parse -> Semantic Analysis stage of a compiler is not suited to an OO based design, and no attempt to shoehorn this into an OO framework is going to be as effective as recognising this and working with the grain of the problem. You can see this clearly illustrated if you look at the actual file generated by sablecc. It is not object oriented in the slightest, rather it is a massive automaton (itql has 205 states), with each state associated with a small fragment of functional code. This accurately reflects the nature of the problem. That the the user is then presented an interface that ignores this underlying reality in favour of ideological purity is unfortunate.

The only justification given is that it allows the semantic analysis to be seperated from the grammar defintion. But then the seperation of the first stage SA from grammar is undesirable, so this is a moot point. A stage-1 SA must follow the exact shape of the productions in the grammar. As structure is very awkward to keep synchronised, DRY dictates that this structure should be defined in exactly one place. Moreover the as the parser is completely defined by the structure, don't think of the 'grammar' file as the parser's grammar; think of it as the stage-1 SA definition. The parser just happens to be generated directly from a simple structural analysis of the SA definition. I have written numerous parsers, they cease being difficult when you stop trying to think of them in imperative terms, but consider them as declarative definitions of symbolic tree transformations. Anyone having trouble with this concept should reread sections 5.1-5.4 of Aho/Sethi/Ullman (Dragon Book).

Parsing is easy. Semantics is not. The visitor pattern results in a very clean elegant interface to the parser, and makes the parser writers life easy. However it wasn't a fundamentally hard life to begin with, and the decision results in scattering the semantic analysis code as 1-3 line fragments across dozens of files (unless you do what kowari does and breaks encapsulation). To the extent you follow the pattern, you need a visitor for each unique synthesised attribute. What is generally a one line annotation on an EBNF grammar becomes an entire class. If you allow apply() to return a synthesised attribute, you can normally reduce the number of classes by combining visitors. Be aware though that having used this approach myself the price is in maintainability and flexibility as you have to be very careful you avoid undesired interactions between the combined visitors.

Parsing is only occasionally hard; Semantic Analysis is only occasionally easy. We should not be trying to find ways of making parsing easier just because it is easy; rather we should be trying to find ways to make semantic analysis easier precisely because it is hard. We are dealing with a functional problem and trying to find an object-oriented imperative solution is working against the grain, and it leaves me wondering, "Why you would bother?".

Tuesday, April 11, 2006

Visitor Pattern and Trees Considered Harmful

I have just finished a very fustrating week fighting a parser generator implementing some syntactic sugar for Kowari. The reason why it's been so fustrating is simply because it should have taken one day to implement, test, and document, except that the parser generator was sablecc.

Now sablecc has been stable, featureful, and reasonably performant. Documentation is a minor problem given that it really only consists of a tutorial and the author's masters thesis; still it's a LALR parser generator once you have an EBNF exactly how hard can it be? As a parser generator sablecc works wonderfully.

Unfortunately that's also where the trouble starts, because it's very rare for someone to only want a parser. Generally someone is using a parser generator because they are writing some sort of compiler, and so the parser generator feeds into some sort of semantic analysis stage. And this is where sablecc fails, cf. the topic of todays post.

Sablecc generates an AST. Sablecc always generates an AST! And of course how does your hard working, OOP entrenched, lemming of an author support inspection of this tree? Well as with all well behaved OOP lemmings the author parrots off in the true unquestioning drone of the acolyte, "The visitor pattern of course". Think I'm joking? The thesis was called "SABLECC, AN OBJECT-ORIENTED COMPILER FRAMEWORK"! At this point swearing would be appropriate.

Let's step back and look at the problem we are actually trying to solve. We have an context-free grammar that describes how we can generate an abstract syntax tree from a given input. Semantic Analysis is effectively a transform applied to the AST. Now the nature of this transform is remarkably consistent across compilers. Occasionally it amounts to a eulers walk over the tree, but generally it is a straight forward post-order traversal generating what are called 'Synthsised Attributes' at each production from it and it's children[0]. The result is called an 'Annotated Syntax Tree', and generally the attribute derivations are defined to ensure that the desired output of the semantic analyser is an attribute at the root of the AST.

Attribute derivation defintions are routinely defined as code snippets that convert child attributes into production attributes. In other words we have a series of functions that are dispatched on the AST node type, are called within the context of the results of the child production's functions, and are called as a post-order traversal.

Finally we have the added advantage that each node in the AST corresponds to a reduction in the LALR bottom-up shift-reduce parser that is the ultimate goal of an LALR parser generator. Being bottom-up, this is automatically a post-order sequence of reductions. Consequently we can choose to forgo the generation of the AST altogether and associate the functions directly with the reductions if we so desire. (and why wouldn't we?)

Now generating an AST is sometimes desirable, for instance when you require the afore mentioned eulers walk based traversal, or if you are wanting to unparse the AST back into source-code again later. But regardless of if you generate an AST or not, most compilations are a simple bottom-up generation of the root anntoation in an annotated syntax tree based on associating functions with AST-nodes/parser-reductions.

So that is the problem we want to solve, and in the strictest possible sense it is fundamentally functional in nature. This of course poses a serious problem to our aforementioned object-oriented-lemming, because the natural, straight forward solution is not object-oriented. So the lemming spits out a tree and of course doesn't even need to think about the next step. After all "the object-oriented way to traverse a tree is the visitor pattern", so we'll disregard the fact that the problem is functional in nature --- we have this hammer and by george if we aren't going to make this problem fit our solution.

The visitor pattern is kludge used by programmers in a language that doesn't support multiple-dispatch to provide themselves with a static version of double-dispatch. The cannonical example that was used by the GoF when they documented the pattern is tree traversal. And ever since that fateful day no OOL has dared consider anything else (feh). Note there is no mention of trees in the definition above. Trees are a datastructure. The visitor pattern is a language semantics idiom. THEY ARE NOT RELATED CONCEPTS! Maybe if you are implementing dynamic traversals over a static tree (which does require double-dispatch to do cleanly) you might consider the visitor pattern as a solution to THIS problem; but only if you are willing to bet the life of your first born to guarentee that you will never ever want to introduce a new tree-node type into your design.

For LALR parsers using code definitions for synthesised attributes, this problem has been solved for decades. Yacc got it right. The limitations and difficulties that programmers have with yacc fall into 2 categories: Memory management - garbage collection neatly solves that problem; Conceptual vagueness - a tool can only rarely even help you understand the problem you are trying to solve.

Why is this the right approach? Because the attribute derivations are generally trivial calls to constructors or functions --- along the lines of foobar = new Foobar(token), or combined = combineFoobars(child1.foobar, child2.foobar). And these derivations are intimately associated with individual productions (as discussed above). Consequently it is extremely awkward to seperate the grammar definition from the attribute derivation definition, as they needs must have an identical structure, and hence seperation violates the DRY principle and makes debugging/enhancement a right royal pain.

So why have I suffered this week? Because OO-Lemmings can't be bothered to consider if OO is an appropriate paradigm for the problem that presents itself to us; and because of this unfortunate association of tree-traversal with the visitor pattern. Now I can't do anything about the prevalence of lemmings that won't get me arrested, but please please please stop using the visitor pattern to traverse trees.

[0] If an attribute derivation requires information from a parent or sibling then it is referred to as an 'Inherited Attribute', and this is when you require a dependency aware eulers walk instead of a post-order traversal.

Thursday, March 23, 2006

Amusing: seen on LtU

Here's the condensed LtU guide to the static types vs dynamic types debate: * Haskell-vs-Scheme is an issue on which reasonable people differ. * Ruby-vs-Java is an issue on which unreasonable people differ. Everything else is details.

Friday, February 10, 2006

Hint to new programmers

So I'm working my way through code written by a recent grad.... this sucks! So to all new programmers out there...


Just because you CAN return void and use an object field as an implicit return parameter DOESN'T MEAN YOU SHOULD!

....and I suppose some lawyer would decide it was murder.....

Monday, January 23, 2006

Loops Considered Harmful (personal reprise)

Paul Gearon posted a short rant on Java's verbosity and general clunkiness. The problem is to write a function that takes a string and returns a string containing the distinct characters of that string in sorted order. While Paul does provide a solution in java, he only alludes to the sort of function you might expect to write. So I thought I might have a go at the problem:

Assuming we have a string type, and a sorted-set in our standard library:

(lambda str (reverse-list->string
                (sorted-set-fold (compose cons flip) '()
                     (string-fold insert (sorted-set) str))))
Note: The reverse reduces the complexity from O(n^2 log m) to O(n log m)
3 lines. No mess, no fuss.

Tuesday, January 10, 2006

Trouble in Kowari-land

Times of transition are always hard, and cultures do not always mix without conflict. The past year has been a time of transition for Kowari, as we have had to move from a close-knit circle of developers mostly working in the same room, to a distributed open-source community. It has of course been complicated by the need to try and reach an understanding with the new copyright owners of much of the kowari codebase, Northrup Grumman.

Yesterday I had the unpleasant duty of accepting the resignation of a good friend, colleague, and co-developer/admin from the Kowari project after he received legal threats from Northrup. I remember watching these sorts of tussles go down in my years within the OSS community. I have always felt sympathy for those volunteers who find themselves in the way of corporate lawyers. Now as the maintainer who has to sit and wait for NG's response I realise just how important the freedom in free-software really is. The MPL 1.1 is now the only thing standing between me and the loss of the Kowari project.

It's not really surprising that this story is starting to find its way onto the blogsphere. I would like to thank the SOFA community for their note of support. In response to Clark Parsia's questions about the legal status of kowari:

  1. The copyright in the vast majority of Kowari as of Jan 2005, and consequently the majority of Kowari now was owned by Tucana Technologies, and hence now by NG. However the majority of the work done in 2005 was done by parties unassociated with NG, and this work is copyright the authors (or in some cases the parties that paid for the work). Of particular note is the work done by Paul Gearon on the krule engine, and the work commissioned by the DSTO on the query rewriting. The former particularly is perfectly capable of independent existence, and while it currently lives in the kowari sourcetree is not derivative.
  2. There have been no releases since Tucana went insolvent. It took 6 months to reorganise after Tucana's fold, and another 3-4 months to prepare for release. We were ready for release in November, however held off at the explicit (and inconvenient) request of NG in an effort to support there integration into the community. I should be clear here; The 9th of January release date was requested by Northrup, and acceeded to by the Kowari administrators as a sign of good-faith. We had originally planned to release 1.1 in November.
  3. IANAL, but my understanding of the MPL --- and my personal first-hand knowledge of the express intent of Tucana when the MPL was chosen as a license --- is that anyone who cares to has the right to take a snapshot of the sourceforge repository; label it MyKowariRelease1.1; and release it to the public. And indeed if open-source means anything, it means the right to fork. However at the present point in time, I am the administrator of the kowari project, and Northrup have the same right to fork from Kowari as anyone else does.
As is clear in Clark Parsia's blog post above, this uncertainty is hurting Kowari so I will do whatever I can to ensure it is resolved promptly. All I can ask is to please be patient and lets see if we can't help Northrup to become a productive member of the opensource community.