@inproceedings{Ager:2002:OnObtaining, author = {M.S. Ager and O. Danvy and H.K. Rohde}, title = {On obtaining {K}nuth, {M}orris, and {P}ratt's string matcher by partial evaluation}, booktitle = {ASIA-PEPM '02: Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation}, year = {2002}, isbn = {1-58113-458-4}, pages = {32--46}, location = {Aizu, Japan}, doi = {http://doi.acm.org/10.1145/568173.568177}, publisher = {ACM Press}, address = {New York, NY, USA}, } @Article{Ager:2003:Fast, author = {M.S. Ager and O. Danvy and H.K. Rohde}, title = {Fast partial evaluation of pattern matching in strings}, journal = {SIGPLAN Not.}, volume = {38}, number = {10}, year = {2003}, issn = {0362-1340}, pages = {3--9}, doi = {http://doi.acm.org/10.1145/966049.777390}, publisher = {ACM Press}, address = {New York, NY, USA}, } @Article{Albert:2001:The, title = "The Narrowing-driven Approach to Functional Logic Program Specialization", author = "E. Albert and G. Vidal", journal = "New Generation Comput", year = "2001", number = "1", volume = "20", bibdate = "2003-12-02", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/ngc/ngc20.html#AlbertV01", pages = "3--26", } @InProceedings{Alimarine:2005:Improved, title = "Improved Fusion for Optimizing Generics", author = "A. Alimarine and S. Smetsers", booktitle = "Practical Aspects of Declarative Languages, 7th International Symposium, {PADL} 2005, Long Beach, {CA}, {USA}, January 10-11, 2005, Proceedings", publisher = "Springer", year = "2005", volume = "3350", editor = "Manuel V. Hermenegildo and Daniel Cabeza", ISBN = "3-540-24362-3", pages = "203--218", series = "Lecture Notes in Computer Science", } @article{Alpuente:1998:Partial, author = "M. Alpuente and M. Falaschi and G. Vidal", title = "{P}artial {E}valuation of {F}unctional {L}ogic {P}rograms", journal = "ACM Transactions on Programming Languages and Systems", publisher = "ACM Press", address = "New York", volume = 20, number = 4, year = 1998, pages = "768-844"} @InProceedings{Augustsson:1985:Compiling, title = "Compiling Pattern Matching", author = "L. Augustsson", year = "1985", bibdate = "2002-12-17", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/fpca/fpca85.html#Augustsson85", booktitle = "FPCA", pages = "368--381", } @InProceedings{Bolingbroke:2010:Supercompilation, title={{Supercompilation by evaluation}}, author={Bolingbroke, M. and {Peyton Jones}, S. L.}, booktitle={Proceedings of the third ACM Haskell symposium on Haskell}, pages={135--146}, year={2010}, organization={ACM} } @Article{Carlsson:2003:Semantic, abstract = {We present a three-layered semantics of Timber, a language designed for programming real-time systems in a reactive, object-oriented style. The innermost layer amounts to a traditional deterministic, pure, functional language, around which we formulate a middle layer of concurrent objects, in terms of a monadic transition semantics. The outermost layer, where the language is married to deadline-driven scheduling theory, is where we define message ordering and CPU allocation to actions. Our main contributions are a formalized notion of a time-constrained reaction, and a demonstration of how scheduling theory, process calculii, and the lambda calculus can be jointly applied to obtain a direct and succinct semantics of a complex, real-world programming language with well-defined real-time behavior.}, author = {Carlsson, M. and Nordlander, J. and Kieburtz, D. }, citeulike-article-id = {266390}, journal = {Lecture Notes in Computer Science}, keywords = {functionalprogramming timber}, month = {January}, pages = {339--356}, priority = {0}, title = {The Semantic Layers of {T}imber}, volume = {2895}, year = {2003} } @inproceedings{Cheadle:2004:Exploring, author = {A. M. Cheadle and A. J. Field and S. Marlow and S. L. Peyton Jones and R. L. While}, title = {Exploring the barrier to entry: incremental generational garbage collection for Haskell}, booktitle = {ISMM '04: Proceedings of the 4th international symposium on Memory management}, year = {2004}, pages = {163--174}, location = {Vancouver, BC, Canada}, publisher = {ACM Press}, address = {New York, NY, USA}, isbn = {1-58113-945-4}, } @Article{Chin:1994:Safe, title = "Safe Fusion of Functional Expressions {II}: Further Improvements", author = "W-N. Chin", journal = "J. Funct. Program", year = "1994", number = "4", volume = "4", bibdate = "2004-03-19", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/jfp/jfp4.html#Chin94", pages = "515--555", } @PhdThesis{Chitil:2000:Type, month = oct, year = "2000", pages = "157", title = "Type-Inference Based Deforestation of Functional Programs", author = "O. Chitil", keywords = "compiler optimisation, program analysis", publication_type = "phdthesis", submission_id = "16294_1077223574", school = "RWTH Aachen", } @InProceedings{Damas:1982:Principal, author = "L. Damas and R. Milner", title = "Principal Type-Schemes for Functional Prograias", pages = "207--212", ISBN = "0-89791-065-6", editor = "Richard DeMillo", booktitle = "Conference Record of the 9th Annual {ACM} Symposium on Principles of Programming Languages", address = "Albuquerque, NM", month = jan, year = "1982", publisher = "ACM Press", } @inproceedings{Danvy:2001:Defunctionalization, author = {O. Danvy and L. R. Nielsen}, title = {Defunctionalization at work}, booktitle = {PPDP '01: Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming}, year = {2001}, isbn = {1-58113-388-X}, pages = {162--174}, location = {Florence, Italy}, publisher = {ACM Press}, address = {New York, NY, USA}, } @inproceedings{Debois:2004:Imperative, author = {S. Debois}, title = {Imperative program optimization by partial evaluation}, booktitle = {PEPM '04: Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation}, year = {2004}, isbn = {1-58113-835-0}, pages = {113--122}, location = {Verona, Italy}, doi = {http://doi.acm.org/10.1145/1014007.1014019}, publisher = {ACM Press}, address = {New York, NY, USA}, } @Article{Dershowitz:1982:Orderings, author = "N. Dershowitz", title = "Orderings for Term-Rewriting Systems", journal = "Theoretical Computer Science", volume = "17", number = "3", year = "1982", keywords = "functional termination simplification orderings Boolean logic", } @Article{Dershowitz:1987:Termination, author = "N. Dershowitz", journal = "Journal of Symbolic Computation", key = "Ders87", keyword = "Rewrite Methods", number = "1", pages = "69--115", title = "Termination of rewriting", volume = "3", year = "1987", } @Article{Futamura:1999:PECa, author = "Y. Futamura", title = "Partial Evaluation of Computation Process, Revisited", journal = "Higher-Order and Symbolic Computation", volume = "12", number = "4", pages = "377--380", month = dec, year = "1999", CODEN = "LSCOEX", doi = "http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1023/A:1010043619517", ISSN = "1388-3690 (print), 1573-0557 (electronic)", bibdate = "Wed Jul 6 15:50:30 MDT 2005", acknowledgement = ack-nhfb, doi-url = "http://dx.doi.org/openurl.asp?genre=article&id=doi:10.1023/A:1010043619517", } @article{Futamura:2002:Program, author = {Y. Futamura and Z. Konishi and R. Gl{\"u}ck}, title = {Program transformation system based on generalized partial computation }, journal = {New Gen. Comput.}, volume = {20}, number = {1}, year = {2002}, issn = {0288-3635}, pages = {75--99}, publisher = {Ohmsha}, address = {Tokyo, Japan, Japan}, } @InProceedings{Ghani:2008:Short, author = {N. Ghani and P. Johann}, title = {Short Cut Fusion of Recursive Programs with Computational Effects}, year = {2008}, booktitle = "{Draft Proceedings of The Ninth Symposium on Trends in Functional Programming (TFP)}", editor = "{Achten}, P. and {Koopman}, P. and {Moraz{\'a}n}, M. T.", number = "ICIS--R08007", institution = "Radboud University Nijmegen", } @url{GHC, Key = "GHC 2008", Title = "Glasgow {H}askell {C}ompiler", URL = "http://www.haskell.org/ghc/", year = "2008", month = "May", added-at = "Thu Nov 22 21:41:42 2007", } @PhdThesis{Gill:1996:Cheap, author = "A. J. Gill", title = "Cheap Deforestation for Non-strict Functional Languages", school = "Univ.\ of Glasgow", month = jan, year = "1996", } @Misc{Glenstrup:2003:Termination, title = "Termination Analysis and Specialization-Point Insertion in Off-line Partial Evaluation", author = "A.J. Glenstrup and N.D. Jones", year = "2003", month = jun # "~25", abstract = "interpretation or constraint solving analyses may be used to detect both modalities of size-change behavior, and can be found in the literature [Chin and Khoo 2002; Hughes et al. 1996]. We develop analyses for the current context in Section 5, in the style of Jones et al. [1993, Section 14.3]. A simple extension of the size-change graph formalism uses two-layered sizechange graphs G = (G ) where (as before) G approximates must-decrease properties on which the size-change approach is based, and G safely approximates may-increase size relations by arcs x ! y. An example: the double program seen before has two-layered size-change graphs: call f(e 1 ,...,en): 9 eval(lkbody(f,pg), append(lkparm(f,pg),ns),...) ACM Transactions on Programming Languages and Systems, Vol. ?, No. ?, January 2003. > > > > > < > > > > > 1 : v x u > > > > > < > > > > > 2 : v {"} v u # u May-increase Must-decrease 4.6 Constraints on binding-time analysis The purpose of binding-time analysis is safely to annotate a program. The central task is to nd a so-called division : ParameterNames ! fS; D; ?g that classies every function parameter as static, dynamic, or as yet undecided. The desired division should have no ?-values and be as static as possible while ensuring that specialization will terminate in all cases. To this end dene w to hold i (x) 6= ? implies (x) = (x) for all parameters x.", language = "en", oai = "oai:CiteSeerPSU:695290", rights = "unrestricted", subject = "Termination Analysis and Specialization-Point Insertion in Off-line Partial Evaluation", URL = "http://citeseer.ist.psu.edu/695290.html; ftp://ftp.diku.dk/diku/semantics/papers/D-498.ps", } @Article{Grobauer:2001:Partial, author = {B. Grobauer and J.L. Lawall}, title = {Partial evaluation of pattern matching in strings, revisited}, journal = {Nordic J. of Computing}, volume = {8}, number = {4}, year = {2001}, issn = {1236-6064}, pages = {437--462}, publisher = {Publishing Association Nordic Journal of Computing}, address = {, Finland}, } @PhdThesis{Hamilton:1993:Compile, author = "G. W. Hamilton", title = "Compile-Time Optimisation of Store Usage in Lazy Funtional Programs", school = "University of Stirling", year = "1993", } @inproceedings{Hamilton:1995:Higher, author = {G. W. Hamilton}, title = {Higher Order Deforestation}, booktitle = {PLILP '96: Proceedings of the 8th International Symposium on Programming Languages: Implementations, Logics, and Programs}, year = {1996}, isbn = {3-540-61756-6}, pages = {213--227}, publisher = {Springer-Verlag}, address = {London, UK}, } @Article{Hamilton:2006:Higher, title = "Higher Order Deforestation", author = "G. W. Hamilton", journal = "Fundam. Informaticae", year = "2006", number = "1-2", volume = "69", bibdate = "2006-03-31", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/fuin/fuin69.html#Hamilton06", pages = "39--61", } @Article{Helsen:2004:Polymorphic, author = {S. Helsen and P. Thiemann}, title = {Polymorphic specialization for ML}, journal = {ACM Trans. Program. Lang. Syst.}, volume = {26}, number = {4}, year = {2004}, issn = {0164-0925}, pages = {652--701}, doi = {http://doi.acm.org/10.1145/1011508.1011510}, publisher = {ACM Press}, address = {New York, NY, USA}, } @phdthesis{Hinze:2000:Generic, title={{Generic Programs and Proofs}}, author={Hinze, R.}, year = "2000", school={Habilitationsschrift, Bonn University} } @Misc{Hudak:1999:Gentle, author = "P. Hudak and J. Peterson and J. Fasel", title = "A Gentle Introduction To {Haskell 98}", added-by = "sti", URL = "http://www.haskell.org/tutorial/haskell-98-tutorial.pdf", howpublished = "\url{http://www.haskell.org/tutorial/}", year = "1999", month = oct, added-at = "Mon Apr 3 12:04:44 2000", } @article{Huet:1997:Zipper, title={{The zipper}}, author={Huet, G.}, journal={Journal of Functional Programming}, volume={7}, number={05}, pages={549--554}, year={1997}, publisher={Cambridge Univ Press} } @Article{Hughes:1989:Why, author = "J. Hughes", title = "Why Functional Programming Matters", journal = "Computer Journal", volume = "32", number = "2", pages = "98--107", year = "1989", } @inproceedings{Hughes:1996:Introduction, author={J. Hughes}, title={{An Introduction to Program Specialisation by Type Inference}}, booktitle={{Functional Programming}}, publisher={Glasgow University}, year={1996}, month={July}, note={published electronically} } @Article{Hughes:1998:Type, author = {J. Hughes}, title = {Type specialization}, journal = {ACM Comput. Surv.}, volume = {30}, number = {3es}, year = {1998}, issn = {0360-0300}, pages = {14}, doi = {http://doi.acm.org/10.1145/289121.289135}, publisher = {ACM Press}, address = {New York, NY, USA}, } @Article{Hutton:1999:Tutorial, author = "G. Hutton", title = "A Tutorial on the Universality and Expressiveness of Fold", journal = "Journal of Functional Programming", volume = "9", number = "4", pages = "355--372", year = "1999", } @InProceedings{Johnsson:1985:Lambda, title = "Lambda Lifting: Transforming Programs to Recursive Equations", author = "T. Johnsson", year = "1985", bibdate = "2002-12-17", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/fpca/fpca85.html#Johnsson85", booktitle = "FPCA", pages = "190--203", } @Article{Jones:1996:Introduction, author = {N.D. Jones}, title = {An introduction to partial evaluation}, journal = {ACM Comput. Surv.}, volume = {28}, number = {3}, year = {1996}, issn = {0360-0300}, pages = {480--503}, doi = {http://doi.acm.org/10.1145/243439.243447}, publisher = {ACM Press}, address = {New York, NY, USA}, } @InProceedings{Jones:1988:ChallengingProblems, author = "N.D. Jones", title = "Challenging Problems in Partial Evaluation and Mixed Computation", booktitle = "Partial Evaluation and Mixed Computation", year = "1988", semno = "D-26", editor = "D. Bj{\o}rner and A. P. Ershov and N. D. Jones", pages = "1--14", organization = "IFIP World Congress Proceedings", publisher = "Elsevier Science Publishers B.V.", address = "North-Holland", summary = "After a discussion of the state of the art in this field, a list of challenging problems for future research is presented.", keywords = "partial evaluation, mixed computation, program specialization", } @Article{Jones:2002:Program, author = "N.D. Jones and A.J. Glenstrup", title = "Program Generation, Termination, and Binding-Time Analysis", journal = "Lecture Notes in Computer Science", volume = "2487", pages = "1--31", year = "2002", CODEN = "LNCSD9", ISSN = "0302-9743", bibdate = "Sat Nov 30 20:57:39 MST 2002", URL = "http://link.springer.de/link/service/series/0558/bibs/2487/24870001.htm; http://link.springer.de/link/service/series/0558/papers/2487/24870001.pdf", acknowledgement = ack-nhfb, } @Article{Jones:2004:Transformation, author = {N.D. Jones}, title = {Transformation by interpreter specialisation}, journal = {Sci. Comput. Program.}, volume = {52}, number = {1-3}, year = {2004}, issn = {0167-6423}, pages = {307--339}, doi = {http://dx.doi.org/10.1016/j.scico.2004.03.010}, publisher = {Elsevier North-Holland, Inc.}, address = {Amsterdam, The Netherlands, The Netherlands}, } @inproceedings{Jones:2001:Playing, title = "Playing by the Rules: Rewriting as a practical optimisation technique in {GHC}", author = "S. L. {Peyton Jones} and A. Tolmach and T. Hoare", year = "2001", month = sep # "~28", crossref = "hinzehw", } @Article{Jones:2002:Secrets, title = "Secrets of the Glasgow Haskell Compiler inliner", author = "S. L. {Peyton Jones} and S. Marlow", journal = "J. Funct. Program", year = "2002", number = "4\&5", volume = "12", bibdate = "2004-03-19", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/jfp/jfp12.html#JonesM02", pages = "393--433", } @book{Jones:2003:Haskell, editor = {S.L. Peyton Jones}, title = {Haskell 98 Language and Libraries}, publisher = {Cambridge University Press}, year = {2003} } @misc{Jonsson:2007:Positive, title = "Positive Supercompilation for a Higher-Order Call-By-Value Language", author = "P. A. Jonsson and J. Nordlander", note = "Submitted to IFL'07", year = "2007", } @MastersThesis{Jonsson:2008:Positive, author = "P. A. Jonsson", title = "Positive Supercompilation for a Higher-Order Call-By-Value Language", school = "Lule{\aa} University of Technology", year = "2008", address = "Sweden", month = "Jun", type = "Licentiate Thesis", } @TechReport{Jonsson:2008:PositiveE, author = "P. A. Jonsson and J. Nordlander", year = "2008", title = "Positive {S}upercompilation for a {H}igher {O}rder {C}all-{B}y-{V}alue {L}anguage: {E}xtended {P}roofs", institution = "Department of Computer science and Electrical engineering, Lule{\aa} University of Technology", number = "2008:17", month = "October", issn = "1402-1528", } @url{Jonsson:2008:Extended, author = "P. A. Jonsson and J. Nordlander", Title = "Positive Supercompilation: Extended proofs", URL = "http://www.csee.ltu.se/~pj/papers/scp/", year = "2008", month = "Jul", added-at = "Tue Jun 17 00:58:23 2008", } @inproceedings{Jonsson:2009:Positive, author = {P. A. Jonsson and J. Nordlander}, title = {Positive Supercompilation for a higher-order call-by-value language}, booktitle = {POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, year = {2009}, } @conference{Jonsson:2010:Strengthening, title={{Strengthening Supercompilation for Call-By-Value Languages}}, author={Jonsson, P. A. and Nordlander, J}, pages={64--81}, booktitle={Second International Workshop on Metacomputation in Russia}, year={2010} } @InCollection{Klop:1992:Term, author = "J. W. Klop", title = "Term Rewriting Systems", booktitle = "Handbook of Logic in Computer Science", year = "1992", publisher = "Oxford University Press", editor = "S. Abramski and D. Gabbay and T. Maibaum", } @inproceedings{Klyuchnikov:2009:Proving, author = {I. Klyuchnikov and S. Romanenko}, title = {Proving the Equivalence of Higher-Order Terms by Means of Supercompilation}, booktitle = {PSI '09: Proceedings of the Seventh International Andrei Ershov Memorial Conference}, year = {2009}, location = {Novosibirsk, Akademgorodok, Russia} } @conference{Klyuchnikov:2010:Towards, title={{Towards Higher-Level Supercompilation}}, author={Klyuchnikov, I. and Romanenko, S.}, pages={82--101}, booktitle={Second International Workshop on Metacomputation in Russia}, year={2010} } @Article{Knuth:1977:FastPattern, author = "D.E. Knuth and J.H. Morris and V.R. Pratt", title = "Fast pattern matching in strings", journal = "SIAM Journal on Computing", volume = "6", year = "1977", pages = "323--350", } @mastersthesis{Kort:1996:Deforestation, title={{Deforestation of a raytracer}}, author={J. Kort}, year={1996}, school={University of Amsterdam}, } @Article{Kruskal:1960:Well, title = "Well-quasi Ordering, the Tree Theorem and {V}azsonyi's Conjecture", author = "J. B. Kruskal", journal = "Trans. Amer. Math. Soc.", year = "1960", volume = "95", pages = "210--225", key = "Kruskal", } @InProceedings{Leuschel:1998:OnThe, author = {M. Leuschel}, title = {On the Power of Homeomorphic Embedding for Online Termination}, booktitle = {SAS '98: Proceedings of the 5th International Symposium on Static Analysis}, year = {1998}, isbn = {3-540-65014-8}, pages = {230--245}, publisher = {Springer-Verlag}, address = {London, UK}, } @InProceedings{Leuschel:2002:Homeomorphic, title = "Homeomorphic Embedding for Online Termination of Symbolic Methods", author = "M. Leuschel", booktitle = "The Essence of Computation, Complexity, Analysis, Transformation. Essays Dedicated to Neil {D}. Jones [on occasion of his 60th birthday]", publisher = "Springer", year = "2002", volume = "2566", editor = "T. {\AE}. Mogensen and D. A. Schmidt and I. Hal Sudborough", ISBN = "3-540-00326-6", pages = "379--403", series = "Lecture Notes in Computer Science", } @inproceedings{Leuschel:2006:Ecce, author = {Leuschel, M. and Elphick, D. and Varea, M. and Craig, S-J and Fontaine, M.}, title = {The Ecce and Logen partial evaluators and their web interfaces}, booktitle = {PEPM '06: Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation}, year = {2006}, isbn = {1-59593-196-1}, pages = {88--94}, location = {Charleston, South Carolina}, publisher = {ACM}, address = {New York, NY, USA}, } @inproceedings{Leuschel:2009:Fast, author = "M. Leuschel and G. Vidal", title = "{Fast Offline Partial Evaluation of Large Logic Programs}", booktitle = "Logic-based Program Synthesis and Transformation (revised and selected papers from LOPSTR'08)", year = 2009, publisher = "Springer LNCS 5438", pages = "119-134", } @InCollection{Lassez:1988:Unification, title = "Unification Revisited", booktitle = "Foundations of Deductive Databases and Logic Programming", editor = "Jack Minker", author = "J-L. Lassez and M. Maher and K. Marriott", year = "1988", pages = "587--625", publisher = "Morgan Kaufmann", } @InProceedings{Liu:2002:Program, author = {Y.A. Liu and S.D. Stoller}, title = {Program optimization using indexed and recursive data structures}, booktitle = {PEPM '02: Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation}, year = {2002}, isbn = {1-58113-455-X}, pages = {108--118}, location = {Portland, Oregon}, doi = {http://doi.acm.org/10.1145/503032.503041}, publisher = {ACM Press}, address = {New York, NY, USA}, } @article{Liu:2003:Dynamic, author = {Y.A. Liu and S.D. Stoller}, title = {Dynamic Programming via Static Incrementalization}, journal = {Higher Order Symbol. Comput.}, volume = {16}, number = {1-2}, year = {2003}, issn = {1388-3690}, pages = {37--62}, publisher = {Kluwer Academic Publishers}, address = {Hingham, MA, USA}, } @InProceedings{Liu:2005:Incrementalization, title = "Incrementalization across object abstraction", author = "Y. A. Liu and S. D. Stoller and M. Gorbovitski and T. Rothamel and Y. E. Liu", bibdate = "2006-02-13", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/oopsla/oopsla2005.html#LiuSGRL05", booktitle = "Proceedings of the 20th Annual {ACM} {SIGPLAN} Conference on Object-Oriented Programming, Systems, Languages, and Applications, {OOPSLA} 2005, October 16-20, 2005, San Diego, {CA}, {USA}", publisher = "ACM", year = "2005", editor = "Ralph Johnson and Richard P. Gabriel", ISBN = "1-59593-031-0", pages = "473--486", } @InProceedings{Makholm:2000:Jones, author = "H. Makholm", year = "2000", title = "On {J}ones-Optimal Specialization for Strongly Typed Languages", booktitle = "Semantics, Applications and Implementation of Program Generation", editor = "Walid Taha", publisher = "Springer-Verlag", address = "Montreal, Canada", series = "Lecture Notes In Computer Science", volume = "1924", pages = "129--148", month = "20 " # sep, semno = "D-424", URL = "http://www.diku.dk/~makholm/saig.ps.gz", puf = "Artikel i proceedings (med censur)", id = "KonR", } @InProceedings{Marlow:1992:Deforestation, title = "Deforestation for Higher-Order Functions", author = "S. Marlow and P. Wadler", publisher = "Springer", year = "1992", bibdate = "2003-02-19", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/fp/fp1992.html#MarlowW92", booktitle = "Functional Programming", editor = "John Launchbury and Patrick M. Sansom", ISBN = "3-540-19820-2", pages = "154--165", series = "Workshops in Computing", } @phdthesis{Marlow:1995:Deforestation, title = "Deforestation for Higher-Order Functional Programs", author = "S. D. Marlow", year = "1995", month = apr # "~27", school = "Department of Computing Science, University of Glasgow", abstract = "Functional programming languages are an ideal medium for program optimisations based on source-to-source transformation techniques. Referential transparency affords opportunities for a wide range of correctness-preserving transformations leading to potent optimisation strategies. This thesis builds on deforestation, a program transformation technique due to Wadler that removes intermediate data structures from first-order functional programs. Our contribution is to reformulate deforestation for higher-order functional programming languages, and to show that the resulting algorithm terminates given certain syntactic and typing constraints on the input. These constraints are entirely reasonable, indeed it is possible to translate any typed program into the required syntactic form. We show how this translation can be performed automatically and optimally. The higher-order deforestation algorithm is transparent. That is, it is possible to determine by examination of the source program w...", citeseer-references = "oai:CiteSeerPSU:66245; oai:CiteSeerPSU:5989; oai:CiteSeerPSU:221054; oai:CiteSeerPSU:37044; oai:CiteSeerPSU:531314; oai:CiteSeerPSU:50357; oai:CiteSeerPSU:286334; oai:CiteSeerPSU:396613; oai:CiteSeerPSU:25492; oai:CiteSeerPSU:12235; oai:CiteSeerPSU:287713; oai:CiteSeerPSU:118569; oai:CiteSeerPSU:71918; oai:CiteSeerPSU:365371; oai:CiteSeerPSU:250500; oai:CiteSeerPSU:25073; oai:CiteSeerPSU:365371; oai:CiteSeerPSU:10679", annote = "Simon David Marlow (Computing Science at the University of Glasgow; September);", bibsource = "OAI-PMH server at cs1.ist.psu.edu", language = "en", oai = "oai:CiteSeerPSU:397882", rights = "unrestricted", } @Book{SML97, author = "R. Milner and M. Tofte and R. Harper and D. MacQueen", title = "The Definition of {S}tandard {ML}, {\rm Revised edition}", publisher = "MIT Press", checked = "Yes", year = "1997", } @InProceedings{Mitchell:2008:ASupercompiler, author = "N. Mitchell and C. Runciman", title = "A Supercompiler for Core Haskell", editor = "O. Chitil et al.", publisher = "Springer-Verlag", series = "Lecture Notes in Computer Science", volume = "5083", booktitle = "Selected Papers from the Proceedings of IFL 2007", year = "2008", pages = "147--164", } @phdthesis{Mitchell:2008:Transformation ,title = {Transformation and Analysis of Functional Programs} ,author = {N. Mitchell} ,year = {2008} ,month = {June} ,day = {4} ,school = {University of York} ,pages = {225} } @inproceedings{Mitchell:2010:Rethinking ,title = {Rethinking Supercompilation} ,author = {N. Mitchell} ,year = {2010} ,month = {September} ,day = {29} ,location = {Baltimore, Maryland, USA} ,pages = {309--320} ,booktitle = {ICFP '10: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming} ,publisher = {ACM} ,isbn = {978-1-60558-794-3} } @Article{Mogensen:2000:Glossary, author = "T.{\AE}. Mogensen", year = "2000", title = "Glossary for Partial Evaluation and Related Topics", journal = "Higher-Order and Symbolic Computation", volume = "13", number = "4", pages = "355--368", month = dec, keywords = "Partial evaluation, Program transformation, Program analysis", summary = "We list a number of commonly used terms in the literature of partial evaluation and related topics and provide explanations for these.", semno = "D-436", puf = "Artikel optaget i tidsskrift", id = "Art2", } @Book{Muchnick:1997:Advanced, author = "S. S. Muchnick", title = "Advanced Compiler Design and Implementation", publisher = "Morgan Kaufmann", year = "1997", } @TechReport{Narendran:1987:On, author = "P. Narendran and J. Stillman", year = "1987", title = "On the {C}omplexity of {H}omeomorphic {E}mbeddings", institution = "Computer Science Department, State Univeristy of New York at Albany", number = "87-8", month = "March", } @Article{Nash-Williams:1963:On, author = "C. St. J. A. Nash-Williams", month = oct, year = "1963", title = "On well-quasi-ordering finite trees", journal = "Proceedings of the Cambridge Philosophical Society", volume = "59", number = "4", pages = "833--835", } @InProceedings{Nemytykh:2003:Supercompiler, title = "The Supercompiler {SCP4}: General Structure", author = "A. P. Nemytykh", booktitle = "Perspectives of Systems Informatics, 5th International Andrei Ershov Memorial Conference, {PSI} 2003, Akademgorodok, Novosibirsk, Russia, July 9-12, 2003, Revised Papers", publisher = "Springer", year = "2003", volume = "2890", editor = "Manfred Broy and Alexandre V. Zamulin", ISBN = "3-540-20813-5", pages = "162--170", series = "LNCS", } @phdthesis{Nordlander:1999:Reactive, author = "Johan Nordlander", title = "Reactive Objects and Functional Programming", school = "Chalmers University of Technology", year = "1999", } @InProceedings{Nordlander:2002:Reactive, title = "Reactive Objects.", author = "J. Nordlander and M.P. Jones and M. Carlsson and R.B. Kieburtz and A.P. Black", year = "2002", oai = "oai:DBLP:inproceedings.conf/isorc/NordlanderJCKB02", conference = "Object-Oriented Real-Time Distributed Computing", } @article{Nordlander:2002:Polymorphic, abstract = {O'Haskell is a programming language derived from Haskell by the addition of concurrent reactive objects and subtyping. Because Haskell already encompasses an advanced type system with polymorphism and overloading, the type system of O'Haskell is much richer than what is the norm in almost any widespread object-oriented or functional language. Yet, there is strong evidence that O'Haskell is not a complex language to use, and that both Java and Haskell programmers can easily find their way with its polymorphic subtyping system. This paper describes the type system of O'Haskell both formally and from a programmer's point of view; the latter task is accomplished with the aid of an illustrative, real-world programming example: a strongly typed interface to the graphical toolkit Tk.}, author = {Nordlander, J. }, citeulike-article-id = {267337}, doi = {10.1016/S0167-6423(02)00026-6}, issn = {0167-6423}, journal = {Science of Computer Programming}, keywords = {ohaskell timber typesystem}, month = {May}, number = {2}, pages = {93--127}, priority = {0}, title = {Polymorphic subtyping in {O'H}askell}, volume = {43}, year = {2002} } @misc{Nordlander:2005:Programming, author = "J. Nordlander and M. Carlsson and M.P. Jones and J. Jonsson", title = "Programming with Time-Constrained Reactions", text = "Submitted to ECRTS '05", year = "2005", } @Misc{OCaml, author = "X. Leroy", title = "The {O}bjective {C}aml System: Documentation and User's Manual", year = "2008", note = "With D. Doligez, J. Garrigue, D. R\'emy, and J. Vouillon. Available from \url{http://caml.inria.fr} (1996--2008)", } @InProceedings{Odersky:1996:Putting, title = "Putting Type Annotations to Work", author = "M. Odersky and K. L{\"a}ufer", year = "1996", bibdate = "2002-12-05", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/popl/popl96.html#OderskyL96", booktitle = {POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, publisher = "ACM", location = "St. Petersburg Beach, Florida, United States", pages = "54--67", eURL = "http://doi.acm.org/10.1145/237721.237729", } @inproceedings{Ohori:2007:Lightweight, author = {A. Ohori and I. Sasano}, title = {Lightweight fusion by fixed point promotion}, booktitle = {POPL '07: Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, year = {2007}, isbn = {1-59593-575-4}, pages = {143--154}, location = {Nice, France}, publisher = {ACM}, address = {New York, NY, USA}, } @InProceedings{Partain:1992:nofib, title = "The nofib Benchmark Suite of Haskell Programs", author = "W. Partain", publisher = "Springer", year = "1992", bibdate = "2003-02-19", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/fp/fp1992.html#Partain92", booktitle = "Functional Programming", editor = "John Launchbury and Patrick M. Sansom", ISBN = "3-540-19820-2", pages = "195--202", series = "Workshops in Computing", } @Book{Parzynski:1987:Introduction, AUTHOR = "W.R Parzynski and P.W. Zipse", TITLE = "Introduction to Mathematical Analysis", PUBLISHER = "McGraw-Hill Book Co., Singapore", YEAR = "1987", } @InProceedings{Pfenning:1991:Unification, title = "Unification and Anti-Unification in the Calculus of Constructions", author = "F. Pfenning", publisher = "IEEE Computer Society", year = "1991", bibdate = "2006-04-25", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/lics/lics91.html#Pfenning91", booktitle = "LICS", pages = "74--85", } @Article{Puschner:2000:Guest, title = "Guest Editorial: {A} Review of Worst-Case Execution-Time Analysis", author = "P.P. Puschner and A. Burns", journal = "Real-Time Systems", year = "2000", number = "2/3", volume = "18", bibdate = "2002-01-03", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/rts/rts18.html#PuschnerB00", pages = "115--128", } @conference{Reich:2010:Supercompilation, title={{Supercompilation and the Reduceron}}, author={Riech, J. S and Naylor, M. and Runciman, C.}, pages={159--172}, booktitle={Second International Workshop on Metacomputation in Russia}, year={2010} } @Article{Sabry:1998:What, author = "A. Sabry", title = "What is a purely functional language?", journal = "Journal of Functional Programming", year = "1998", volume = "8", number = "1", month = jan, pages = "1--22", annote = "28 references.", } @Article{Sands:1996:Proving, title = "Proving the correctness of recursion-based automatic program transformations", author = "D. Sands", pages = "193--233", journal = "Theoretical Computer Science", month = "30~" # oct, year = "1996", volume = "167", number = "1--2", } @Article{Sands:1996:Total, title = "Total Correctness by Local Improvement in the Transformation of Functional Programs", author = "D. Sands", journal = "ACM Transactions on Programming Languages and Systems", pages = "175--234", month = mar, year = "1996", volume = "18", number = "2", } @InProceedings{Sands:1997:From, author = "D. Sands", title = "From {SOS} Rules to Proof Principles: An Operational Metatheory for Functional Languages", booktitle = "Proceedings of the 24th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)", month = jan, year = "1997", publisher = "ACM Press", abstract = "Structural Operational Semantics (SOS) is a widely used formalism for specifying the computational meaning of programs, and is commonly used in specifying the semantics of functional languages. Despite this widespread use there has been relatively little work on the ``metatheory'' for such semantics. As a consequence the operational approach to reasoning is considered \emph{ad hoc} since the same basic proof techniques and reasoning tools are reestablished over and over, once for each operational semantics specification. This paper develops some metatheory for a certain class of SOS language specifications for functional languages. We define a rule format, Globally Deterministic SOS (GDSOS), and establish some proof principles for reasoning about equivalence which are sound for all languages which can be expressed in this format. More specifically, if the SOS rules for the operators of a language conform to the syntax of the GDSOS format, then (i) a syntactic analogy of continuity holds, which relates a recursive function to its finite unwindings, and forms the basis of a Scott-style fixed-point induction technique; (ii) a powerful induction principle called improvement induction holds for a certain class of instrumented GDSOS semantics; (iii) a useful bisimulation-based coinductive proof technique for operational approximation (and its ``instrumented'' variants) is sound.", pdf = "http://www.cs.chalmers.se/~dave/papers/sands-POPL97.pdf", } @TechReport{Secher:1999:Masters, author = "J. P. Secher", year = "1999", title = "Perfect Supercompilation", institution = "Department of Computer Science (DIKU), University of Copenhagen", number = "DIKU-TR-99/1", month = feb, keywords = "program transformation, information propagation, negative information, termination", semno = "D-376", puf = "Tekniske rapport", id = "Tek", } @InProceedings{Secher:1999:Perfect, author = "J.P. Secher and M.H. S{\o}rensen", year = "2000", title = "On Perfect Supercompilation", booktitle = "Proceedings of Perspectives of System Informatics", editor = "D. Bj{\o}rner and M. Broy and A. Zamulin", publisher = "Springer-Verlag", series = "Lecture Notes in Computer Science", volume = "1755", pages = "113--127", keywords = "program transformation, information propagation, negative information, termination", postscript = "http://www.diku.dk/~jpsecher/sechersoerensen.ps.gz", dvi = "http://www.diku.dk/~jpsecher/sechersoerensen.dvi.gz", semno = "D-377", puf = "Artikel i proceedings (med censur)", id = "KonR", } @PhdThesis{Shivers:1991:Control, author = "O. Shivers", title = "Control-Flow Analysis of Higher-Order Languages", school = "Carnegie-Mellon University", year = "1991", month = may, } @Misc{Shootout, author = "B. Fulgham", title = "The Great Language Shootout", URL = "http://shootout.alioth.debian.org/", year = "2007", month = jan, added-at = "Thu Jan 18 21:41:42 2007", } @Article{Soerensen:1996:Positive, semno = "D-300", author = "M.H. S{\o}rensen and R. Gl{\"u}ck and N.D. Jones", title = "A Positive Supercompiler", journal = "Journal of Functional Programming", volume = "6", number = "6", pages = "811--838", year = "1996", puf = "Artikel optaget i tidsskrift", id = "Art2", keywords = "Supercompilation, deforestation, partial evaluation, GPC, positive supercompilation, pattern matching", } @InProceedings{Soerensen:1998:Convergence, author = "M.H. S{\o}rensen", title = "Convergence of Program Transformers in the Metric Space of Trees", booktitle = "MPC: 4th International Conference on Mathematics of Program Construction", publisher = "LNCS, Springer-Verlag", year = "1998", } @inproceedings{Soerensen:1999:Introduction, author = {M.H. S{\o}rensen and R. Gl\&\#252;ck}, title = {Introduction to Supercompilation}, booktitle = {Partial Evaluation - Practice and Theory, DIKU 1998 International Summer School}, year = {1999}, isbn = {3-540-66710-5}, pages = {246--270}, publisher = {Springer-Verlag}, address = {London, UK}, } @Article{Soerensen:2000:Convergence, title = "Convergence of program transformers in the metric space of trees", author = "M.H. S{\o}rensen", journal = "Sci. Comput. Program", year = "2000", number = "1-3", volume = "37", bibdate = "2003-11-27", bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/scp/scp37.html#Sorensen00", pages = "163--205", } @inproceedings{Sulzmann:2007:System, author = {M. Sulzmann and M. M. T. Chakravarty and S. {Peyton Jones} and K. Donnelly}, title = {System {F} with type equality coercions}, booktitle = {TLDI '07: Proceedings of the 2007 ACM SIGPLAN international worksh op on Types in languages design and implementation}, year = {2007}, isbn = {1-59593-393-X}, pages = {53--66}, location = {Nice, Nice, France}, publisher = {ACM}, address = {New York, NY, USA}, } @InProceedings{Svenningsson:2002:Shortcut, title = "Shortcut fusion for accumulating parameters \& zip-like functions", author = "J. Svenningsson", year = "2002", bibdate = "2003-02-13", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/icfp/icfp2002.html#Svenningsson02", booktitle = "ICFP", pages = "124--132", } @url{Syme:2008:The, author = "D. Syme", Title = "The {F}\# programming language", URL = "http://research.microsoft.com/fsharp", year = "2008", month = "Jun", added-at = "Tue Jun 17 00:58:23 2008", } @inproceedings{Taha:2001:Tag, author = {W. Taha and H. Makholm and J. Hughes}, title = {Tag Elimination and Jones-Optimality}, booktitle = {PADO '01: Proceedings of the Second Symposium on Programs as Data Objects}, year = {2001}, isbn = {3-540-42068-1}, pages = {257--275}, publisher = {Springer-Verlag}, address = {London, UK}, } @InProceedings{Takano:1995:Shortcut, title = "Shortcut Deforestation in Calculational Form", author = "A. Takano and E. Meijer", year = "1995", bibdate = "2002-12-17", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/fpca/fpca95.html#TakanoM95", booktitle = "FPCA", pages = "306--313", } @misc{Timber, title = "The {T}imber home page", key = {Timber}, url = "http://www.timber-lang.org", author = {J. Nordlander and M. Carlsson and A. Gill and P. Lindgren and B. {von Sydow}}, year = {2008} } @Article{Turing:1935:Computable, author = "A.M. Turing", title = "On Computable Numbers with an Application to the {E}ntscheidungsproblem", journal = "Proc. London Math. Soc. (2)", volume = "42", year = "1935", pages = "230--265", annote = "Hodges page 96 note 2.37; Reprinted in {\em The Undecidable}.", } @inproceedings{Vidal:2002:Cost, author = {G. Vidal}, title = {Cost-augmented narrowing-driven specialization}, booktitle = {PEPM '02: Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation}, year = {2002}, isbn = {1-58113-455-X}, pages = {52--62}, location = {Portland, Oregon}, doi = {http://doi.acm.org/10.1145/503032.503037}, publisher = {ACM Press}, address = {New York, NY, USA}, } @article{Vidal:2004:Cost, author = {G. Vidal}, title = {Cost-Augmented Partial Evaluation of Functional Logic Programs}, journal = {Higher Order Symbolic Computation}, volume = {17}, number = {1-2}, year = {2004}, issn = {1388-3690}, pages = {7--46}, publisher = {Kluwer Academic Publishers}, address = {Hingham, MA, USA}, } @inproceedings{Vidal:2010:Hybrid, author = "G. Vidal", title = "{A Hybrid Approach to Conjunctive Partial Deduction}", booktitle = "Proc.\ of the 21th Int'l Symp.\ on Logic-based Program Synthesis and Transformation (LOPSTR'10)", year = 2010, note = "Available from \verb$http://users.dsic.upv.es/~gvidal/german/papers.html$", } @InProceedings{Wadler:1984:Listlessness, author = "P. Wadler", title = "Listlessness is Better than Laziness", booktitle = "Conference Record of the 1984 {ACM} Symposium on Lisp and Functional Programming", organization = "ACM", publisher = "ACM", month = aug, year = "1984", pages = "45--52", refs = "25", checked = "19940320", source = "dept. library", keywords = "program transformation", sjb = "Describes how expressions of the form \begin{verbatim} sum (map square (upto 1 n)) \end{verbatim} Can be transformed into listless versions. The appendices contain a simple word counter in KRC and the resulting listless version.", reffrom = "Waters:iait:1987", reffrom = "Wadler:esop:1988", reffrom = "Chin:acm:lfp:1992", } @InProceedings{Wadler:1985:Listlessness, author = "P. Wadler", editor = "H. Ganziger and N. D. Jones", title = "Listlessness is better than laziness {II}: composing listless functions", booktitle = "Proc. Workshop on Programs as Data Objects", series = "LNCS", volume = "217", publisher = "SpringerVerlag", year = "1985", keywords = "FP,functional programming, applicative, list, stream, streams", abstract = "preorder listless function composition", } @InProceedings{Wadler:1989:Theorems, title = "Theorems for Free!", author = "P. Wadler", year = "1989", bibdate = "2002-12-17", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/fpca/fpca89.html#Wadler89", booktitle = "FPCA", pages = "347--359", } @Article{Wadler:1990:Deforestation, author = "P. Wadler", title = "Deforestation: transforming programs to eliminate trees", journal = "Theoretical Computer Science", volume = "73", number = "2", pages = "231--248", day = "22", month = jun, year = "1990", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory); C6150C (Compilers, interpreters and other processors)", corpsource = "Dept. of Comput. Sci., Glasgow Univ., UK", keywords = "algorithm; deforestation; eliminate; intermediate trees; optimizing compiler; program compilers; program transformation; programming theory; syntactic form; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Misc{Yoshii:2005:rdtsc, author = "K. Yoshii", title = "Time-stamp counter", URL = "http://www-unix.mcs.anl.gov/~kazutomo/rdtsc.html", year = "2007", month = Nov, } @proceedings{hinzehw, editor = {Hinze,Ralf}, booktitle = {Proceedings of the 2001 ACM SIGPLAN Haskell Workshop (HW'2001), 2nd September 2001, Firenze, Italy.}, series = {Electronic Notes in Theoretical Computer Science, Vol 59}, publisher = {Utrecht University}, note = {UU-CS-2001-23}, year = 2001, }