Difference between revisions of "Research papers/Compilation"
Jump to navigation
Jump to search
DonStewart (talk | contribs) (another fusion paper) |
m |
||
(34 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
− | |||
__TOC__ |
__TOC__ |
||
Line 6: | Line 5: | ||
===CPR=== |
===CPR=== |
||
− | ;[ |
+ | ;[https://www.cambridge.org/core/services/aop-cambridge-core/content/view/53F8937E9686B7CB261AE727124FE1D0/S0956796803004751a.pdf/constructed-product-result-analysis-for-haskell.pdf Constructed Product Result Analysis for Haskell] |
:Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones, Journal of Functional Programming 14(2), March 2004, pp 211-245. |
:Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones, Journal of Functional Programming 14(2), March 2004, pp 211-245. |
||
===Usage analysis=== |
===Usage analysis=== |
||
+ | ;[http://www.cs.chalmers.se/~josefs/publications/APLAS2006.pdf Polymorphism, Subtyping, Whole Program Analysis and Accurate Data Types in Usage Analysis] |
||
− | ;[http://research.microsoft.com/~simonpj/Papers/usage-types/usage.htm Simple Polymorphic Usage Analysis] |
||
+ | :Tobias Gedell, Jörgen Gustavsson and Josef Svenningsson; The Fourth ASIAN Symposium on Programming Languages and Systems, 2006. |
||
+ | |||
+ | ;[https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-623.pdf Simple Polymorphic Usage Analysis] |
||
:Keith Wansbrough (2002), PhD thesis, Computer Laboratory, University of Cambridge. |
:Keith Wansbrough (2002), PhD thesis, Computer Laboratory, University of Cambridge. |
||
+ | ;[http://www.cs.chalmers.se/~gustavss/publications/ifl00.html A usage analysis with bounded usage polymorphism and subtyping] |
||
− | ;[http://research.microsoft.com/~simonpj/Papers/usage-types/usage.htm Simple Usage Polymorphism] |
||
+ | : Jörgen Gustavsson and Josef Svenningsson; Workshop on Implementation of Functional Languages 2000. |
||
+ | |||
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.132&rep=rep1&type=pdf Simple Usage Polymorphism] |
||
:Keith Wansbrough and Simon Peyton Jones; Workshop on Types In Compilation 2000. |
:Keith Wansbrough and Simon Peyton Jones; Workshop on Types In Compilation 2000. |
||
− | ;[ |
+ | ;[https://dl.acm.org/doi/pdf/10.1145/292540.292545 Once Upon a Polymorphic Type] |
:Keith Wansbrough and Simon Peyton Jones, POPL'99. |
:Keith Wansbrough and Simon Peyton Jones, POPL'99. |
||
+ | ;[http://www.cs.chalmers.se/~gustavss/publications/icfp98.html A Type Based Sharing Analysis for Update Avoidance and Optimisation] |
||
− | ===Inlining=== |
||
+ | :Jörgen Gustavsson; ICFP'98. |
||
− | |||
− | ;[http://research.microsoft.com/~simonpj/Papers/inlining/index.htm Secrets of the Glasgow Haskell Compiler inliner] |
||
− | :Simon Peyton Jones and Simon Marlow. IDL'99; revised version Journal of Functional Programming 12(4), July 2002, pp393-434. |
||
− | |||
− | ===Laziness=== |
||
;[http://www.cse.ogi.edu/~jl/Papers/update.ps Avoiding Unnecessary Updates] |
;[http://www.cse.ogi.edu/~jl/Papers/update.ps Avoiding Unnecessary Updates] |
||
:John Hughes, John Launchbury, Andy Gill, Simon Marlow, Simon Peyton Jones, and Philip Wadler. 1993 Glasgow Workshop on Functional Programming. |
:John Hughes, John Launchbury, Andy Gill, Simon Marlow, Simon Peyton Jones, and Philip Wadler. 1993 Glasgow Workshop on Functional Programming. |
||
+ | |||
+ | ===Inlining=== |
||
+ | |||
+ | ;[https://www.cambridge.org/core/services/aop-cambridge-core/content/view/8DD9A82FF4189A0093B7672193246E22/S0956796802004331a.pdf/secrets-of-the-glasgow-haskell-compiler-inliner.pdf Secrets of the Glasgow Haskell Compiler inliner] |
||
+ | :Simon Peyton Jones and Simon Marlow. IDL'99; revised version Journal of Functional Programming 12(4), July 2002, pp393-434. |
||
===Strictness=== |
===Strictness=== |
||
Line 38: | Line 44: | ||
:John Hughes, John Launchbury. Mathematical Structures in Computer Science 2(3): 301-326 (1992) |
:John Hughes, John Launchbury. Mathematical Structures in Computer Science 2(3): 301-326 (1992) |
||
− | ;[http:// |
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.5525&rep=rep1&type=pdf Measuring the effectiveness of a simple strictness analyser] |
:SL Peyton Jones and WD Partain, Functional Programming, Glasgow 1993, ed Hammond and O'Donnell, Springer Verlag Workshops in Computing, 1993, pp201-220. |
:SL Peyton Jones and WD Partain, Functional Programming, Glasgow 1993, ed Hammond and O'Donnell, Springer Verlag Workshops in Computing, 1993, pp201-220. |
||
Line 66: | Line 72: | ||
===Lambda lifting=== |
===Lambda lifting=== |
||
− | ;[ |
+ | ;[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.1125&rep=rep1&type=pdf A modular fully-lazy lambda lifter in Haskell] |
:SL Peyton Jones and D Lester, Software Practice and Experience 21(5), May 1991, pp479-506. |
:SL Peyton Jones and D Lester, Software Practice and Experience 21(5), May 1991, pp479-506. |
||
+ | |||
+ | ;[http://citeseer.ist.psu.edu/johnsson85lambda.html Lambda Lifting: Transforming Programs to Recursive Equations] |
||
+ | ;Thomas Johnsson, Functional programming languages and computer architecture, September 1985. |
||
+ | |||
+ | ===Common subexpression elimination (CSE)=== |
||
+ | |||
+ | ;[http://www.cs.kent.ac.uk/pubs/1997/1904/index.html Common Subexpression Elimination in a Lazy Functional Language] |
||
+ | :Olaf Chitil. In Chris Clack, Tony Davie, and Kevin Hammond, editors, Draft Proceedings of the 9th International Workshop on Implementation of Functional Languages, pages 501-516. St Andrews, Scotland, September 1997. |
||
+ | |||
+ | ;[http://www.cs.kent.ac.uk/pubs/1998/1905/index.html Common Subexpressions are Uncommon in Lazy Functional Languages] |
||
+ | :Olaf Chitil. In Chris Clack, Tony Davie, and Kevin Hammond, editors, Proceedings of the 9th International Workshop on Implementation of Functional Languages (September 1997), pages 53-71. St Andrews, Scotland, Springer, 1998. |
||
===Let floating=== |
===Let floating=== |
||
− | ;[http:// |
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.2589&rep=rep1&type=pdf Let-floating: moving bindings to give faster programs] |
:(ICFP '96), SL Peyton Jones, WD Partain, A Santos, Proc International Conference on Functional Programming, Philadelphia (ICFP'96), May 1996. |
:(ICFP '96), SL Peyton Jones, WD Partain, A Santos, Proc International Conference on Functional Programming, Philadelphia (ICFP'96), May 1996. |
||
− | ===Free variables=== |
+ | ===Free variables and substitution=== |
;[http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/notanum.pdf Conor McBride, James McKinna Functional pearl: I am not a number--I am a free variable] |
;[http://www.dcs.st-andrews.ac.uk/~james/RESEARCH/notanum.pdf Conor McBride, James McKinna Functional pearl: I am not a number--I am a free variable] |
||
:Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, Snowbird, Utah, USA, 1-9 2004 ISBN 1-58113-850-4 |
:Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, Snowbird, Utah, USA, 1-9 2004 ISBN 1-58113-850-4 |
||
+ | ;[http://www.cs.ioc.ee/~tarmo/papers/cmcs03.ps.gz Substitution in non-wellfounded syntax with variable binding] |
||
− | ===Fusion and deforestation=== |
||
+ | :R. Matthes, T. Uustalu. Theor. Comput. Sci., v. 327, n. 1-2, pp. 155-174, 2004. - ( Elsevier Science) // Conf. version in H. P. Gumm, ed., Proc. of 6th Int. Wksh. on Coalgebraic Methods in Computer Science, CMCS '03 (Warsaw, Apr. 2003), v. 82, n. 1 of Electron. Notes. in Theor. Comput. Sci.. Elsevier, 2003. |
||
+ | |||
+ | ;[http://www.cs.ioc.ee/~tarmo/papers/merlin03-dl.ps.gz Explicit substitutions and higher-order syntax] |
||
+ | :N. Ghani, T. Uustalu, M. Hamana. Higher-Order and Symb. Comput., v. 19, n. 2-3, to appear. - .pdf, 330K // Conf. version in F. Honsell, M. Miculan, A. Momigliano, eds., Proc. of 2nd ACM SIGPLAN Wksh. on Mechanized Reasoning about Languages with Variable Binding, MER?IN '03 (Uppsala, Aug. 2003), 7 pp. ACM Press, 2003. |
||
+ | |||
+ | ===Constructor specialisation=== |
||
+ | |||
+ | ;[https://www.researchgate.net/profile/Simon-Peyton-Jones/publication/228350990_Constructor_specialisation_for_Haskell_programs/links/0c960517e31f2ab5f1000000/Constructor-specialisation-for-Haskell-programs.pdf Constructor specialisation for Haskell programs] |
||
+ | :Simon Peyton Jones. Submitted to ICFP 2007. |
||
+ | |||
+ | ===[[Fusion]] and [[deforestation]]=== |
||
+ | |||
+ | See also [[Research_papers/Data_structures#Lists|papers on lists]] |
||
− | ;[ |
+ | ;[https://theses.gla.ac.uk/4817/1/1996gillphd.pdf Cheap deforestation for non-strict functional languages] |
:A Gill, PhD thesis, University of Glasgow, Jan 1996. |
:A Gill, PhD thesis, University of Glasgow, Jan 1996. |
||
− | ;[ |
+ | ;[https://dl.acm.org/doi/pdf/10.1145/165180.165214 A short cut to deforestation] |
:A Gill, SL Peyton Jones, J Launchbury, Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp223-232. |
:A Gill, SL Peyton Jones, J Launchbury, Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp223-232. |
||
Line 104: | Line 134: | ||
;[http://doi.acm.org/10.1145/317636.317907 Typer inference builds a short cut to deforestation] |
;[http://doi.acm.org/10.1145/317636.317907 Typer inference builds a short cut to deforestation] |
||
:Olaf Chitil, ICFP '99: Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, 1999, 1-58113-111-9, 249--260, Paris, France, ACM Press, New York, NY, USA |
:Olaf Chitil, ICFP '99: Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, 1999, 1-58113-111-9, 249--260, Paris, France, ACM Press, New York, NY, USA |
||
+ | |||
+ | ;[http://www.cs.kent.ac.uk/pubs/1999/1910/index.html Type-inference based short cut deforestation (nearly) without inlining] |
||
+ | :Olaf Chitil. In Chris Clack and Pieter Koopman, editors, Draft Proceedings of the 11th International Workshop on Implementation of Functional Languages, pages 17-32, 1999. Lochem, Netherlands, September 7th-10th 1999. |
||
+ | |||
+ | ;[http://www.cs.kent.ac.uk/pubs/2000/1900/index.html Deforestation of Functional Programs through Type Inference] |
||
+ | :Olaf Chitil. In Wolfgang Goerigk, editor, 17 Workshops der GI-Fachgruppe 2.1.4. Programmiersprachen und Rechenkonzepte mit Schwerpunkt Softwarecomponenten, pages 121-130. Bad Honnef, Bericht Nr. 2007 des Instituts fur Informatik und Praktische Mathematik der Christian-Albrechts-Universitat zu Kiel, July 2000. |
||
+ | |||
+ | ;[http://www.cs.kent.ac.uk/pubs/2000/1815/index.html Type-inference based deforestation of functional programs] |
||
+ | :Olaf Chitil. PhD thesis, RWTH Aachen, October 2000. |
||
;[http://citeseer.ist.psu.edu/johann00warm.html Warm fusion in Stratego: A case study in generation of program transformation systems] |
;[http://citeseer.ist.psu.edu/johann00warm.html Warm fusion in Stratego: A case study in generation of program transformation systems] |
||
Line 116: | Line 155: | ||
;[http://citeseer.ist.psu.edu/meijer91functional.htm Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire] |
;[http://citeseer.ist.psu.edu/meijer91functional.htm Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire] |
||
:Erik Meijer and Maarten Fokkinga and Ross Paterson, Proceedings 5th {ACM} Conf. on Functional Programming Languages and Computer Architecture, FPCA'91, Cambridge, MA, USA, 26--30 Aug 1991, 523, Springer-Verlag, Berlin, J. Hughes, 124--144, 1991 |
:Erik Meijer and Maarten Fokkinga and Ross Paterson, Proceedings 5th {ACM} Conf. on Functional Programming Languages and Computer Architecture, FPCA'91, Cambridge, MA, USA, 26--30 Aug 1991, 523, Springer-Verlag, Berlin, J. Hughes, 124--144, 1991 |
||
+ | |||
+ | ;[http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/arith.pdf Arithmetic coding with folds and unfolds] |
||
+ | :Richard Bird and Jeremy Gibbons. In Johan Jeuring and Simon Peyton Jones, editors, Advanced Functional Programming 4, volume 2638 of Lecture Notes in Computer Science, pages 1-26. Springer-Verlag, 2003. |
||
+ | |||
+ | ;[http://www.cs.ut.ee/~varmo/papers/icfp05.ps.gz Monadic augment and generalised short cut fusion] |
||
+ | :N. Ghani, P. Johann, T. Uustalu, V. Vene. In Proc. of 10th ACM SIGPLAN Int. Conf. on Functional Programming, ICFP'05 (Tallinn, Sept. 2005), ACM SIGPLAN Notices, v. 40, n. 9, pp. 294-305. ACM Press, 2005 |
||
+ | |||
+ | ;[http://www.cs.ut.ee/~varmo/papers/aplas04.ps.gz Build, augment and destroy, universally] |
||
+ | :N. Ghani, T. Uustalu, V. Vene. In W.-N. Chin, ed., Proc. of 2nd Asian Symp. on Programming Languages and Systems, APLAS'04 (Taipei, Nov. 2004), Lecture Notes in Computer Science (LNCS), v. 3302, pp. 327-347, Springer-Verlag, 2004. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/p114-voigtlaender.pdf Concatenate, Reverse and Map Vanish For Free] |
||
+ | :Janis Voigtländer, International Conference on Functional Programming, Proceedings, vol. 37(9) of SIGPLAN Notices, pp. 14-25, ACM Press, 2002. |
||
+ | |||
+ | ;[https://arxiv.org/pdf/2105.03389v3 GADTs, Functoriality, Parametricity: Pick Two] |
||
+ | :Patricia Johann, Enrico Ghiorzi, and Daniel Jeffries, 16th Logical and Semantic Frameworks with Applications (LSFA 2021) EPTCS 357, 2022, pp. 77–92. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/seqFinal.pdf The Impact of seq on Free Theorems-Based Program Transformations] |
||
+ | :Patricia Johann and Janis Voigtländer, Fundamenta Informaticae, vol. 69(1-2), pp. 63-102, 2006. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/HOSC.pdf Using Circular Programs to Deforest in Accumulating Parameters] |
||
+ | :Janis Voigtländer, Higher-Order and Symbolic Computation, vol. 17(1-2), pp. 129-163, 2004. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/JFP-main.pdf Composition of functions with accumulating parameters] ([http://wwwtcs.inf.tu-dresden.de/~voigt/JFP-appendix.pdf proof appendix]) |
||
+ | :Janis Voigtländer and Armin Kühnemann, Journal of Functional Programming, vol. 14(3), pp. 317-363, 2004. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/TOCS.pdf Formal Efficiency Analysis for Tree Transducer Composition] |
||
+ | :Janis Voigtländer, Theory of Computing Systems, vol. 41(4), pp. 619-689, 2007. |
||
+ | |||
+ | ;[http://www.cse.unsw.edu.au/~dons/papers/CSL06.html Rewriting Haskell Strings] |
||
+ | :Duncan Coutts, Don Stewart and Roman Leshchinskiy, PADL 2007. |
||
+ | |||
+ | ;[http://metagraph.org/papers/stream_fusion.pdf Stream Fusion: From Lists to Streams to Nothing at All] |
||
+ | :Duncan Coutts, Roman Leshchinskiy and Don Stewart. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/TCS.pdf Selective strictness and parametricity in structural operational semantics, inequationally] |
||
+ | :Janis Voigtländer and Patricia Johann, Theoretical Computer Science, vol. 388(1-3), pp. 290-318, 2007. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/pepm09-voigtlaender.pdf Proving Correctness via Free Theorems: The Case of the destroy/build-Rule] |
||
+ | :Janis Voigtländer. Partial Evaluation and Semantics-Based Program Manipulation (PEPM'08), Proceedings, pages 13-20, ACM Press, 2008. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/flops.pdf Semantics and Pragmatics of New Shortcut Fusion Rules] |
||
+ | :Janis Voigtländer. Functional and Logic Programming (FLOPS'08), Proceedings, LNCS 4989:163-179, Springer-Verlag, 2008. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/iandc.pdf A family of syntactic logical relations for the semantics of Haskell-like languages] |
||
+ | :Patricia Johann and Janis Voigtländer, Information and Computation, vol. 207(2), pp. 341-368, 2009. |
||
==Compiler construction== |
==Compiler construction== |
||
− | ;[ |
+ | ;[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.6555&rep=rep1&type=pdf The Glasgow Haskell compiler: a technical overview] |
:SL Peyton Jones, CV Hall, K Hammond, WD Partain, PL Wadler, Proceedings of Joint Framework for Information Technology Technical Conference, Keele, March 1993, pp249-257. |
:SL Peyton Jones, CV Hall, K Hammond, WD Partain, PL Wadler, Proceedings of Joint Framework for Information Technology Technical Conference, Keele, March 1993, pp249-257. |
||
Line 127: | Line 211: | ||
==Intermediate languages== |
==Intermediate languages== |
||
− | ;[ |
+ | ;[https://www.researchgate.net/profile/Simon-Peyton-Jones/publication/2952858_Henk_A_Typed_Intermediate_Language/links/00463518a0cf76044e000000/Henk-A-Typed-Intermediate-Language.pdf Henk: a typed intermediate language] |
:SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997. |
:SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997. |
||
− | ;[ |
+ | ;[https://dl.acm.org/doi/pdf/10.1145/268946.268951 Bridging the gulf: a common intermediate language for ML and Haskell] |
:SL Peyton Jones, J Launchbury, MB Shields, and AP Tolmach, POPL98. |
:SL Peyton Jones, J Launchbury, MB Shields, and AP Tolmach, POPL98. |
||
Line 139: | Line 223: | ||
:Martin Sulzmann, Manuel M. T. Chakravarty, and Simon Peyton Jones. |
:Martin Sulzmann, Manuel M. T. Chakravarty, and Simon Peyton Jones. |
||
− | ;[ |
+ | ;[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.7735&rep=rep1&type=pdf A Single Intermediate Language That Supports Multiple Implementations of Exceptions] |
− | :Norman Ramsey and Simon Peyton Jones. PLDI 2000. 2000. |
+ | :Norman Ramsey and Simon Peyton Jones. PLDI 2000. 2000. |
+ | |||
+ | ;[http://www.iro.umontreal.ca/~monnier/tct.pdf Statically Verified Type-Preserving Code Transformations in Haskell] |
||
+ | :Louis-Julien Guillemette and Stefan Monnier. |
||
+ | |||
+ | ;[http://www.cs.chalmers.se/~boquist/phd/index.html Code Optimization for Lazy Functional Languages] |
||
+ | :Urban Boquist. PhD Thesis, Chalmers University of Technology, Gothenburg, Sweden, April 1999. |
||
+ | |||
+ | ;[http://www.cl.cam.ac.uk/~mb566/papers/tacc-hs09.pdf Types are calling conventions] |
||
+ | :Maximilian C. Bolingbroke, University Of Cambridge and Simon L. Peyton Jones, Microsoft Research. Proceedings of the 2nd ACM SIGPLAN symposium on Haskell 2009. ([http://vimeo.com/6688091 Video of paper presentation]) |
||
==Type inference== |
==Type inference== |
||
Line 149: | Line 242: | ||
==Compilation by transformation== |
==Compilation by transformation== |
||
− | ;[http:// |
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.5393&rep=rep1&type=pdf A transformation-based optimiser for Haskell] |
:SL Peyton Jones and A Santos, Science of Computer Programming 32(1-3), pp3-47, September 1998. |
:SL Peyton Jones and A Santos, Science of Computer Programming 32(1-3), pp3-47, September 1998. |
||
− | ;[http:// |
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.4431&rep=rep1&type=pdf Compiling Haskell by program transformation: a report from the trenches] |
:SL Peyton Jones Proc European Symposium on Programming (ESOP'96), Linkping, Sweden, Springer Verlag LNCS 1058, Jan 1996. |
:SL Peyton Jones Proc European Symposium on Programming (ESOP'96), Linkping, Sweden, Springer Verlag LNCS 1058, Jan 1996. |
||
− | ;[ |
+ | ;[https://theses.gla.ac.uk/74568/1/10992188.pdf Compilation by transformation in non-strict functional languages] |
:A Santos, PhD thesis, University of Glasgow, Sept 1995. |
:A Santos, PhD thesis, University of Glasgow, Sept 1995. |
||
− | ;[ |
+ | ;[https://www.researchgate.net/profile/Simon-Peyton-Jones/publication/2383730_Playing_by_the_Rules_Rewriting_as_a_practical_optimisation_technique_in_GHC/links/0046351edd5b81a049000000/Playing-by-the-Rules-Rewriting-as-a-practical-optimisation-technique-in-GHC.pdf Playing by the rules: rewriting as a practical optimisation technique in GHC] |
:Simon Peyton Jones, Andrew Tolmach and Tony Hoare, Haskell Workshop 2001. |
:Simon Peyton Jones, Andrew Tolmach and Tony Hoare, Haskell Workshop 2001. |
||
;[http://www.soi.city.ac.uk/~ross/papers/embeddings.html Transforming Lazy Functions using Comportment Properties] |
;[http://www.soi.city.ac.uk/~ross/papers/embeddings.html Transforming Lazy Functions using Comportment Properties] |
||
:Ross Paterson, Programming Languages: Implementations, Logics and Programs, LNCS, vol. 1292, pp. 111-125, Springer, Southampton, UK, 1997. |
:Ross Paterson, Programming Languages: Implementations, Logics and Programs, LNCS, vol. 1292, pp. 111-125, Springer, Southampton, UK, 1997. |
||
+ | |||
+ | ;[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.329.1855&rep=rep1&type=pdf On the Fundamental Limitations of Transformational Design] |
||
+ | :Jeroen Voeten, ACM Transactions on Design Automation of Electronic Systems, Vol. 6, No. 4, October 2001, pages 533–552. |
||
==Type errors== |
==Type errors== |
||
Line 168: | Line 264: | ||
;[http://www.cs.uu.nl/groups/ST/stbib/swierstra-by-year/heeren2002improving.bib Improving type-error messages in functional languages] |
;[http://www.cs.uu.nl/groups/ST/stbib/swierstra-by-year/heeren2002improving.bib Improving type-error messages in functional languages] |
||
:B. Heeren, J. Jeuring, S. D. Swierstra, and P. A. Alcocer. Technical Report UU-CS-2002-009, Institute of Information and Computing Science, University Utrecht, Netherlands, February 2002 |
:B. Heeren, J. Jeuring, S. D. Swierstra, and P. A. Alcocer. Technical Report UU-CS-2002-009, Institute of Information and Computing Science, University Utrecht, Netherlands, February 2002 |
||
+ | |||
+ | [[Category:Research]] |
Latest revision as of 23:58, 20 September 2024
Compiler Analyses
CPR
- Constructed Product Result Analysis for Haskell
- Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones, Journal of Functional Programming 14(2), March 2004, pp 211-245.
Usage analysis
- Polymorphism, Subtyping, Whole Program Analysis and Accurate Data Types in Usage Analysis
- Tobias Gedell, Jörgen Gustavsson and Josef Svenningsson; The Fourth ASIAN Symposium on Programming Languages and Systems, 2006.
- Simple Polymorphic Usage Analysis
- Keith Wansbrough (2002), PhD thesis, Computer Laboratory, University of Cambridge.
- A usage analysis with bounded usage polymorphism and subtyping
- Jörgen Gustavsson and Josef Svenningsson; Workshop on Implementation of Functional Languages 2000.
- Simple Usage Polymorphism
- Keith Wansbrough and Simon Peyton Jones; Workshop on Types In Compilation 2000.
- Once Upon a Polymorphic Type
- Keith Wansbrough and Simon Peyton Jones, POPL'99.
- A Type Based Sharing Analysis for Update Avoidance and Optimisation
- Jörgen Gustavsson; ICFP'98.
- Avoiding Unnecessary Updates
- John Hughes, John Launchbury, Andy Gill, Simon Marlow, Simon Peyton Jones, and Philip Wadler. 1993 Glasgow Workshop on Functional Programming.
Inlining
- Secrets of the Glasgow Haskell Compiler inliner
- Simon Peyton Jones and Simon Marlow. IDL'99; revised version Journal of Functional Programming 12(4), July 2002, pp393-434.
Strictness
- Implementing Projection-based Strictness Analysis
- Ryszard Kubiak, John Hughes, John Launchbury. Functional Programming 1991: 207-224
- Projections for Polymorphic First-Order Strictness Analysis
- John Hughes, John Launchbury. Mathematical Structures in Computer Science 2(3): 301-326 (1992)
- Measuring the effectiveness of a simple strictness analyser
- SL Peyton Jones and WD Partain, Functional Programming, Glasgow 1993, ed Hammond and O'Donnell, Springer Verlag Workshops in Computing, 1993, pp201-220.
- Compiling Laziness using Projections
- Ross Paterson, Static Analysis Symposium, LNCS, vol. 1145, pp. 255-269, Springer, Aachen, Germany, 1996.
- Projection-based Strictness Analysis - Theoretical and Practical Aspects
- Ralf Hinze. Inauguraldissertation, Universitt Bonn, November 1995.
- Strictness analysis aids time analysis
- Philip Wadler. 15'th ACM Symposium on Principles of Programming Languages, San Diego, California, January 1988.
- Strictness analysis on non-flat domains (by abstract interpretation over finite domains)
- Philip Wadler. Chapter in Samson Abramsky and Chris Hankin, editors, Abstract Interpretation, Ellis Horwood, 1987.
- Strictness Analysis: Proved and Improved
- Kei Davis and Philip Wadler. 1989 Glasgow Workshop on Functional Programming. August 1989.
- Strictness Analysis in 4D
- Kei Davis. 1990 Glasgow Workshop on Functional Programming. August 1990.
Abstract interpretation
- Fast Abstract Interpretation Using Sequential Algorithms
- John Hughes and Alex Ferguson. The Workshop on Static Analysis, WSA 1993: 45-59
Lambda lifting
- A modular fully-lazy lambda lifter in Haskell
- SL Peyton Jones and D Lester, Software Practice and Experience 21(5), May 1991, pp479-506.
- Lambda Lifting: Transforming Programs to Recursive Equations
- Thomas Johnsson, Functional programming languages and computer architecture, September 1985.
Common subexpression elimination (CSE)
- Common Subexpression Elimination in a Lazy Functional Language
- Olaf Chitil. In Chris Clack, Tony Davie, and Kevin Hammond, editors, Draft Proceedings of the 9th International Workshop on Implementation of Functional Languages, pages 501-516. St Andrews, Scotland, September 1997.
- Common Subexpressions are Uncommon in Lazy Functional Languages
- Olaf Chitil. In Chris Clack, Tony Davie, and Kevin Hammond, editors, Proceedings of the 9th International Workshop on Implementation of Functional Languages (September 1997), pages 53-71. St Andrews, Scotland, Springer, 1998.
Let floating
- Let-floating: moving bindings to give faster programs
- (ICFP '96), SL Peyton Jones, WD Partain, A Santos, Proc International Conference on Functional Programming, Philadelphia (ICFP'96), May 1996.
Free variables and substitution
- Conor McBride, James McKinna Functional pearl: I am not a number--I am a free variable
- Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, Snowbird, Utah, USA, 1-9 2004 ISBN 1-58113-850-4
- Substitution in non-wellfounded syntax with variable binding
- R. Matthes, T. Uustalu. Theor. Comput. Sci., v. 327, n. 1-2, pp. 155-174, 2004. - ( Elsevier Science) // Conf. version in H. P. Gumm, ed., Proc. of 6th Int. Wksh. on Coalgebraic Methods in Computer Science, CMCS '03 (Warsaw, Apr. 2003), v. 82, n. 1 of Electron. Notes. in Theor. Comput. Sci.. Elsevier, 2003.
- Explicit substitutions and higher-order syntax
- N. Ghani, T. Uustalu, M. Hamana. Higher-Order and Symb. Comput., v. 19, n. 2-3, to appear. - .pdf, 330K // Conf. version in F. Honsell, M. Miculan, A. Momigliano, eds., Proc. of 2nd ACM SIGPLAN Wksh. on Mechanized Reasoning about Languages with Variable Binding, MER?IN '03 (Uppsala, Aug. 2003), 7 pp. ACM Press, 2003.
Constructor specialisation
- Constructor specialisation for Haskell programs
- Simon Peyton Jones. Submitted to ICFP 2007.
Fusion and deforestation
See also papers on lists
- Cheap deforestation for non-strict functional languages
- A Gill, PhD thesis, University of Glasgow, Jan 1996.
- A short cut to deforestation
- A Gill, SL Peyton Jones, J Launchbury, Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp223-232.
- Deforestation: transforming programs to eliminate trees
- Philip Wadler. Theoretical Computer Science, (Special issue of selected papers from 2'nd European Symposium on Programming), 73: 231-248, 1990.
- Shortcut Deforestation in Calculational Form
- Akihiko Takano and Erik Meijer, Conf. Record 7th ACM SIGPLAN/SIGARCH Int. Conf. on Functional Programming Languages and Computer Architecture, {FPCA}'95, ACM Press, New York, 306--313, 1995.
- A Calculational Fusion System HYLO
- Y. Onoue, Z. Hu, H. Iwasaki, M. Takeichi, IFIP TC 2 Working Conference on Algorithmic Languages and Calculi. Le Bischenberg, France. pp.76-106. February 1997. Chapman & Hall.
- Deriving Structural Hylomorphisms from Recursive Definitions
- Z. Hu, H. Iwasaki, M. Takeichi, ACM SIGPLAN International Conference on Functional Programming (ICFP'96), Philadelphia, pp.73-82. May 1996. ACM Press.
- Shortcut fusion for accumulating parameters and zip-like functions
- Josef Svenningsson, ICFP '02: Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, 2002, 1-58113-487-8, 124--132, Pittsburgh, PA, USA
- Typer inference builds a short cut to deforestation
- Olaf Chitil, ICFP '99: Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, 1999, 1-58113-111-9, 249--260, Paris, France, ACM Press, New York, NY, USA
- Type-inference based short cut deforestation (nearly) without inlining
- Olaf Chitil. In Chris Clack and Pieter Koopman, editors, Draft Proceedings of the 11th International Workshop on Implementation of Functional Languages, pages 17-32, 1999. Lochem, Netherlands, September 7th-10th 1999.
- Deforestation of Functional Programs through Type Inference
- Olaf Chitil. In Wolfgang Goerigk, editor, 17 Workshops der GI-Fachgruppe 2.1.4. Programmiersprachen und Rechenkonzepte mit Schwerpunkt Softwarecomponenten, pages 121-130. Bad Honnef, Bericht Nr. 2007 des Instituts fur Informatik und Praktische Mathematik der Christian-Albrechts-Universitat zu Kiel, July 2000.
- Type-inference based deforestation of functional programs
- Olaf Chitil. PhD thesis, RWTH Aachen, October 2000.
- Warm fusion in Stratego: A case study in generation of program transformation systems
- P Johann, E Visser, Annals of Mathematics and Artificial Intelligence, 2000
- Short Cut Fusion: Proved and Improved
- Patricia Johann, SAIG 2001: Proceedings of the Second International Workshop on Semantics, Applications, and Implementation of Program Generation, 2001, 3-540-42558-6, 47--71, Springer-Verlag, London, UK
- The under-appreciated unfold
- Jeremy Gibbons and Geraint Jones, ICFP '98: Proceedings of the third ACM SIGPLAN international conference on Functional programming, 1998, 1-58113-024-4, 273--279, Baltimore, Maryland, United States, http://doi.acm.org/10.1145/289423.289455, ACM Press, New York, NY, USA
- Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
- Erik Meijer and Maarten Fokkinga and Ross Paterson, Proceedings 5th {ACM} Conf. on Functional Programming Languages and Computer Architecture, FPCA'91, Cambridge, MA, USA, 26--30 Aug 1991, 523, Springer-Verlag, Berlin, J. Hughes, 124--144, 1991
- Arithmetic coding with folds and unfolds
- Richard Bird and Jeremy Gibbons. In Johan Jeuring and Simon Peyton Jones, editors, Advanced Functional Programming 4, volume 2638 of Lecture Notes in Computer Science, pages 1-26. Springer-Verlag, 2003.
- Monadic augment and generalised short cut fusion
- N. Ghani, P. Johann, T. Uustalu, V. Vene. In Proc. of 10th ACM SIGPLAN Int. Conf. on Functional Programming, ICFP'05 (Tallinn, Sept. 2005), ACM SIGPLAN Notices, v. 40, n. 9, pp. 294-305. ACM Press, 2005
- Build, augment and destroy, universally
- N. Ghani, T. Uustalu, V. Vene. In W.-N. Chin, ed., Proc. of 2nd Asian Symp. on Programming Languages and Systems, APLAS'04 (Taipei, Nov. 2004), Lecture Notes in Computer Science (LNCS), v. 3302, pp. 327-347, Springer-Verlag, 2004.
- Concatenate, Reverse and Map Vanish For Free
- Janis Voigtländer, International Conference on Functional Programming, Proceedings, vol. 37(9) of SIGPLAN Notices, pp. 14-25, ACM Press, 2002.
- GADTs, Functoriality, Parametricity: Pick Two
- Patricia Johann, Enrico Ghiorzi, and Daniel Jeffries, 16th Logical and Semantic Frameworks with Applications (LSFA 2021) EPTCS 357, 2022, pp. 77–92.
- The Impact of seq on Free Theorems-Based Program Transformations
- Patricia Johann and Janis Voigtländer, Fundamenta Informaticae, vol. 69(1-2), pp. 63-102, 2006.
- Using Circular Programs to Deforest in Accumulating Parameters
- Janis Voigtländer, Higher-Order and Symbolic Computation, vol. 17(1-2), pp. 129-163, 2004.
- Composition of functions with accumulating parameters (proof appendix)
- Janis Voigtländer and Armin Kühnemann, Journal of Functional Programming, vol. 14(3), pp. 317-363, 2004.
- Formal Efficiency Analysis for Tree Transducer Composition
- Janis Voigtländer, Theory of Computing Systems, vol. 41(4), pp. 619-689, 2007.
- Rewriting Haskell Strings
- Duncan Coutts, Don Stewart and Roman Leshchinskiy, PADL 2007.
- Stream Fusion: From Lists to Streams to Nothing at All
- Duncan Coutts, Roman Leshchinskiy and Don Stewart.
- Selective strictness and parametricity in structural operational semantics, inequationally
- Janis Voigtländer and Patricia Johann, Theoretical Computer Science, vol. 388(1-3), pp. 290-318, 2007.
- Proving Correctness via Free Theorems: The Case of the destroy/build-Rule
- Janis Voigtländer. Partial Evaluation and Semantics-Based Program Manipulation (PEPM'08), Proceedings, pages 13-20, ACM Press, 2008.
- Semantics and Pragmatics of New Shortcut Fusion Rules
- Janis Voigtländer. Functional and Logic Programming (FLOPS'08), Proceedings, LNCS 4989:163-179, Springer-Verlag, 2008.
- A family of syntactic logical relations for the semantics of Haskell-like languages
- Patricia Johann and Janis Voigtländer, Information and Computation, vol. 207(2), pp. 341-368, 2009.
Compiler construction
- The Glasgow Haskell compiler: a technical overview
- SL Peyton Jones, CV Hall, K Hammond, WD Partain, PL Wadler, Proceedings of Joint Framework for Information Technology Technical Conference, Keele, March 1993, pp249-257.
- Type-safe, self inspecting code
- Arthur I. Baars and S. Doaitse Swierstra, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell. Snowbird, Utah, USA 69 - 79, 2004, ISBN 1-58113-850-4
Intermediate languages
- Henk: a typed intermediate language
- SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997.
- Bridging the gulf: a common intermediate language for ML and Haskell
- SL Peyton Jones, J Launchbury, MB Shields, and AP Tolmach, POPL98.
- An External Representation for the GHC Core Language
- Andrew Tolmach
- System F with Type Equality Coercions
- Martin Sulzmann, Manuel M. T. Chakravarty, and Simon Peyton Jones.
- A Single Intermediate Language That Supports Multiple Implementations of Exceptions
- Norman Ramsey and Simon Peyton Jones. PLDI 2000. 2000.
- Statically Verified Type-Preserving Code Transformations in Haskell
- Louis-Julien Guillemette and Stefan Monnier.
- Code Optimization for Lazy Functional Languages
- Urban Boquist. PhD Thesis, Chalmers University of Technology, Gothenburg, Sweden, April 1999.
- Types are calling conventions
- Maximilian C. Bolingbroke, University Of Cambridge and Simon L. Peyton Jones, Microsoft Research. Proceedings of the 2nd ACM SIGPLAN symposium on Haskell 2009. (Video of paper presentation)
Type inference
- Scripting the type inference process
- B. Heeren, J. Hage, and S. D. Swierstra. In Eighth ACM Sigplan International Conference on Functional Programming, pages 3 -- 13, New York, 2003. ACM Press.
Compilation by transformation
- A transformation-based optimiser for Haskell
- SL Peyton Jones and A Santos, Science of Computer Programming 32(1-3), pp3-47, September 1998.
- Compiling Haskell by program transformation: a report from the trenches
- SL Peyton Jones Proc European Symposium on Programming (ESOP'96), Linkping, Sweden, Springer Verlag LNCS 1058, Jan 1996.
- Compilation by transformation in non-strict functional languages
- A Santos, PhD thesis, University of Glasgow, Sept 1995.
- Playing by the rules: rewriting as a practical optimisation technique in GHC
- Simon Peyton Jones, Andrew Tolmach and Tony Hoare, Haskell Workshop 2001.
- Transforming Lazy Functions using Comportment Properties
- Ross Paterson, Programming Languages: Implementations, Logics and Programs, LNCS, vol. 1292, pp. 111-125, Springer, Southampton, UK, 1997.
- On the Fundamental Limitations of Transformational Design
- Jeroen Voeten, ACM Transactions on Design Automation of Electronic Systems, Vol. 6, No. 4, October 2001, pages 533–552.
Type errors
- Improving type-error messages in functional languages
- B. Heeren, J. Jeuring, S. D. Swierstra, and P. A. Alcocer. Technical Report UU-CS-2002-009, Institute of Information and Computing Science, University Utrecht, Netherlands, February 2002