Programming in the 1990s

Programming is a fascinating and challenging subject. Unfortunately, it is rarely presented as such. Most often it is taught by "induction": features of some famous programming languages are given operational meaning (e.g. a loop "goes round and round"), a number of examples are shown, and by induction, we are asked to develop other programs, often radically different from the ones we've seen. Basically we are taught to guess our programs, and then to patch up our guesses. Our errors are given the cute name of "bugs". Fixing them becomes puzzle-solving, as does finding tricks that exploit or avoid poorly designed features of the programming language. The entire process is time-consuming and expensive. And even so, we are never quite sure if our programs really work in all cases. When approached in this way, programming is indeed a dull activity. There is, however, another approach to programming, an approach in which programs can be developed reliably, with attention to the real issues. It is a practical approach based on methodically developing programs from their specifications. Besides being practical, it is exciting. Many programs can be developed with relative ease. Problems which once were difficult can now be solved by beginners. Elegant solutions bring great satisfaction. This is our subject. We are interested in making programming an exciting topic!

0 What can we learn from a cake?.- 0.0 Introduction.- 0.1 What can we learn from a cake?.- 1 Preliminary notions, notations, and terminology.- 1.0 Introduction.- 1.1 The shapes of our calculations.- 1.2 Laws and so on.- 1.3 On avoiding parentheses.- 1.4 On carrying out calculations.- 1.5 Three new arithmetic operators.- 1.6 The problem with the three dots.- 1.7 What are the natural numbers?.- 1.8 A bit about function application.- 1.9 What next?.- 2 Predicates A — Boolean operators.- 2.0 Introduction.- 2.1 The equivalence.- 2.2 The disjunction.- 2.3 Intermezzo on some interesting formulae.- 2.4 The conjunction.- 2.5 The implication.- 2.6 The consequence.- 2.7 The negation.- 2.8 The discrepancy.- 2.9 Summary of binding powers.- 2.10 Final comments.- 2.11 Exercises.- 3 Predicates B — Quantified expressions.- 3.0 How to write quantified expressions.- 3.1 Laws for quantified expressions.- 3.2 Universal quantification.- 3.3 Existential quantification.- 3.4 Some arithmetic quantifications.- 3.5 Other quantified expressions.- 3.6 Additional exercises.- 4 Specifications.- 4.0 Introduction.- 4.1 Assigning meaning to our predicates.- 4.2 Towards writing specifications.- 4.3 Examples of specifications.- 4.4 Intermezzo on the array.- 4.5 More examples of specifications.- 4.6 Intermezzo on ascending functions.- 4.7 Even more examples of specifications.- 4.8 Other notations for functional specifications.- 4.9 Comments on specifications.- 5 The shapes of programs.- 5.0 Introduction.- 5.1 The shapes of programs.- 5.2 When is a program correct?.- 5.3 A bit about wp.S.- 5.4 Defining wp.S for all programs S.- 5.4.0 The skip and the abort.- 5.4.1 The composition.- 5.4.2 The assignment.- 5.4.3 The alternation.- 5.4.4 The repetition.- 6 Intermezzo on calculations.- 7 Developing loopless programs.- 7.0 Introduction.- 7.1 Calculating expressions in assignments.- 7.2 Developing IFs.- 8 Developing loops — an introduction.- 9 Loops A — On deleting a conjunct.- 9.0 Introduction.- 9.1 An example — Integer-division.- 9.2 An example — The linear search (and its billions of uses).- 9.3 An example — 3-tuple sort (and avoiding avoidable case-analyses).- 9.4 An example — Integer-division improved (and postponing design decisions).- 10 Loops B — On replacing constants by fresh variables.- 10.0 Introduction.- 10.1 An example — Evaluating a polynomial.- 10.2 An example — The minimum value.- 10.3 An example — Determining the multiple.- 10.4 An example — A table of cubes.- 10.5 An example — The maximum section sum.- 10.6 An example — The binary search (and its numerous applications).- 10.7 An example — Rearranging an array.- 10.8 An example — The bounded linear search.- 11 Mainly on recursion.- 11.0 Introduction.- 11.1 The general solution.- 11.2 An example — The sum of digits.- 11.3 An example — Exponentiation.- 11.4 Introducing four new types.- 11.5 An example — Reversing a sequence (and the importance of good notation).- 11.6 An example — The post-order of a binary tree.- 11.7 An example — The depth of a binary tree.- 11.8 Exercises.- 12 Back to scratch.- 12.0 Introduction.- 12.1 An example — Evaluating a polynomial (and the discovery of nice specifications).- 12.2 An example — Greatest common divisors (and the discovery of useful properties).- 12.3 An example — All shortest paths (and the specification as logical firewall).- 12.4 A final example — Shiloach’s algorithm.- 12.5 Additional exercises.- 13 Where to go from here.- 13.0 On what we have learned.- 13.1 Where to go from here.- 13.2 Be a little discriminating.- 13.3 Inspirations and acknowledgements.- 13.4 Selected references.- 13.5 If you find a nice example….