PSD: Duncan White's Practical Software Development Pages

Welcome to Duncan White's Practical Software Development (PSD) Pages.

I'm Duncan White, an experienced and professional programmer, and have been programming for well over 20 years, mainly in C and Perl, although I know many other languages. In that time, despite my best intentions:-), I just can't help learning a thing or two about the practical matters of designing, programming, testing, debugging, running projects etc. Back in 2007, I thought I'd start writing an occasional series of articles, book reviews, more general thoughts etc, all focussing on software development without all the guff.

See all my Practical Software Development (PSD) Pages

Testing and Development part 2

In the First Part of this article I discussed testing your programs, an old field newly reinvigorated by the recent strong emphasis on testing in Extreme Programming (XP) and it's spin-off Test Driven Development (TDD)

Now, in part 2, let's work through an example of development and testing, that very well-understood ADT - the stack of elements. Specifically, let's build a stack of integers.

Worked Example of TDD - the Stack
The stack has a simple imperative-style modular interface, expressed here in some vaguely C-like pseudo-code:
    stack s = empty_stack():          create an empty stack.
    bool b = isempty(s):              is the given stack empty?
    void push(element n, stack s):    push n onto stack s, modifying the stack.
    element n = top(stack s):         return the top element off stack s, w/o altering s.
		                      precondition: stack is not empty.
    element n = pop(stack s):         pop the top element off stack s, return the element.
		                      precondition: stack is not empty.
    int nel = depth(stack s):         how many elements are currently on stack s?
    void destroy_stack(stack s):      clear up operation, reclaim stack resources.
Before we think of implementing the stack, let's establish the typical use of this interface - by example:
build a two-element stack with 30 on top and 20 underneath:
    stack s = empty_stack();
    push( 20, s );
    push( 30, s );
pop the values off again by:
    int x = pop(s);
    assert( x == 30 );
    int y = pop(s);
    assert( y == 20 );
test for an empty stack by:
    assert( isempty(s) );
Now we've established typical use, let's think of a few obvious property-check tests - still before choosing the implementation language, let alone writing the code!
test1: the create empty stack/destroy stack test:
    import stack;

    stack s = empty_stack();
    assert( isempty(s) );
    assert( depth(s) == 0 );

    destroy_stack(s);
    exit 0;
test2: the push 1 value test:
    import stack;

    stack s = empty_stack();
    assert( isempty(s) );
    assert( depth(s) == 0 );

    push( 20, s );
    assert( !isempty(s) );
    assert( depth(s) == 1 );
    assert( top(s) == 20 );

    destroy_stack(s);
    exit 0;
Finally, for now, test3: the push 1, pop 1 test:
    import stack;

    stack s = empty_stack();
    assert( isempty(s) );
    assert( depth(s) == 0 );

    push( 20, s );
    assert( !isempty(s) );
    assert( depth(s) == 1 );
    assert( top(s) == 20 );

    assert( pop(s) == 20 );
    assert( isempty(s) );
    assert( depth(s) == 0 );

    destroy_stack(s);
    exit 0;
Note that each of these later tests is an extension of the earlier one. You could think of these as a single test developing over time - test1 tests empty_stack(), is_empty(), depth() and destroy_stack(), test2 also tests push() and top(), and test3 also tests pop().
Developing the Stack module the TDD Way

Ok, turning now to implementation, let's choose C as our implementation language and a Unix environment for the tools surrounding C, eg. make, perl, sh. Specifically, I'm using gcc 4.6.3 on Ubuntu 12.04 Gnu/Linux. Note that the choice of language sometimes effects the interface - if we chose Perl, we might not bother to build a separate stack ADT, because Perl arrays can be trivially used as stacks - via predefined push and pop functions, and their own growable nature.

Let's try the TDD concept of building the tests before implementing the code to make them work, watch them fail, then write code and check the tests now work! We're going to rely heavily on stubs - deliberately leaving function bodies empty (or brokenly simple) so the functions exist but don't do what they should! Of course, the core choice when implementing a stack in C is going to be what data structure to use - but notice that we can start before having decided on the data structure - by stubbing types as well as functions.

TDD Phase I: The Stub Stack
In order to set up the complete framework, let's build a stub stack - in which the pieces (type and operators) exist as stubs - so that we can write the first test, set up the build environment, compile and link the first test against the stub stack, and even run the first test, all before choosing the real type or implementing a single operator for real!

