research-article

The architecture of the Utrecht Haskell compiler

Authors:

S. Doaitse SwierstraAuthors Info & Claims

Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell

Pages 93 - 104

https://doi.org/10.1145/1596638.1596650

Published: 03 September 2009 Publication History

Abstract

In this paper we describe the architecture of the Utrecht Haskell Compiler (UHC).

UHC is a new Haskell compiler, that supports most (but not all) Haskell 98 features, plus some experimental extensions. It targets multiple backends, including a bytecode interpreter backend and a whole-program analysis backend, both via C. The implementation is rigorously organized as stepwise transformations through some explicit intermediate languages. The tree walks of all transformations are expressed as an algebra, with the aid of an Attribute Grammar based preprocessor. The compiler is just one materialization of a framework that supports experimentation with language variants, thanks to an aspect-oriented internal organization.

Supplementary Material

JPG File (thearchitecturesoftheutrechthaskellcompileronvimeo.jpg)

Download
17.04 KB

MP4 File (thearchitecturesoftheutrechthaskellcompileronvimeo.mp4)

Download
124.43 MB

References

[1]

L. Augustsson. The HBC compiler. http://www.cs.chalmers.se/~augustss/hbc/hbc.html, 1998.

[2]

R. Bird and O. de Moor.The algebra of programming.Prentice Hall, 1996.

Digital Library

[3]

R. S. Bird.Using Circular Programs to Eliminate Multiple Traversals of Data.Acta Informatica, 21:239--250, 1984.

Digital Library

[4]

H. Boehm. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/, 2006.

[5]

H. Boehm and M. Weiser. Garbage Collection in an Uncooperative Environment. Software Practice and Experience, pages 807--820, Sep 1988.

Digital Library

[6]

M. Bolingbroke and S. Peyton Jones.Types are calling conventions (submitted to Haskell Symposium 2009).2009.

Digital Library

[7]

U. Boquist. Code Optimisation Techniques for Lazy Functional Languages, PhD Thesis. Chalmers University of Technology, 1999.

[8]

U. Boquist and T. Johnsson.The GRIN Project: A Highly Optimising Back End For Lazy Functional Languages. In Selected papers from the 8th International Workshop on Implementation of Functional Languages, 1996.

Digital Library

[9]

A. Dijkstra.Stepping through Haskell.PhD thesis, Utrecht University, Department of Information and Computing Sciences, 2005.

[10]

A. Dijkstra, J. Fokker, and S. D. Swierstra. The Structure of the Essential Haskell Compiler, or Coping with Compiler Complexity. In Implementation of Functional Languages, 2007.

[11]

A. Dijkstra, J. Fokker, and S. D. Swierstra.UHC Utrecht Haskell Compiler. http://www.cs.uu.nl/wiki/UHC, 2009.

[12]

A. Dijkstra and S. D. Swierstra. Ruler: Programming Type Rules. In Functional and Logic Programming: 8th International Symposium, FLOPS 2006, Fuji-Susono, Japan, April 24--26, 2006, number 3945 in LNCS, pages 30--46. Springer-Verlag, 2006.

Digital Library

[13]

K.-F. Faxen.A Static Semantics for Haskell. Journal of Functional Programming, 12(4):295, 2002.

Digital Library

[14]

J. Fokker and S. D. Swierstra. Abstract interpretation of functional programs using an attribute grammar system. In A. Johnstone and J. Vinju, editors, Language Descriptions, Tools and Applications (LDTA08), 2008.

[15]

GHC Team. The New GHC/Hugs Runtime System. http://citeseer.ist.psu.edu/marlow98new.html, 1998.

[16]

Haskell' Committee. Haskell Prime. http://hackage.haskell.org/trac/haskell--prime/, 2009.

[17]

B. Heeren, A. v. IJzendoorn, and J. Hage.Helium, for learning Haskell. http://www.cs.uu.nl/helium/, 2005.

[18]

D. Himmelstrup, S. Bronson, and A. Seipp. LHC Haskell Compiler. http://lhc.seize.it/, 2009.

[19]

ISO. Common language infrastructure (ISO/EIC standard 23271). ECMA, 2006.

[20]

M. P. Jones.Typing Haskell in Haskell.In Haskell Workshop, 1999.

[21]

M. P. Jones.Hugs 98.http://www.haskell.org/hugs/, 2003.

[22]

D. Knuth.Semantics of context-free languages.Mathematical Systems Theory, 2(2):127--145, 1968.

[23]

D. Knuth. Literate Programming. Journal of the ACM, (42):97--111, 1984.

Digital Library

[24]

R. Lammel and S. Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming.In Types In Languages Design And Implementation, pages 26--37, 2003.

Digital Library

[25]

C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis&Transformation.In Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO'04), Palo Alto, California, Mar 2004.

Digital Library

[26]

S. Marlow and S. Peyton Jones. The Glasgow Haskell Compiler. http://www.haskell.org/ghc/, 2004.

[27]

J. Meacham. Jhc Haskell Compiler. http://repetae.net/computer/jhc/, 2009.

[28]

S. Peyton Jones. Compiling Haskell by program transformation: a report from the trenches.In European Symposium On Programming, pages 18--44, 1996.

Digital Library

[29]

S. Peyton Jones.Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In Engineering theories of software construction, Marktoberdorf Summer School, 2002.

[30]

S. Peyton Jones. Haskell 98, Language and Libraries, The Revised Report.Cambridge Univ. Press, 2003.

[31]

S. Peyton Jones and S. Marlow. Secrets of the Glasgow Haskell Compiler inliner. Journal of Functional Programming, pages 393--434, 2002.

Digital Library

[32]

