Home

The Essential Haskell Compiler

On the same subject as the Scheme compiler in 90 Minutes, is the Essential Haskell Compiler. From the HC&AR summary:

The purpose of the EHC project is to provide a description a Haskell compiler which is as understandable as possible so it can be used for education as well as research


In order to avoid overwhelming the innocent reader, the description of the compiler is organised as a series of increasingly complex steps. Each step corresponds to a Haskell subset which itself is an extension of the previous step. The first step starts with the essentials, namely typed lambda calculus.



Sounds like BC Pierce's Types and Programming Languages.
Also notable is that EHC uses Utrecht's Attribute Grammars, which are interesting in their own right.

By shapr at 2004-11-11 16:56 | Functional | Implementation | Software Engineering | other blogs | 12545 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The Structure of the Essential Haskell Compiler

On reddit, dons posted a link to The Structure of the Essential Haskell Compiler.

It's a recent paper that provides a high-level overview of the structure of the EHC compiler. The architecture involves transformations through up to eight intermediate languages (depending on how you count), plus a target language such as C or LLVM. The goal of the architecture is to manage complexity at multiple levels: design, implementation, description, and maintenance.

I found section 3.1 particularly interesting. Language semantics can be implemented by a tree walk over the parse tree, and it ought to be possible to implement this as a fold parameterized over an algebra, i.e. a catamorphism, leading to a clean and well-factored implementation. However, in practice in real compilers, there are cross-cutting dependencies and other complexities — five of which are identified in the paper — that tend to lead to more ad-hoc recursive functions being developed. The authors claim to recover the simplicity of the catamorphism approach by the use of UUAGC, the "Utrecht University Attribute Grammar Compiler" mentioned by shapr in the topic.

By Anton van Straaten at Fri, 2007-12-07 23:36 | login or register to post comments