[Haskell-cafe] Hierachical abstraction

[Luke Palmer]

On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin
<andrewcoppin at btinternet.com> wrote:
> I wonder if you can make a parser combinator library which is *not* monadic?
> And, if you could, in what way would that limit the kinds of things you can
> parse?

Absolutely!  I believe both Applicatives and Arrows were originally
invented for parsers.  I could be mistaken, but at least there are
both Applicative and Arrow parser libraries.  I don't know how to
classify the language that they parse -- it is not strictly
context-free.  It corresponds roughly to context-free where certain
types of infinite chains are allowed.  Anyway they are less expressive
than Parsec, but more efficient and optimizable, for reasons you
correctly identified.

> I'm basically looking at a problem which is like this. There are primitive
> constructs, and there are more sophisticated abstractions built from these,
> and I would like to come up with a system where abstractions are
> first-class, new abstractions can be added, and for any particular data
> structure, you can statically guarantee which abstractions are or aren't
> present.

So you're interested in structures which are all similar in a way.
GHC converting between different representations has advantages
*because* the representations are so different -- different
optimization opportunities are apparent in each one that aren't
available in the others.  But at the very least for extensibility
people want to have AST-like structures which have different features,
and those features are statically guaranteed.

I don't remember the name, but there is a technique where you compose
the features you want and then take its fixed point to get your AST.
You can make a typeclass for each feature that uses it on any data
structure in which it is present.  Not the prettiest thing ever, but
fairly powerful.

Luke