\[\newcommand{\andalso}{\quad\quad} \newcommand{\infabbrev}[2]{\infax{#1 \quad\eqdef\quad #2}} \newcommand{\infrule}[2]{\displaystyle \dfrac{#1}{#2}} \newcommand{\ar}{\rightarrow} \newcommand{\Int}{\mathtt{Int}} \newcommand{\Bool}{\mathtt{Bool}} \newcommand{\becomes}{\Downarrow} \newcommand{\trule}[1]{(\textbf{#1})} \newcommand{\FV}[1]{\mathtt{fv}(#1)} \newcommand{\FTV}[1]{\mathtt{ftv}(#1)} \newcommand{\BV}[1]{\mathtt{bv}(#1)} \newcommand{\compiles}[1]{\text{C}\llbracket{#1}\rrbracket} \newcommand{\exec}[1]{\text{E}\llbracket{#1}\rrbracket} \renewcommand{\t}[1]{\mathtt{#1}} \newcommand{\ite}[3]{\text{if }#1\text{ then }#2\text{ else }#3} \]

Building a modern functional compiler from first principles.

Stephen Diehl

In 2014 I wrote a short tutorial about building a small imperative language in Haskell that compiled into LLVM. I was extremely happy with the effect the tutorial seemed to have, and the warm response I got from so many people was very encouraging.

I've done a great bit of thinking about what the most impactful topic I could write about in 2015 could be; and decided throughout this year I will follow up with a large endeavor for another project-based tutorial on building a simple functional programming language from first principles.

This is a nontrivial topic and is unfortunately very much underserved, the knowledge to build such a modern functional language is not widely disseminated among many programmers. The available resources most often discuss language theory in depth while completely glossing over the engineering details. I wished to write a project-based tutorial that included the engineering details and left the reader with a fully functional toy language at the end that could be extended for further projects.

We will build a small functional language called Fun which is a partial Haskell 2010 toy language; complete with a parser, type inference, datatypes, pattern matching, desugaring, typeclasses, higher-kinded types, monadic IO, arbitrary-rank polymorphism, records, Core language, STG intermediate language, lazy evaluation, interpreter, native code generator, a runtime, and several optimization passes.

As with most of my writing, this is the pre-edited rough cut version, which I will refine over time.


Addendum

License

This written work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. You may reproduce and edit this work with attribution for all non-commercial purposes.

The included source is released under the terms of the MIT License.