Table of Contents
List of Figures and Tables.
I. Getting Started. 1. A Little Simple Math.
Formulas and Language.2. Specifying a Simple Clock.
An Hour Clock.
A Closer Look at the Specification.
The Specification in TLA+.
An Alternative Specification.3. An Asynchronous Interface.
The First Specification.
Types: A Reminder.
Comments.4. A FIFO.
The Inner Specification.
Instantiation Is Substitution.
Instantiation Without Renaming.
Hiding the Queue.
A Bounded FIFO.
What We're Specifying.5. A Caching Memory.
The Memory Interface.
A Linearizable Memory.
Tuples as Functions.
Recursive Function Definitions.
A Write-Through Cache.
Proving Implementation.6. Some More Math.
Functions versus Operators.
Choose.7. Writing a Specification: Some Advice.
What to Specify.
The Grain of Atomicity.
The Data Structures.
Writing the Specification.
Some Further Hints.
When and How to Specify.
II: More Advanced Topics. 8. Liveness and Fairness.
Temporal Proof Rules.
The Memory Specification.
The Liveness Requirement.
Another Way to Write It.
The Write-Through Cache.
Temporal Logic Examined.
Machine Closure and Possibility.
Refinement Mappings and Fairness.
The Unimportance of Liveness.
Temporal Logic Considered Confusing.9. Real Time.
The Hour Clock Revisited.
Real-Time Specifications in General.
A Real-Time Caching Memory.
Hybrid System Specifications.
Remarks on Real Time.10. Composing Specifications.
Composing Two Specifications.
Composing Many Specifications.
Composition with Shared State.
Explicit State Changes.
Composition with Joint Actions.
A Brief Review.
A Taxonomy of Composition.
Joint Actions Reconsidered.
Liveness and Hiding.
Liveness and Machine Closure.
A Binary Hour Clock.
Refining a Channel.
Interface Refinement in General.
Should You Compose?.11. Advanced Examples.
Specifying Data Structures.
Solving Differential Equations.
Other Memory Specifications.
The Correctness Condition.
A Serial Memory.
A Sequentially Consistent Memory.
The Memory Specifications Considered.
III: The Tools. 12. The Syntactic Analyzer. 13. The TLATEX Typesetter.
How It Typesets the Specification.
How It Typesets Comments.
Adjusting the Output Format.
Using LATEX Commands.14. The TLC Model Checker.
Introduction to TLC.
What TLC Can Cope With.
How TLC Evaluates Expressions.
Assignment and Replacement.
Evaluating Temporal Formulas.
How TLC Computes States.
How TLC Checks Properties.
Views and Fingerprints.
Taking Advantage of Symmetry.
Limitations of Liveness Checking.
The TLC Module.
How to Use TLC.
Debugging a Specification.
Hints on Using TLC Effectively.
What TLC Doesn't Do.
The Fine Print.
The Grammar of the Configuration File.
Comparable TLC Values.
IV: The TLA+ Language. Mini-Manual 268-273. 15. The Syntax of TLA+.
The Simple Grammar.
The Complete Grammar.
Precedence and Associativity.
The Lexemes of TLA+.16. The Operators of TLA+.
The Choose Operator.
Interpretations of Boolean Operators.
The Let/In Construct.
The Operators of Set Theory.
. Nonconstant Operators.
Basic Constant Expressions.
The Meaning of a State Function.
Temporal Operators.17. The Meaning of a Module.
Operators and Expressions.
The Order and Arity of an Operator.
Simplifying Operator Application.
The Meaning of a ?? Expression.
The Meaning of a Module.
Theorems and Assumptions.
Correctness of a Module.
The Semantics of Instantiation.18. The Standard Modules.
The Numbers Modules.Index. 032114306XT07022002
This book is the distillation of over 25 years of work by one of the world's most renowned computer scientists. A specification is a written description of what a system is supposed to do, plus a way of checking to make sure that it works. Specifying a system helps us understand it. It's a good idea to understand a system before building it, so it's a good idea to write a specification of a system before implementing it. The most effective tool to describe a specification is the Temporal Logic of Actions, or TLA, because it provides a mathematical, i.e. precise, foundation for describing systems. TLA+ is the language the author developed to write the mathematical specifications. TLA+ is available freely on the web. It can be used for both software and hardware. In fact, Intel is using TLA+ with great success in the design of a new chip. The book is divided into four parts. The first part contains all that most programmers and engineers need to know about writing specifications. The second part contains more advanced material for more sophisticated readers. The third and fourth parts comprise a reference manual for TLA+ - both the language itself as well as its tools.
About the Author
Leslie Lamport, a computer scientist, is well known for his contributions to concurrent computing and distributed systems. His "Time, Clocks, and the Ordering of Events in a Distributed System" paper has been honored for its enduring influence on the field. Lamport is also known for creating the LaTeX typesetting system and the best-selling book, LaTeX, Second Edition, which documents it (Addison-Wesley, 1994). Now at Microsoft Research in Mountain View, California, he began his work on TLA+ at the Digital (later Compaq) Systems Research Center in Palo Alto. Lamport, who earned his Ph.D. in mathematics from Brandeis University, is a member of the National Academy of Engineering.