[Haskell-cafe] Re: compilation related questions
wren ng thornton
wren at freegeek.org
Fri Apr 10 17:19:04 EDT 2009
minh thu wrote:
> Say you have an AST, with just the information after a parsing pass.
> Then you compute 'derived' values at each node (maybe, I'm not sure if
> it would be practical, type, strictness, ...). To do that, you can
> have a function that, applied to any node, give the desired additional
> information.
>
> But for some functions, it can be seen clearly that such information
> could have been constructed at the same time that the data structure.
>
> So it is related to fusion techniques, but with the additional
> possibility of adding fields to the original data structure.
The problem with doing this automatically is that you don't get that
data for free. Storing the length of finite lists as you construct them
means that getting the length is constant time, but it introduces a
space overhead of one Integer per (:). If you call length often enough
it may be worth it, but generally the book-keeping will be too expensive.
We could use modified strategies where we have two different (:)s, one
that stores the length and one that doesn't. Then we could apply some
heuristic like exponential backoff to minimize the space overheads
subject to some logarithmic bound on the asymptotic cost of calculating
the length of the list until the first label. Or we could apply dynamic
memoization techniques and switch a non-length-storing (:) into a
length-storing (:) whenever we evaluate a call to length, so it'll be
quicker next time. Or,...
There're a lot of strategies here, but I doubt it's feasible to
automatically choose a good strategy for a given program (since "good"
may depend on the vagaries of runtime data). Automatically doing the
transformations and suggesting them to the user is doable though. You
may be interested in looking into attribute grammars[1] and finger
trees[2] for more ideas along this route.
[1]
http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter
[2] http://apfelmus.nfshost.com/monoid-fingertree.html
--
Live well,
~wren
More information about the Haskell-Cafe
mailing list