[Haskell-cafe] Hierachical abstraction
Andrew Coppin
Let's start with parsers. A monadic parser library (e.g., Parsec) gives
you a set of primitive parsers. It also supplies functions to construct
more complex commonly-used parsers. And then it provides functions for
constructing even more complex parsers. (E.g., Parsec's expression
parser builder.)
Let's call the most basic primitive parsers level-0. Then we have
level-1 functions, which construct parsers from level-0 parsers. And
later we have level-2 functions which call the level-1 functions to
construct even more sophisticated parsers. And so on and so forth, to
unlimited depth. (The parser library itself has a limited depth, but the
library can have clients that build functions on top of functions.)
And so, in the end, the user calls a level-64 function, and gets a
parser that does the required task. And that's great.
The only problem is, the parser you get is a black box. You can't see
what's inside it or what it's going to do. You can only run it. (Or
combine it with other parsers.)
Why is that a problem? Well, suppose you want to pass the finished
parser through some kind of optimiser to rearrange its internal
structure. Ah. You can't. It's a black box.
Veering off onto a tangent for a moment... It seems to me that this is
an inevitable consequence for any monadic parser. After all, the bind
method runs some parse primitive, but it then feeds the result to a
general function, which can undertake some arbitrarily complex
Turing-complete calculation to decide what parse primitive to run next.
Hell, I can write a parser that parses a description of a grammar,
dynamically constructs a parser for that grammer, and then runs it!
There's no way in hell that some static optimiser can hope to optimise
the meta-parser so that it always generates optimal parsers. Even in
theory it's utterly impossible.
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?
Anyway, coming back on topic... Let's suppose that instead of parsers,
we've interested in queries. Suppose I'm writing some kind of relational
database engine library, and I want to optimise queries before running them.
The obvious solution is to design some kind of algebraic data type which
can represent every possible level-0 query primitive. I can then write
level-1 functions that construct level-0 data structures, and level-2
functions that call the level-1 functions, and so on, and at the end the
caller will get a (presumably complex) level-0 description, which my
optimiser can then go away and chew on.
Now suppose I want to perform optimisations on the higher-level
structure of the query. Currently, I can't. The hierachy of abstractions
gets flatterend to level-0 in the process of the call stack, so my
optimiser can only see the final level-0 representation.
The obvious solution would be to design an algebraic data type for every
level of the hierachy you want to analyse, complete with a function for
converting to the next level down. As I understand it, this is how GHC
works. It starts with raw Haskell source code, which it mashes around,
and eventually converts into Core. The Core representation is then
fiddled around with further, and eventually turned into STG. The STG
gets poked and prodded, and converted to C--. And that eventually
becomes raw assembly.
The thing is, these are all radically different representations of the
program. You can't mix (say) Haskell and STG together. And nor would you
want to, given that they're such wildly different abstractions.
[I notice in passing that, apparently, you can now FFI into C--, which
is interesting...]
However, consider the initial Haskell input. Initially it reflects what
the programmer typed in. But GHC gradually desugars this into some
minimal subset of the full Haskell language, before actually converting
it to Core. That means that [picking an example out of thin air]
initially an expression might contain the if/then/else construct, but at
some point [I presume] this is desugared into a case expression. And
that must mean that there are parts of the GHC codebase where it is
permissible for an expression to contain if/then/else, and other parts
where this is not permissible (and the code expects this construct to
not be present).
Is it possible to encode this kind of expectation into the type system?
Or does GHC just tacitly rely on the fact that source code takes a
predetermined path through the compiler engine? (That works for a
monolithic product like a compiler, but it wouldn't be so hot for a
library that 3rd parties can poke and prod arbitrary data into.)
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.
Has anybody ever looked at a general solution to something like that?
[I'm going to stop talking now...]
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Luke Palmer
<andrew...@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
Sebastian Fischer
On Jan 28, 2010, at 9:31 PM, Luke Palmer wrote:
> 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.
Did you think of "Data types � la carte" by Wouter Swierstra?
http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf
Also see the comments on Phil Wadler's blog:
http://wadler.blogspot.com/2008/02/data-types-la-carte.html
> You can make a typeclass for each feature that uses it on any data
> structure in which it is present.
I don't fully understand this sentence but it reminds me of "Finally
Tagless, Partially Evaluated" by Jacques Carette, Oleg Kiselyov and
Chung-chieh Shan:
http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf
Regarding the question of representing in the type system which
features are used, phantom types might also be helpful. If I remember
correctly, they were introduced by Daan Leijen and Erik Meijer to
restrict a data type that represents syntactically
correct database queries such that only type correct queries can be
made:
http://research.microsoft.com/en-us/um/people/emeijer/Papers/HaskellDB.pdf
Sebastian
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
Nils Anders Danielsson
> 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.
If the token set is finite you don't get any expressive advantage from a
monadic parser combinator library (in a lazy setting): you can parse any
decidable language using a simple library with an applicative functor
interface.
--
/NAD
Edward Kmett
means. I tend to consider them "codata CFGs", because they can have infinite
breadth and depth. However, a 'codata CFG' can handle a much larger class of
languages than CFGs. To that end, it is interesting to consider that to
maximize the ability to successfully parse such degenerate grammars you are
well served to use a traversal that can handle both of those cases. Such a
traversal can be built out of Luke's Omega monad or a logic monad with fair
conjunction/disjunction and provides a straightforward if inefficient
'top-down' parser.
<http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html>On
the other hand, I've had greater success by working with Applicatives to
build a CFG with 'pure' nodes represented as epsilons, using evil StableName
hackery to build bottom up parsers. Although, for that to work you basically
need to give up the ability to encode arbitrary "codata CFGs" in order to
let the grammar finish compiling. This limits my approach to handling true
CFGs (or TIGs), with an extension that covers TAGs, but lets me build a much
more efficient parser.
And yes, one of the major motivating ideas behind Arrows were the parsers of
Swierstra and Duponcheel (
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2446).
There are also compromise approaches. For instance Swierstra's uu-parsinglib
internally uses both a monadic and applicative parser and a by virtue of a
special bind operation that can glue them together yields a monad that can
at least optimize the last run of applicative computations.
http://www.cs.uu.nl/wiki/bin/view/HUT/ParserCombinators
-Edward Kmett
On Thu, Jan 28, 2010 at 6:22 PM, Sebastian Fischer <
se...@informatik.uni-kiel.de> wrote:
>
> On Jan 28, 2010, at 9:31 PM, Luke Palmer wrote:
>
>> 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.
>
> Did you think of "Data types à la carte" by Wouter Swierstra?
> http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf
> You can make a typeclass for each feature that uses it on any data
>> structure in which it is present.
>>
>
> I don't fully understand this sentence but it reminds me of "Finally
> Tagless, Partially Evaluated" by Jacques Carette, Oleg Kiselyov and
> Chung-chieh Shan:
> http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf
Actually, it is quite the opposite of the Kiselyov Carette and Shan trick.
interpreting an ADT is an initial algebraic construction, while the "Finally
Tagless" is a final coalgebraic construction.
-Edward Kmett
Edward Kmett
wrote:
> If the token set is finite you don't get any expressive advantage from a
> monadic parser combinator library (in a lazy setting): you can parse any
> decidable language using a simple library with an applicative functor
> interface.
>
Ah good point. I'd realized the class of 'codata CFGs' I was working with
was very large, but I hadn't made that painfully obvious in retrospect
connection! Just enumerate the inhabitants of the language via your
Applicative, er well, technically, Alternative combinators.
-Edward Kmett
Nils Anders Danielsson
> Luke pretty much nailed the summary of what you can parse using Applicative
> means. I tend to consider them "codata CFGs", because they can have infinite
> breadth and depth. However, a 'codata CFG' can handle a much larger class of
> languages than CFGs. To that end, it is interesting to consider that to
> maximize the ability to successfully parse such degenerate grammars you are
> well served to use a traversal that can handle both of those cases. Such a
> traversal can be built out of Luke's Omega monad or a logic monad with fair
> conjunction/disjunction and provides a straightforward if inefficient
> 'top-down' parser.
If you restrict the amount of coinduction that you allow, then you can
guarantee termination of parsing:
http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.html
--
/NAD
Andrew Coppin
> On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin
> <andrew...@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 have no idea what Applicative is, but I understand that one of the
main ideas behind Arrows is the ability to analyse the finished computation.
(Also, not all arrows support using the result of an arrow as the
continuation - and those that do are isomorphic to monads. So it seems
to be just another example of how limiting what you can do allows you to
make bigger guarantees...)
> 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.
>
Hmm, OK.
> So you're interested in structures which are all similar in a way.
>
Basically, yes.
Stuff like... a circle can be represented as a point and a radius. But
you can also represent it as a vast profusion of straight line segments.
Now I could design an algebraic data type that can represent circles and
lines, but then how do I guarantee that a particular expression contains
no circles, only lines? GADTs presumably.
But now suppose that I want not just circles, but *anything* that can
possibly be reduced to line segments. An algebraic data type,
generalised or not, has the property that it is "closed", and cannot be
added to once created. (I.e., you can't add new constructors later.)
Interestingly, you can write a class for "things that can be turned into
line segments", and an existential wrapper to type-cast any shape into a
universal type. But you can't cast it back again. You certainly can't do
pattern matching on it like you can with a case-expression over a
regular ADT. I've been pondering this today...
> 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.
>
Interesting... but vague. ;-)
Andrew Coppin
> Luke pretty much nailed the summary of what you can parse using
> Applicative means. I tend to consider them "codata CFGs", because they
> can have infinite breadth and depth. However, a 'codata CFG' can
> handle a much larger class of languages than CFGs.
Aren't CFGs banned in most countries due to concerns about the ozone layer?
> And yes, one of the major motivating ideas behind Arrows were the
> parsers of Swierstra and Duponcheel
> (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2446).
Doesn't surprise me... ;-)
I'm not sure what such a parser would look like, but by the looks of it
enough people have made them that I ought to be able to find some
examples to look at if I search around.
(I must say, while the idea of arrows sounds nice, I've never actually
tried using them due to the complexity of the mere syntax.)
Luke Palmer
<andrew...@btinternet.com> wrote:
> But now suppose that I want not just circles, but *anything* that can
> possibly be reduced to line segments.
If all you know about it is that it can be reduced to line segments,
there is no loss of generality in representing that simply as
[LineSegment]. This is getting close to the discussion in my recent
post about the existential typeclass pattern[1] -- there is no need
for extra structure if you cannot use it.
Luke
[1] http://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-typeclass/