Programming Languages, Compiler Construction, and Program Analysis
Introduction to Static Analysis: An Abstract Interpretation Perspective
Xavier Rival and Kwanggkeun Yi
This book introduces abstract interpretation very well and provides the reader with a rich set of bibliography for advanced topics in the subject. Throughout the text, multiple programming languages are specified. The first one is a language for geometric drawing (a picture is worth a thousand words) that allows for a nice graphical illustration of abstract interpretation and abstract domains. Complex language features, in particular those of C, are examined toward the end of the book but only at their surface. Chapters are pedagogically developed: the initial discussion is informal and under a simple setup; latter it is formalised and expanded. Both denotation and operational semantics are covered, but I find that coverage of the latter is lacking. Specifically, there are big leaps in Chapter 4 for content that deserved further elaboration. The authors show genuine concern of conveying the importance of a "right" choice of logical program properties. Pictures and diagrams are intuitive and descriptive, although some color would have been welcome. I'm uncertain whether the book serves as a general introduction to static analysis... even though it approaches concepts such as soundness and completeneess from a foundational standpoint and briefs about other static analysis techniques like data flow or pointer analysis (in Chapter 10 there's an insightful correlation between abstract interpretation and type inference), the overall content is around abstract interpretation; Overall I liked a lot reading this book, but it contains a non-negligible amount of errors, typos, incorrect cross-references, and inconsistent notation. I think the book could have gone through a couple more editorial/technical reviews.
Formal Methods: An Appetizer
Flemming Nielson and Hanne Riis Nielson
This book has the most beautiful (coloured) layout and typesetting ever! The text is surprisingly easy to read; at least, when compared to the Nielson & Nielson's Principles of Program Analysis. Topics, despite complex, are addressed in succinct and clear form. Chapters and sections consist of a sequence of (i) a few descriptive paragraphs; (ii) a definition, sometimes followed by a proposition; (iii) a couple of examples; and (iv) exercises. All formal methods are elaborated on top of a uniform program representation: a Program Graph (a sort of "transposed" version of a Control Flow Graph). Such a graph's implied language is elegantly shown to be equivalent to that of a finite automata. To bridge between theory and practice, the Guarded Command Language is used. (Did you know that Dijkstra was also a language designer?) But an F# implementation of a C-like language called MicroC also is provided. Although the book is oriented toward formal methods, I'd consider it for a good introduction on language's semantics as well; it offers a taste of (interprocedural) dataflow and concurrency analysis. Recall that Nielson & Nielson are also the authors of Semantics with Applications: An Appetizer.
Programming Language Pragmatics
Michael L. Scott
This book is a joyful read, with an engaging writing style. It doesn't offer much theory; yet, the author manages to capture the (theoretical) essence of language features through practical and informal plain English. This means that the word pragmatics from the title is consistent with the text of the book. Many features of mainstream programming languages are examined and compared across each other. The approach is appealing to emphasize the fundamental choices when designing a programming language. Michael demonstrates actual experience with multiple programming languages, given that a great variety of features are covered. As a side note, the first chapters of the book discuss a compiler's front-end in a holistic yet succint way; similar to what you would see in the first chapters of a compiler book, but with a lighter load. That said, if you want to understand the basics of a compiler front-end, but without diving too deep into the topic, this book provides a rather friendly introduction to the topic.
Types and Programming Languages
Benjamin C. Pierce
This book opened to me an universe that I was not familiar with. It was my first highly theoretical read on the subject. My perception on programming languages has substantially broadened after reading it. An interesting pedagogical approach is the introduction of the lambda calculus and its increment by basic extensions and advanced features. In between a few chapters, an ML implementation of the type system being studied is discussed. Bringing certain concepts of the text into concrete languages can be subtle sometimes, but it's typically delightful to see them in action on a functional-style programming language - I'm currently studying Haskell. A good companion to this book is the online material of the Oregon Programming Languages Summer School. Without any question, this is the book if you want to do research on programming languages. It teaches you the formalism necessary and tells you how story evolved in this area.
Design Concepts in Programming Languages
Franklyn Turbak et al.
This is another book with a strong academic background. Surprisingly, the reading is reasonably light -- several small/toy languages are presented throughout the book, but their increments are well defined and separated. The reason I bought this book is because it's one of the few books with a good treatment of programming language semantics. Parsing and code generation is addressed in numerous compilers books; type theory, along with related fundamentals, is discussed in a few books as well. Not many books, however, deal with operational semantics (big and small step), denotational semantics, program equivalence and transformation, etc. Of course, it touches typing further down the road. Also, it comes with a lot of code and a good amount of notation - the appendix A, for the meta language, is worth its own. I've taken this book as a great companion to Pierce's book.
Compilers: Principles, Techniques, and Tools
Alfred Aho et al.
Also known as the Dragon book, this was my first compiler book. The material is quite theoretical, full of formalisms, and well supported in terms of references and academic background. For instance, the chapter on lexers includes an entire discussion about regular expression and automata theory. The backend part goes beyond code generation and touches a wide variety of topics like optimizations and static analysis (e.g., the monotone framework). Despite it being a great book, if you're a practical person, I'd suggest other alternatives as an initial reading on the subject.
Modern Compiler Design
Dick Grüne et al.
This book has a good mix of theory and practice. The discussion about parsing is very rich -- as expected, given that Dick Grüne is a parser expert and has also written a book exclusively on parsing techniques. The text doesn't contain as many topics as the Tiger/Dragon books, but the ones available are thoroughly addressed. The content is easy to follow and there's plenty of code examples. This is the book that I'd recommend to someone who would like to get a basic compiler up and running, with a comprehensive discussion about its major components, but without entering too much into formalisms.
Modern Compiler Implementation in C
Andrew W. Appel
At first I was a bit reluctant to buy this book because I read a few bad reviews about it. But in the end I decided to take a chance; and I'm happy I did. In my opinion, this is "the compiler book" -- it might be difficult to digest when you don't have a certain background knowledge. The text has a pragmatic approach: sections are generally short and straight to the point, accompanied by a sample implementation. References to academic material are always provided, though. Furthermore, the content covers a wide range of topics like SSA, unification, garbage collection, and others that aren't available neither in the Dragon nor in Dick Grüne's book. Although a language called Tiger serves as guide, there'll be hints on features that are not present in it.
The C++ Programming Language, 3rd/4th ed. - Bjarne Stroustrup
This book is from the C++ creator, who also happens to be a very good writer. You'll understand a few decisions behind C++'s design and you'll get an accurate explanation of language rules. This is probably the most complete book about C++, but it might not be the best one if you're still learning how to program. Many areas of C++'s standard library are covered. The text has a personal touch about style and idiomatic C++, according to Stroustrup. As a bonus, you'll get code samples that can be used in real scenarios. One example, which is no longer available in the 4th ed., is a memory pool allocator.
The C++ Standard Library: A Tutorial and Reference, 1st/2nd ed. - Nicolai Josuttis
Most of the content of this book is focused on the STL. Cool, because I'm a big fan of generic programming. Yet, the book does an excellent job for the remaining parts of C++'s standard library. As expected, the 2nd ed. brings all C++11 additions - a plus, since it distinguishes the new stuff. You could read this book just to learn how to use containers, iterators, algorithms, function objects, and the utilities. However, it's an excellent opportunity to inspect the construction principles of the library. If you've been around the old SGI's STL website, I'm pretty sure you'll enjoy this book.
Standard C++ IOStreams and Locales - Angelika Langer and Klaus Kreft
Finally locale and facets made into my brains. The overall architecture of the IOStreams library was always confusing to me. Including the relationship among conversion, transport, buffering, and representation layers. This book makes it easier. Not only does it show how to use IOStream components but how they could be implemented. Ways by which the IOStreams library interacts with the STL are also well described. If you need documentation of every class and method that is related to IOStreams, locales or facets, it's the best reference guide out there.
C++ Templates: The Complete Guide - David Vandevoorde and Nicolai Josuttis
Simply everything (and more) you need to know about templates: function templates, class templates, specializations, traits, policies, type functions, meta-programming, and a lot more. Nice discussion about argument deduction and the instantiation process; Interesting (and fancy) techniques for type mapping and classification; Optimization techniques like the Empty Base Class Optimization (EBCO); An enlightening example on expression templates; The Curiously Recurring Template Pattern (CRTP). Vandervoorde is inside C++'s committee, so the discussion is well supported. Awesome book.
Effective C++ - Scott Meyers
This is a classic and a book that can actually take you to the next level of C++ skills. If you're beginning with the language, I'm pretty sure that you'll make at least one discovery in each item of the book. Would I be too pretentious if I say that this book has the answers for a lot of the common C++ doubts and questions you can find on the Internet? Anyway, don't begin a project without reading it (unless, of course, you have obtained equivalent knowledge from somewhere else). Scott's writing is attractive and entertaining.
Effective Modern C++ - Scott Meyers
This is the C++11/14 version of Scott's effective C++ series. As fair as I know, the book was originally planned for C++11 only, but somewhere along the way Scott decided to wait for C++14. This decision was great. There are subtle changes from C++11 to C++14, such as the use of auto in lambdas or things like decltype(auto), which are clearly pointed out. The book's discussion about type deduction is, without a question, the most complete one out there. Who thought auto could be so complicated? It was only with this book that I could fully understand rvalue references and their interaction with template parameters. After all, Scott was the one (I believe) that triggered the debate about the rvalue references weirdness - although, I confess that I don't like his universal references terminology and I'm glad that the C++ committee has ultimately decided to stick with the term forwarding references in C++17.
Effective STL - Scott Meyers
You should read this one if you already have some experience with the STL. It's not that you won't be able to follow it. (A nice characteristic of Scott's books is that he makes sure that you really get what he's saying.) It's just that a few items won't ring a bell. You'll read them and say: OK, that's obvious. Months later you might catch yourself writing code that falls into "traps" mentioned in the book. Bottom line: My impression is that most book items are in the category "Oh, I've seen this before. That error... That doubt... That problem...". And this is exactly what makes the reading pleasant and remarkable.
Exceptional C++ - Herb Sutter
This book has an interesting approach: question and answer. Together with More Exceptional C++ it's the best text I know when it comes to exception-safety. Another topic that is touched very successfully and is commonly seen in many software (at least in the ones I have worked) is the abuses of inheritance. This book opened to me a broader perspective on the influence of namespaces and argument dependent lookup (ADL). It also made me realize that I should use pimpl more frequently. Altogether, the books teach you about software engineering (best practices, idioms and patterns) from a C++ standpoint.
More Exceptional C++ - Herb Sutter
Continues from Exceptional C++. The topics are related but the content is different. When there is an overlapping it's just for contextualization. It contains the best discussion about multiple inheritance that I've ever seen. I very much liked the chapter on optimization and performance. It analyses implementations of a few string classes with different characteristics like sharedness, copy-on-write, and multi-threading. As for Exceptional C++, the book brings detailed information on exception-safety and resource management.
Exceptional C++ Style - Herb Sutter
Although not called Even More Exceptional C++ (or something similar), this book is a continuation of Exceptional C++ and More Exceptional C++. Right at the beginning there is a very useful item covering quite a common subject: What are the available string formatters and how they compare. In the generic programming part, a great discussion about specialization and overloading of function templates is presented. The exception safety content is interesting, but I think that two of three items are somehow enforcements of what has already been said in the other books from the series. Resource management and class design from a C++ perspective are once more well explained. There are things good to know about traps and pitfalls, but they are more like a "curiosities" category for me. On the other hand, the case studies at the end of the book deal with relevant issues.
C++ Coding Standards - Herb Sutter and Andrei Alexandrescu
If I'm a team leader of a large project and I have to choose a single C++ book for inexperienced newcomers, it would be this one. This book doesn't get into many details about anything, but it opens the doors for those who want to investigate them further. It's a straightforward guide: Do this; Don't do that. Its scope ranges from trivial things like recommending prefix versions of ++ and -- (instead of postfix ones) to not so easily detectable problems caused by non-intentional generic code or crashes across modules boundaries due to incompatible types.
C++ Concurrency in Action - Anthony Williams
This book is the complete guide on C++11 threading infrastructure. Anthony has been involved with the threading library since the Boost version (which originated the standard one). In my opinion, the prime advantage of this book is that it also teaches us about multithreading programming in general. The examples used throughout the book are inspired by real-world situations - Anthony's anecdotes used to illustrate threading problems in terms of normal-life episodes are awesome. One thing I haven't made my mind yet is whether the order of the chapters (and sections) is the best one. But anyways, the content is extraordinary.
Modern C++ Design - Andrei Alexandrescu
Tough to read. More than once I happened to stay for a complete hour in order to understand a few lines of code. In fact, just the first chapter provoked an explosion of ideas in my head. It was the first time that I actually thought of class templates as practical building blocks. (It's curious because that's exactly the picture on the cover of the book C++ Templates. Oh... It makes sense.) In the second chapter I started to think that I could construct an entire application just using type mapping and selection. In the third chapter, code gets a bit more complex and even more interesting. Typelists are really cool. Then I only went through some scattered sections until chapter six. If you appreciate design patterns and the GoF book, you'll be familiar with what's coming next: Singletons, factories and visitors. However, this time in the template world.
API Design for C++ - Martin Reddy
The only book I'm aware of on the topic of C++ API design. Surprisingly... Given the fact that, historically, C++ APIs are not considered to be the most friendly ones out there. C++'s rich semantics (pointer, references, stack x heap allocation, etc) deserve more API-related material like this. There's a clear influence of the Qt framework in this book. This is a good thing, since Qt's API is probably one of best documented, designed, and stable C++ APIs in the market - certainly one of the reasons for its long life. Software engineering, in general, appears in numerous parts (design patterns, open/closed, Liskov's substitution principle, etc).
C++ How to Program - Deitel
Nice introductory book. Although there are other options available with similar content, this is a good choice if you don't know anything about programming nor C++. A friend of mine got the last edition and I was surprised to see some new chapters.
Algorithms and Data Structures
Algorithms in C++ (Parts 1-4) - Robert Sedgewick
This is one of my favorite books overall. It provides an excellent balance between theory and practice. Proofs are well written. Organization and pedagogical "sequencing" stands out. Lots of implementation details are covered, which is relevant if you're really into coding. Basically, everything I ever needed on fundamental algorithms and data structures, I was able to find in it (or at least a good reference to what I was looking for). The Cormen book, which is also great material, seems to be more popular than Sedgewick's. But if you can't afford to have both, my personal feeling picks this one.
Algorithms in C++ (Part 5) - Robert Sedgewick
The comments I made for parts 1-4 of this book series apply to this one as well, but now in the universe of graphs - algorithms, as the name says, this is not a "graph theory" book. The book doesn't go into advanced stuff like planarity-test or graph drawing/layout algorithms. It does, however, an outstanding job for traditional algorithms like search (BFS, DFS, priority-based), shortest-paths, flows, and minimum-costs. Again, you'll find interesting tips on concrete implementations.
Introduction to Algorithms - Cormen et al.
This is quite a popular book on the subject. Algorithms are in pseudo-code. In general, this is not my preferred style of presentation, but it can be better in certain cases. Particularly, when an concrete implementation would risk deviating the reader due to "circumstantial details" or when the principal idea is simply better expressed in plain English form. When compared to Sedgewick’s book, my view is that this book covers a larger variety of distinct topics, while the other goes into deeper details within a topic (think, for example, on the vast range of search tree design alternatives).
Graph Drawing and Computational Geometry
Computational Geometry: Algorithms and Applications - Mark de Berg et al.
Since this is the only computational geometry book I've ever read, I cannot make comparisons. What I can say though, is that I found it a delightful and smart book. It expects knowledge about fundamental algorithms and data structures. Most chapters are preceded by a thorough discussion of a real scenario where a particular algorithm might be needed to solve a problem. In some cases, a naive strategy is initially proposed. Following it, the authors provoke intriguing thoughts of whether or not this would be a good solution and suggest a better approach. The algorithms are in pseudo-code. Usually, I don't like such presentation form, but I admit that in this case I'm perfectly cool with it for at least a few reasons: Each step is precise and well explained. It's not too practical to use a programming language because the code can get long and complex. In addition, it would also have to depend on a precision arithmetic library for the results to be correct. Reading this book increases your options even for general algorithms.
Graph Drawing: Algorithms for the Visualization of Graphs - Di Battista et al.
My master's degree was related to graph drawing algorithms, so I used this book quite a lot. Some pages are falling apart. Surely this is an excellent starting point for people that knows absolutely nothing about graph drawing. The first chapter is basically concerned on explaining what graph drawing is and where it's present. This book is a collection of scientific papers organized in a reasonably pedagogical manner. It's not concerned about implementation details. Major benefits from the book are an overall view of graph drawing methodologies and strategies, a rigorous source of references, and the description of well known graph drawing algorithms.
Website generated with TMTMIPP
© Copyright Leandro T. C. Melo