UnivTrevesV1, Istex, Corpus, bibRecord, 001228

Constraints to stop deforestation

Identifieur interne : 001228 ( Istex/Corpus ); précédent : 001227; suivant : 001229

Constraints to stop deforestation

Source :

Science of Computer Programming [ 0167-6423 ] ; 1998.

RBID : ISTEX:2433FAE70BD0B56561C7128BF852DB4A81343F84

Abstract

Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but general techniques for higher-order programs were introduced only recently first by Hamilton and then by Marlow. We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis. We also relate our technique to previous approaches to termination of first- and higher-order deforestation in some detail.

Url:

https://api.istex.fr/document/2433FAE70BD0B56561C7128BF852DB4A81343F84/fulltext/pdf

DOI: 10.1016/S0167-6423(97)00031-2

Links to Exploration step

ISTEX:2433FAE70BD0B56561C7128BF852DB4A81343F84

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Constraints to stop deforestation</title>
<author><name sortKey="Seidl, H" sort="Seidl, H" uniqKey="Seidl H" first="H." last="Seidl">H. Seidl</name>
<affiliation><mods:affiliation>E-mail: seidl@uni-trier.de</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>FB IV - Informatik, Universität Trier, D-54286 Trier, Germany</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="S Rensen, M H" sort="S Rensen, M H" uniqKey="S Rensen M" first="M. H." last="S Rensen">M. H. S Rensen</name>
<affiliation><mods:affiliation>Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø Denmark</mods:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:2433FAE70BD0B56561C7128BF852DB4A81343F84</idno>
<date when="1998" year="1998">1998</date>
<idno type="doi">10.1016/S0167-6423(97)00031-2</idno>
<idno type="url">https://api.istex.fr/document/2433FAE70BD0B56561C7128BF852DB4A81343F84/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001228</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001228</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a">Constraints to stop deforestation</title>
<author><name sortKey="Seidl, H" sort="Seidl, H" uniqKey="Seidl H" first="H." last="Seidl">H. Seidl</name>
<affiliation><mods:affiliation>E-mail: seidl@uni-trier.de</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>FB IV - Informatik, Universität Trier, D-54286 Trier, Germany</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="S Rensen, M H" sort="S Rensen, M H" uniqKey="S Rensen M" first="M. H." last="S Rensen">M. H. S Rensen</name>
<affiliation><mods:affiliation>Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø Denmark</mods:affiliation>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Science of Computer Programming</title>
<title level="j" type="abbrev">SCICO</title>
<idno type="ISSN">0167-6423</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1998">1998</date>
<biblScope unit="volume">32</biblScope>
<biblScope unit="issue">1–3</biblScope>
<biblScope unit="page" from="73">73</biblScope>
<biblScope unit="page" to="107">107</biblScope>
</imprint>
<idno type="ISSN">0167-6423</idno>
</series>
<idno type="istex">2433FAE70BD0B56561C7128BF852DB4A81343F84</idno>
<idno type="DOI">10.1016/S0167-6423(97)00031-2</idno>
<idno type="PII">S0167-6423(97)00031-2</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0167-6423</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but general techniques for higher-order programs were introduced only recently first by Hamilton and then by Marlow. We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis. We also relate our technique to previous approaches to termination of first- and higher-order deforestation in some detail.</div>
</front>
</TEI>
<istex><corpusName>elsevier</corpusName>
<author><json:item><name>H. Seidl</name>
<affiliations><json:string>E-mail: seidl@uni-trier.de</json:string>
<json:string>FB IV - Informatik, Universität Trier, D-54286 Trier, Germany</json:string>
</affiliations>
</json:item>
<json:item><name>M.H. Sørensen</name>
<affiliations><json:string>Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø Denmark</json:string>
</affiliations>
</json:item>
</author>
<subject><json:item><lang><json:string>eng</json:string>
</lang>
<value>Deforestation</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Intermediate data structures</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Higher-order functional programs</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Termination detection</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Constraint-based program analysis</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Integer constraints</value>
</json:item>
</subject>
<language><json:string>eng</json:string>
</language>
<originalGenre><json:string>Full-length article</json:string>
</originalGenre>
<abstract>Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but general techniques for higher-order programs were introduced only recently first by Hamilton and then by Marlow. We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis. We also relate our technique to previous approaches to termination of first- and higher-order deforestation in some detail.</abstract>
<qualityIndicators><score>6.248</score>
<pdfVersion>1.2</pdfVersion>
<pdfPageSize>468 x 684 pts</pdfPageSize>
<refBibsNative>true</refBibsNative>
<keywordCount>6</keywordCount>
<abstractCharCount>784</abstractCharCount>
<pdfWordCount>12334</pdfWordCount>
<pdfCharCount>72843</pdfCharCount>
<pdfPageCount>35</pdfPageCount>
<abstractWordCount>104</abstractWordCount>
</qualityIndicators>
<title>Constraints to stop deforestation</title>
<pii><json:string>S0167-6423(97)00031-2</json:string>
</pii>
<refBibs><json:item><author><json:item><name>Z.M. Ariola</name>
</json:item>
<json:item><name>M. Felleisen</name>
</json:item>
<json:item><name>M. Maraist</name>
</json:item>
<json:item><name>J. Odersky</name>
</json:item>
<json:item><name>P. Wadler</name>
</json:item>
</author>
<host><pages><last>246</last>
<first>233</first>
</pages>
<author></author>
<title>Conf. Record of the Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages</title>
</host>
<title>A call-by-need lambda-calculus</title>
</json:item>
<json:item><author><json:item><name>H.P. Barendregt</name>
</json:item>
</author>
<host><author></author>
<title>Handbook of Logic in Computer Science</title>
</host>
<serie><author></author>
<title>Handbook of Logic in Computer Science</title>
</serie>
<title>Lambda calculi with types</title>
</json:item>
<json:item><author><json:item><name>R. Bird</name>
</json:item>
</author>
<host><volume>21</volume>
<pages><last>250</last>
<first>239</first>
</pages>
<author></author>
<title>Acta Inform.</title>
</host>
<title>Using circular programs to eliminate multiple traversals of data</title>
</json:item>
<json:item><author><json:item><name>A. Bondorf</name>
</json:item>
</author>
<host><author></author>
<title>DIKU-Rapport 90/17</title>
</host>
<serie><author></author>
<title>DIKU-Rapport 90/17</title>
</serie>
<title>Self-applicable partial evaluation</title>
</json:item>
<json:item><author><json:item><name>A. Bondorf</name>
</json:item>
</author>
<host><volume>17</volume>
<pages><last>34</last>
<first>3</first>
</pages>
<issue>1–3</issue>
<author></author>
<title>Science of Computer Programming</title>
</host>
<title>Automatic autoprojection of recursive equations</title>
</json:item>
<json:item><author><json:item><name>R.M. Burstall</name>
</json:item>
<json:item><name>J. Darlington</name>
</json:item>
</author>
<host><volume>24</volume>
<pages><last>67</last>
<first>44</first>
</pages>
<issue>1</issue>
<author></author>
<title>J. Assoc. Comput. Mach.</title>
</host>
<title>A transformation system for developing recursive programs</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
</author>
<host><author></author>
<title>Ph.D. Thesis</title>
</host>
<serie><author></author>
<title>Ph.D. Thesis</title>
</serie>
<title>Automatic methods for program transformation</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
</author>
<host><author></author>
<title>BIGRE</title>
</host>
<serie><author></author>
<title>Workshop on Static Analysis of Equational, Functional and Logic Programming Languages</title>
</serie>
<title>Generalising deforestation to all first-order functional programs</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
</author>
<host><author></author>
<title>Yale University Technical Report YALEU/DCS/RR-909</title>
</host>
<serie><author></author>
<title>Proc. ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation</title>
</serie>
<title>Fully lazy higher-order removal</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
</author>
<host><pages><last>20</last>
<first>11</first>
</pages>
<author></author>
<title>ACM Conf. on Lisp and Functional Programming</title>
</host>
<title>Safe fusion of functional expressions</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
</author>
<host><volume>4</volume>
<pages><last>555</last>
<first>515</first>
</pages>
<issue>4</issue>
<author></author>
<title>J. Funct. Programming</title>
</host>
<title>Safe fusion of functional expressions II: Further improvements</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
<json:item><name>J. Darlington</name>
</json:item>
</author>
<host><author></author>
<title>Australian Computer Science Conf., Vol. 14,1 of Australian CS Comm.</title>
</host>
<serie><author></author>
<title>Australian Computer Science Conf., Vol. 14,1 of Australian CS Comm.</title>
</serie>
<title>Higher-order removal transformation technique for functional programs</title>
</json:item>
<json:item><author><json:item><name>W.-N. Chin</name>
</json:item>
<json:item><name>S.-C. Khoo</name>
</json:item>
</author>
<host><author></author>
<title>Logics and Programs, Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Programming Languages: Implementations</title>
</serie>
<title>Better consumers for deforestation</title>
</json:item>
<json:item><author><json:item><name>J. Darlington</name>
</json:item>
</author>
<host><volume>16</volume>
<pages><last>46</last>
<first>1</first>
</pages>
<author></author>
<title>Artificial Intelligence</title>
</host>
<title>An experimental program transformation and synthesis system</title>
</json:item>
<json:item><author><json:item><name>M.S. Feather</name>
</json:item>
</author>
<host><volume>4</volume>
<pages><last>20</last>
<first>1</first>
</pages>
<issue>1</issue>
<author></author>
<title>ACM Trans. Programming Languages Systems</title>
</host>
<title>A system for assisting program transformation</title>
</json:item>
<json:item><author><json:item><name>L. Fegaras</name>
</json:item>
<json:item><name>T. Sheard</name>
</json:item>
<json:item><name>T. Zhou</name>
</json:item>
</author>
<host><author></author>
<title>Proc. ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation</title>
</host>
<title>Improving programs which recurse over multiple inductive structures</title>
</json:item>
<json:item><author><json:item><name>A. Ferguson</name>
</json:item>
<json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><pages><last>56</last>
<first>39</first>
</pages>
<author></author>
<title>Glasgow Workshop on Functional Programming</title>
</host>
<title>When will deforestation stop?</title>
</json:item>
<json:item><author><json:item><name>A.J. Gill</name>
</json:item>
</author>
<host><author></author>
<title>Ph.D. Thesis</title>
</host>
<serie><author></author>
<title>Ph.D. Thesis</title>
</serie>
<title>Cheap deforestation for non-strict functional languages</title>
</json:item>
<json:item><author><json:item><name>A.J. Gill</name>
</json:item>
<json:item><name>J. Launchbury</name>
</json:item>
<json:item><name>S.L.Peyton Jones</name>
</json:item>
</author>
<host><pages><last>232</last>
<first>223</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>A short cut to deforestation</title>
</json:item>
<json:item><author><json:item><name>A.J. Gill</name>
</json:item>
<json:item><name>S.L.Peyton Jones</name>
</json:item>
</author>
<host><pages><last>586</last>
<first>581</first>
</pages>
<author></author>
<title>IFIP</title>
</host>
<title>Cheap deforestation in practice: An optimiser for Haskell</title>
</json:item>
<json:item><author><json:item><name>G. Hamilton</name>
</json:item>
</author>
<host><author></author>
<title>Ph.D. Thesis</title>
</host>
<serie><author></author>
<title>Ph.D. Thesis</title>
</serie>
<title>Compile-time optimisations of storage usage in lazy functional programs</title>
</json:item>
<json:item><author><json:item><name>G. Hamilton</name>
</json:item>
</author>
<host><author></author>
<title>Technical Report TR 95-06</title>
</host>
<serie><author></author>
<title>Technical Report TR 95-06</title>
</serie>
<title>Extending first order deforestation</title>
</json:item>
<json:item><author><json:item><name>G. Hamilton</name>
</json:item>
</author>
<host><author></author>
<title>Technical Report TR 95-07</title>
</host>
<serie><author></author>
<title>Technical Report TR 95-07</title>
</serie>
<title>Higher order deforestation</title>
</json:item>
<json:item><author><json:item><name>G. Hamilton</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Programming Languages: Implementations, Logics and Programs</title>
</serie>
<title>Higher order deforestation</title>
</json:item>
<json:item><author><json:item><name>G. Hamilton</name>
</json:item>
<json:item><name>S.B. Jones</name>
</json:item>
</author>
<host><pages><last>145</last>
<first>134</first>
</pages>
<author></author>
<title>Glasgow Workshop on Functional Programming</title>
</host>
<title>Extending deforestation for first order functional programs</title>
</json:item>
<json:item><author><json:item><name>G. Hamilton</name>
</json:item>
<json:item><name>S.B. Jones</name>
</json:item>
</author>
<host><author></author>
<title>BIGRE</title>
</host>
<serie><author></author>
<title>Workshop on Static Analysis of Equational, Functional and Logic Programming Languages</title>
</serie>
<title>Transforming programs to eliminate intermediate structures</title>
</json:item>
<json:item><author><json:item><name>N. Heintze</name>
</json:item>
</author>
<host><pages><last>317</last>
<first>306</first>
</pages>
<author></author>
<title>ACM Conf. on Lisp and Functional Programming</title>
</host>
<title>Set-based analysis of ML programs</title>
</json:item>
<json:item><author><json:item><name>F. Henglein</name>
</json:item>
</author>
<host><volume>15</volume>
<pages><last>289</last>
<first>253</first>
</pages>
<issue>2</issue>
<author></author>
<title>ACM Trans. Programming Languages Systems</title>
</host>
<title>Type inference with polymorphic recursion</title>
</json:item>
<json:item><author><json:item><name>J.R. Hindley</name>
</json:item>
</author>
<host><volume>146</volume>
<pages><last>60</last>
<first>29</first>
</pages>
<author></author>
<title>Trans. Amer. Math. Soc.</title>
</host>
<title>The principal type scheme of an object in combinatory logic</title>
</json:item>
<json:item><author><json:item><name>C.K. Hoist</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</serie>
<title>Finiteness analysis</title>
</json:item>
<json:item><author><json:item><name>J. Hughes</name>
</json:item>
</author>
<host><author></author>
<title>Research Topics in Functional Programming</title>
</host>
<title>Why functional programming matters</title>
</json:item>
<json:item><author><json:item><name>R.B. Kierburtz</name>
</json:item>
<json:item><name>J. Schultis</name>
</json:item>
</author>
<host><pages><last>48</last>
<first>41</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>Transformations of FP program schemes</title>
</json:item>
<json:item><author><json:item><name>J. Launchbury</name>
</json:item>
<json:item><name>T. Sheard</name>
</json:item>
</author>
<host><pages><last>323</last>
<first>314</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>Warm fusion: Deriving build-catas from recursive definitions</title>
</json:item>
<json:item><author><json:item><name>M. Leuschel</name>
</json:item>
<json:item><name>B. Martens</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Partial Evaluation</title>
</serie>
<title>Global control for partial deduction through characteristic atoms and global trees</title>
</json:item>
<json:item><author><json:item><name>Z. Manna</name>
</json:item>
<json:item><name>R. Waldinger</name>
</json:item>
</author>
<host><volume>5</volume>
<pages><last>164</last>
<first>157</first>
</pages>
<issue>4</issue>
<author></author>
<title>IEEE Trans. Software Engng.</title>
</host>
<title>Synthesis: Dreams => programs</title>
</json:item>
<json:item><author><json:item><name>S. Marlow</name>
</json:item>
<json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><pages><last>165</last>
<first>154</first>
</pages>
<author></author>
<title>Glasgow Workshop on Functional Programming, Workshops in Computing</title>
</host>
<title>Deforestation for higher-order functions</title>
</json:item>
<json:item><author><json:item><name>S.D. Marlow</name>
</json:item>
</author>
<host><author></author>
<title>Ph.D. Thesis</title>
</host>
<serie><author></author>
<title>Ph.D. Thesis</title>
</serie>
<title>Deforestation for higher-order functional languages</title>
</json:item>
<json:item><author><json:item><name>R. Milner</name>
</json:item>
</author>
<host><volume>17</volume>
<pages><last>375</last>
<first>348</first>
</pages>
<author></author>
<title>J. Comput. System Sci.</title>
</host>
<title>A theory of type polymorphism in programming</title>
</json:item>
<json:item><author><json:item><name>A. Mycroft</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Proc. 6th Internat. Conf. on Programming</title>
</serie>
<title>Polymorphic type schemes and recursive definitions</title>
</json:item>
<json:item><author><json:item><name>K. Nielsen</name>
</json:item>
<json:item><name>M.H. Sorensen</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Static Analysis Symp.</title>
</serie>
<title>Call-by-name CPS-translation as a binding-time improvement</title>
</json:item>
<json:item><author><json:item><name>H.R. Nielson</name>
</json:item>
<json:item><name>F. Nielson</name>
</json:item>
</author>
<host><pages><last>345</last>
<first>332</first>
</pages>
<author></author>
<title>Conf. Record of the Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages</title>
</host>
<title>Infinitary control flow analysis: a collecting semantics for closure analysis</title>
</json:item>
<json:item><author><json:item><name>J. Palsberg</name>
</json:item>
</author>
<host><volume>17</volume>
<pages><last>82</last>
<first>47</first>
</pages>
<author></author>
<title>ACM Trans. Programming Languages Systems</title>
</host>
<title>Closure analysis in constraint form</title>
</json:item>
<json:item><author><json:item><name>J. Palsberg</name>
</json:item>
<json:item><name>P. O'Keefe</name>
</json:item>
</author>
<host><volume>17</volume>
<pages><last>599</last>
<first>576</first>
</pages>
<author></author>
<title>ACM Trans. Programming Languages Systems</title>
</host>
<title>A type system equivalent to flow analysis</title>
</json:item>
<json:item><author><json:item><name>D. Sands</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Theory and Practice of Software Development</title>
</serie>
<title>Proving the correctness of recursion-based automatic program transformation</title>
</json:item>
<json:item><author><json:item><name>D. Sands</name>
</json:item>
</author>
<host><pages><last>232</last>
<first>221</first>
</pages>
<author></author>
<title>Conf. Record of the Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages</title>
</host>
<title>Total correctness by local improvement in program transformation</title>
</json:item>
<json:item><author><json:item><name>D. Sands</name>
</json:item>
</author>
<host><volume>167</volume>
<author></author>
<title>Theoret. Comput. Sci. A</title>
</host>
<title>Proving the correctness of recursion-based automatic program transformations</title>
</json:item>
<json:item><author><json:item><name>D. Sands</name>
</json:item>
</author>
<host><volume>18</volume>
<issue>2</issue>
<author></author>
<title>ACM Trans. Programming Languages Systems</title>
</host>
<title>Total correctness by local improvement in the transformation of functional programs</title>
</json:item>
<json:item><author><json:item><name>W.L. Scherlis</name>
</json:item>
</author>
<host><pages><last>49</last>
<first>41</first>
</pages>
<author></author>
<title>Conf. Record of the Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages</title>
</host>
<title>Program improvement by internal specialization</title>
</json:item>
<json:item><author><json:item><name>H. Seidl</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Internat. Coll. on Automata, Languages, and Programming</title>
</serie>
<title>Least solutions of equations over N</title>
</json:item>
<json:item><author><json:item><name>H. Seidl</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>European Symp. on Programming</title>
</serie>
<title>Integer constraints to stop deforestation</title>
</json:item>
<json:item><author><json:item><name>H. Seidl</name>
</json:item>
</author>
<host><volume>3</volume>
<pages><last>62</last>
<first>41</first>
</pages>
<author></author>
<title>Nordic J. Comput.</title>
</host>
<title>Least and greatest solutions of equations over N</title>
</json:item>
<json:item><author><json:item><name>H. Seidl</name>
</json:item>
<json:item><name>M.H. Sorensen</name>
</json:item>
</author>
<host><pages><last>413</last>
<first>400</first>
</pages>
<author></author>
<title>Conf. Record of the Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages</title>
</host>
<title>Constraints to stop higher-order deforestation</title>
</json:item>
<json:item><author><json:item><name>P. Sestoft</name>
</json:item>
</author>
<host><pages><last>506</last>
<first>485</first>
</pages>
<author></author>
<title>Partial Evaluation and Mixed Computation</title>
</host>
<title>Automatic call unfolding in a partial evaluator</title>
</json:item>
<json:item><author><json:item><name>P. Sestoft</name>
</json:item>
</author>
<host><pages><last>53</last>
<first>29</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>Replacing function parameters by global variables</title>
</json:item>
<json:item><author><json:item><name>T. Sheard</name>
</json:item>
<json:item><name>L. Fegaras</name>
</json:item>
</author>
<host><pages><last>242</last>
<first>233</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>A fold for all seasons</title>
</json:item>
<json:item><author><json:item><name>T. Sheard</name>
</json:item>
<json:item><name>L. Fegaras</name>
</json:item>
</author>
<host><author></author>
<title>Technical Report 94-004</title>
</host>
<serie><author></author>
<title>Technical Report 94-004</title>
</serie>
<title>Optimizing algebraic programs</title>
</json:item>
<json:item><author><json:item><name>O. Shivers</name>
</json:item>
</author>
<host><pages><last>128</last>
<first>114</first>
</pages>
<author></author>
<title>Programming Languages: Design and Implementation</title>
</host>
<title>Control-flow analysis in scheme</title>
</json:item>
<json:item><author><json:item><name>O. Shivers</name>
</json:item>
</author>
<host><author></author>
<title>Ph.D. Thesis</title>
</host>
<serie><author></author>
<title>Ph.D. Thesis</title>
</serie>
<title>Control-flow analysis of higher-order languages</title>
</json:item>
<json:item><author><json:item><name>M.H. Sørensen</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Coll. on Trees in Algebra and Programming</title>
</serie>
<title>A grammar-based data-flow analysis to stop deforestation</title>
</json:item>
<json:item><author><json:item><name>M.H. Sorensen</name>
</json:item>
<json:item><name>R. Glück</name>
</json:item>
</author>
<host><pages><last>479</last>
<first>465</first>
</pages>
<author></author>
<title>Logic Programming: Proceedings of the 1995 Internat. Symp.</title>
</host>
<title>An algorithm of generalization in positive supercompilation</title>
</json:item>
<json:item><author><json:item><name>A. Takano</name>
</json:item>
<json:item><name>E. Meijer</name>
</json:item>
</author>
<host><pages><last>313</last>
<first>306</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>Shortcut deforestation in calculational form</title>
</json:item>
<json:item><author><json:item><name>V.F. Turchin</name>
</json:item>
<json:item><name>R. Nirenberg</name>
</json:item>
<json:item><name>D. Turchin</name>
</json:item>
</author>
<host><pages><last>55</last>
<first>47</first>
</pages>
<author></author>
<title>ACM Conf. on Lisp and Functional Programming</title>
</host>
<title>Experiments with a supercompiler</title>
</json:item>
<json:item><author><json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><pages><last>32</last>
<first>25</first>
</pages>
<author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>Applicative style programming, program transformation, and list operators</title>
</json:item>
<json:item><author><json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><pages><last>305</last>
<first>282</first>
</pages>
<author></author>
<title>ACM Conf. on Lisp and Functional Programming</title>
</host>
<title>Listlessness is better than laziness</title>
</json:item>
<json:item><author><json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>Workshop on Programs as Data Objects</title>
</serie>
<title>Listlessness is better than lazyness II: Composing listless functions</title>
</json:item>
<json:item><author><json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><author></author>
<title>Lecture Notes in Computer Science</title>
</host>
<serie><author></author>
<title>European Symp. on Programming</title>
</serie>
<title>Deforestation: transforming programs to eliminate trees</title>
</json:item>
<json:item><author><json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><author></author>
<title>Conf. on Functional Programming and Computer Architecture</title>
</host>
<title>Theorems for free!</title>
</json:item>
<json:item><author><json:item><name>P.L. Wadler</name>
</json:item>
</author>
<host><volume>73</volume>
<pages><last>248</last>
<first>231</first>
</pages>
<author></author>
<title>Theoret. Comput. Sci.</title>
</host>
<title>Deforestation: transforming programs to eliminate intermediate trees</title>
</json:item>
</refBibs>
<genre><json:string>research-article</json:string>
</genre>
<serie><volume>Vol. 11</volume>
<pages><last>309</last>
<first>117</first>
</pages>
<language><json:string>unknown</json:string>
</language>
<title>Handbook of Logic in Computer Science</title>
</serie>
<host><volume>32</volume>
<pii><json:string>S0167-6423(00)X0018-4</json:string>
</pii>
<pages><last>107</last>
<first>73</first>
</pages>
<issn><json:string>0167-6423</json:string>
</issn>
<issue>1–3</issue>
<genre><json:string>journal</json:string>
</genre>
<language><json:string>unknown</json:string>
</language>
<title>Science of Computer Programming</title>
<publicationDate>1998</publicationDate>
</host>
<categories><wos><json:string>science</json:string>
<json:string>computer science, software engineering</json:string>
</wos>
<scienceMetrix><json:string>applied sciences</json:string>
<json:string>information & communication technologies</json:string>
<json:string>software engineering</json:string>
</scienceMetrix>
</categories>
<publicationDate>1998</publicationDate>
<copyrightDate>1998</copyrightDate>
<doi><json:string>10.1016/S0167-6423(97)00031-2</json:string>
</doi>
<id>2433FAE70BD0B56561C7128BF852DB4A81343F84</id>
<score>0.60968417</score>
<fulltext><json:item><extension>pdf</extension>
<original>true</original>
<mimetype>application/pdf</mimetype>
<uri>https://api.istex.fr/document/2433FAE70BD0B56561C7128BF852DB4A81343F84/fulltext/pdf</uri>
</json:item>
<json:item><extension>zip</extension>
<original>false</original>
<mimetype>application/zip</mimetype>
<uri>https://api.istex.fr/document/2433FAE70BD0B56561C7128BF852DB4A81343F84/fulltext/zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/document/2433FAE70BD0B56561C7128BF852DB4A81343F84/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Constraints to stop deforestation</title>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<publisher>ELSEVIER</publisher>
<availability><p>ELSEVIER</p>
</availability>
<date>1998</date>
</publicationStmt>
<sourceDesc><biblStruct type="inbook"><analytic><title level="a">Constraints to stop deforestation</title>
<author xml:id="author-1"><persName><forename type="first">H.</forename>
<surname>Seidl</surname>
</persName>
<email>seidl@uni-trier.de</email>
<note type="correspondence"><p>Corresponding author.</p>
</note>
<affiliation>FB IV - Informatik, Universität Trier, D-54286 Trier, Germany</affiliation>
</author>
<author xml:id="author-2"><persName><forename type="first">M.H.</forename>
<surname>Sørensen</surname>
</persName>
<affiliation>Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø Denmark</affiliation>
</author>
</analytic>
<monogr><title level="j">Science of Computer Programming</title>
<title level="j" type="abbrev">SCICO</title>
<idno type="pISSN">0167-6423</idno>
<idno type="PII">S0167-6423(00)X0018-4</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1998"></date>
<biblScope unit="volume">32</biblScope>
<biblScope unit="issue">1–3</biblScope>
<biblScope unit="page" from="73">73</biblScope>
<biblScope unit="page" to="107">107</biblScope>
</imprint>
</monogr>
<idno type="istex">2433FAE70BD0B56561C7128BF852DB4A81343F84</idno>
<idno type="DOI">10.1016/S0167-6423(97)00031-2</idno>
<idno type="PII">S0167-6423(97)00031-2</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><creation><date>1998</date>
</creation>
<langUsage><language ident="en">en</language>
</langUsage>
<abstract xml:lang="en"><p>Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but general techniques for higher-order programs were introduced only recently first by Hamilton and then by Marlow. We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis. We also relate our technique to previous approaches to termination of first- and higher-order deforestation in some detail.</p>
</abstract>
<textClass><keywords scheme="keyword"><list><head>Keywords</head>
<item><term>Deforestation</term>
</item>
<item><term>Intermediate data structures</term>
</item>
<item><term>Higher-order functional programs</term>
</item>
<item><term>Termination detection</term>
</item>
<item><term>Constraint-based program analysis</term>
</item>
<item><term>Integer constraints</term>
</item>
</list>
</keywords>
</textClass>
</profileDesc>
<revisionDesc><change when="1998">Published</change>
</revisionDesc>
</teiHeader>
</istex:fulltextTEI>
<json:item><extension>txt</extension>
<original>false</original>
<mimetype>text/plain</mimetype>
<uri>https://api.istex.fr/document/2433FAE70BD0B56561C7128BF852DB4A81343F84/fulltext/txt</uri>
</json:item>
</fulltext>
<metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration>
<istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType>
<istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>SCICO</jid>
<aid>97000312</aid>
<ce:pii>S0167-6423(97)00031-2</ce:pii>
<ce:doi>10.1016/S0167-6423(97)00031-2</ce:doi>
<ce:copyright type="unknown" year="1998"></ce:copyright>
</item-info>
<head><ce:title>Constraints to stop deforestation</ce:title>
<ce:author-group><ce:author><ce:given-name>H.</ce:given-name>
<ce:surname>Seidl</ce:surname>
<ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup>
</ce:cross-ref>
<ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup>
</ce:cross-ref>
<ce:e-address>seidl@uni-trier.de</ce:e-address>
</ce:author>
<ce:author><ce:given-name>M.H.</ce:given-name>
<ce:surname>Sørensen</ce:surname>
<ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup>
</ce:cross-ref>
</ce:author>
<ce:affiliation id="AFF1"><ce:label>a</ce:label>
<ce:textfn>FB IV - Informatik, Universität Trier, D-54286 Trier, Germany</ce:textfn>
</ce:affiliation>
<ce:affiliation id="AFF2"><ce:label>b</ce:label>
<ce:textfn>Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø Denmark</ce:textfn>
</ce:affiliation>
<ce:correspondence id="COR1"><ce:label>∗</ce:label>
<ce:text>Corresponding author.</ce:text>
</ce:correspondence>
</ce:author-group>
<ce:abstract><ce:section-title>Abstract</ce:section-title>
<ce:abstract-sec><ce:simple-para>Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but general techniques for higher-order programs were introduced only recently first by Hamilton and then by Marlow.</ce:simple-para>
<ce:simple-para>We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis.</ce:simple-para>
<ce:simple-para>We also relate our technique to previous approaches to termination of first- and higher-order deforestation in some detail.</ce:simple-para>
</ce:abstract-sec>
</ce:abstract>
<ce:keywords><ce:section-title>Keywords</ce:section-title>
<ce:keyword><ce:text>Deforestation</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Intermediate data structures</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Higher-order functional programs</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Termination detection</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Constraint-based program analysis</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Integer constraints</ce:text>
</ce:keyword>
</ce:keywords>
</head>
</converted-article>
</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo><title>Constraints to stop deforestation</title>
</titleInfo>
<titleInfo type="alternative" contentType="CDATA"><title>Constraints to stop deforestation</title>
</titleInfo>
<name type="personal"><namePart type="given">H.</namePart>
<namePart type="family">Seidl</namePart>
<affiliation>E-mail: seidl@uni-trier.de</affiliation>
<affiliation>FB IV - Informatik, Universität Trier, D-54286 Trier, Germany</affiliation>
<description>Corresponding author.</description>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<name type="personal"><namePart type="given">M.H.</namePart>
<namePart type="family">Sørensen</namePart>
<affiliation>Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø Denmark</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre type="research-article" displayLabel="Full-length article"></genre>
<originInfo><publisher>ELSEVIER</publisher>
<dateIssued encoding="w3cdtf">1998</dateIssued>
<copyrightDate encoding="w3cdtf">1998</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="iso639-2b">eng</languageTerm>
<languageTerm type="code" authority="rfc3066">en</languageTerm>
</language>
<physicalDescription><internetMediaType>text/html</internetMediaType>
</physicalDescription>
<abstract lang="en">Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but general techniques for higher-order programs were introduced only recently first by Hamilton and then by Marlow. We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis. We also relate our technique to previous approaches to termination of first- and higher-order deforestation in some detail.</abstract>
<subject><genre>Keywords</genre>
<topic>Deforestation</topic>
<topic>Intermediate data structures</topic>
<topic>Higher-order functional programs</topic>
<topic>Termination detection</topic>
<topic>Constraint-based program analysis</topic>
<topic>Integer constraints</topic>
</subject>
<relatedItem type="host"><titleInfo><title>Science of Computer Programming</title>
</titleInfo>
<titleInfo type="abbreviated"><title>SCICO</title>
</titleInfo>
<genre type="journal">journal</genre>
<originInfo><dateIssued encoding="w3cdtf">199809</dateIssued>
</originInfo>
<identifier type="ISSN">0167-6423</identifier>
<identifier type="PII">S0167-6423(00)X0018-4</identifier>
<part><date>199809</date>
<detail type="issue"><title>6th European Symposium on Programming</title>
</detail>
<detail type="volume"><number>32</number>
<caption>vol.</caption>
</detail>
<detail type="issue"><number>1–3</number>
<caption>no.</caption>
</detail>
<extent unit="issue pages"><start>1</start>
<end>221</end>
</extent>
<extent unit="pages"><start>73</start>
<end>107</end>
</extent>
</part>
</relatedItem>
<identifier type="istex">2433FAE70BD0B56561C7128BF852DB4A81343F84</identifier>
<identifier type="DOI">10.1016/S0167-6423(97)00031-2</identifier>
<identifier type="PII">S0167-6423(97)00031-2</identifier>
<recordInfo><recordContentSource>ELSEVIER</recordContentSource>
</recordInfo>
</mods>
</metadata>
</istex>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001228 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001228 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Istex
   |étape=   Corpus
   |type=    RBID
   |clé=     ISTEX:2433FAE70BD0B56561C7128BF852DB4A81343F84
   |texte=   Constraints to stop deforestation
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

Constraints to stop deforestation

Constraints to stop deforestation

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri