97 Things Every Programmer Should Know

(Chris Devlin) #1

(^188) 97 Things Every Programmer Should Know

Write Small Functions Using Examples .................

Keith Braithwaite

WOULDE W LiKE TO WRiTE CODE THAT iS CORRECT, and have evidence on
hand that it is correct. It can help with both issues to think about the “size” of a
function. Not in the sense of the amount of code that implements a function—
although that is interesting—but rather the size of the mathematical function
that our code manifests.

For example, in the game of Go there is a condition called atari in which a
player’s stones may be captured by her opponent: a stone with two or more free
spaces adjacent to it (called liberties) is not in atari. It can be tricky to count
how many liberties a stone has, but determining atari is easy if that is known.
We might begin by writing a function like this:

boolean atari(int libertyCount)
libertyCount < 2

This is larger than it looks. A mathematical function can be understood as a
set, some subset of the Cartesian product of the sets that are its domain (here,
int) and range (here, boolean). If those sets of values were the same size as in
Java, then there would be 2L(Integer.MAX_VALUE+(–1LInteger.MIN_VALUE)+1L)
or 8,589,934,592 members in the set int×boolean. Half of these are members
of the subset that is our function, so to provide complete evidence that our
function is correct, we would need to check around 4.3×109 examples.

Free download pdf