Bibliography

Below is presented a selection of books, papers and web sites that are pertinent to the Tiger project. Of course, you are not requested to read them all, except Modern Compiler Implementation. A suggested ordered small selection of books is:

  1. Modern Compiler Implementation
  2. C++ Primer
  3. Design Patterns - Elements of Reusable Object-Oriented Software
  4. Effective Modern C++
  5. Effective C++
  6. Effective STL

The books are available at the EPITA Library: you are encouraged to borrow them there. If some of these books are missing, please suggest them to the library’s manager. To buy these books, we recommend Le Monde en “tique”, a bookshop that has demonstrated several times its dedication to its job, and its kindness to EPITA students/members.

Web Site: Autotools Tutorial – Alexandre Duret-Lutz

The Autotools Tutorial is the best introduction to Autoconf, Automake, and Libtool, that we know. It covers also other components of the GNU Build System. You should read this before diving into the documentation.

Other resources include:

Web Site: Bjarne Stroustrup
../_images/bjarne.jpg

Bjarne Stroustrup is the author of C++, which he describes as (The C++ Programming Language):

C++ is a general purpose programming language with a bias towards systems programming that

  • is a better C
  • supports data abstraction
  • supports object-oriented programming
  • supports generic programming.

His web page contains interesting material on C++, including many interviews. The interview by Aleksey V. Dolya for the Linux Journal contains thoughts about C and C++. For instance:

I think that the current mess of C/C++ incompatibilities is a most unfortunate accident of history, without a fundamental technical or philosophical basis. Ideally the languages should be merged, and I think that a merger is barely technically possible by making convergent changes to both languages. It seems, however, that because there is an unwillingness to make changes it is likely that the languages will continue to drift apart–to the detriment of almost every C and C++ programmer. […] However, there are entrenched interests keeping convergence from happening, and I’m not seeing much interest in actually doing anything from the majority that, in my opinion, would benefit most from compatibility.

His list of C++ Applications is worth the browsing.

Web Site: Boost.org

The Boost.org web site reads:

The Boost web site provides free peer-reviewed portable C++ source libraries. The emphasis is on libraries that work well with the C++ Standard Library. One goal is to establish “existing practice” and provide reference implementations so that the Boost libraries are suitable for eventual standardization. Some of the libraries have already been proposed for inclusion in the C++ Standards Committee’s upcoming C++ Standard Library Technical Report.

In addition to actual code, a lot of good documentation is available. Amongst libraries, you ought to have a look at the Spirit object-oriented recursive-descent parser generator framework, the Boost Graph Library, the Boost Variant Library etc.

Paper: BURG: Fast Optimal Instruction Selection and Tree Parsing – Christopher W. Fraser, Robert R. Henry, Todd A. Proebsting

SIGPLAN Notices 24(4), 68-76. 1992.

This paper is a description of BURG and an introduction to the concept of code generator generators.

Book: Compilers and Compiler Generators, an introduction with C++ – P.D. Terry

Its site reads:

This site provides an on-line edition of the text and other material from the book “Compilers and Compiler Generators - an introduction with C++”, published in 1997 by International Thomson Computer Press. The original edition is now out of print, and the copyright has reverted to the author.

This book is not very interesting for us: it depends upon tools we don’t use, its C++ is antique, and its approach to compilation is significantly different from Appel’s.

Book: C++ Primer – Stanley B. Lippman, Josée Lajoie
../_images/c++-primer.jpg

Published by Addison-Wesley; ISBN 0-201-82470-1.

This book teaches C++ for programmers. It is quite extensive and easy to read. Unfortunately it is not 100% standard compliant, in particular many std:: are missing. Weirdly enough, the authors seems to promote using declarations instead of explicit qualifiers; the page 441 reads:

In this book, to keep the code examples Short, and because many of the examples were compiled with implementations not supporting namespace, we have not explicitly listed the using declarations needed to properly compile the examples. It is assumed that using declarations are provided for the members of namespace std used in the code examples.

It should not be too much of a problem though. This is the book we recommend to learn C++. See the Addison-Wesley C++ Primer Page.

