Write Small Functions Using Examples

From WikiContent

(Difference between revisions)
Jump to: navigation, search
(first half or so)
Current revision (13:20, 5 August 2009) (edit) (undo)
m
 
(15 intermediate revisions not shown.)
Line 1: Line 1:
-
The [http://www.digital60.org/birth/program/firstprog.html earliest recorded program] for an electronic computer is covered in crossings-out, amendments, corrections and expressions of uncertainty. From the very beginning programers have struggled to write code that is correct and that they know is correct. One approach that can help with both issues is to think about the "size" of the functions we write. 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.
+
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 one or more of 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 on the board (these are called ''liberties'') is not in atari. While it can be surprisingly tricky to work out 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:
+
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: 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)
+
boolean atari(int libertyCount)
-
if liberty < 2
+
libertyCount < 2
-
true
+
-
false
+
-
This function is simply ''enormous''. A mathematical function can be understood as a set, specifically the product of the sets that are its domain and range. Here the domain is the set of all <code>int</code> values and the range is the set of all <code>boolean</code> values. If these were the same size as the corresponding ones in Java then there would be <code>2L * (Integer.MAX_VALUE + (-1L * Integer.MIN_VALUE) + 1L)</code> or 8,589,934,592 members of the set <code>int * boolean</code>. The function <code>atari</code> as written is also very trivial, but because the function it models is so huge it would be very hard to produce evidence that it is correct. It would be ludicrous to set about creating eight and a half thousand million test cases.
+
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, <code>int</code>) and range (here, <code>boolean</code>). If those sets of values were the same size as in Java then there would be <code>2L*(Integer.MAX_VALUE+(-1L*Integer.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>&times;<code>boolean</code>. 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&times;10<sup>9</sup> examples.
 +
 
 +
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 of a stone is not any <code>int</code>, but exactly one of {1,2,3,4}. So we could alternatively write:
 +
 
 +
LibertyCount = {1,2,3,4}
 +
boolean atari(LibertyCount libertyCount)
 +
libertyCount == 1
 +
 
 +
This is much more tractable: The function computed is now a set with at most eight members. In fact, four checked examples would constitute evidence of complete certainty that the function is correct. This is one reason why it's a good idea to use types closely related to the problem domain to write programs, rather than native types. Using domain–inspired types can often make our functions much smaller. One way to find out what those types should be is to find the examples to check in problem domain terms, before writing the function.
 +
 
 +
by [[Keith Braithwaite]]
 +
 
 +
This work is licensed under a
 +
[http://creativecommons.org/licenses/by/3.0/us/ Creative Commons Attribution 3]
 +
 
 +
 
 +
Back to [[97 Things Every Programmer Should Know]] home page

Current revision

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: 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+(-1L*Integer.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.

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 of a stone 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)
    libertyCount == 1

This is much more tractable: The function computed is now a set with at most eight members. In fact, four checked examples would constitute evidence of complete certainty that the function is correct. This is one reason why it's a good idea to use types closely related to the problem domain to write programs, rather than native types. Using domain–inspired types can often make our functions much smaller. One way to find out what those types should be is to find the examples to check in problem domain terms, before writing the function.

by Keith Braithwaite

This work is licensed under a Creative Commons Attribution 3


Back to 97 Things Every Programmer Should Know home page

Personal tools