[Haskell-cafe] library on common sub-expression elimination?

[Vinod Grover]

in "let t= a!i"  a!i might be out of bounds ?

On Fri, Aug 12, 2011 at 9:52 AM, Anton Kholomiov
<anton.kholomiov at gmail.com>wrote:

> 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.
>>
>>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110812/74076d4f/attachment.htm>