Warning: The French translation is L’Essentiel du C++, which is extremely stupid since Essential C++ is another book from Stanley B. Lippman (but not with Josée Lajoie).

Book: Compilers: Principles, Techniques and Tools – Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman
_
Book: The Dragon Book
../_images/compilers-principles-techniques-and-tools.jpg

Published by Addison-Wesley 1986; ISBN 0-201-10088-6.

This book is the bible in compiler design. It has extensive insight on the whole architecture of compilers, provides a rigorous treatment for theoretical material etc. Nevertheless I (Akim) would not recommend this book to EPITA students, because

it is getting old
It doesn’t mention RISC, object orientation, functional, modern optimization techniques such as SSA, register allocation by graph coloring [1] etc.
it is fairly technical
The book can be hard to read for the beginner, contrary to Modern Compiler Implementation.

Nevertheless, curious readers will find valuable information about historically important compilers, people, papers etc. Reading the last section of each chapter (Bibliographical Notes) is a real pleasure for whom is interested.

It should be noted that the French edition, “Compilateurs: Principes, techniques et outils”, was brilliantly translated by Pierre Boullier, Philippe Deschamp, Martin Jourdan, Bernard Lorho and Monique Lazaud: the pleasure is as good in French as it is in English.

Web Site: Cool: The Classroom Object-Oriented Compiler
The Classroom Object-Oriented Compiler, from the University of California, Berkeley, is very similar in its goals to the Tiger project as described here. Unfortunately it seems dead: there are no updates since 1996. Nevertheless, if you enjoy the Tiger project, you might want to see its older siblings.
Paper: CStupidClassName – Dejan Jelovi
This short paper, CStupidClassName, explains why naming classes CLikeThis is stupid, but why lexical conventions are nevertheless very useful. It turns out we follow the same scheme that is emphasized there.
Book: Design Patterns: Elements of Reusable Object-Oriented Software – Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
../_images/design-patterns.jpg

Published by Addison-Wesley; ISBN: 0-201-63361-2.

A book you must have read, or at least, you must know it. In a few words, let’s say it details nice programming idioms, some of them you should know: the VISITOR, the FLYWEIGHT, the SINGLETON etc. See the Design Patterns Addison-Wesley Page. A pre-version of this book is available on the Internet as a paper: Design Patterns: Abstraction and Reuse of Object-Oriented Design. Surprisingly, The full version of Design Pattern CD is available on the net.

You may find additional information about Design Patterns on the Portland Pattern Repository.

Book: Effective Modern C++ – Scott Meyers
../_images/effective-modern-c++.jpg

336 pages; Publisher: O’Reilly Media; 1st edition (November 2014); ISBN: 1-491-90399-6

An amazingly practical book when using C++11 and C++14 (modern C++). These days, it should be the first book that every new C++ programmer should read. It follows the same format as Effective C++. Effective Modern C++ O’Reilly Page.

In this document, EMCN refers to item n in Effective Modern C++.

Book: Effective C++ – Scott Meyers
../_images/effective-c++.jpg

320 pages; Publisher: Addison-Wesley Pub Co; 3rd edition (May 2005); ISBN: 0-321-33487-6

An excellent book that might serve as a C++ lecture for programmers. Every C++ programmer should have read it at least once, as it treasures C++ recommended practices as a list of simple commandments. Be sure to buy the second edition, as the first predates the C++ standard. See the Effective C++ Addison-Wesley Page.

In this document, ECN refers to item n in Effective C++.

Book: Effective STL – Scott Meyers
../_images/effective-stl.jpg

Published by Addison-Wesley; ISBN: 0-201-74962-9

A remarkable book that provides deep insight on the best practice with STL. Not only does it teach what’s to be done, but it clearly shows why. A book that any C++ programmer should have read. See the Effective STL Addison-Wesley Page.

In this document, ESN refers to item n in Effective STL.

Paper: Engineering a simple, efficient code generator generator – Christopher W. Fraser, David R. Hanson, Todd A. Proebsting

ACM Letters on Programming Languages and Systems 1, 3 (Sep. 1992), 213-226.

