Unit Testing and Test Cases
in [OOP]
|
Prev: Teaching OO
Next: multimethod + multiple inheritance
From: Oliver Wong on 13 Mar 2006 10:21 "Kenneth P. Turvey" <kt-usenet(a)squeakydolphin.com> wrote in message news:pan.2006.03.12.08.43.30.195267(a)squeakydolphin.com... > > On Mon, 06 Mar 2006 20:27:16 +0000, Oliver Wong wrote: > >> For any contract "A" with runnable pre-conditions, if there exists a >> client C who accepts contract A and uses an implementation of that >> contract >> in their program, then it is always possible to construct a contract B >> such >> that it has fewer (possibly zero) pre-conditions than contract A did, and >> whose implementation can swapped in for the implementation of contract A >> without changing the behaviour of the program (where behaviour includes >> asymptotic runtime). > > I've been thinking about this a bit and I think your statement is still > too strong. For example I have a method that updates some sub-set in a > set: > > void updateSubSet(SomeParam param) { > .. > } > > The preconditions include the pre-condition that no element of set will > be null and the post-conditions include the post-condition that no element > of set will be null. > > The method must make sure that any updates it makes to the the set do not > result in null values. Since it can be confident that the set didn't > contain any null values when it was called, it was a precondition, it can > guarantee that the set will not have any null when it completes. > > In order to replace this method with a method that does not have the > pre-condition requiring that all elements are defined in the set means > that the method must iterate over every element in the set and check it. > This is not asymptoticly the same as the original since the original only > had to look at the subset. We can imagine that the entire set is possibly > infinite. You would be correct if I had omitted the keyword "runnable" before "pre-conditions", but since the pre-condition "no element of the set will be null" is not runnable in the case where the set is infinite, then this "counter example" doesn't actually counter my statement above. I must admit I hadn't considered the example you proposed though, and it does make me more nervous now about the truth value of my statement. ;) - Oliver
From: Kenneth P. Turvey on 13 Mar 2006 16:35 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Mon, 13 Mar 2006 15:21:35 +0000, Oliver Wong wrote: > You would be correct if I had omitted the keyword "runnable" before > "pre-conditions", but since the pre-condition "no element of the set will be > null" is not runnable in the case where the set is infinite, then this > "counter example" doesn't actually counter my statement above. Even with the "runnable" one can imagine that checking the entire set is O(n^2) while just checking the subset is O(n). The point was that the extra time a method takes after your transformation is unbounded by the original runtime. > I must admit I hadn't considered the example you proposed though, and it > does make me more nervous now about the truth value of my statement. ;) I think your statement is true until you start making claims about runtime. As soon as you do, I think you are leaving out a large class of possible pre-conditions. The example I just gave is an example of a "Good Data in -> Good data out" set of conditions that isn't at all atypical and often would require quite a bit of effort to convert to "Any data in -> Good data out or exception". - -- Kenneth P. Turvey <kt-usenet(a)squeakydolphin.com> XMPP IM: kpturvey(a)jabber.org Yahoo IM: kpturvey2 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFEFeWdi2ZgbrTULjoRAsZ1AJ9WbW3n2ESKrvSb8zSuZYxoFS1sJwCg12wa JtvA9KrxCLz4Jghr3r3Re74= =FQvw -----END PGP SIGNATURE-----
From: Oliver Wong on 13 Mar 2006 16:49
"Kenneth P. Turvey" <kt-usenet(a)squeakydolphin.com> wrote in message news:pan.2006.03.13.21.35.32.807446(a)squeakydolphin.com... > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > On Mon, 13 Mar 2006 15:21:35 +0000, Oliver Wong wrote: > >> You would be correct if I had omitted the keyword "runnable" before >> "pre-conditions", but since the pre-condition "no element of the set will >> be >> null" is not runnable in the case where the set is infinite, then this >> "counter example" doesn't actually counter my statement above. > > Even with the "runnable" one can imagine that checking the entire set is > O(n^2) while just checking the subset is O(n). The point was that the > extra time a method takes after your transformation is unbounded by the > original runtime. I'll try to make this discussion more concrete by providing pseudo code. So contract A, and implementation A, look like this: /* pre: data does not contain null. post: return some subset of data. This subset will not contain null. */ public implementationA(data) { return getEveryOtherElementIn(data); } /* pre: none. post: returns some subset of data. If data did not contain null, the subset will not contain null either. */ public implementationB(data) { return getEveryOtherElementIn(data); } > >> I must admit I hadn't considered the example you proposed though, and >> it >> does make me more nervous now about the truth value of my statement. ;) > > I think your statement is true until you start making claims about > runtime. As soon as you do, I think you are leaving out a large class of > possible pre-conditions. The example I just gave is an example of a "Good > Data in -> Good data out" set of conditions that isn't at all atypical and > often would require quite a bit of effort to convert to "Any data in -> > Good data out or exception". You are probably correct about it being difficult to convert "Good Data in -> Good Data out" to "Any data in -> Good data out or exception", but perhaps it's "always easy" to convert it to "Good data in -> Good data out; Bad data in -> Bad data out". - Oliver |