Write Small Functions Using Examples

From WikiContent

Revision as of 09:21, 2 August 2009 by KeithBraithwaite (Talk | contribs)
(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)
Jump to: navigation, search

The 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.

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:

boolean atari (int libertyCount)
    if liberty < 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 int values and the range is the set of all boolean values. If these were the same size as the corresponding ones 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. The function atari 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.

Personal tools