This paper describes iburg, a BURG clone that delay dynamic programming at compile time (BURG-like programs use dynamic programming to select the optimum tree tiling during a bottom-up walk).

Technical Report: Generic Visitors in C++ – Nicolas Tisserand

This report is available on line from Visitors Page: Generic Visitors in C++. Its abstract reads:

The Visitor design pattern is a well-known software engineering technique that solves the double dispatch problem and allows decoupling of two inter-dependent hierarchies. Unfortunately, when used on hierarchies of Composites, such as abstract syntax trees, it presents two major drawbacks: target hierarchy dependence and mixing of traversal and behavioral code.

CWI’s visitor combinators are a seducing solution to these problems. However, their use is limited to specific “combinators aware” hierarchies.

We present here Visitors, our attempt to build a generic, efficient C++ visitor combinators library that can be used on any standard “visitable” target hierarchies, without being intrusive on their codes.

This report is in the spirit of Modern C++ Design, and should probably be read afterward.

News: Guru of the Week

Written by various authors, compiled by Herb Sutter

Guru of the Week (GotW) is a regular series of C++ programming problems created and written by Herb Sutter. Since 1997, it has been a regular feature of the Internet newsgroup comp.lang.c++.moderated, where you can find each issue’s questions and answers (and a lot of interesting discussion).

The Guru of the Week Archive (the famous GotW) is freely available. In this document, GotWn refers to the item number n.

Article: How not to go about a programming assignment – Agustín Cernuda del Río

This paper provides excellent advice on how to succeed an assignment by showing the converse: how *not* to go about a programming assignment:

  • All about programming, in the strictest sense of the word
    • Ignore messages
    • Don’t stop to think
    • I don’t want any trouble
  • If only I could find the words
    • Reading
    • Writing
  • Your relationship with your lecturer
    • Don’t ask for help
    • Challenge your lecturer
    • Be clever using electronic mail
  • And, of course…
    • Leave it all for the last minute
    • Cheat with your assignment
Book: Lex & Yacc – John R. Levine, Tony Mason, Doug Brown

Published by O’Reilly & Associates; 2nd edition (October 1992); ISBN: 1-565-92000-7.

../_images/lex-and-yacc.jpg

Because the books aims at a complete treatment of Lex and Yacc on a wide range of platforms, it provides too many details on material with little interest for us (e.g., we don’t care about portability to other Lexes and Yacces), and too few details on material with big interest for us (more about exclusive start condition (Flex only), more about Bison only stuff, interaction with C++ etc.).

Article: Making Compiler Design Relevant for Students who will (Most Likely) Never Design a Compiler – Saumya K. Debray
This paper about teaching compilers justifies this lecture. This paper is addressing compiler construction lectures, not compiler construction projects, and therefore it misses quite a few motivations we have for the Tiger project.
Book: Modern C++ Design – Generic Programming and Design Patterns Applied – Andrei Alexandrescu
../_images/modern-c++-design.jpg

Published by Addison-Wesley in 2001; ISBN: 0-52201-70431-5

A wonderful book on very advanced C++ programming with a heavy use of templates to achieve beautiful and useful designs (including the classical design patterns, see Design Patterns - Elements of Reusable Object-Oriented Software). The code is available in the form of the Loki Library. The Modern C++ Design Web Site includes pointers to excerpts such as the Smart Pointers chapter.

Read this book only once you have gained good understanding of the C++ core language, and after having read the “Effective C++/STL” books.

Book: Modern Compiler Implementation in C, Java, ML – Andrew W. Appel

Published by Cambridge University Press; ISBN: 0-521-58390-X

../_images/appel-c.jpg ../_images/appel-java-1.jpg ../_images/appel-ml.jpg ../_images/appel-java-2.jpg

Modern Compiler Implementation. In our humble opinion, most books give way too much emphasis to scanning and parsing, leaving little material to the rest of the compiler, or even nothing for advanced material. This book does not suffer these flaws.

Web Site: Object Management Group
OMG’s Home Page, with a lot of ressources for object-oriented software engineering, particularly on the Unified Modeling Language (UML).
Book: Parsing Techniques – A Practical Guide – Dick Grune and Ceriel J. Jacob

