Modern Compiler Implementation in ML

by Andrew W. Appel

This new, expanded textbook describes all phases of a modern compiler: lexical analysis, parsing, abstract syntax, semantic actions, intermediate representations, instruction selection via tree matching, dataflow analysis, graph-coloring register allocation, and runtime systems. It includes good coverage of current techniques in code generation and register allocation, as well as functional and object-oriented languages, that are missing from most books. In addition, more advanced chapters are now included so that it can be used as the basis for two-semester or graduate course. The most accepted and successful techniques are described in a concise way, rather than as an exhaustive catalog of every possible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actual C header files. The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compiler design. The second part, Advanced Topics, which includes the advanced chapters, covers the compilation of object-oriented and functional languages, garbage collection, loop optimizations, SSA form, loop scheduling, and optimization for cache-memory hierarchies.

Genres: Computer Science, Programming, Technology, Textbooks, Technical, Programming Languages, Software

552 pages, Paperback

First published January 13, 1997

About the author

Andrew W. Appel, Ph.D. (Computer Science, Carnegie Mellon University, 1985; A.B., Princeton University, 1981) is the Eugene Higgins Professor of Computer Science at Princeton University, where he has been on the faculty since 1986. He served as department chair from 2009 to 2015. His research is in software verification, computer security, programming languages and compilers, and technology policy.

He has been editor-in-chief of ACM Transactions on Programming Languages and Systems and is a fellow of the ACM (Association for Computing Machinery). He has worked on fast N-body algorithms (1980s), Standard ML of New Jersey (1990s), Foundational Proof-Carrying Code (2000s), and the Verified Software Toolchain (2010s). He is the author of several scientific papers on voting machines and election technology, served as an expert witness on two voting-related court cases in New Jersey, and has taught a course at Princeton on election machinery.

Reviews

[Gregory Blake · Rating 5 out of 5]

Appel's stated goal in writing this book was, rather than to provide a laundry list of compiler algorithms that could potentially be used to implement a compiler, to use the algorithms that now dominate modern compilers. His thorough and authoritative approach starts with building a complete working compiler in the first half of the book before exploring deeper specialized topics in the last half of the book. Each chapter comes with example ML code from the chapter along with programming exercises which build off of the chapter's code so that at the end you have built a working optimizing compiler.

The book is an enjoyable read the whole way through. I particularly enjoyed the chapters on Instruction Selection, Register Allocation, Functional Languages, Loop Optimizations, and the Memory Hierarchy. This book gave me a new appreciation for how sophisticated a compiler's job is. If you're looking for an introduction or refresher on compilers, start with this book.

[Jorge Barrios · Rating 5 out of 5]

Hands-On. Appel challenges the reader to write a compiler, provided with essential tools and libraries—e.g., Lex and Yacc. ML is a fine language to write compilers and gain fluency in functional programming.

[Sameer Rahmani · Rating 4 out of 5]

The ML version of this book is totally recommended over the other two

[Златозар Желязков · Rating 5 out of 5]

As a companion use this source:
https://github.com/gumchum/tiger

and book "MIPS Assembly Language Programming" by Robert Britton

PS:Here is my implementation using F#: https://github.com/zlatozar/TigerLang...

[Sonia · Rating 4 out of 5]

A helpful textbook.