Write You a Haskell: Building a modern functional compiler from first principles
Now this is very interesting!<p>There are plenty of compiler writing tutorials for conservative, imperative programming languages with a straightforward static type system (like C).<p>I did study a little bit of compilers for functional languages from Simon Peyton-Jones' old book "The Implementation of Functional Programming Languages" [0]. It predates the Haskell programming language and uses a contemporary research language called Miranda as the target as well as the "host" language.<p>... which brings me to another topic: Monads. The SPJ book has a few chapters on implementing a Hindley-Milner -style type inference algorithm. It's written in Miranda without any Monads and uses a clever trick for coming up with unique temporary type names. There's an infinite list of integers [0..], which is "split" when traversing the syntax tree so that the left branch of the recursion tree gets the even numbers and the right branch gets the odd numbers.<p>The method works fine and is indeed very clever but try comparing that code to the same algorithm re-implemented (by me) with Monads (State and Error monads + transformer) [1]. The original algorithm is rather long and hard to follow (because lists of unique integers are passed to all functions).<p>I had a blast writing this algorithm, and I wanted to share it. It's been a few years since I last worked with it. It was my first non-trivial use of monads and I really like how it turned out in the end.<p>[0] <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/" rel="nofollow">http://research.microsoft.com/en-us/um/people/simonpj/papers...</a>
[1] <a href="https://github.com/rikusalminen/funfun/blob/master/FunFun/TypeChecker.hs" rel="nofollow">https://github.com/rikusalminen/funfun/blob/master/FunFun/Ty...</a>