Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers

Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers

by Leslie Lamport
     
 

ISBN-10: 032114306X

ISBN-13: 9780321143068

Pub. Date: 08/02/2002

Publisher: Addison-Wesley

"TLA+ represents the only effective methodology I've seen for visualizing and quantifying algorithmic complexity in a way that is meaningful to engineers."
--Brannon Batson, Processor Architect, Intel Corporation

This long-awaited book shows how to write unambiguous specifications of complex computer systems.

The first part provides a concise and

Overview

"TLA+ represents the only effective methodology I've seen for visualizing and quantifying algorithmic complexity in a way that is meaningful to engineers."
--Brannon Batson, Processor Architect, Intel Corporation

This long-awaited book shows how to write unambiguous specifications of complex computer systems.

The first part provides a concise and lucid introduction to specification, explaining how to describe, with mathematical precision, the behavioral properties of a system--what that system is allowed to do. The emphasis here is on safety properties.

The second part of the book covers more advanced topics, including liveness and fairness, real-time properties, and composition.

The book's final two parts provide a complete reference manual for the TLA+ language and tools, as well as a handy mini-manual. TLA+ is the language developed by the author for writing simple and elegant specifications of algorithms and protocols and for verifying the correctness of a design. The language already has proved to be a valuable aid in understanding and building concurrent and distributed systems. Tools for TLA+ syntax analysis and model checking are freely available from the Web, where you can also find supplemental materials for this book, including exercises.

032114306XB06262002

Product Details

ISBN-13:
9780321143068
Publisher:
Addison-Wesley
Publication date:
08/02/2002
Edition description:
New Edition
Pages:
364
Sales rank:
984,281
Product dimensions:
7.40(w) x 9.00(h) x 1.00(d)

Table of Contents

List of Figures and Tables.

Acknowledgments.

Introduction.

I. Getting Started.

1. A Little Simple Math.

Propositional Logic.

Sets.

Predicate Logic.

Formulas and Language.

2. Specifying a Simple Clock.

Behaviors.

An Hour Clock.

A Closer Look at the Specification.

The Specification in TLA+.

An Alternative Specification.

3. An Asynchronous Interface.

The First Specification.

Another Specification.

Types: A Reminder.

Definitions.

Comments.

4. A FIFO.

The Inner Specification.

Instantiation Examined.

Instantiation Is Substitution.

Parametrized Instantiation.

Implicit Substitutions.

Instantiation Without Renaming.

Hiding the Queue.

A Bounded FIFO.

What We're Specifying.

5. A Caching Memory.

The Memory Interface.

Functions.

A Linearizable Memory.

Tuples as Functions.

Recursive Function Definitions.

A Write-Through Cache.

Invariance.

Proving Implementation.

6. Some More Math.

Sets.

Silly Expressions.

Recursion Revisited.

Functions versus Operators.

Using Functions.

Choose.

7. Writing a Specification: Some Advice.

Why Specify.

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

Temporal Tautologies.

Temporal Proof Rules.

Weak Fairness.

The Memory Specification.

The Liveness Requirement.

Another Way to Write It.

A Generalization.

Strong Fairness.

The Write-Through Cache.

Quantification.

Temporal Logic Examined.

A Review.

Machine Closure.

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.

Zeno Specifications.

Hybrid System Specifications.

Remarks on Real Time.

10. Composing Specifications.

Composing Two Specifications.

Composing Many Specifications.

The FIFO.

Composition with Shared State.

Explicit State Changes.

Composition with Joint Actions.

A Brief Review.

A Taxonomy of Composition.

Interleaving Reconsidered.

Joint Actions Reconsidered.

Liveness and Hiding.

Liveness and Machine Closure.

Hiding.

Open-System Specifications.

Interface Refinement.

A Binary Hour Clock.

Refining a Channel.

Interface Refinement in General.

Open-System Specifications.

Should You Compose?.

11. Advanced Examples.

Specifying Data Structures.

Local Definitions.

Graphs.

Solving Differential Equations.

BNF Grammars.

Other Memory Specifications.

The Interface.

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.

Introduction.

Comment Shading.

How It Typesets the Specification.

How It Typesets Comments.

Adjusting the Output Format.

Output Files.

Trouble-Shooting.

Using LATEX Commands.

14. The TLC Model Checker.

Introduction to TLC.

What TLC Can Cope With.

TLC Values.

How TLC Evaluates Expressions.

Assignment and Replacement.

Evaluating Temporal Formulas.

Overriding Modules.

How TLC Computes States.

How TLC Checks Properties.

Model-Checking Mode.

Simulation Mode.

Views and Fingerprints.

Taking Advantage of Symmetry.

Limitations of Liveness Checking.

The TLC Module.

How to Use TLC.

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

Alignment.

Comments.

Temporal Formulas.

Two Anomalies.

The Lexemes of TLA+.

16. The Operators of TLA+.

Constant Operators.

Boolean Operators.

The Choose Operator.

Interpretations of Boolean Operators.

Conditional Constructs.

The Let/In Construct.

The Operators of Set Theory.

Functions.

Records.

Tuples.

Strings.

Numbers.

. Nonconstant Operators.

Basic Constant Expressions.

The Meaning of a State Function.

Action Operators.

Temporal Operators.

17. The Meaning of a Module.

Operators and Expressions.

The Order and Arity of an Operator.

¿¿ Expressions.

Simplifying Operator Application.

Expressions.

Levels.

Contexts.

The Meaning of a ¿¿ Expression.

The Meaning of a Module.

Extends.

Declarations.

Operator Definitions.

Function Definitions.

Instantiation.

Theorems and Assumptions.

Submodules.

Correctness of a Module.

Finding Modules.

The Semantics of Instantiation.

18. The Standard Modules.

Module Sequences.

Module FiniteSets.

Module Bags.

The Numbers Modules.

Index. 032114306XT07022002

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >