What I cannot create, I do not understand.

Just because you've implemented something, doesn't mean you understand it.

Errors in the Stream

Or, handling syntax errors without exceptions

I didn’t always find parsing interesting. That might be a surprise judging from the past half dozen blog posts I’ve written, but I got interested in compilers and programming language implementation through various Lisp and Scheme books, like SICP and The Little Schemer, so I quickly adopted the “parsing is boring!” mantra that is espoused by some authors.

However, parsing is part of every compiler (even Lisp compilers), and syntax is part of every programming language, so I couldn’t ignore it forever. I’m enchanted with how programming languages work in part because it feels like peeling back the curtain and finding out that there is no magic, just code. I couldn’t treat parsers as a black box for very long.

Parsing is more than taking a stream of characters and producing an abstract syntax tree; that’s just the bare minimum. Parsers must be usable, by humans who are feeding them source code, and by backends of compilers and interpreters. This means proper error handling, and treating errors as first class citizens. There are a lot of other things that makes parsers interesting (well they ARE monads after all…), but error handling is a subtle art that is often swept under the rug.

exceptions in ML

Standard ML (and OCaml, and the “platonic ML”) has an exception mechanism which should be familiar to many programmers who have used almost any other language with exceptions. In some ways, exceptions are fundamental to ML, since there are certain obvious cases (taking the head of an empty list, dividing by zero, non-exhaustive matches) where the runtime must raise an error, and allowing the programmer handle them makes sense. Exceptions are interesting in a few different theoretical ways involving types, but they’re perfectly usable by the working programmer too.

Over use (or frankly even any use) of exceptions is somewhat bad practice in my humble opinion. For the same reason ML programmers would rather opt for the classic 'a option type over pervasive nullable pointers, it seems to me that embedding all possible values in the type of an expression and avoiding exceptions altogether would lead to more robust code. There are other uses of exceptions beyond error handling, for non-local control flow, but I doubt anyone would seriously advocate it’s good style. Like mutable state, I think using exceptions in ML programs is more of a patch over an incomplete design than a good practice. I’m sure there are exceptions to this rule, but I don’t think parsing is one of them.

exceptions in parsing

Let’s talk about a concrete example, the parser I plan to write for s-expressions. Without writing the implementation, here’s the type of a parser “factory”:

1
val makeParser : (token, 'a) reader -> (sexpr, 'a) reader = (* ... *)

Like the lexical analyzer factory, this function takes a token reader and returns a parser, which is a new reader that produces abstract syntax trees (sexprs) from the stream. Recall that readers return a value of type ('a, 'b) option, in other words either a SOME (element, stream) or NONE. In the case of I/O or general stream processing code, the NONE value is simple: it just signifies that the stream is empty or the file handle has reached the EOF. (If this paragraph was incomprehensible to you, start here.)

As for the parser, what should happen in the case of a syntax error? Success is easy enough to understand, the result will be SOME (ast, stream) but failure is more complicated than just NONE. Reaching the end of the stream isn’t an exceptional circumstance, and shouldn’t represent an error (reaching the end EARLY is an error, but that just underlines my point, that NONE clobbers any granularity we might want). Ideally the parser would report something more interesting than just the existence of an error, but also an error message and where it occurred. This is necessary to achieve my goal of:

1
2
3
Syntax error on line 1 col 20:
(let ((x 1) (y 2)) (
~~~~~~~~~~~~~~~~~~~~^ unexpected EOF

What if we tried to use exceptions anyway? You could try, knowing it was a crutch and only a stepping stone to refactoring the code into a more complete, elegant design. But you run into an interesting problem pretty quickly. Look at the type of the parser factory above, polymorphic in the type of the stream. If we want to throw an exception that includes the stream itself, so that we can print an error message pointing at concrete syntax like the one above, the exception would have to be polymorphic too. But that type variable is scoped to the function, and Standard ML doesn’t allow you to define a polymorphic exception at the top-level.

specializing either

There is an alternative to 'a option which isn’t part of the Standard ML basis but is easy to define and should be familiar to Haskell programmers: ('a, 'b) either.

1
type ('a, 'b) either = Left of 'a | Right of 'b

This is basically a generalized union for types. Given two types 'a and 'b, either constructs a type consisting of their union or sum. It’s useful when you want to return an optional value but want the NONE variant to carry some extra data. You can imagine instead of Left and Right using:

1
type ('a, 'b) either = Success of 'a | Error of 'b

In our case, this is close but not quite enough. There are actually two possibilities other than success when trying to parse an ast from a stream: errors but also simply reaching the end of the stream. Reaching the end of a stream isn’t actually a error condition: it just means I’ve finished parsing a file or some other I/O stream (like a REPL being terminated with `). So it turns out that the following ternary type is better suited to parsing:

1
type ('a, 'b) result = Success of 'a * 'b | Error of string * 'b | EOF

I’ve further specified the type to return a pair of resulting element and rest of stream in the case of success, and return a pair of error message and stream in the case of errors. Here are a few example values of this type for clarification:

1
2
val Success (ASTNode (x, y, z), stream') = parse stream
val Error ("Expected END but got IF", stream') = parse stream

And here’s a little example function that consumes values of this type:

1
2
3
4
5
6
fun repl s =
    case parse s of
        Success (ast, s') => (print (eval ast)
                            ; repl s')
      | Error (msg, s')   => print (error (msg, s'))
      | EOF               => ()

an error-reporting parser for s-expressions

Our parser will take a stream and return an ML datatype representing s-expressions. This type is a simplified version of s-expressions that does not include “dotted pairs” because dotted pairs complicates the parser quite a bit without making it much more interesting.

1
datatype 'a sexpr = Atom of 'a * string | List of 'a * 'a sexpr list

The sexpr type is polymorphic leaving room for any data to be attached to each and every node in the abstract syntax tree. In our case, this will simply be line and column number (Pos.t) but you can imagine in a real compiler you might have more interesting data to attach, like scope or type information.

Finally, here is the complete source for the parser factory function, which takes a lexer and returns a parser:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fun makeParser (rdr : (Lexer.token * Pos.t, 'a * Pos.t) reader) : (Pos.t sexpr, 'a * Pos.t) parser =
    let
       fun sexpr s =
            case rdr s of
                SOME ((Lexer.Atom a, p), s') => Success (Atom (p, a), s')
              | SOME ((Lexer.LParen, p), s') => sexprList p s' []
              | SOME ((Lexer.RParen, _), _)  => Error ("unexpected )", s)
              | NONE => EOF

       and sexprList p s acc =
            case rdr s of
                NONE                         => Error ("unexpected EOF", s)
              | SOME ((Lexer.RParen, _), s') => Success (List (p, rev acc), s')
              | SOME _                       =>
                case sexpr s of
                    Success (x, s') => sexprList p s' (x :: acc)
                  | other           => other
    in
       sexpr
    end

This function follows from the s-expression grammar:

1
2
3
4
sexpr     -> <atom>
          -> ( sexprList )
sexprList -> .
          -> sexpr sexprList

The most interesting bit of this is probably the recursive call to sexpr on line 15. Here, I recursively parse an s-expression appearing inside a list and unpack the result only if it was successfully parsed, otherwise I return the result which is likely an error; I don’t believe that this call could ever produce the EOF value but I haven’t actually proved it or tested the code heavily to be sure.

1
2
3
4
5
6
7
8
9
10
local
   open Parser
in
   val Success (List ({line=1, col=0},
                      [Atom ({line=1, col=1}, "foo"),
                       List ({line=2, col=0},
                             [Atom ({line=2, col=1}, "bar")])]),
                _) =
       parse (Pos.stream "(foo\n(bar))")
end

Unfortunately, s-expressions are so simple there are only really two interesting errors: unexpected end of streams, and unexpected closing parentheses.

1
2
3
4
5
6
- parse (Pos.stream "(foo (bar") ;
val it = Error ("unexpected EOF",("",{col=9,line=1}))
  : (Pos.t Parser.sexpr,string * Pos.t) Parser.result
- parse (Pos.stream ")") ;
val it = Error ("unexpected )",(")",{col=0,line=1}))
  : (Pos.t Parser.sexpr,string * Pos.t) Parser.result

However, since every node in the abstract syntax tree is annotated with a position in concrete syntax, an interpreter or compiler that consumed the tree could use that position for better runtime error reporting. Hopefully you can also imagine a type checker doing the same for type errors.

Printing a nice error message with a little caret to the offending character requires a little extra work. When the error is discovered the parser has a reference to the rest of the stream, but this corresponds to the input source just after the error and beyon. The reader/stream abstraction doesn’t include any way to backtrack. Fortunately it’s not hard to remedy this. In most cases printing the line number, then the full line in question, and then the error message and column number would suffice to report the syntax error to the programmer. So the only problem is getting back to the start of the offending. It’s enough to just keep the stream at the beginning of the current line around until the reader reaches a new line:

1
2
3
4
5
6
fun reader rdr =
    fn (s, t, p) =>
       case rdr t of
           NONE            => NONE
         | SOME (#"\n", u) => SOME ((#"\n", p), (u, u, incrLine p))
         | SOME (x,     u) => SOME ((x,     p), (s, u, incrCol  p))

This is a function that takes a character reader (rdr) and returns a new reader that operates on a “richer” positional stream, one that also includes the stream state at the start of the current line. The reader takes a triple of s, t, p, where s is the stream at the start of the line, t is the current stream in the middle of the line, and p is the position. Printing the error message is then a question of taking the stream at the start of the line, consuming the entire line from that stream, and formatting the output nicely. This is left as an exercise for the reader. ;)

pretty-printing ASTs

It’s worth noting that some programming language implementations take a pretty drastically different approach to this entire problem: pretty printing abstract syntax trees. Particularly relevant is SML/NJ, which uses this when printing type errors:

1
2
3
4
5
val xs = [1,2,3]

val _ = case List.getItem xs of
            SOME (y, ys) => y
          | NONE         => xs

This is a simple example (note that the case expression’s branches are of different type) that yields the following error:

1
2
3
4
5
6
7
3.9-5.31 Error: case object and rules don't agree [tycon mismatch]
  rule domain: (int list * 'Z) option
  object: (int * int list) option
  in expression:
    (case (List.getItem xs)
      of SOME (y,ys) => y
       | NONE => xs)

The concrete syntax appearing after “in expression:” has been reconstructed and pretty-printed (I think) from the abstract syntax tree, and differs from the original in whitespace and parentheses. This occasionally causes me some confusion when debugging really hairy type errors, with more complicated expressions. Interestingly, the position (“3.9-5.31” which is the start and end of the expression, in the form “line.column-line.column”) DOES match up with the original input. So SML/NJ must keep that info around but doesn’t use it to go back to the original input when rendering the problematic bit of code in the error message.