S. Peyton Jones and E. Meijer.Henk: A Typed Intermediate Language. In Workshop on Types in Compilation, 1997.

[33]

T. Shackell, N. Mitchell, A. Wilkinson, et al. YHC York Haskell Compiler. http://haskell.org/haskellwiki/Yhc, 2009.

[34]

S. D. Swierstra, P. Azero Alocer, and J. Saraiva. Designing and Implementing Combinator Languages. In 3rd Advanced Functional Programming, number 1608 in LNCS, pages 150--206. Springer-Verlag, 1999.

[35]

M. Viera, S. D. Swierstra, and W. S. Swierstra. Attribute grammars fly first class: How to do aspect oriented programming in haskell. In International Conference on Functional programming (ICFP '09), New York, NY, USA, 2009. ACM Press.

Digital Library

[36]

E. Visser. Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5. In A. Middeldorp, editor, Rewriting Techniques and Applications (RTA'01), number 2051 in LNCS, pages 357--361. Springer-Verlag, 2001.

Digital Library

[37]

E. Visser. Stratego Home Page. http://www.program--transformation.org/Stratego/WebHome, 2005.

[38]

York Functional Programming Group. NHC98 Haskell Compiler. http://haskell.org/nhc98/, 2007.

Cited By

Podlovics PHruska CPénzes A(2021)A Modern Look at GRIN, an Optimizing Functional Language Back EndActa Cybernetica10.14232/actacyb.28296925:4(847-876)Online publication date: 3-Feb-2021
https://doi.org/10.14232/actacyb.282969
Stelle GStefanovic DOlivier SForrest S(2019)Cactus Environment MachineMicrobial Metabolic Engineering10.1007/978-3-030-14805-8_2(24-43)Online publication date: 21-Feb-2019
https://doi.org/10.1007/978-3-030-14805-8_2
Fernandes JMartins PPardo ASaraiva JViera M(2018)Memoized zipper-based attribute grammars and their higher order extensionScience of Computer Programming10.1016/j.scico.2018.10.006Online publication date: Nov-2018
https://doi.org/10.1016/j.scico.2018.10.006
Show More Cited By

Index Terms

The architecture of the Utrecht Haskell compiler
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Preprocessors
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

The Intel labs Haskell research compiler
Haskell '13: Proceedings of the 2013 ACM SIGPLAN symposium on Haskell

The Glasgow Haskell Compiler (GHC) is a well supported optimizing compiler for the Haskell programming language, along with its own extensions to the language and libraries. Haskell's lazy semantics imposes a runtime model which is in general difficult ...
The Intel labs Haskell research compiler
Haskell '13

The Glasgow Haskell Compiler (GHC) is a well supported optimizing compiler for the Haskell programming language, along with its own extensions to the language and libraries. Haskell's lazy semantics imposes a runtime model which is in general difficult ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell Symposium

Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell

September 2009

148 pages

ISBN:9781605585086

DOI:10.1145/1596638

Program Chair:
Stephanie Weirich
University of Pennsylvania, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '09

Sponsor:

ICFP '09: ACM SIGPLAN International Conference on Functional Programming

September 3, 2009

Edinburgh, Scotland

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Podlovics PHruska CPénzes A(2021)A Modern Look at GRIN, an Optimizing Functional Language Back EndActa Cybernetica10.14232/actacyb.28296925:4(847-876)Online publication date: 3-Feb-2021
https://doi.org/10.14232/actacyb.282969
Stelle GStefanovic DOlivier SForrest S(2019)Cactus Environment MachineMicrobial Metabolic Engineering10.1007/978-3-030-14805-8_2(24-43)Online publication date: 21-Feb-2019
https://doi.org/10.1007/978-3-030-14805-8_2
Fernandes JMartins PPardo ASaraiva JViera M(2018)Memoized zipper-based attribute grammars and their higher order extensionScience of Computer Programming10.1016/j.scico.2018.10.006Online publication date: Nov-2018
https://doi.org/10.1016/j.scico.2018.10.006
Martins PFernandes JSaraiva JVan Wyk ESloane A(2016)Embedding attribute grammars and their extensions using functional zippersScience of Computer Programming10.1016/j.scico.2016.03.005132:P1(2-28)Online publication date: 15-Dec-2016
https://dl.acm.org/doi/10.1016/j.scico.2016.03.005
Fernandes JMartins PPardo ASaraiva JViera M(2016)Memoized Zipper-Based Attribute GrammarsProgramming Languages10.1007/978-3-319-45279-1_4(46-61)Online publication date: 17-Sep-2016
https://doi.org/10.1007/978-3-319-45279-1_4
Ryu S(2016)Scalable framework for parsingSoftware—Practice & Experience10.1002/spe.238046:9(1219-1238)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1002/spe.2380
Bransen JDijkstra ASwierstra SAsai KSagonas K(2015)Incremental Evaluation of Higher Order AttributesProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation10.1145/2678015.2682541(39-48)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2678015.2682541
Verstoep HHage JAsai KSagonas K(2015)Polyvariant Cardinality Analysis for Non-strict Higher-order Functional LanguagesProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation10.1145/2678015.2682536(139-142)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2678015.2682536
Bransen JBinsbergen LClaessen KDijkstra A(2015)Linearly Ordered Attribute Grammar Scheduling Using SAT-SolvingProceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Volume 903510.1007/978-3-662-46681-0_24(289-303)Online publication date: 11-Apr-2015
https://dl.acm.org/doi/10.1007/978-3-662-46681-0_24
Bransen JDijkstra ASwierstra SChin WHage J(2014)Lazy stateless incremental evaluation machinery for attribute grammarsProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543735(145-156)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543735
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents