Modern Compiler Implementation in ML: Basic Techniques

by Andrew W. Appel

This textbook explains all phases of a modern compiler: lexical analysis, parsing, abstract syntax, semantic actions, intermediate representations, instruction selection via tree matching, dataflow analysis, graph-colouring register allocation with coalescing, and runtime systems. It covers current techniques in code generation and register allocation, as well as functional and object-oriented languages. The author illustrates the most accepted and successful techniques in a concise way, rather than as an exhaustive catalogue of every possible variant. Detailed descriptions of the interfaces between the modules of a compiler are illustrated with actual ML signatures. A unique feature of the book is a well-designed compiler implementation project in ML, including front-end and 'high-tech' back-end phases, so that students can build a complete working compiler in one semester. The textbook is meant for use in a one-semester first course for undergraduates in compiler design. Accompanying software is available.

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

400 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.