Resources for Amateur Compiler Writers

This is a nice introductory tutorial on how to implement Hindley-Milner type inference: https://github.com/jozefg/hm

This is a more advanced tutorial that illustrates a nice but tricky optimization that OCaml's type checker internally uses: http://okmij.org/ftp/ML/generalization.html

Finally, TAPL's type checkers are pretty good. They aren't designed for efficiency, though. They're designed to closely follow the book's contents: http://www.cis.upenn.edu/~bcpierce/tapl/checkers/

What about using scope environments and variable binding? For lambda calculus, variable binding (of the single variable x) in an environment (the current application of lambda) is a fundamental part of it anyway.

A scope environment gives you a place to name "things". "Things" can be functions. It's just a name-value map. You create a local scope environment for every function invocation. You can bind things (value or functions) to names in the local environment. Then you can refer to "things" by their names, like calling a function using its name.

Parent scope environments can be nested in the local scope when the function is called. A search on a name not found on the current scope can be delegated to the parent scope, so that functions defined and named in outer scope can be referenced in inner scope.

Recursive call is not a problem for named function since you can look up the function by name. It becomes a problem for anonymous function (lambda) since it can't be looked by name. For that you can introduce a special name like "_lamb" for it. Upon entry of a function, you bind the current function to the name in the current environment. A reference to it would call the current function again. e.g. _lamb(). You can even have a special name "_parent" to bind to the parent environment. In that case you can call the anonymous parent function. E.g. _parent._lamb()

Function calling and recursive function have nothing to do with OO or Java/Python/Ruby. It has everything to do with name, binding, scope, and environment.

Language Implementation Patterns by Terrance Parr might be right up your alley. Implementing Programming Languages by Aarne Ranta is likewise a refreshing take on language implementation instruction. Bonus points for both books being rather concise and affordable.

I've also really enjoyed Elements of Programming Languages by Friedman & Wand (older editions cover different topics than the current 3rd edition, and it may be worth reading both the 1st and 3rd editions). Focuses primarily on interpreters, but most of the topics covered have applications for compilers as well.

Going a slightly more traditional route, I've found Andrew Appel's compiler books, Modern Compiler Implementation in ML and Compiling with Continuations to present pretty wide coverage of techniques at all phases of a compiler. The former is the one I normally recommend for people looking for their first (and hopefully only) compiler book (if they're actually looking for a compiler book rather than a DSL book).

Of course, techniques for processing the Lisp family are well-covered in Christian Quiennec's classic Lisp in Small Pieces (he's written some other books which are quite interesting for Lisp historians as well). Implementors of Lisps will also probably want to look into The Art of the Metaobject Protocol by Kiczales et al. SICP's coverage in chapters 4 and 5 is also pretty good as an introduction, even if it only barely scratches the surface.

Getting into types, you're pretty much limited to Pierce's Types and Programming Languages, but Bob Harper et al. have also written Homotopy Type Theory which is freely available on the Web. I haven't finished HoTT yet, so I can't comment on how accessible it is or how broad/deep its coverage is.

Those interested in rewriting systems should start with Term Rewriting and All That by Baader and Nipkow, which I've found to be extremely accessible and fairly comprehensive (covering abstract rewriting systems, string rewriting, graph rewriting, etc.). Your choices for books on rewriting written in English is pretty small (I've literally found only three, one of which costs $300 USD(!) -- where does Cambridge University Press get off??), but fortunately the Baader and Nipkow book is so good that you probably won't need another book and can proceed straight to the literature.

---

There are tons of books on compilation, but I honestly think they're mostly a waste of time. Each book, for the most part, only re-iterates the basics in another way, so unless you didn't quite grasp it from the first book you tried, maybe look at another one, but once you understand the material, don't waste any more time or money on compiler books. After you've grokked the basics (i.e., worked through one or two introductory books), you'll get far more value from reading books on other related concepts (e.g., type theory, term rewriting, metaobject protocols, etc.), reading research papers, journal articles, dissertations, etc., and, of course, reading code.

I say all this as someone who made the mistake of spending lots of time and money on lots of different compiler books, stupidly hoping to learn something new with each one. The silver lining is that this puts me in a pretty good position to recommend particular compiler books :)

That the Dragon Book is still considered the standard introduction is baffling, even the most recent edition is horrendously outdated and dwells far too much on parsing techniques (where, from the perspective of a compiler writer, parsing is effectively a solved problem -- not to mention that there are quite a few parsing techniques the Dragon Book doesn't cover, despite the amount of text devoted to parsing). And, like you said, the techniques it covers are really only immediately applicable to imperative procedural languages without sophisticated type systems, such as C or Pascal.