Published by the authors; ISBN: 0-13-651431-6

A remarkable review of all the parsing techniques. Because the book is out of print, its authors made it freely available: Parsing Techniques – A Practical Guide.

Book: Programming: Principles and Practice Using C++ – Bjarne Stroustrup
../_images/programming-principles-and-practice-using-c++.jpg

This book targets the “advanced beginner” in C++ and covers a wide range of topics including non-core C++ subjects such as GUI programming. A recommended lecture for modern C++ learning.

Published by Addison-Wesley Professional, 2008; ISBN-13: 978-0321543721.

Report: SPOT: une bibliothèque de vérification de propriétés de logique temporelle à temps linéaire – Alexandre Duret-Lutz & Rachid Rebiha
This report presents SPOT, a model checking library written in C++ and Python. Parts were inspired by the Tiger project, and reciprocally, parts inspired modifications in the Tiger project. For instance, earlier versions of SPOT made use of a visitor hierarchy. You are encouraged to read the sections about the visitor hierarchy and its implementation. Another useful source of inspiration was the use of Python and Swig to write the command line interface.
Paper: Testing student-made compilers – José de Oliveira Guimaraes

ACM SIGCSE Bulletin archive Volume 26, Issue 3 (September 1994).

This paper gives a classified list of test cases for a small Pascal compiler. It is a good source of inspiration for any other language.

Book: The Design and Evolution of C++ – Bjarne Stroustrup
../_images/the-design-and-evolution-of-c++.jpg

Published by Addison-Wesley, ISBN 0-201-54330-3.

This book is definitely worth reading for curious C++ programmers. I (Roland) find it an excellent companion to reference C++ books, or even to the C++ standard. Many aspects of the language that are often criticized find a justification in this book. Moreover, the book not only tells the history of C++ (up to 1994), but it also explains the design choices and reflexions of its authors (and Bjarne Stroustrup’s in the first place), which go far beyond the scope of C++.

However, the book only describes the first 15 years of C++ or so. Recent work on C++ (and especially on the C++0x effort that eventually led to C++ 2011) can be found in Stroustrup’s papers, available online.

Book: The Elements of Style – William Strunk Jr., E.B. White
../_images/the-elements-of-style.jpg

Published by Pearson Allyn & Bacon; 4th edition (January 15, 2000); ISBN: 020530902X.

This little book (105 pages) is perfect for people who want to improve their English prose. It is quite famous, and, in addition to providing useful writing thumb rules, it features rules that are interesting as pieces of writing themselves! For instance “The writer must, however, be certain that the emphasis is warranted, lest a clipped sentence seem merely a blunder in syntax or in punctuation”.

You may find the much shorter (43 pages) First Edition of The Elements of Style on line.

Book: Thinking in C++ Volume 1 – Bruce Eckel

Published by Prentice Hall; ISBN: 0-13-979809-9

Available on the Internet on many Book Download Sites. For instance, Thinking in C++ Volume 1 Zipped.

Book: Thinking in C++ Volume 2 – Bruce Eckel and Chuck Allison
Available on the Internet on many Book Download Sites. For instance, Thinking in C++ Volume 2 Zipped.
Article: Traits: a new and useful template technique – Nathan C. Myers
The first presentation of the traits technique is from this paper, Traits: a new and useful template technique. It is now a common C++ programming idiom, which is even used in the C++ standard.
Book: Writing Compilers and Interpreters – An Applied Approach Using C++ – Ronald Mak

Published by Wiley; Second Edition, ISBN: 0-471-11353-0

This book is not very interesting for us: the compiler material is not very advanced (no real AST, not a single line on optimization, register allocation is naive as the translation is stack based etc.), and the C++ material is not convincing (for a start, it is not standard C++ as it still uses #include <iostream.h> and the like, there is no use of STL etc.).

Web site: STL Home
SGI’s STL Home Page, which includes the complete documentation on line.
[1]To be fair, the Dragon Book leaves a single page (not sheet) to graph coloring.