# Write Small Functions Using Examples

(Difference between revisions)
 Revision as of 14:53, 2 August 2009 (edit)m (Write Small Functions moved to Write Small Functions Using Examples: turns out to be a better motivation)← Previous diff Revision as of 14:58, 2 August 2009 (edit) (undo)m Next diff → Line 8: Line 8: false false - It might not look it, but this function is pretty huge. A mathematical function can be understood as a set, specifically some subset of the Cartesian product of all the sets that are its domain and range. Here the domain is the set of all int values and the range is the set of all boolean values. If these were the same size as in Java then there would be 2L * (Integer.MAX_VALUE + (-1L * Integer.MIN_VALUE) + 1L) or 8,589,934,592 members of the set int * boolean. To produce evidence that this function as written is correct then in principle we would need to create checked examples for all 4.3×109 possible invocations. The function atari as written is trivial, but because the function it models is so big it would be very hard to produce strong evidence that it is correct. This is the essence of the claim that test cannot prove the absence of bugs. + This function is larger than it looks. A mathematical function can be understood as a set, specifically some subset of the Cartesian product of all the sets that are its domain and range. Here the domain is the set of all int values and the range is the set of all boolean values. If these were the same size as in Java then there would be 2L * (Integer.MAX_VALUE + (-1L * Integer.MIN_VALUE) + 1L) or 8,589,934,592 members of the set int * boolean. Only half of these are members of the subset that is our function, but still to produce compelling evidence that this function as written is correct then in principle we would need to create checked examples for all 4.3×109 possible invocations. - Tests can demonstrate the presence of features, though. But still we have this issue of size. + This is the essence of the claim that test cannot prove the absence of bugs. Tests can demonstrate the presence of features, though. But still we have this issue of size. The problem domain helps us out. The nature of Go means that number of liberties is not any int, but exactly one of {1,2,3,4}. So we could alternatively write: The problem domain helps us out. The nature of Go means that number of liberties is not any int, but exactly one of {1,2,3,4}. So we could alternatively write: Line 19: Line 19: false false This is much more tractable, the function is computed is now a set with at most 8 members. In fact, 4 checked examples would constitute evidence of complete certainty that the function is correct. This is much more tractable, the function is computed is now a set with at most 8 members. In fact, 4 checked examples would constitute evidence of complete certainty that the function is correct. + + This is one reason why its a good idea to use new types closely related to the problem domain to write programs, rather than use native types everywhere. Using domain–inspired types can often make our functions much smaller.

## Revision as of 14:58, 2 August 2009

We would like to write code that is correct, and have evidence on hand that it is correct. It can help with both issues is to think about the "size" of a functions. 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 their opponent. The rule is that a stone with two or more free spaces adjacent to it (these are called liberties) is not in atari. While it can be surprisingly tricky to count how many liberties a stone has, once we know that working out if the stone is in atari is easy. We might begin by writing a function (in pseudo–code) like this:

```boolean atari (int libertyCount)
if libertyCount < 2
true
false
```

This function is larger than it looks. A mathematical function can be understood as a set, specifically some subset of the Cartesian product of all the sets that are its domain and range. Here the domain is the set of all `int` values and the range is the set of all `boolean` values. If these were the same size as in Java then there would be `2L * (Integer.MAX_VALUE + (-1L * Integer.MIN_VALUE) + 1L)` or 8,589,934,592 members of the set `int * boolean`. Only half of these are members of the subset that is our function, but still to produce compelling evidence that this function as written is correct then in principle we would need to create checked examples for all 4.3×109 possible invocations.

This is the essence of the claim that test cannot prove the absence of bugs. Tests can demonstrate the presence of features, though. But still we have this issue of size.

The problem domain helps us out. The nature of Go means that number of liberties is not any `int`, but exactly one of {1,2,3,4}. So we could alternatively write:

```LibertyCount = {1,2,3,4}
boolean atari(LibertyCount libertyCount)
if libertyCount < 2
true
false
```

This is much more tractable, the function is computed is now a set with at most 8 members. In fact, 4 checked examples would constitute evidence of complete certainty that the function is correct.

This is one reason why its a good idea to use new types closely related to the problem domain to write programs, rather than use native types everywhere. Using domain–inspired types can often make our functions much smaller.