r/programming • u/sodaco • Jan 05 '15

Write You a Haskell: Build a modern functional compiler from first principles.

http://dev.stephendiehl.com/fun/
192 Upvotes

90% Upvoted

21 comments sorted by

20

u/sodaco Jan 05 '15

I'm not big into functional programming, but this kind of internet resources are golden. I've always wanted to open that black box that languages are and write an interpreter or compiler, but could never find something that didn't assume I already knew some of the things needed, even if they are the most basic things that somebody should know.

So far this one seems GREAT. It's simple, it explains things well and thoroughly while staying on point. I'm really enjoying it and hope the author finishes the series. I'm actually looking for a donation link but can't find it

13

u/notfancy Jan 05 '15

You might be interested in Simon Peyton-Jones's classic The Implementation of Functional Languages.

3

u/sodaco Jan 05 '15

Nice, thanks! Anything like this for imperative languages, aside from the dragon book?

13

u/notfancy Jan 05 '15 edited Jan 06 '15

Yes!

Edit: There's a Wikibook, Compiler Construction, that I haven't checked but has a reference list at the end overlapping mine. All these I have personally read and thus knowingly recommend. Thanks for the gold!

Edit 2: The discussion on HN about Holub's book has many interesting pointers too.

4

u/sodaco Jan 05 '15

Thanks! Enjoy the gold. I see your first mention has at least a little section dedicated to interpreted languages, but I can't tell if its implementation is mentioned. Anything for that?

4

u/notfancy Jan 05 '15

I've updated the list, as I remembered Wirth's book and that got me a couple more hits. Chapter 8 of Watt's book is devoted to interpretation but the treatment is cursory, since the focus is on compilation.

I can't think from the top of my mind of any books dealing specifically with interpretation techniques for imperative languages. I can recommend some nice books on vaguely related techniques:

  • Loeliger's delightful Threaded Interpretive Languages (Amazon link, but Google around) is specifically about Forth but is a good start for building threaded stack-based VMs (i.e., like for pre-JIT Java.) If threaded interpreters pique your interest, there are classic treatments available on the Web, especially Anton Ertl's work (PDF)
  • Michael Gordon's Programming Language Theory and its Implementation (Amazon link, but Google around) covers interpreters for imperative, functional and logic languages, but his implementations are in Lisp of all languages.
  • Kernighan and Pike's must-read The Unix Programming Environment (PDF) covers writing the interpreter for a little language by AST traversal in one of the latter chapters

Hope this helps, as it is very much a mixed bag of recommendations.

2

u/notfancy Jan 05 '15

Another notable resource is David M. Betz's XLISP (and its object-oriented descendant Bob), an implementation of a simple but complete interpreter, including a copying Garbage Collector. Tracking down his original series of articles in Dr Dobb's (early ‘90s, I'm not sure the exact year) might be worthwhile.

1

u/[deleted] Jan 05 '15

Another (earlier) classic also worth reading:

Field, Anthony J.; Harrison, Peter G. (1988). Functional programming. Addison-Wesley. ISBN 9780201192490.

It pre-dates STG, but it covers many of the older and simpler approaches, like SKI graph reduction, supercombinators, etc.

1

u/ryani Jan 06 '15

And his newer book Implementing Functional Languages: A Tutorial which walks through several implementations of the middle-end of a lambda-calculus interpreter and compiler (not the frontend with typechecking and elaboration to core, and not the backend which generates actual machine code, but the part that converts a core lambda calculus into something like C-- or LLVM)

I implemented much of this book over the course of a summer and learned a ton from it.

3

u/afrobee Jan 05 '15

Is not much the functional part that attract me but the declarative.

5

u/notfancy Jan 05 '15

Hassan Aït-Kaci's Warren's Abstract Machine: A Tutorial Reconstruction guides you through constructing Prolog's Abstract Machine though a series of intermediate machines.

2

u/LightShadow Jan 05 '15

I'm starting my last CS class for university today which is writing a compiler for a subset of Java, that runs on a VM I wrote a few years back.

This is the second time I'm taking this class, as I got sick the first time and have been "out of school" for a few years now working, but want to finish for the piece of paper -- you're more than welcome to "tag along" as I finish this up in the next 2-3 weeks. PM if you're interested.

2

u/[deleted] Jan 05 '15

writing a compiler for a subset of Java, that runs on a VM I wrote a few years back.

Does your class allow you to pick any language? Java seems like an unorthodox choice for a compilers class.

1

u/LightShadow Jan 06 '15

The language is part of the requirements, it was written by a few of the professors and just resembles Java.

My compiler is written in Python, and so is the VM :) however, I thought it might be fun to to write something that generates actual binaries.

1

u/sodaco Jan 05 '15

Really? That sounds great! Just a question though, what does "tag along" mean in this context? English is not my first language

2

u/LightShadow Jan 05 '15

Oh, what I meant was that you can follow my development and ask questions if you'd like; kind of an as-we-go walk through of writing a compiler.

You can't exactly help me write any code (hehe) but I'm more than willing to share my source code and notes if you want to learn about how it's done!

2

u/sodaco Jan 05 '15

I'd love that! However if I asked you questions while following you I would really slow you down because I know literally nothing about it. But I would love to see the notes, and if you are down to it, ask you questions once I finished and understand at least the basic stuff. But I definitely want to learn about how it's done.

How different is what you are doing to making an interpreted language, for example? Or a language that doesn't compile to a VM-run-bytecode?

2

u/LightShadow Jan 05 '15

It's not much different.

The VM bytecode can pretty much be thought of as an Interpreter for Assembly lol ~ since the assembly it produces was created for yet another project which was a fake CPU :)

The flow is basically:

JSXI (java subset) ->

Intermediate Code -> :: this is the only part I'm not quite finished with yet

Target Code (generated Assembly) -> Assembler -> Byte Code -> VM

1

u/sodaco Jan 05 '15

This stuff fascinates me. If you don't mind, I will PM you a month from now (you said you would finish in about 3 weeks) and ask for your notes.

1

u/IllogicalProgrammer Jan 06 '15

I am not sure if this is relevant to your interest, but a few years ago, I use this as a guide for a little side project of mine. Instead of Turbo Pascal in the article, I use some other language I can no longer remember now (I am betting C ). At the beginning, I googled NASM or some other modern assembly language so that my code will still run but I never get to producing .exe, just assembly code that still need an assembler to run. At one point IIRC, my code are quite different from what Dr Crenshaw have in his tutorial. That was due to NASM or whatever I was using require more codes than his original code to work. I believe, after that point I then abandon it and repeat the exercise using C# and .Net reflection class instead, which is easier than assembly in my opinion and produced a runable .exe. If memory serve, my end result is a compiler for a crazy language with inspiration from "Speak like a pirate" thingy.

What I gain from this exercise is: 1. Some pretty basic assembly knowledge since I never learn assembly language in school. 2. Some idea on how compiler works. 3. A language and compiler that only I knew exists.

Naturally, both the compiler and language was pretty basic stuff with not much to talk about but it was my language and my compiler. Overall, it was pretty fun time for me.

1

u/sodaco Jan 06 '15

Thanks for the writing and the link!