https://wiki.haskell.org/api.php?action=feedcontributions&user=Sqrt&feedformat=atomHaskellWiki - User contributions [en]2024-03-28T08:46:04ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Research_papers/Compilation&diff=18095Research papers/Compilation2008-01-05T19:16:18Z<p>Sqrt: Corrected link</p>
<hr />
<div>__TOC__<br />
<br />
==Compiler Analyses==<br />
<br />
===CPR===<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/cpr/index.htm Constructed Product Result Analysis for Haskell]<br />
:Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones, Journal of Functional Programming 14(2), March 2004, pp 211-245.<br />
<br />
===Usage analysis===<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/usage-types/usage.htm Simple Polymorphic Usage Analysis]<br />
:Keith Wansbrough (2002), PhD thesis, Computer Laboratory, University of Cambridge.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/usage-types/usage.htm Simple Usage Polymorphism]<br />
:Keith Wansbrough and Simon Peyton Jones; Workshop on Types In Compilation 2000.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/usage-types/usage.htm Once Upon a Polymorphic Type]<br />
:Keith Wansbrough and Simon Peyton Jones, POPL'99.<br />
<br />
===Inlining===<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/inlining/index.htm Secrets of the Glasgow Haskell Compiler inliner]<br />
:Simon Peyton Jones and Simon Marlow. IDL'99; revised version Journal of Functional Programming 12(4), July 2002, pp393-434.<br />
<br />
===Laziness===<br />
<br />
;[http://www.cse.ogi.edu/~jl/Papers/update.ps Avoiding Unnecessary Updates]<br />
:John Hughes, John Launchbury, Andy Gill, Simon Marlow, Simon Peyton Jones, and Philip Wadler. 1993 Glasgow Workshop on Functional Programming.<br />
<br />
===Strictness===<br />
<br />
;[http://www.cse.ogi.edu/~jl/Papers/implementing.ps Implementing Projection-based Strictness Analysis]<br />
:Ryszard Kubiak, John Hughes, John Launchbury. Functional Programming 1991: 207-224 <br />
<br />
;[http://www.cse.ogi.edu/~jl/Papers/polyProj.ps Projections for Polymorphic First-Order Strictness Analysis]<br />
:John Hughes, John Launchbury. Mathematical Structures in Computer Science 2(3): 301-326 (1992)<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/simple-strictnes-analyser.ps.gz&pub=SpringerMeasuring the effectiveness of a simple strictness analyser]<br />
:SL Peyton Jones and WD Partain, Functional Programming, Glasgow 1993, ed Hammond and O'Donnell, Springer Verlag Workshops in Computing, 1993, pp201-220.<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/projections.html Compiling Laziness using Projections]<br />
:Ross Paterson, Static Analysis Symposium, LNCS, vol. 1145, pp. 255-269, Springer, Aachen, Germany, 1996.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/dissertation.ps.gz Projection-based Strictness Analysis - Theoretical and Practical Aspects]<br />
:Ralf Hinze. Inauguraldissertation, Universitt Bonn, November 1995.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/stricttime/stricttime.ps.gz Strictness analysis aids time analysis]<br />
:Philip Wadler. 15'th ACM Symposium on Principles of Programming Languages, San Diego, California, January 1988.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/strictnonflat/strictnonflat.ps.gz Strictness analysis on non-flat domains (by abstract interpretation over finite domains)]<br />
:Philip Wadler. Chapter in Samson Abramsky and Chris Hankin, editors, Abstract Interpretation, Ellis Horwood, 1987.<br />
<br />
;[http://www.c3.lanl.gov/~kei/gfp89.ps Strictness Analysis: Proved and Improved]<br />
:Kei Davis and Philip Wadler. 1989 Glasgow Workshop on Functional Programming. August 1989.<br />
<br />
;[http://www.c3.lanl.gov/~kei/gfp90.ps Strictness Analysis in 4D]<br />
:Kei Davis. 1990 Glasgow Workshop on Functional Programming. August 1990.<br />
<br />
===Abstract interpretation===<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/Papers/cds-padova.ps Fast Abstract Interpretation Using Sequential Algorithms]<br />
:John Hughes and Alex Ferguson. The Workshop on Static Analysis, WSA 1993: 45-59<br />
<br />
===Lambda lifting===<br />
<br />
;[http://research.microsoft.com/users/simonpj/papers/fully-lazy-lambda-lifter.ps.gz A modular fully-lazy lambda lifter in Haskell]<br />
:SL Peyton Jones and D Lester, Software Practice and Experience 21(5), May 1991, pp479-506.<br />
<br />
===Common subexpression elimination (CSE)===<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/1997/1904/index.html Common Subexpression Elimination in a Lazy Functional Language]<br />
: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.<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/1998/1905/index.html Common Subexpressions are Uncommon in Lazy Functional Languages]<br />
: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.<br />
<br />
===Let floating===<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/float.ps.gz&pub=ACM Let-floating: moving bindings to give faster programs]<br />
:(ICFP '96), SL Peyton Jones, WD Partain, A Santos, Proc International Conference on Functional Programming, Philadelphia (ICFP'96), May 1996.<br />
<br />
===Free variables and substitution===<br />
<br />
;[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]<br />
:Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, Snowbird, Utah, USA, 1-9 2004 ISBN 1-58113-850-4<br />
<br />
;[http://www.cs.ioc.ee/~tarmo/papers/cmcs03.ps.gz Substitution in non-wellfounded syntax with variable binding]<br />
: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. <br />
<br />
;[http://www.cs.ioc.ee/~tarmo/papers/merlin03-dl.ps.gz Explicit substitutions and higher-order syntax] <br />
: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.<br />
<br />
===Constructor specialisation===<br />
<br />
;[http://research.microsoft.com/~simonpj/papers/spec-constr/index.htm Constructor specialisation for Haskell programs]<br />
:Simon Peyton Jones. Submitted to ICFP 2007. <br />
<br />
===Fusion and deforestation===<br />
<br />
See also [[Research_papers/Data_structures#Lists|papers on lists]]<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/andy-thesis.ps.gz Cheap deforestation for non-strict functional languages]<br />
:A Gill, PhD thesis, University of Glasgow, Jan 1996.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/deforestation-short-cut.ps.Z A short cut to deforestation]<br />
:A Gill, SL Peyton Jones, J Launchbury, Proc Functional Programming Languages and Computer Architecture (FPCA'93), Copenhagen, June 1993, pp223-232.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps.gz Deforestation: transforming programs to eliminate trees]<br />
:Philip Wadler. Theoretical Computer Science, (Special issue of selected papers from 2'nd European Symposium on Programming), 73: 231-248, 1990.<br />
<br />
;Shortcut Deforestation in Calculational Form<br />
: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.<br />
<br />
;[http://www.ipl.t.u-tokyo.ac.jp/~onoue/pub/ifip97.ps.gz A Calculational Fusion System HYLO]<br />
: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.<br />
<br />
;[http://www.ipl.t.u-tokyo.ac.jp/~hu/pub/icfp96.ps.gz Deriving Structural Hylomorphisms from Recursive Definitions]<br />
:Z. Hu, H. Iwasaki, M. Takeichi, ACM SIGPLAN International Conference on Functional Programming (ICFP'96), Philadelphia, pp.73-82. May 1996. ACM Press.<br />
<br />
;[http://www.cs.chalmers.se/~josefs/publications/fusion.ps Shortcut fusion for accumulating parameters and zip-like functions]<br />
: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<br />
<br />
;[http://doi.acm.org/10.1145/317636.317907 Typer inference builds a short cut to deforestation]<br />
: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<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/1999/1910/index.html Type-inference based short cut deforestation (nearly) without inlining] <br />
: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.<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2000/1900/index.html Deforestation of Functional Programs through Type Inference]<br />
: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.<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2000/1815/index.html Type-inference based deforestation of functional programs]<br />
:Olaf Chitil. PhD thesis, RWTH Aachen, October 2000.<br />
<br />
;[http://citeseer.ist.psu.edu/johann00warm.html Warm fusion in Stratego: A case study in generation of program transformation systems]<br />
:P Johann, E Visser, Annals of Mathematics and Artificial Intelligence, 2000<br />
<br />
;[http://crab.rutgers.edu/~pjohann/saig01.pdf Short Cut Fusion: Proved and Improved]<br />
: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<br />
<br />
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#unfold The under-appreciated unfold]<br />
: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<br />
<br />
;[http://citeseer.ist.psu.edu/meijer91functional.htm Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire]<br />
: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<br />
<br />
;[http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/arith.pdf Arithmetic coding with folds and unfolds]<br />
: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.<br />
<br />
;[http://www.cs.ut.ee/~varmo/papers/icfp05.ps.gz Monadic augment and generalised short cut fusion]<br />
: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<br />
<br />
;[http://www.cs.ut.ee/~varmo/papers/aplas04.ps.gz Build, augment and destroy, universally]<br />
: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.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/p114-voigtlaender.pdf Concatenate, Reverse and Map Vanish For Free]<br />
:Janis Voigtländer, International Conference on Functional Programming, Proceedings, vol. 37(9) of SIGPLAN Notices, pp. 14-25, ACM Press, 2002.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/seqFinal.pdf The Impact of seq on Free Theorems-Based Program Transformations]<br />
:Patricia Johann and Janis Voigtländer, Fundamenta Informaticae, vol. 69(1-2), pp. 63-102, 2006.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/HOSC.pdf Using Circular Programs to Deforest in Accumulating Parameters]<br />
:Janis Voigtländer, Higher-Order and Symbolic Computation, vol. 17(1-2), pp. 129-163, 2004.<br />
<br />
;[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])<br />
:Janis Voigtländer and Armin Kühnemann, Journal of Functional Programming, vol. 14(3), pp. 317-363, 2004.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/TOCS.pdf Formal Efficiency Analysis for Tree Transducer Composition] <br />
:Janis Voigtländer, Theory of Computing Systems, vol. 41(4), pp. 619-689, 2007.<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/papers/CSL06.html Rewriting Haskell Strings]<br />
:Duncan Coutts, Don Stewart and Roman Leshchinskiy, PADL 2007.<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/papers/CLS07.html Stream Fusion: From Lists to Streams to Nothing at All]<br />
:Duncan Coutts, Roman Leshchinskiy and Don Stewart.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/TCS.pdf Selective strictness and parametricity in structural operational semantics, inequationally]<br />
:Janis Voigtländer and Patricia Johann, Theoretical Computer Science, vol. 388(1-3), pp. 290-318, 2007.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/pepm09-voigtlaender.pdf Proving Correctness via Free Theorems: The Case of the destroy/build-Rule]<br />
:Janis Voigtländer. Workshop on Partial Evaluation and Program Manipulation (PEPM'08), Proceedings, ACM Press, 2008.<br />
<br />
==Compiler construction==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/grasp-jfit.ps.Z The Glasgow Haskell compiler: a technical overview]<br />
: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.<br />
<br />
;[http://www.cs.uu.nl/people/doaitse/papers/2003/TypeSafeSelfInspecting.pdf Type-safe, self inspecting code]<br />
: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<br />
<br />
==Intermediate languages==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/henk.ps.gz Henk: a typed intermediate language]<br />
:SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997.<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/neutral.ps.gz&pub=ACM Bridging the gulf: a common intermediate language for ML and Haskell]<br />
:SL Peyton Jones, J Launchbury, MB Shields, and AP Tolmach, POPL98.<br />
<br />
;[http://haskell.org/ghc/docs/papers/core.ps.gz An External Representation for the GHC Core Language]<br />
:Andrew Tolmach<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/SCP06.html System F with Type Equality Coercions]<br />
:Martin Sulzmann, Manuel M. T. Chakravarty, and Simon Peyton Jones.<br />
<br />
;[http://research.microsoft.com/Users/simonpj/Papers/c--exn-pldi.ps.gz A Single Intermediate Language That Supports Multiple Implementations of Exceptions]<br />
:Norman Ramsey and Simon Peyton Jones. PLDI 2000. 2000.<br />
<br />
;[http://www.iro.umontreal.ca/~monnier/tct.pdf Statically Verified Type-Preserving Code Transformations in Haskell]<br />
:Louis-Julien Guillemette and Stefan Monnier.<br />
<br />
==Type inference==<br />
<br />
;[http://www.cs.uu.nl/groups/ST/stbib/swierstra-by-year/HHS-scripting.bib Scripting the type inference process]<br />
: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.<br />
<br />
==Compilation by transformation==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/comp-by-trans-scp.ps.gz A transformation-based optimiser for Haskell]<br />
:SL Peyton Jones and A Santos, Science of Computer Programming 32(1-3), pp3-47, September 1998.<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gz&pub=18 Compiling Haskell by program transformation: a report from the trenches]<br />
:SL Peyton Jones Proc European Symposium on Programming (ESOP'96), Linkping, Sweden, Springer Verlag LNCS 1058, Jan 1996.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/santos-thesis.ps.gz Compilation by transformation in non-strict functional languages]<br />
:A Santos, PhD thesis, University of Glasgow, Sept 1995.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/rules.htm Playing by the rules: rewriting as a practical optimisation technique in GHC]<br />
:Simon Peyton Jones, Andrew Tolmach and Tony Hoare, Haskell Workshop 2001.<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/embeddings.html Transforming Lazy Functions using Comportment Properties]<br />
:Ross Paterson, Programming Languages: Implementations, Logics and Programs, LNCS, vol. 1292, pp. 111-125, Springer, Southampton, UK, 1997.<br />
<br />
==Type errors==<br />
<br />
;[http://www.cs.uu.nl/groups/ST/stbib/swierstra-by-year/heeren2002improving.bib Improving type-error messages in functional languages]<br />
: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<br />
<br />
[[Category:Research]]</div>Sqrt