[Haskell-cafe] Backpatching

[Thomas Conway]

Hi All,

One of the things I've been working on lately is some ASN.1 stuff.One
of the first things I wrote in Haskell was an ASN.1 parser. It only
worked for a subset, and I'm revisiting it to make it handle a
larger subset.

One of the things that gets messy is that in lots of places you can
put either a thing or a reference to a thing (i.e. the name of a thing
defined elsewhere). For example, consider the production:

    NamedNumber ::= identifier "(" SignedNumber ")"
                  | identifier "(" DefinedValue ")"

If we ignore the second alternative, the natural translation into a
Parsec parser would look like:

    namedNumber = do
        name <- identifier
        val <- parens signedNumber
        return (name, val)

Now to handle the second alternative is easy enough:

    namedNumber = do
        name <- identifier
        val <- parens (fmap Left signedNumber <|> fmap Right definedValue)
        return (name, val)

however because names can be used before they are defined the result
typegoes from being

    type NamedNumber = (Name,Integer)

to

    type NamedNumber = (Name,Either Integer Name)

Nothing too terrible so far. The messiness comes in when you
considerthe number of places that you have to replace a type 't' with
(Either t Name). I'd really like to avoid having to do this.

If I were using Prolog, I could finesse the problem by introducing
afree variable and filling it in when I come across the definition[*].
Logic variable backpatching. :-)

So one possibility would be to return a closure:

        ...
        return $ \bindings -> (name,resolve val bindings)

    resolve :: (Either t Name) -> Map Name t -> t

or something like that. Then when you get to the end, you apply the
bindings and voila, out pops the simple type. I'm not sure this will
work quite as well as it sounds.

This sounds like a common problem type. Is there a well known solution
to this sort of problem?

cheers,
Tom
[*] And then at the end use var/1 to look for undefined names. Urk.
Actually, if I were using Prolog in the way most Prolog programmers use
it, I wouldn't be thinking about the types.
-- 
Dr Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.