[Haskell-cafe] library on common sub-expression elimination?
Anton Kholomiov
anton.kholomiov at gmail.com
Fri Aug 12 18:52:49 CEST 2011
Just to make it explicit, is it
\a i ->
let t = a ! i in
if i >= 0 then
t
else if i > 0 then
t + a ! (i-1)
else ....
bad idea, because of last else-case? Can it be mended with
one another pass for if-expressions?
The upcoming distilled tutorial at DSL 2011 - thank you for the link.
I'm going to experiment with data-reify, while the library you've mentioned
is
OCaml only.
2011/8/12 <oleg at okmij.org>
>
> I guess you mean the function that converts an abstract syntax tree to
> a directed acyclic graph (DAG).
>
> Just for completeness I should mention that if the object language has
> effects including non-termination, one has to be careful eliminating
> seemingly common expressions. For example, in
>
> \a i ->
> if i >= 0 then
> a ! i
> else if i > 0 then
> a ! i + a ! (i-1)
> else ....
>
> we see the expression (a ! i) repeated in both branches of
> the conditional. Eliminating the `duplicate' by pulling it out
>
> \a i ->
> let t = a ! i in
> if i >= 0 then
> t
> else if i > 0 then
> t + a ! (i-1)
> else ....
>
> would be wrong, wouldn't it?
>
> This issue has been extensively investigated in the Fortran compiler
> community; Elliott, Finne and de Moor's ``Compiling Embedded Languages''
> (JFP 2003) talks about it at length.
>
>
> The standard technique to detect occurrences of common subexpressions
> is so-called hash-consing. There are (OCaml) libraries for it:
>
> author = {Jean-Christophe Filli{\^a}tre and Sylvain Conchon},
> title = {Type-Safe Modular Hash-Consing},
> pages = {12--19},
> crossref = "ml2006",
> doi = "10.1145/1159876.1159880",
>
> The upcoming distilled tutorial at DSL 2011
>
> http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&view=article&id=2&Itemid=2
>
> will present a Haskell library for hash-consing. The library can work
> with the standard Haskell Hash-tables or without them (using Data.Map,
> for example). The library does _not_ rely on Stable names and other
> internal GHC operations with unstable semantics. The library will find
> all common sub-expressions.
>
>
> Incidentally, despite the Lisp-sounding name, hash-consing was
> invented before Lisp. It was described, for the English audience, in
> the first volume of Comm. ACM, in 1958:
>
> @Article{ Ershov-hash-consing,
> author = {A. P. Ershov},
> title = {On programming of arithmetic operations},
> journal = "Communications of the {ACM}",
> year = 1958,
> volume = 1,
> number = 8,
> pages = {3--6},
> doi ="10.1145/368892.368907",
> url = "http://portal.acm.org/citation.cfm?id=368907"
> }
>
> The translation is quite accurate, as far as I could see, but misses
> the flowcharts and the diagram of the original paper. This short paper
> fully describes what we now call hash tables, hash functions, useful
> properties of hash functions, and hash-consing. The article analyzes
> the time complexity of the algorithm. Since the algorithm has two
> exits, writing programs in the continuation-passing style must have been
> familiar back then.
>
>
> The library to be presented at DSL 2011 unwittingly follows Ershov's
> algorithm closely. The library is (hopefully) better described (see
> the preface to the English translation of Ershov's paper). Nowadays,
> starting a paper with the phrase ``All unexplained terms are those
> from [1]'' (where [1] is the single reference) would not be taken
> kindly by reviewers.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110812/cf5dfdc4/attachment.htm>
More information about the Haskell-Cafe
mailing list