Write You a Haskell: Building a modern functional compiler from first principles
Now this is very interesting!There are plenty of compiler writing tutorials for conservative, imperative programming languages with a straightforward static type system (like C).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.... 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.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).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.[0] http://research.microsoft.com/en-us/um/people/simonpj/papers...
[1] https://github.com/rikusalminen/funfun/blob/master/FunFun/Ty...