Formal Methods of Software Design
"Formal methods of software design" means using mathematics to write
error-free programs. The mathematics needed is not complicated; it's
just boolean algebra. The word "formal" means the use of a formal
language, so that the program logic can be machine checked. Our
compilers already tell us if we make a syntax error, or a type error, and
they tell us what and where the error is. Formal methods take the next
step, telling us if we make a logic error, and they tell us what and where
the error is. And they tell us this as we make the error, not after the
program is finished. It is good to get any program correct while writing
it, rather than waiting for bug reports from users. It is absolutely
essential for programs that lives will depend on.
The course begins by introducing (or reviewing) the basic logic that will
be used in the course as an aid to programming. Then we look at formal
specifications, and how they are refined to become programs. At each
refinement step, there is a small theorem to be proven (that the step is
correct), so that at the end, the program is correct. Most of the course
uses just those programming constructs that are common to most
programming languages (assignment statement, if statement, array). We
also look at parallel and interacting processes, at probabilistic
programming, and functional programming. Along the way, we
formally define the language features we use (both execution control and
data structures). The emphasis is on program development to meet
specifications, and on program modifications that preserve correctness,
rather than on verification after a program is finished.
Prerequisites: some programming experience, and some mathematical ability.
This course comes in two versions: for-credit, and not-for-credit.
For-Credit: You must be registered at a university that accepts this
course. There is a start date and a finish date for the course. There are
three one-hour tests during the term, each worth 20%, and a two-hour exam at the end, worth 40%.
The times and places of the tests and exam are set by the university. The
printed textbook may be used during the tests and exam. You may have
written anything you like on the printed textbook. No other aids are
allowed. For each question, a blank answer is worth approximately
33%; from that, marks will be awarded for relevant and correct
information, and marks will be deducted for irrelevant or incorrect
information. The graded tests will be given back; the graded exam will
not be given back.
Not-For-Credit: You may start the course whenever you like, proceed at
your own pace, and finish whenever you like. There are no tests or
Whether you are taking the course for-credit or not-for-credit, it is very
valuable for your understanding of the course material to do written
exercises (assignments) as you go through the course. With each lecture
segment, there is a suggested small exercise or two from the textbook,
and there are hundreds more exercises in the textbook for you to choose
from. You may work on them by yourself or in a group. In the
for-credit version, there is an online chat room for students to discuss the
exercises and course material with each other. In the not-for-credit
version, you may email questions to the course instructor. If you choose
to typeset your solutions in LaTeX, here is a helpful set of macros.
When you have done an exercise, send your solution to the course
instructor by email, and you will receive a solution by email to compare
with your solution. Solutions to exercises will not be graded.
The three best motivations for this course are written here,
and here. Read comments on this course's formal methods.
Get the course textbook.
Here are some study questions.
And here is some tutorial material for Chapter 1,
and Chapter 4.
Solutions to exercises are available to course instructors.
There are 34 lectures below for you to watch at your convenience. You may need to zoom in or zoom out in your
browser to get the size right. The title panel lasts a few seconds before the lecture starts.
After each lecture segment listed below, there is a link to the visuals used in the lecture.
For the purpose of printing the visuals, here they are in a more convenient, compact form, by chapter:
visuals for Chapter 0,
visuals for Chapter 1,
visuals for Chapter 2,
visuals for Chapter 3,
visuals for Chapter 4,
visuals for Chapter 5,
visuals for Chapter 6,
visuals for Chapter 7,
visuals for Chapter 8,
visuals for Chapter 9.
Then there is a link to the lecture transcript, then the lecture time.
Finally, there is a suggested exercise or two from the textbook.
Lecture segment 0, visual 0, and transcript 0 [11:28] Introduction; try Exercise 0
Lecture segment 1, visual 1, and transcript 1 [26:17] Boolean Theory; try Exercises 5 and 12
Lecture segment 2, visual 2, and transcript 2 [11:09] Boolean Theory continued, Number Theory, Character Theory; try Exercises 2(f,m,p,s,u) and 16
Lecture segment 3, visual 3, and transcript 3 [14:04] Collections: Bunches and Sets; try Exercises 41 and 44
Lecture segment 4, visual 4, and transcript 4 [25:13] Sequences: Strings and Lists; try Exercise 53
Lecture segment 5, visual 5, and transcript 5 [10:06] Functions; try Exercise 55
Lecture segment 6, visual 6, and transcript 6 [11:22] Quantifiers; try Exercise 63
Lecture segment 7, visual 7, and transcript 7 [17:22] Function Fine Points; try Exercise 81
Lecture segment 8, visual 8, and transcript 8 [27:45] Specification; try Exercise 99
Lecture segment 9, visual 9, and transcript 9 [11:03] Refinement; try Exercises 116 and 120
Lecture segment 10, visual 10, and transcript 10 [23:41] Program Development; try Exercise 125
Lecture segment 11, visual 11, and transcript 11 [26:14] Time Calculation; try Exercise 133
Lecture segment 12, visual 12, and transcript 12 [17:38] Searching; try Exercise 158
Lecture segment 13, visual 13, and transcript 13 [21:27] Two Great Examples: Fast Exponentiation and Fibonacci; try Exercise 161
Lecture segment 14, visual 14, and transcript 14 [14:47] Space Calculation; try Exercise 215
Lecture segment 15, visual 15, and transcript 15 [15:18] Scope and Data Structures; try Exercise 263
Lecture segment 16, visual 16, and transcript 16 [29:28] Control Structures; try Exercise 208(a)
Lecture segment 17, visual 17, and transcript 17 [23:20] Mid-Course Review; try Exercise 202
Lecture segment 18, visual 18, and transcript 18 [13:44] Time and Space Dependence and Assertions; try Exercise 276
Lecture segment 19, visual 19, and transcript 19 [15:04] Subprograms and Aliasing; try Exercise 274
Lecture segment 20, visual 20, and transcript 20 [24:39] Probabilistic Programming; try Exercises 279 and 280
Lecture segment 21, visual 21, and transcript 21 [15:00] Functional Programming; try Exercise 144
Lecture segment 22, visual 22, and transcript 22 [18:21] Recursive Data Definition; try Exercise 309
Lecture segment 23, visual 23, and transcript 23 [8:32] Recursive Program Definition; try Exercise 321(a,b,c)
Lecture segment 24, visual 24, and transcript 24 [27:26] Data Theory Design; try Exercise 338
Lecture segment 25, visual 25, and transcript 25 [12:05] Program Theory Design; try Exercise 351
Lecture segment 26, visual 26, and transcript 26 [21:40] Data Transformation; try Exercise 365
Lecture segment 27, visual 27, and transcript 27 [11:57] Limited Queue; try Exercise 372
Lecture segment 28, visual 28, and transcript 28 [13:47] Independent Composition; try Exercise 375
Lecture segment 29, visual 29, and transcript 29 [21:04] Sequential to Parallel Transformation; try Exercise 381
Lecture segment 30, visual 30, and transcript 30 [15:49] Interactive Variables; try Exercise 386
Lecture segment 31, visual 31, and transcript 31 [19:41] Communication Channels; try Exercise 410
Lecture segment 32, visual 32, and transcript 32 [15:35] Local Channel Declaration, Deadlock, Broadcast; try Exercise 414
Lecture segment 33, visual 33, and transcript 33 [18:45] Final Review; try Exercise 226
total lecture time [10:01:10]