in "let t= a!i" a!i might be out of bounds ? On Fri, Aug 12, 2011 at 9:52 AM, Anton Kholomiov <[email protected]>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 <[email protected]> > > >> 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