For our stub stack, let's define the stack datatype as the simplest possible type - int. Of course, this is a hopelessly stupid choice - how can a single integer possibly store a collection of elements? But perhaps we'll discover this later..
Note that my interface also uses a non-standard C type: bool, so let's define bool - as I always do - in a little bool.h header file that I copy from project to project:
    /*
     *	bool.h: why oh why isn't this standard?
     */
    typedef enum {false,true} bool;
    
    #define bool_as_str(b)	((b)?"true":"false")
Note that even this most trivial type obeys my every ADT needs display_as_str injunction! Lest you think I'm slavishly following my own stupid rules, we'll use this real soon now!
stack.h follows directly from the interface and the stub type choices we have made:
    /*
     * stack.h: STUB VERSION of stack of integer elements
     */
    typedef int element;              /* element == integer, easy to change for reuse */
    typedef int stack;                /* STUB! A stack is not really an integer:-) */

    extern stack empty_stack(void);   /* create an empty stack */
    extern bool isempty(stack);       /* is the given stack empty? */
    extern int depth(stack);          /* how many elements on stack? */
    extern void push(element, stack); /* push element n onto stack */
    extern element top(stack);        /* return the top element of stack */
    extern element pop(stack);        /* pop the top element off stack */
    extern void destroy_stack(stack); /* clear up operation, reclaim resources */
Next, we implement the stub stack itself stack.c, shown here in a compact form to save space:
    /*
     * stack.c: STUB VERSION of stack of integer elements
     */
    #include <stdio.h>
    #include <assert.h>
    #include "bool.h"
    #include "stack.h"
    
    stack empty_stack(void)       {return -1;}    /* create an empty stack */
    bool isempty(stack s)         {return false;} /* is the given stack empty? */
    int depth(stack s)            {return -1;}    /* how many elements on stack? */
    void push(element n, stack s) {}              /* push element n onto stack s */
    element top(stack s)          {return -1;}    /* look at the top element of stack */
    element pop(stack s)          {return -1;}    /* pop the top element off stack */
    void destroy_stack(stack s)   {}              /* clear up operation, reclaim resources */
Note that every non-void function now returns a value of the correct type (-1 for ints, false for booleans) whereas every void function (procedure!) has an empty body. Some people prefer each stub to print out it's name, but I think that clutters up the output unnecessarily. Of course, the stub implementations don't return the correct values, just arbitrary stub values of the correct types!
Next, we can turn our attention to test1.c, translating what was previously (C-like) pseudo-code into proper compilable C:
    /*
     * test1: the create/check empty/destroy stack test
     */
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include "bool.h"
    #include "stack.h"
    
    int main( void )
    {
    	stack s = empty_stack();
    	assert( isempty(s) );
    	assert( depth(s) == 0 );
    	destroy_stack(s);
    	exit(0);
    }
Now, we need a Makefile to embody all the compilation and testing rules:
    tests   =       test1
    CFLAGS  =       -Wall -g
    CC      =       gcc

    all:    $(tests) check

    test1:          test1.o stack.o
    test1.o:        bool.h stack.h
    stack.o:        bool.h stack.h

    clean:
	rm -f *.o $(tests)

    check:  $(tests)
	./checker $(tests)
It's beyond the scope of this article to explain Makefiles, go read up! However, note that the last rule (the check target) is invoked automatically by make's first rule (the all target), and runs the following Perl script (called checker) on all the tests:
    #!/usr/bin/perl
    
    use strict;
    use warnings;
    
    foreach my $test (@ARGV)
    {
	my $status = system( "./$test" );
	my $result = $status == 0 ? "ok" : "failed";
	print "$test $result\n";
    }
Now, with this framework in place, we can compile our modules test1.c and stack.c, link them to form test1 and run checker test1 - all by typing the single command:
    make
