[Haskell-cafe] Hierachical abstraction

[Edward Kmett]

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.

http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html

<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 <
sebf at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100128/80ffef8b/attachment.html