Write Small Functions Using Examples - Revision history

KeithBraithwaite at 13:20, 5 August 2009

KeithBraithwaite — Wed, 05 Aug 2009 13:20:57 GMT

←Older revision		Revision as of 13:20, 5 August 2009
Line 6:		Line 6:
	libertyCount < 2		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, <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+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<code>boolean</code>. Half of these are members of the subset that is our function, so to ~~produce compelling~~ evidence that our function is correct we would need to check around 4.3×10<sup>9</sup> examples.	+	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+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<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×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.		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.

KeithBraithwaite: tweaks post email conversation

KeithBraithwaite — Wed, 05 Aug 2009 13:05:54 GMT

tweaks post email conversation

←Older revision		Revision as of 13:05, 5 August 2009
Line 4:		Line 4:

	boolean atari(int libertyCount)		boolean atari(int libertyCount)
-	if libertyCount < 2	+	libertyCount < 2
-	~~true~~	+
-	~~false~~	+

	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+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<code>boolean</code>. Half of these are members of the subset that is our function, so to produce compelling evidence that our function is correct we would need to check around 4.3×10<sup>9</sup> examples.		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+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<code>boolean</code>. Half of these are members of the subset that is our function, so to produce compelling evidence that our function is correct we would need to check around 4.3×10<sup>9</sup> examples.
Line 16:		Line 14:
	LibertyCount = {1,2,3,4}		LibertyCount = {1,2,3,4}
	boolean atari(LibertyCount libertyCount)		boolean atari(LibertyCount libertyCount)
-	if libertyCount == 1	+	libertyCount == 1
-	~~true~~	+
-	~~false~~	+

-	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.	+	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]]		by [[Keith Braithwaite]]

Kevlin at 11:11, 5 August 2009

Kevlin — Wed, 05 Aug 2009 11:11:44 GMT

←Older revision		Revision as of 11:11, 5 August 2009
Line 3:		Line 3:
	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:		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 libertyCount < 2		if libertyCount < 2
	true		true

Kevlin at 11:06, 5 August 2009

Kevlin — Wed, 05 Aug 2009 11:06:39 GMT

←Older revision		Revision as of 11:06, 5 August 2009
Line 1:		Line 1:
-	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.	+	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 ~~knowing that~~ determining atari is easy. We might begin by writing a function 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)
Line 13:		Line 13:

	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:		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}		LibertyCount = {1,2,3,4}
	boolean atari(LibertyCount libertyCount)		boolean atari(LibertyCount libertyCount)
Line 18:		Line 19:
	true		true
	false		false
-	This is much more tractable~~, the~~ function 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 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.	+
		+	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.
		+
		+	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

KeithBraithwaite: copyedit

KeithBraithwaite — Sun, 02 Aug 2009 18:09:59 GMT

copyedit

←Older revision		Revision as of 18:09, 2 August 2009
Line 18:		Line 18:
	true		true
	false		false
-	This is much more tractable, the function is computed is now a set with at most 8 members, 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 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.	+	This is much more tractable, the function 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 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.

KeithBraithwaite: copyedit

KeithBraithwaite — Sun, 02 Aug 2009 18:02:24 GMT

copyedit

←Older revision		Revision as of 18:02, 2 August 2009
Line 8:		Line 8:
	false		false

-	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 ~~and range. Here the domain is the set of~~ <code>int</code> ~~values~~ and ~~the~~ range ~~that of~~ <code>boolean</code> ~~values~~. If ~~these~~ were the same size as in Java then there would be <code>2L(Integer.MAX_VALUE+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<code>boolean</code>. ~~Only half~~ of these are members of the subset that is our function, so to produce compelling evidence that our function is correct we would need to check around 4.3×10<sup>9</sup> examples.	+	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+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<code>boolean</code>. Half of these are members of the subset that is our function, so to produce compelling evidence that our function is correct we would need to check around 4.3×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.		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 <code>int</code>, 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 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}		LibertyCount = {1,2,3,4}
	boolean atari(LibertyCount libertyCount)		boolean atari(LibertyCount libertyCount)

KeithBraithwaite at 15:16, 2 August 2009

KeithBraithwaite — Sun, 02 Aug 2009 15:16:28 GMT

←Older revision		Revision as of 15:16, 2 August 2009
Line 13:		Line 13:

	The problem domain helps us out. The nature of Go means that number of liberties is not any <code>int</code>, 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 <code>int</code>, but exactly one of {1,2,3,4}. So we could alternatively write:
-	LibertyCount = {1,2,3,4}	+	LibertyCount = {1,2,3,4}
	boolean atari(LibertyCount libertyCount)		boolean atari(LibertyCount libertyCount)
-	if libertyCount ~~< 2~~	+	if libertyCount == 1
	true		true
	false		false
	This is much more tractable, the function is computed is now a set with at most 8 members, 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 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.		This is much more tractable, the function is computed is now a set with at most 8 members, 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 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.

KeithBraithwaite at 15:14, 2 August 2009

KeithBraithwaite — Sun, 02 Aug 2009 15:14:02 GMT

←Older revision		Revision as of 15:14, 2 August 2009
Line 1:		Line 1:
	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.		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:	+	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 knowing that determining atari is easy. We might begin by writing a function like this:

	boolean atari (int libertyCount)		boolean atari (int libertyCount)
Line 8:		Line 8:
	false		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~~ <code>int</code> values and the range ~~is the set~~ of ~~all~~ <code>boolean</code> values. If these were the same size as in Java then there would be <code>2L(Integer.MAX_VALUE+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members of the set <code>int</code>×<code>boolean</code>. 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×10<sup>9</sup> ~~possible invocations~~.	+	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 and range. Here the domain is the set of <code>int</code> values and the range that of <code>boolean</code> values. If these were the same size as in Java then there would be <code>2L(Integer.MAX_VALUE+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members in the set <code>int</code>×<code>boolean</code>. Only half of these are members of the subset that is our function, so to produce compelling evidence that our function is correct we would need to check around 4.3×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.		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.
Line 18:		Line 18:
	true		true
	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, 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 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.
-		+
-	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.	+

KeithBraithwaite at 15:06, 2 August 2009

KeithBraithwaite — Sun, 02 Aug 2009 15:06:28 GMT

←Older revision		Revision as of 15:06, 2 August 2009
Line 8:		Line 8:
	false		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 <code>int</code> values and the range is the set of all <code>boolean</code> values. If these were the same size as in Java then there would be <code>2L(Integer.MAX_VALUE+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members of the set <code>int * boolean</code>. 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×10<sup>9</sup> possible invocations.	+	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 <code>int</code> values and the range is the set of all <code>boolean</code> values. If these were the same size as in Java then there would be <code>2L(Integer.MAX_VALUE+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members of the set <code>int</code>×<code>boolean</code>. 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×10<sup>9</sup> 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.		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.

KeithBraithwaite at 15:05, 2 August 2009

KeithBraithwaite — Sun, 02 Aug 2009 15:05:46 GMT

←Older revision		Revision as of 15:05, 2 August 2009
Line 8:		Line 8:
	false		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 <code>int</code> values and the range is the set of all <code>boolean</code> values. If these 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 of the set <code>int * boolean</code>. 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×10<sup>9</sup> possible invocations.	+	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 <code>int</code> values and the range is the set of all <code>boolean</code> values. If these were the same size as in Java then there would be <code>2L(Integer.MAX_VALUE+(-1LInteger.MIN_VALUE)+1L)</code> or 8,589,934,592 members of the set <code>int * boolean</code>. 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×10<sup>9</sup> 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.		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.