here's the output that produces, annotated slightly:
    gcc -Wall -g   -c -o test1.o test1.c      # compile test1.c
    gcc -Wall -g   -c -o stack.o stack.c      # compile stack.c
    gcc -o test1 test1.o stack.o              # link test1
    ./checker test1                           # run all tests, i.e. test1
    test1: test1.c:15: main: Assertion `isempty(s)' failed.
    test1 failed
To save you typing, a .tgz file containing all files mentioned so far is available for download here. It extracts to create a stack/01a.stub+assert directory containing the complete implementation so far - all the C source code, the Makefile and the checker Perl script.
We got the assertion isempty(s) failed message because the isempty() stub returned false, even when the stack was empty. The assertion message is pretty clear, but it could be improved by being even clearer about what value isempty(s) did deliver (in this case, false), and what value it was expected to deliver (in this case, true). Wouldn't it be nice if we could get this style of output instead:
    test1.c:15 - isempty(s): was false, expected true
We can do this by adapting a brilliant technique from H&T p121 - add a new file check.h (which can also follow you around from project to project) containing CHECK macros (one per type) like:
    #define CHECK_INT(EXPR, EXPECTED)					   \
	do {								   \
	    int rc = EXPR;						   \
	    if( rc != EXPECTED )					   \
	    {								   \
	        fprintf( stderr, "%s:%d - %s: was %d, expected %d\n",      \
		    __FILE__, __LINE__, #EXPR, rc, EXPECTED );             \
		exit(1);						   \
	    }								   \
	} while(0)

    #define CHECK_BOOL(EXPR, EXPECTED)					   \
	do {								   \
	    bool rc = EXPR;						   \
	    if( rc != EXPECTED )					   \
	    {								   \
	        fprintf( stderr, "%s:%d - %s: was %s, expected %s\n",      \
		    __FILE__, __LINE__, #EXPR,				   \
		    bool_as_str(rc), bool_as_str(EXPECTED) );              \
		exit(1);						   \
	    }								   \
	} while(0)
The CHECK macros use C and C pre-processor techniques (including the ANSI C #PARAM syntax which stringifies PARAM - I have to admit this was new to me - and the do { } while(0) to make a block that executes once) in order to produce excellent assertion-style checks and messages. Note that CHECK_BOOL uses the bool_as_str(b) operator.
Each assert( EXPR == EXPECTED ) call can now be replaced with CHECK_INT(EXPR,EXPECTED). Doing this replacement to test1.c, removing assert.h and adding check.h, we obtain:
    #include <stdio.h>
    #include <stdlib.h>
    #include "bool.h"
    #include "check.h"
    #include "stack.h"
    
    int main( void )
    {
    	stack s = empty_stack();
    	CHECK_BOOL( isempty(s), true );
    	CHECK_INT( depth(s), 0 );
    	destroy_stack(s);
    	exit(0);
    }
We also need to alter the Makefile slightly - add a check.h dependency on the test1.o rule, the order doesn't really matter but it's nice to keep it the same as the #includes:
    test1.o:	bool.h check.h stack.h
You can download this modified version (creating the stack/01b.stub+check directory) here. You'll find that version of check.h has a few more CHECK_ macros than shown above.
now make reports our desired output:
    test1.c:15 - isempty(s): was false, expected true
    test1 failed
TDD Phase II: Choose stack type and make test1 pass!
Now, it's time to turn our stub stack into one that works - at least well enough to make test1 pass. As we said above, the core choice is: what data structure are we going to use for the stack itself? There are three obvious possibilities to choose from:

A linked list.

A fixed size array with a count of elements.

A growable array.
The simplest of these is (2) - and quite adequate for us at present. So our type definition wll be:
    #define MAXDEPTH 100
    typedef struct
    {
	int nel;		/* number of elements on the stack */
	element data[MAXDEPTH]; /* elements in data[0..nel-1]      */
    } *stack;
Why is a stack a pointer to the structure rather than the structure itself? Recall that some of our operations take stacks and modify them, as in:
    element pop(stack s);
C passes structures by value, i.e. copying them on input, so changes made within a structure parameter are made to a copy, and lost on return. So, if stack was a structure, we couldn't change it! To fix this, we must either explicitly change the interface to read:
    element pop(stack *s);
and change typical calls to:
    n = pop(&mystack);
which is far too unpleasant to consider, or make a stack a type that allows modification when copied - i.e. a pointer. We've chosen the latter, but that brings up the question of where the storage to which the pointer points come from! The obvious answer is: malloc() it in empty_stack() and free() it in destroy_stack.
Ok, using that type, and our new understanding of storage allocation, let's proceed to implement just those functions needed for test1.c - empty_stack(), isempty(s), depth(s) and destroy_stack(s):
Let's start with empty_stack() and destroy_stack(s), a matching pair - Download this version here:
    stack empty_stack(void)              /* create an empty stack */
    {
        stack s = (stack) malloc(sizeof(*s));
        assert( s != NULL );             /* or return NULL for callers to check */
        s->nel = 0;
        int i;
        for( i = 0; i<MAXDEPTH; i++ )    /* initialise elements; not essential */
        {
            s->data[i] = 0;
        }
        return s;
    }
    
    void destroy_stack(stack s)          /* clear up operation, reclaim resources */
    {
        if( s != NULL ) free(s);
    }
isempty() and depth() are incredibly simple:
    bool isempty(stack s)                /* is the given stack empty? */
    {
        return s->nel == 0;
    }

    int depth(stack s)                   /* how many elements on stack? */
    {
        return s->nel;
    }
Download this version here. Recompiling and rechecking reveals that we are the masters of all [empty stacks] that we survey:
    make
    gcc -Wall -g   -c -o test1.o test1.c
    gcc -Wall -g   -c -o stack.o stack.c
    gcc -o test1 test1.o stack.o
    ./checker test1
    test1 ok
TDD Phase III: Get Test2 Working
Now that test1 succeeded, let's move onto our next test (test2.c, the push 1 value test we discussed earlier), which is the first test to use push() and top(). So, we want to see it fail against the stubs, and then implement push() and top(), and get the test to pass:
Here's test2.c, as before we're using CHECK_* rather than assert:
    /*
     * test2: the push 1 value test.
     */
    #include <stdio.h>
    #include <stdlib.h>
    #include "bool.h"
    #include "check.h"
    #include "stack.h"
    
    int main( void )
    {
	stack s = empty_stack();
	CHECK_BOOL( isempty(s), true );
	CHECK_INT( depth(s), 0 );
	push( 20, s );
	CHECK_BOOL( isempty(s), false );
	CHECK_INT( depth(s), 1 );
	CHECK_INT( top(s), 20 );
	destroy_stack(s);
	exit(0);
    }
Modify the Makefile to include information about compiling and testing test2 - add test2 to the tests variable:
    tests	=	test1 test2
and clone the test1 compilation rules for test2:
    test2:	test2.o stack.o
    test2.o:	bool.h check.h stack.h
Download this version here. Recompiling and rechecking reveals:
    make
    gcc -Wall -g   -c -o test2.o test2.c
    gcc -o test2 test2.o stack.o
    ./checker test1 test2
    test1 ok
    test2.c:19 - isempty(s): was true, expected false
    test2 failed
To refresh our memory, push() is still a stub at this stage, so after the (stub) push(20) call the stack was still empty, so isempty(s) was true. However, a working push() would have made the stack non-empty, so the expected (correct) value of isempty(s) was false. Note that, at a higher level, we expected the test to fail - and it did.
Now, let's implement push(), testing that the stack isn't full, incrementing the number of elements and storing the new element:
    void push(element n, stack s)    /* push element n onto stack s */
    {
	assert( s->nel < MAXDEPTH ); /* not full */
	s->nel++;
	s->data[s->nel] = n;
    }
Download this version here, now the test gets a step further before dying at the top() stub:
    make
    gcc -Wall -g   -c -o stack.o stack.c
    gcc -o test1 test1.o stack.o
    gcc -o test2 test2.o stack.o
    ./checker test1 test2
    test1 ok
    test2.c:21 - top(s): was -1, expected 20
    test2 failed
Fair enough, top() was still a stub, let's add it:
    element top(stack s)             /* look at the top element of stack */
    {
	assert( s->nel > 0 );        /* not empty */
	return s->data[s->nel];
    }
Download this version here, retest - wow, both tests now appear to work:
    make
    gcc -Wall -g   -c -o stack.o stack.c
    gcc -o test1 test1.o stack.o
    gcc -o test2 test2.o stack.o
    ./checker test1 test2
    test1 ok
    test2 ok
Phew! Let's take stock!
We've now developed a stack module that can successively pass our first two test cases (test1 and test2). Test2 ends up having pushed a single integer onto a stack, leaving a non-empty depth 1 stack whose top value was the value we pushed.
In the Third Part of this article, we'll introduce more test cases and get them working via TDD.

d.white@imperial.ac.uk
Back to the first part of this article Back to PSD Top
Written: March-June 2013