A continuation of Stephen Diehl's Write You a Haskell
The goal of this project is to try and, in some sense, complete Steven Diehl’s Write You a Haskell. I don’t know if my continuation will have the same level of detail as Diehl’s original work. I plan on having my own project grow linearly as this progresses, but I will attempt to save the work into a separate Github repository at key milestones as I progress. This is a learning experience for me too - code won’t be perfect, and I may make large mistakes. I’m following algorithms presented by papers where possible, and GHC itself otherwise.
I don’t plan on targeting
llvm. I plan on targetting
Java. Partly this is because I’ve written garbage collectors before and don’t feel the need to do it again. UPDATE: As of returning to this project, I am now considering targeting
C instead, for two reasons. It makes the discussion of the runtime system more interesting, and should make it considerably easier to add an NCG in the future. Considerations will continue. I may start by targeting
Java and then have a section later about adding a
C backend. A
Java backend will (probably) not have an FFI that can understand subclasses. See Eta if you want that.
We’ll be beginning after chapter 7, with the
Poly language as a starting point. We’ll be building off of plans laid out in chapter 8, and using some of the parsing ideas presented in chapter 9. The parser will be an Alex lexer + Parsec parser, purely because I’m more comfortable with Parsec then with Happy. Feel free to use Happy instead, as an exercise.
Finally, before beginning, a few words which Diehl omits, presumably since the project never reached a point where they would matter. A compiler, even for a toy language, can become a monolithic piece of software, and there will be lots of code, in lots of files, many of which have similar names (
STGExpr, all containing a type called
Expr). Therefore it is critically important that we remain organized and make good use of qualified imports. I think I have a minority opinion that GHC’s use of unqualified module names can make dependencies hard to find and follow for little gain. I’ve rearranged the modules from Chapter 7 as follows:
| - Compiler | - Parser | - Lexer.hs \ - Parser.hs | - PhSyn | - PhExpr.hs # The abstract syntax of ProtoHaskell expressions \ - PhType.hs # The abstract representation of ProtoHaskell types | - TypeCheck # Everything related to type-checking Eventually includes Core \ - TcInfer.hs \ - Types # Wide-spread type utilities, like TyEnv \ - TyEnv.hs | - Control \ - Monad # Custom monadic logic will live here If it is needed in many places | - Supply | - Class.hs \ - Supply.hs # Monad Transformer for monads which store a supply of some type. Thin wrapper around StateT, and will usually be used for names. | - Interpreter | - Eval.hs \ - Main.hs \ - Utils \ - Outputable.hs # Re-exports most of the pretty library and an Outputable class
This may seem like overkill now, but the organization will be nice later, even if several folders never grow beyond 2 to 4 modules.
By default, I have the following extensions enabled:
ApplicativeDo BangPatterns FlexibleInstances FunctionalDependencies GeneralizedNewtypeDeriving LambdaCase MultiParamTypeClasses NamedFieldPuns OverloadedStrings PatternGuards TupleSections ViewPatterns
I won’t include
LANGUAGE pragmas for these extensions. Note that
FlexibleContexts is not on (or implied by) this list. I may occasionally comment on their usage, since I suspect this document will turn out to be attractive towards relatively new Haskellers.
For the same reason as the above, I will try to provide very brief overviews of Haskell idioms the first time they appear, usually a sentence or less.
Finally, it is not my goal that the ProtoHaskell Compiler should be able to compile itself.
Control.Monad.Supply.Class already uses
UndecidableInstances and I would prefer ease of coding over restricting the subset of GHC-Haskell that I use.