4 ms·
Now this is very interesting! There are plenty of compiler writing tutorials for conservative, imperative programming languages with a straightforward static t
by exDM69 12y ago
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/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers...
[1] https://github.com/rikusalminen/funfun/blob/master/FunFun/TypeChecker.hs https://github.com/rikusalminen/funfun/blob/master/FunFun/Ty...
- thu 12y agoI think the online version of that book actually uses Haskell (but the text still refers to Miranda).
- exDM69 12y agoI don't think so, but Miranda and Haskell are very alike so it's easy to be mistaken.
- pselbert 12y agoThat seems like an easy mistake to make from what I remember in reading the origin of Haskell. They had issue with the licensing and cost of Miranda and struck out to build upon it. Here's the original article, "A History of Haskell: Being Lazy With Class"[0] [0]: http://research.microsoft.com/en-us/um/people/simonpj/Papers/history-of-haskell/history.pdf http://research.microsoft.com/en-us/um/people/simonpj/Papers...
- dons 12y agoNote that SPJ's book (1987) pre-dates Wadler's popularization of monads (1992) by a good 5 years, and Moggi's idea to use monads to describe different notions of computation by 4 years^1. So they're missing for a reason. 1. http://www.cs.cmu.edu/afs/cs/user/crary/www/819-f09/Moggi91.pdf http://www.cs.cmu.edu/afs/cs/user/crary/www/819-f09/Moggi91....
- exDM69 12y agoYes, I know that. There's a long and interesting history on the "round hole, square peg" problem of I/O, side effects and functional programming. My sole intent was to emphasize, using a practical example, how neat and elegant monads can be at best.
- vajrabum 12y agoDon't forget that Simon Peyton Jones 2nd book on compiling functional languages written with PJ Lester is also out of print but available from him directly on the web and includes source code from the book. Way fun, if slightly dated stuff. http://research.microsoft.com/en-us/um/people/simonpj/Papers/pj-lester-book/ http://research.microsoft.com/en-us/um/people/simonpj/Papers...
- YAYERKA 12y agoThanks for sharing, and for anyone else reading you might also like the following book--`Modern Compiler Implementation in ML' by Appel. (http://www.cs.princeton.edu/~appel/modern/ml/ http://www.cs.princeton.edu/~appel/modern/ml/)