You could be right about the fail

Huh.  If I start a sentence “If they sail…,” Word asks me to ‘correct’ sail to fail.  Doesn’t happen with any other pronoun.  Apparently groups only get to go sailing if they invite you or me.

Wanted

Browser whose usability does not suck more with each release.  Can offer part exchange on an arthritic cat.

Keeping up with the parking meters

In the annals of bad install screens, the latest Java update deserves a special mention.

The message appears to be, “Parking meters and public transportation passes run Java.  You should too!”  Apparently Oracle doesn’t understand that the software that runs on parking meters is completely irrelevant to whether Java is any use to me on my PC.  It’s not as if I need my PC to double as a parking meter, or that there are applications built for parking meters that I’d like to run.  And it’s not like having Java on my PC will equip me with skills that will save my bacon next time I need to use a parking meter.

Of the ugly design, the “I found this great 1000 Free and Shareware Fonts CD from 1994” text quality and the fact that this sales pitch appears after I have already agreed to install the product, it is not necessary to speak.  The parking meters have it.

Recursive parsers in FParsec

Probably world + dog knows this already, but it didn’t jump out at me in the FParsec documentation or in Google, so I thought I’d write it down anyway.

The problem

Many languages contain recursive structures.  A list in Scheme or Lisp can contain sub-lists; a JSON object can contain sub-objects.

In FParsec, a parser for a linguistic structure is represented by a variable of parser type.  Here’s a simple example:

let number = many1 digit |>> Number

(FParsec does include built-in parsers for common number types – I just wanted a simple example.  And the Number constructor, like List in the next fragment, is just a constructor for a hypothetical AST node.)

Now consider a parser for a Scheme list of numbers – that is, a list of numbers enclosed in brackets and separated by spaces.  This is a bit more complicated:

let sepOrEnd = (spaces1 <|> (spaces >>. followedByString ")"))
let listElement = parseExpr .>> sepOrEnd
let series = spaces >>. many listElement |>> List
let list = between (pchar '(') (pchar ')') series

(I am sure there are more elegant ways to do this, but I don’t want to get hung up on that right now I’m trying to avoid line breaks.)

And we’ll say that an expression can be either a number or a list:

let expr = choice [ number; list ]

In reality, of course, a list should be able to contain any kind of expression.  So we need to redefine listElement as follows:

let listElement = expr .>> sepOrEnd

But now disaster strikes.  F# refuses to compile listElement, complaining that expr isn’t defined.  And there’s no way to move things around to avoid this.  expr depends on list, which depends on series, which depends on listElement, which depends on expr.

You might think we could get out of this with a let rec, making the relevant parsers mutually recursive, but let rec only works for recursive functions.  FParsec parsers are values.  Think of it as if you were trying to define four C# member or local variables.  C# is happy to let you define four methods in terms of each other, but not for you initialise to initialise four variables in terms of each other.

The solution

To get around this, FParsec provides you with a way to effectively forward declare a parser.  If I could ‘declare’ the expr parser before the listElement parser, so that listElement knew about it, but defer the implementation until after the list parser, then that would break the mutual dependency.  F# doesn’t have the notion of forward declaration, but FParsec simulates it using a function.

To forward declare a parser, call the createParserForwardedToRef function.  This function returns a pair.  The first element of the pair is a parser you can use without having defined it.  It’s the forward declaration, if you like.  The second element of the pair is a reference cell you can later overwrite with the implementation of the parser.  FParsec takes care of hooking up the ‘forward declaration’ parser to the eventual implementation.

This sounds more confusing than it actually is, so let’s see it in action.

let expr, exprImpl = createParserForwardedToRef()

Now expr is a parser which is hooked up to exprImpl, and exprImpl is a reference which we can overwrite later.  Because expr is a proper honest-to-goodness variable as far as F# is concerned, and is now defined before listElement, the compiler is now happy for us to use it in listElement:

let listElement = expr .>> sepOrEnd

Of course, now we can no longer write let expr = … when we want to implement expr parser, because expr is already declared.  And this is where exprImpl comes in.  Because this is a reference, we can overwrite its contents with the parser we actually need:

do exprImpl := choice [ number ; list ]

Note the use of do and := instead of let and =.  We are not rebinding exprImpl – it’s not mutable so F# wouldn’t allow that – but because it’s a reference cell, we can overwrite its contents.

Because of the way FParsec set up the expr ‘forward declaration’ – in reality, because of the implementation FParsec generated for the expr parser – all calls to expr actually end up going to exprImpl.  As a result, when exprImpl invokes expr (indirectly through listElement), it ends up invoking itself.  And we have a recursive parser, just as we needed.

Final code

let expr, exprImpl = createParserForwardedToRef()
 
let number = many1 digit |>> Number
 
let sepOrEnd = (spaces1 <|> (spaces >>. followedByString ")"))
let listElement = expr .>> sepOrEnd
let series = spaces >>. many listElement |>> List
let list = between (pchar '(') (pchar ')') series
 
do exprImpl := choice [ number; list ]