Methodology, III:
The Program and Algebra
Our example used a fairly mathematical notation, of the sort usually
found in algebra texts. This is an informal notation, but not very
far removed from an actual program. We could re-write the function to
look more conventional and program-like:
in-list? (i, sl) =
if (empty? (sl))
false
if (i = first (sl))
true
in-list? (i, rest (sl))
We've just assumed the existence of a few primitive functions and
written the program in terms of them. These primitive functions
behave in a very algebraic manner. For example,
empty? (empty) = true
empty? (put (i, sl)) = false
first (put (i, sl)) = i
rest (put (i, sl)) = sl
In flavor, these equations are no different from those students are
exposed to already:
(x + y)2 = x2 + 2 x y + y2
x (y + z) = x y + x z
Using the algebraic rules, students can compute the result of
their programs exactly as they would reduce an algebraic term to a
value. For this reason, our methodology is a natural extension of
high-school algebra. If both capitalizes on the knowledge they
already have, and broadens their understanding of that knowledge.
One final puzzle: what should the algebraic rules be for equations
like?
first (empty)
rest (empty)
These expressions are faulty: There is no meaningful value
they can return. They reflect an error in the program, and must be
reported immediately so that the student understands where the mistake
is, and can correct it. Unfortunately, most programming languages
blithely ignore these situations and continue to compute, producing
meaningless answers. These languages destroy most of the advantages
of this systematic methodology. We will have more to say on the
choice of programming language later.
Now let's summarize this process.
PLT /
scheme@cs.rice.edu
Last modified at 10:48:40 CST on Monday, November 10, 1997