You are previewing Systematic Program Design.
O'Reilly logo
Systematic Program Design

Book Description

A systematic program design method can help developers ensure the correctness and performance of programs while minimizing the development cost. This book describes a method that starts with a clear specification of a computation and derives an efficient implementation by step-wise program analysis and transformations. The method applies to problems specified in imperative, database, functional, logic and object-oriented programming languages with different data, control and module abstractions. Designed for courses or self-study, this book includes numerous exercises and examples that require minimal computer science background, making it accessible to novices. Experienced practitioners and researchers will appreciate the detailed examples in a wide range of application areas including hardware design, image processing, access control, query optimization and program analysis. The last section of the book points out directions for future studies.

Table of Contents

  1. Cover Page
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Table of Contents
  7. Preface
  8. 1 Introduction
    1. 1.1 From clarity to efficiency: systematic program design
    2. 1.2 Iterate, incrementalize, and implement
    3. 1.3 Languages and cost models
    4. 1.4 History of this work
  9. 2 Loops: Incrementalize
    1. 2.1 Loops with primitives and arrays
    2. 2.2 Incrementalize: maintain invariants
    3. 2.3 Iterate and implement: little to do
    4. 2.4 Example: hardware design
    5. 2.5 Example: image processing
    6. 2.6 Need for higher-level abstraction
  10. 3 Sets: Incrementalize and Implement
    1. 3.1 Set expressions—data abstraction
    2. 3.2 Iterate: compute fixed points
    3. 3.3 Incrementalize: compose incremental maintenance
    4. 3.4 Implement: design linked data structures
    5. 3.5 Example: access control
    6. 3.6 Example: query optimization
    7. 3.7 Need for control abstraction
  11. 4 Recursion: Iterate and Incrementalize
    1. 4.1 Recursive functions—control abstraction
    2. 4.2 Iterate: determine minimum increments, transform recursion into iteration
    3. 4.3 Incrementalize: derive incremental functions, achieve dynamic programming
    4. 4.4 Implement: use linked and indexed data structures
    5. 4.5 Example: combinatorial optimization
    6. 4.6 Example: math and puzzles
    7. 4.7 Need for data abstraction
  12. 5 Rules: Iterate, Incrementalize, and Implement
    1. 5.1 Logic rules-data abstraction and control abstraction
    2. 5.2 Iterate: transform to fixed points
    3. 5.3 Incrementalize: exploit high-level auxiliary maps
    4. 5.4 Implement: design linked and indexed data structures
    5. 5.5 Time and space complexity guarantees
    6. 5.6 Example: program analysis
    7. 5.7 Example: trust management
    8. 5.8 Need for module abstraction
  13. 6 Objects: Incrementalize Across Module Abstraction
    1. 6.1 Objects with fields and methods—module abstraction
    2. 6.2 Queries and updates: clarity versus efficiency
    3. 6.3 Incrementalize: develop and apply incrementalization rules
    4. 6.4 Example: health records
    5. 6.5 Example: robot games
    6. 6.6 Invariant-driven transformations: incrementalization rules as invariant rules
    7. 6.7 Querying complex object graphs
  14. 7 Conclusion
    1. 7.1 A deeper look at incrementalization
    2. 7.2 Example: sorting
    3. 7.3 Building up and breaking through abstractions
    4. 7.4 Implementations and experiments
    5. 7.5 Limitations and future work
  15. References
  16. Index