The Evolution of Programs

by Alan M. Dershowitz

1. Introduction.- 2. General Overview.- 2.1. Introduction.- 2.2. The Problem.- 2.3. Annotation.- 2.4. Debugging.- 2.5. Modification.- 2.6. Abstraction.- 2.7. Instantiation.- 2.8. Synthesis.- 2.9. Discussion.- 3. Program Modification and Debugging.- 3.1. Introduction.- 3.2. Overview.- 3.2.1. Basic Analogy.- 3.2.2. Special Debugging.- 3.2.3. Correctness Considerations.- 3.2.4. Completing an Analogy.- 3.3. Examples.- 3.3.1. Real Division.- 3.3.1.1. First Correction.- 3.3.1.2. Second Correction.- 3.3.2. Integer Division.- 3.3.2.1. Modification.- 3.3.2.2. Extension.- 3.3.3. Array Search.- 3.3.3.1. Modification.- 3.3.3.2. Transformation.- 3.4. Discussion.- 3.4.1. Pre-modification Phase.- 3.4.2. Modification Phase.- 3.4.3. Post-modification Phase.- 4. Program Abstraction and Instantiation.- 4.1. Introduction.- 4.2. Overview.- 4.2.1. Basic Analogy.- 4.2.2. Correctness Considerations.- 4.2.3. Instantiation.- 4.2.4. Special Program Transformations.- 4.3. Examples.- 4.3.1. Extremum.- 4.3.2. Binary Search.- 4.3.3. Associative Recursion.- 4.4. Discussion.- 5. Program Synthesis and Extension.- 5.1. Introduction.- 5.2. Overview.- 5.2.1. Strengthening.- 5.2.2. Splitting.- 5.2.2.1. Disjoint Goals.- 5.2.2.2. Protection.- 5.2.2.3. Preservation.- 5.2.3. Assignments.- 5.2.4. Conditionals.- 5.2.5. Loops.- 5.2.5.1. Forward Iterative Loops.- 5.2.5.2. Backward Iterative Loops.- 5.2.5.3. Termination.- 5.2.5.4. Recursive Loops.- 5.2.6. Extension.- 5.3. Examples.- 5.3.1. Array Minimum.- 5.3.1.1. Goal Splitting.- 5.3.1.2. Loop Formation.- 5.3.1.3. Conditional Formation.- 5.3.1.4. Extension.- 5.3.2. Integer Square-Root.- 5.3.2.1. Goal Splitting.- 5.3.2.2. Loop Formation.- 5.3.2.3. Alternatives.- 5.3.2.4. Extension.- 5.3.2.5. Binary Integer Square-Root.- 5.3.3. Associative Recursion.- 5.3.3.1. Recursive Solution.- 5.3.3.2. Iterative Solution.- 5.3.4. Partition.- 5.3.4.1. First Solution.- 5.3.4.2. Second Solution.- 5.4. Discussion.- 6. Program Annotation and Analysis.- 6.1. Introduction.- 6.2. Overview.- 6.2.1. Notation and Terminology.- 6.2.2. Assignment Rules.- 6.2.3. Control Rules.- 6.2.4. Schematic Rules.- 6.2.5. Heuristic Rules.- 6.2.6. Counters.- 6.3. Examples.- 6.3.1. Real Division.- 6.3.1.1. Assignment Rules.- 6.3.1.2. Control Rules.- 6.3.1.3. Heuristic Rules.- 6.3.1.4. Analysis.- 6.3.2. Array Minimum.- 6.3.2.1. Assignment Rules.- 6.3.2.2. Control Rules.- 6.3.2.3. Generalization Heuristic.- 6.3.2.4. Analysis.- 6.3.3. Selection Sort.- 6.3.3.1. Algorithmic Rules.- 6.3.3.2. Heuristics.- 6.3.3.3. Analysis.- 6.4. Discussion.- 7. General Discussion.- Appendix 1: Global Transformations.- Appendix 2: Program Schemata.- Appendix 3: Synthesis Rules.- Appendix 4: Annotation Rules.- 4.1. Assignment Rules.- 4.1.1. Range Rules.- 4.1.2. Set Assignment Rules.- 4.1.3. Counter Relation Rules.- 4.1.4. Basic Relation Rules.- 4.1.5. Assorted Relation Rules.- 4.2. Control Rules.- 4.2.1. Control Axioms.- 4.2.2. Assignment Control Rules.- 4.2.3. Conditional Control Rules.- 4.2.4. Loop Control Rules.- 4.2.5. Value Rules.- 4.3. Heuristic Rules.- 4.3.1. Control Heuristics.- 4.3.2. Dangerous Heuristics.- Appendix 5: Implementation.- 5.1. Introduction.- 5.2. Modification.- 5.3. Synthesis.- 5.4. Annotation.- References.- Name Index.

368 pages, Paperback

First published January 1, 1983

About the author

Alan Morton Dershowitz is an American lawyer, jurist, and political commentator. He is the Felix Frankfurter Professor of Law at Harvard Law School. He is known for his career as an attorney in several high-profile law cases and commentary on the Arab-Israeli conflict.

He has spent most of his career at Harvard, where, at the age of 28, he became the youngest full professor in its history, until Noam Elkies took the record. Dershowitz still holds the record as the youngest person to become a professor of law there.

As a criminal appellate lawyer, Dershowitz has won thirteen out of the fifteen murder and attempted murder cases he has handled. He successfully argued to overturn the conviction of Claus von Bülow for the attempted murder of Bülow's wife, Sunny. Dershowitz was the appellate advisor for the defense in the criminal trial of O.J. Simpson for the murder of his ex-wife Nicole Simpson and her friend Ronald Goldman.