Bits of Learning

Learning sometimes happens in big jumps, but mostly in little tiny steps. I share my baby steps of learning here, mostly on topics around programming, programming languages, software engineering, and computing in general. But occasionally, even on other disciplines of engineering or even science. I mostly learn through examples and doing. And this place is a logbook of my experiences in learning something. You may find several things interesting here: little cute snippets of (hopefully useful) code, a bit of backing theory, and a lot of gyan on how learning can be so much fun.

Wednesday, December 13, 2023

Test Driven Development -- An Example

This post is written as a model answer to an exam question. As I have clarified earlier, this is way too long to be written in the exam. But, it suffices as an example.

The main philosophy of test-driven development is:
  • Use test cases as specifications.
  • Test cases should be written preferably before the part of the implementation they test. Hence, a newly introduced test would typically fail. Then the code should be modified to make it pass, possibly followed by some refactoring to improve the design.
  • We stop coding as soon as we get all test cases to pass.
  • If we are thinking of a new feature, or cases within the new feature, we should first write a test case corresponding to that.
These tests become part of the project assets, and can be used later at any point in time. TDD is aligned with agile methodology as it focuses on creating work code as opposed to separate documentation.

First set up the testing environment. For simplicity and self-sufficiency, I have created my own TestResult class.
#include <iostream>

using namespace std;

class TestResult {
public:
	const bool result;
	const string message;

	TestResult(bool r, string m) : result(r), message(m) {}
};

The algorithm for palindrome detection that I want to use is the following:

match S with:

case "" --> raise exception

case "x" --> true

case "xy" --> x = y

case "xS'y" --> x = y /\ pal(S')

This is not the most efficient implementation. But that is not the point here. We intend this to be an illustration of the test-driven methodology.

Going by the above algorithm, the first case we would like to test is that if an empty string is given, the function should throw an exception. The test case for checking this is as follows:

TestResult t1() {
	try {
		isPalindrome("");
		TestResult r(false, "Exception not thrown");
		return r;
	}
	catch (string e) {
		TestResult r(true, e);
		return r;
	}
}

The main function or the driver for now is as follows:

int main() {
	TestResult r1 = t1();
	cout << r1.result << ", " << r1.message << endl;
	return 0;
}

The first cut implementation of the isPalindrome function is as follows:

bool isPalindrome(string s) {
	return true;
}

As you can see, it's designed to fail t1. And when we run it, it indeed does:

0, Exception not thrown

Next we modify the function to make t1 pass.

bool isPalindrome(string s) {
	if(s == "") {
		throw string("Empty string provided");
	}
	return true;
}

t1 passes:

1, Empty string provided

Now, we wish to handle the next case.

case "x" --> true

TestResult t2() {
	try {
		bool ans = isPalindrome("a");
		TestResult r(ans == true, "");
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

This test passes without any need of change to the code.

So, we move over to the next case:

case "xy" --> x = y

TestResult t3() {
	try {
		bool ans = isPalindrome("aa");
		TestResult r(ans == true, "Correct!");
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

This passes:

1, Empty string provided
1, 
1, Correct!

But we need to test this case more, for the subcase when we are expecting a negative answer:

TestResult t4() {
	try {
		bool ans = isPalindrome("ab");
		bool result = ans == false;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(ans == false, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

As expected, this test case fails:

1, Empty string provided
1, 
1, Correct!
0, Wrong answer

The palindrome function needs to be modified appropriately to make this test case pass:

bool isPalindrome(string s) {
	if(s == "") {
		throw string("Empty string provided");
	}
	if(s.size() == 1) {
	  return true;
	}
	if(s.size() == 2) {
		return s[0] == s[1];
	}
}

Now, t4 passes:

1, Empty string provided
1, 
1, Correct!
1, Correct

Now that we have tested the third case to our satisfaction, we move over to the final case:

case "xS'y" --> x = y and pal(S')

We first add a test case for testing the final case:

TestResult t5() {
	try {
		bool ans = isPalindrome("aba");
		bool result = ans == true;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

t5 passes without any need of code change.

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct

Let's add t6 to check the negative case:

TestResult t6() {
	try {
		bool ans = isPalindrome("abb");
		bool result = ans == false;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

This fails:

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct
0, Wrong answer

This requires us to implement another function, say 'sub', which gives us a copy of the passed string with the first and the last character omitted. Formally:

"xS'y"  --> raise exception if S' = ""

--> S' if S' != ""

This should be used on strings with length greater than or equal to 2. We make some code changes to make place for the sub function. We begin with a dummy implementation of sub as follows:

string sub(string s) {
  return "Hello";
}

bool isPalindrome(string s) {
	if(s == "") {
		throw string("Empty string provided");
	}
	if(s.size() == 1) {
	  return true;
	}
	if(s.size() == 2) {
		return s[0] == s[1];
	}
	
	return s[0] == s[s.size() - 1] && isPalindrome(sub(s));
}

The above causes t6 to pass, but breaks t5.

1, Empty string provided
1, 
1, Correct!
1, Correct
0, Wrong answer
1, Correct

We understand that this is because of the erroneous implementation of sub function. So, we turn our attention to sub.

We start with a test case to check its first case:

"xS'y"  --> raise exception if S' = ""

TestResult t7() {
	try {
		string ans = sub("a");
		TestResult r(false, "Exception not thrown");
		return r;
	}
	catch (string e) {
		TestResult r(true, e);
		return r;
	}
}

t7 fails. And we make the requisite code modification to get it to pass.

string sub(string s) {
	if(s.size() < 2) {
		throw string("Insufficient size.");
	}
	return "Hello";
}

For sure, t7 passes:

1, Empty string provided
1, 
1, Correct!
1, Correct
0, Wrong answer
1, Correct
1, Insufficient size.

But t5 is still failing. Clearly, all is not well with sub. Anyway, let's proceed to handle the other case in sub:

--> S' if S' != ""

We jump any ceremony and make the following change to sub:

string sub(string s) {
	if(s.size() < 2) {
		throw string("Insufficient size.");
	}
	string new_s = "";
	for(unsigned int i = 1; i < s.size() - 1; i++) {
		new_s += s[i];
	}
	return new_s;
}

t5 passes:

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct
1, Correct
1, Insufficient size.

This has presumably completed our development of the code. However, we need to run it through some more tests before we can call it complete.

TestResult t8() {
try { bool ans = isPalindrome("aba"); bool result = ans == true; string message = result ? "Correct" : "Wrong answer"; TestResult r(result, message); return r; } catch (string e) { TestResult r(false, "Exception: " + e); return r; } } TestResult t9() { try { bool ans = isPalindrome("abba"); bool result = ans == true; string message = result ? "Correct" : "Wrong answer"; TestResult r(result, message); return r; } catch (string e) { TestResult r(false, "Exception: " + e); return r; } } TestResult t10() { try { bool ans = isPalindrome("aaba"); bool result = ans == false; string message = result ? "Correct" : "Wrong answer"; TestResult r(result, message); return r; } catch (string e) { TestResult r(false, "Exception: " + e); return r; } }

To our pleasure, all these new test cases pass in one shot!

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct
1, Correct
1, Insufficient size.
1, Correct
1, Correct
1, Correct

This completes the test driven development of the isPalindrome function.

No comments: