
On Tue, Oct 17, 2006 at 09:23:24AM +0100, Ross Paterson wrote:
On Mon, Oct 16, 2006 at 11:07:13PM -0700, John Meacham wrote:
The basic issue is that frisby relys on optimizing the parser before executing it, so any static information that can be gleaned from the built parser is very important to have available. however, the optimizer has no way to "see through" an 'fmap' since the functional argument is opaque as far as frisby is concerned. [...] note I don't really consider RULES appropriate here, knowing that the optimizer will be able to see through these operations is vital for writing a parser that works at all.
I don't follow this part. The argument of fmap is a semantic action, which is presumably independent of parsing decisions. So without special versions of the operations you lose the ability to simplify composed actions, which will cost, but how does it prevent the parser from working at all?
a vital optimization involves finding common sub-parsers, for which it performs a normalization pass and then a hash-consing to find common parts. Since there is no way to figure out whether two functions are equal, it is forced to be pessamistic and assume they are distinct. If this occurs too often, this creates a blow up in the final number of rules to the point that the parser is no longer practical to use.
I would also like to see mapM_ as part of the class definition for traversable. For many monads it makes the difference between linear and constant space usage and space behavior of haskell programs is hard enough to reason about without having to worry about certain rules firing.
Do you have an example where Data.Foldable.mapM_ uses linear space, and can this be avoided with a custom definition of Data.Foldable.foldr?
I ran into them before, I'll try to dig up an example that was causing me trouble... John -- John Meacham - ⑆repetae.net⑆john⑈