Research papers/Compilation
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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.
- 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