Practical Software Development: Use Automation Wherever Possible

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 30 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

Automatic Code Generators: build tools to help you program at a range of small...medium scales.

As programmers, we are used to building large-scale software that (hopefully) performs useful tasks, correctly, and at decent speed. We often use large-scale tools to reduce the amount of code that we must write by hand. For example, tools like Yacc (aka Bison) and Lex (aka Flex), or my own Datadec tool (described in Article 8 of this series) are large tools, that took substantial amounts of time to design and build.
They each solve one problem - letting you write some simple high-level representation of that problem (Yacc: parser grammars in BNF, Lex: lexical analyser rules in regexes, Datadec: recursive data types), and then each tool automatically generates valid C modules from your high-level representation, that are guaranteed to work and which can be linked straight into the rest of your code.
Each of these tools is what the Pragmatic Programmer book calls Code Generators, and the input to such tools is what Kernighan and Pike in The Practice of Programming call Little Languages. Using the Pragmatic Programmer terminology of Code Generators, they exhort us to write Code Generators - programs that write programs. They emphasize that this sounds more complex than it is, that a simple Code Generator can be written in a few minutes and still save hours of work.
So Yacc, Lex and Datadec are (large scale) Code Generators, that repay the time and effort taken to design and build them by enabling programmers to learn these tools once, and then reuse these tools aggressively on many different projects throughout their careers. But when it comes to building such tools, opportunities to build such large-scale tools don't come along very often in a programmer's career - just as well, perhaps, or we'd spend all our time building tools rather than building the software that we're paid to produce!
But what about much smaller Code Generators? There are many occasions when opportunities to build and use small Code Generators come up. This article is going to explore some examples of small to medium Code Generators, and how to design and build them. Here we can use my guiding principle of Ruthless automation to help ourselves: If you find yourself doing something boring and repetitive while programming, consider writing a quick tool to make your own life easier! Don't suffer, write a tool!

The core principle underlying most Code Generators is spotting patterns and then exploiting them.
Case 1: the Perlstub Code Generator

In my Article 4: Perlstub: Building a Tool, Extending your Editor, I described building one small code generator that helps me program in Perl, and how I embedded it in my favourite editor, There, the pattern I spotted was that I laid out every Perl function (subroutine) in a common format, with some duplication - violating the Pragmatic Programmer's Don't Repeat Yourself (DRY) principle. Specifically I would write a function like this:
    #
    # my @nodups = remove_duplicates( @list );
    #     return @nodups, a list in the same order 
    #     as the input @list without the duplicates.
    #
    sub remove_duplicates (@)
    {
        my( @list ) = @_;
        # STUB: body goes here.
    }
It occurred to me that a simple tool could produce all the above - including the entire subroutine stub - from the following "example call description":
    my @nodups = remove_duplicates( @list );
    {
    return @nodups, a list in the same order 
    as the input @list without the duplicates.
    }
I exploited that pattern - and made my life easier - by building a code generator to construct the Perl function declaration from the example call description. Building the code generator took only a modest amount of time, and I then worked out how to invoke this code generator from my favourite editor, passing it some text. Now this code generator saves me time every single time I write a new Perl function, I write the example call, and press a single key, and the function stub is automatically written for me. It's paid back my investment a hundredfold - probably more.
Read the whole of article 4 for more details of how I did that.
Case 2: Ad-hoc Code Generators: Pattern Instances
Often while programming, you find yourself writing hundreds of boring and repetitive pattern instances, differing only in small details. For example:
int plus( int a, int b ) { return (a+b); }
int minus( int a, int b ) { return (a-b); }
int times( int a, int b ) { return (a*b); }
...
Even as you are writing the third instance, your mind should be thinking aha! I've spotted a pattern: all that varies from line to line is (funcname,operator), eg. (plus,+), (minus,-) etc.
If you're only going to need 10 functions of this form, then we'd all grin and bear it - probably figuring out how to drive our favourite editor to efficiently clone and modify the line 10 times. But if you need to generate tens or hundreds of similar functions, why not generate the output automatically using an ad-hoc code generator, scaffolding that you build, use a few times, then discard? especially if you could write the code generator in a few minutes, less time than it would take to do the job by hand!
My technique for such cases is to specify the inputs as a Little Language and show the corresponding outputs:
  INPUT:
    foreach line: F, Op pairs
  OUTPUT:
    foreach line: "int F( int a, int b ) { return (a Op b); }"
A suitable input file might be:
plus,+
minus,-
times,*
div,/
mod,%
If you'd like to follow along - which is best - create a file called input containing the above text.
Now, a code generator does not have to written in the same language as it generates. In this case, we are generating ANSI C - or a very similar language like C++ or Java - but we have a completely free choice of how to build the tool.
This is a simple job for a text manipulation language like Perl, so here's a Perl oneliner I composed in about two minutes to do the job. Notice in passing that perl -nle implements the foreach line in the input logic, the ($f,$op)=split(/,/) does the input parsing, and the print statement the output formatting:
  perl -nle '($f,$op)=split(/,/); print "int ${f}( int a, int b ) { return (a${op}b); }"' < input
Having created the input file (containing the above five lines), run the above command and you'll get the output:
  int plus( int a, int b ) { return (a+b); }
  int minus( int a, int b ) { return (a-b); }
  int times( int a, int b ) { return (a*b); }
  int div( int a, int b ) { return (a/b); }
  int mod( int a, int b ) { return (a%b); }
Even if we insist on doing this in C, it's not that hard, might take about 30 minutes using low-level string manipulation. Is it still worth it? It depends on how much time we stand to save: perhaps yes, perhaps no.
To reduce our time investment - and thus make it more appealling to do - we can use the standard ANSI C library function strtok() which can do the token splitting for us. Using this might reduce the time to 15-20 minutes. If we happen to already have a pre-written readline() function that reads a single line and removes the trailing newline lying around - and I did - then that reduces the time still further.
I had a go, and took about 10 minutes to write a 45-line cgen1.c working C program. Here's a tarball containing a README, a Makefile, cgen1.c. Download and extract it, then compile it and run it via:
  tar xzf tinytool-v1.tgz
  cd tinytool-v1
  make
  ./cgen1 < ../input
to produce the same output as the Perl one-liner generated above.
Of course, having worked out how to generate the functions once via our one-shot tool, whether the Perl one-liner or C program, we might later want more similar functions - and if we're sneaky we might be able to do things we hadn't even thought of when building the code generator - edit the input file and add:
  first,+0*
  second,*0+
  aplus2b,+2*
Now rerun the script and we get:
  ...
  int first( int a, int b ) { return (a+0*b); }
  int second( int a, int b ) { return (a*0+b); }
  int aplus2b( int a, int b ) { return (a*2+b); }
first(a,b) and second(a,b) ignore one of their arguments by multiplying it by zero, and aplus2b(a,b) multiples b by 2 before adding a to it.
By further abusing the notion of an "operator", we can even create functions that square one of their arguments and discard the other:
  asquared,*a+0*
  bsquared,*0+b*
Because our output format (in the print statement) already contains outer brackets in the return statement we generate, we can even introduce apparently mismatched brackets into the "operator" to change the priority:
  a_times_bplus3,)*(3+
And finally, we can even introduce conditional logic using C's ternary choice operator:
  max,>b?a:
The above examples produce the following functions:
  int asquared( int a, int b ) { return (a*a+0*b); }
  int bsquared( int a, int b ) { return (a*0+b*b); }
  int a_times_bplus3( int a, int b ) { return (a)*(3+b); }
  int squaredsum( int a, int b ) { return (a*a+b*b); }
  int max( int a, int b ) { return (a>b?a:b); }
(You'll find the full extended version of input, called fullinput in the tinytool-v1 tarball you downloaded earlier).
An important point here is that A tool - especially an ad-hoc tool - does not need to be perfect. It just needs to be good enough to save you more time in use than it took you to build.
Now we have our tiny code generator, are any improvements worthwhile? how about left-justifying the function names in a field of some suitable width. eg: in the Perl version:
  perl -nle '($f,$op)=split(/,/); printf "int %-15s( int a, int b ) { return (a${op}b); }\n", $f' < input
This gives the rather prettier:
  int plus           ( int a, int b ) { return (a+b); }
  int minus          ( int a, int b ) { return (a-b); }
  int times          ( int a, int b ) { return (a*b); }
  int div            ( int a, int b ) { return (a/b); }
  int mod            ( int a, int b ) { return (a0); }
  int first          ( int a, int b ) { return (a+0*b); }
  int second         ( int a, int b ) { return (a*0+b); }
Next, suppose we decide that the generated function names should have the typename prefixed onto them, eg. int_plus, and they should be displayed in a slightly wider field? Easy:
  perl -nle '($f,$op)=split(/,/); printf "int %-20s( int a, int b ) { return (a${op}b); }\n", "int_${f}"' < input
This gives the output:
  int int_plus            ( int a, int b ) { return (a+b); }
  int int_minus           ( int a, int b ) { return (a-b); }
  int int_times           ( int a, int b ) { return (a*b); }
  int int_div             ( int a, int b ) { return (a/b); }
  int int_mod             ( int a, int b ) { return (a0); }
  int int_first           ( int a, int b ) { return (a+0*b); }
  int int_second          ( int a, int b ) { return (a*0+b); }
Noticing all those "int"s, let's make it easier to change in future:
  perl -nle '$t="int"; ($f,$op)=split(/,/); printf "${t} %-20s( ${t} a, $t b ) { return (a${op}b); }\n", "${t}_${f}"' < input
Now this is getting quite long for a one-liner, let's make a proper Perl script to do it, in order to lay it out more clearly. Create a file called perlgen containing:
  #!/usr/bin/perl -nl
  $t="int";
  ($f,$op)=split(/,/);
  printf "${t} %-20s( ${t} a, $t b ) { return (a${op}b); }\n", "${t}_${f}";
You can find this version in tinytool-v2.tgz - a second tarball. After extracting the contents, on Unix systems, make perlgen executable and run it by:
  chmod +x perlgen
  ./perlgen < input
On other operating systems (like Windows), run it by:
  perl perlgen < input
For greater clarity, you can expand the -nl flags into an explicit for each line loop, only initialise $t once, add another variable $fullname, and even add a couple of comments, let's call this perlgen2 - you'll find this in the above tarball as well:
  #!/usr/bin/perl
  $t="int";
  while( <> )		# for each line in the file
  {
     chomp;
     ($f,$op)=split(/,/);
     $fullname = "${t}_${f}";
     printf "$t %-20s( $t a, $t b ) { return (a${op}b); }\n", $fullname;
  }
perlgen2 behaves exactly the same as perlgen did.
Now, rather than specify the type name in the program, we could choose to make the first line of the input specify the type to use. So alter our input file to read:
  double
  plus,+
  minus,-
  ...
  max,>b?a:
For the first time since we started, we change our tool specification to:
  INPUT:
    first line: T (sets the type used in all other lines)
    foreach other line: F, Op pairs
  OUTPUT:
    foreach other line: "T F( T a, T b ) { return (a Op b); }"
To implement this, we create perlgen3 reading:
  #!/usr/bin/perl
  $t=<>; chomp $t;	# first line specifies the type
  while( <> )		# for each line in the rest of the file
  {
     chomp;
     ($f,$op)=split(/,/);
     $fullname = "${t}_${f}";
     printf "$t %-20s( $t a, $t b ) { return (a${op}b); }\n", $fullname;
  }
You'll find this version (and an equivalent C version called cgen3.c) in tinytool-v3.tgz - a third tarball. Read the README for details again, when you run it the output will be:
  double double_plus    ( double a, double b ) { return (a+b); }
  double double_minus   ( double a, double b ) { return (a-b); }
  ...
  double double_squaredsum( double a, double b ) { return (a*a+b*b); }
  double double_max     ( double a, double b ) { return (a>b?a:b); }
This now opens up the possibility of running the tool more than once with different input files, to generate (say) a set of integer operator functions and then a corresponding set of floating point operator functions.
But neater still would be to run the tool once, but let the user change the type half way through - as in the input:
  TYPE,int
  plus,+
  minus,-
  TYPE,double
  plus,+
  minus,-
This will generate
  int int_plus       ( int a, int b ) { return (a+b); }
  int int_minus      ( int a, int b ) { return (a-b); }
  double double_plus    ( double a, double b ) { return (a+b); }
  double double_minus   ( double a, double b ) { return (a-b); }
To implement this, change our specification to:
  INPUT:
    foreach line: F, Op pair
         special case: if F=="TYPE", T=Op

  OUTPUT:
    foreach F, Op pair unless F=="TYPE":
    	"T T_F( T a, T b ) { return (a Op b); }"
Coding this in Perl gives us perlgen4:
  #!/usr/bin/perl
  while( <> )                                       # for each line in the file
  {
     chomp;
     ($f,$op)=split(/,/);
     if( $f eq "TYPE" ) { $t = $op; next; }
     $t || die "error: TYPE line needed first\n";   # error checking!
     $fullname = "${t}_${f}";
     printf "$t %-20s( $t a, $t b ) { return (a${op}b); }\n", $fullname;
  }
which will generate us the output form we now desire. You'll find this version (and an equivalent C version called cgen4.c) in tinytool-v4.tgz - a fourth tarball.
Our final thought in this section, instead of hardcoding the output format in the program (in the print/printf statement), we could replace the TYPE line with an output TEMPLATE, for example:
  TEMPLATE,int <0>( int a, int b ) { return (a<1>b); }
Here, we pick some arbitrary but simple marker syntax (<0>) meaning "replace this marker with the current value of the first field". Similarly, <1> means "replace this with the second field". Then our Perl program becomes the rather different perlgen5:
  #!/usr/bin/perl
  while( <> )		                    # for each line in the file
  {
     chomp;
     @f=split(/,/,$_,2);		    # split into exactly 2 fields
     if( $f[0] eq "TEMPLATE" )              # handle TEMPLATE lines
     {
        $t=$f[1];
        next;
     }
     $t || die "error: TEMPLATE line needed first\n";# error checking!
     $_=$t;
     s/<([01])>/$f[$1]/g;		    # expand template against @f fields
     die "error: use of $1\n" if /(<\d>)/;
     print "$_\n";
  }
$t is now a template, instead of splitting the line into pairs we split it into an array of 2 pieces (because the template often contains commas in it, and we want the whole thing), then for each non-template line we copy $t to Perl's implicit variable $_, then modify $_ replacing all <n> occurrences with the current value of $f[n], then finally we print $_ and a trailing newline.
This is now a very simple macro processor.
You'll find this version (and an equivalent C version called cgen5.c) in tinytool-v5.tgz - a fifth tarball. The C version uses a completely different method of splitting the string (again because the template may contain commas - strtok() isn't helpful in this situation) and of expanding every occurrence of <n> to the corresponding field value.

Now, how long would it have taken you to build one of these tools for real? You wouldn't have needed a Perl version and a C version - and of course you could have used any language you like to build it. You wouldn't have needed all those different evolutionary versions: you'd have just written the tool that you needed. Whether as a Perl one-liner, or a short Perl program, or a standalone C program, it doesn't matter. It would only take you a few minutes to build such a tool in practice. This is a very small amount of time to invest, the point I'm trying to make here is that the barrier to building tools can be tiny, and easily overcome!
Case 3: Autogenerating Stack Tests via a Code Generator and Little Language
At the end of Part 4 of Article 5, on Test-Driven Development (TDD), after building a stack Abstract Data Type (ADT) via TDD, we ended with an exciting speculation:
Perhaps we could autogenerate a series of stack tests, and their correct answers by defining an operation string: a sequence of stack operations to perform. Then we could build an "interpreter" for operation strings, that executed those operations one by one, calculated what the correct state of the stack should be before and after each operation, and then automatically wrote a C program that performed the corresponding sequence of stack operations - and checked that every operation leaves the correct stack.
In article 5, we didn't build that automatic stack tester: let's do so now!
To recap, we'd built a stack ADT (as a C module) with a series of obvious stack operations (create an empty stack, push an element onto a stack, pop an element off a stack, check whether a given stack is empty etc). We also added a less obvious operation called stack_as_str() that generates a convenient displayable form of the stack as a string (following the idea from my very first PSD article that: every ADT needs a display_as_str operation). For example, a stack on which 10 was pushed, then 20 was pushed on top, would be displayed as [20,10], indicating 20 is on the top of the stack, with 10 underneath it, and nothing under that.
Then we had the idea of defining an operation string such as:
  20 30 -
to represent the sequence of stack operations and checks, such as:

start with an empty stack, check that the printable form of the stack is [].

'20': push 20 onto the stack, then check that the stack has printable form [20].

'30': push 30 onto the stack, check the stack is now [30,20].

'-': pop off a value, check that the popped value is correct (30) and the remaining stack is [20].

Or, in actual C code:
  stack s = empty_stack();     check_stack( s, "[]" );
  push( 20, s );               check_stack( s, "[20]" );
  push( 30, s );               check_stack( s, "[30,20]" );
  CHECK_ELEMENT( pop(s), 30 ); check_stack( s, "[20]" );
  destroy_stack(s);
This "operation string" notation is a nice Little Language - a very compact representation of a whole class of stack tests. For example:
  20 30 45 - - -
could represent the fifth and largest test program presented back in Article 5: the 27-line test5.c, the core of which is:
  stack s = empty_stack();     check_stack( s, "[]" );
  push( 20, s );               check_stack( s, "[20]" );
  push( 30, s );               check_stack( s, "[30,20]" );
  push( 45, s );               check_stack( s, "[45,30,20]" );
  CHECK_ELEMENT( pop(s), 45 ); check_stack( s, "[30,20]" );
  CHECK_ELEMENT( pop(s), 30 ); check_stack( s, "[20]" );
  CHECK_ELEMENT( pop(s), 20 ); check_stack( s, "[]" );
  destroy_stack(s);
Let's start by downloading the final stack C tarball from article5. Unpack it via:
  tar xzf stack-07a.stack_as_str.tgz
and it'll create a stack/07a.stack_as_str directory. Cd into there, and compile it via make. The stack module, and 5 test programs, are compiled and linked. If you then run make check the 5 test programs are run and shown to succeed.
Now, what we'd like to be able to do is run a non-existent program to generate, compile and run a new C test program - enforcing a max stack depth of 5:
  ./autotest '20 30 - -' 5
So our task is to build the simplest possible autotest program. Let's just concentrate on generating the new test program, and ignoring compiling and running it.
The structure of all stack test programs is composed of three pieces: first, some boilerplate code at the top (that does not change) - call this the preamble:
  #include <stdio.h>
  #include <stdlib.h>
  #include "bool.h"
  #include "check.h"
  #include "stack.h"
  
  #define CHECK_ELEMENT CHECK_INT
  
  int main( void )
  {
     stack s = empty_stack();        check_stack(s,"[]");
Second, the variable part, one or more stack push() and pop() operations, together with the desired tests, that implements our operation string. In the case of '20 30 - -' on a stack with capacity>1, these tests might be:
     push(10, s);                    check_stack(s,"[10]");
     push(20, s);                    check_stack(s,"[20,10]");
     CHECK_ELEMENT(pop(s), 20);      check_stack(s,"[10]");
     CHECK_ELEMENT(pop(s), 10);      check_stack(s,"[]");
Third and finally, some bottom-boilerplate, call it the postamble:
     destroy_stack(s);
     return 0;
  }
Temporarily ignoring the variable middle part, the first version of our Perl autotest program, which takes sensible arguments that we'll ignore for now (but use soon) - an operation string and a maximum stack depth, and then creates a file called atest.c containing the preamble and the postamble, is as follows - you can download this, with a few extra comments, via this autotest-v1 link:
  #!/usr/bin/perl -w
  #
  # autotest: generate a stack "correct string" check C program,
  #	    from a mini language, in which "20 30 - -" means
  #	    push 20, push 30, pop, pop, doing all obvious tests
  #	    as we go.  In particular, we need to simulate the
  #	    stack ourselves to know what the correct answer is!
  #
  use strict;
  
  die "Usage: autotest opstr maxdepth\n" unless @ARGV == 2;
  my $opstr = shift;
  my $maxdepth = shift;
  
  sub preamble ($)
  {
  	my( $outfh ) = @_;
  	print $outfh <<EOF;
  #include <stdio.h>
  #include <stdlib.h>
  #include "bool.h"
  #include "check.h"
  #include "stack.h"
  
  #define CHECK_ELEMENT CHECK_INT
  
  int main( void )
  {
  	stack s = empty_stack();       \tcheck_stack(s,"[]");
  EOF
  }
  
  sub postamble ($)
  {
  	my( $outfh ) = @_;
  
  	print $outfh <<EOF;
  	destroy_stack(s);
  	return 0;
  }
  EOF
  }
  
  my $name = "atest";
  open( my $outfh, '>', "$name.c" ) ||
  	die "autotest: can't create $name.c, $!\n";
  preamble( $outfh );
  postamble( $outfh );
  close( $outfh );
  print "look at $name.c now\n";
  exit 0;
Having downloaded this, make it executable via chmod +x autotest-v1 and then run:
  ./autotest-v1 '10 20 - -' 5
(the arguments are ignored for now), this produces atest.c containing:
  #include <stdio.h>
  #include <stdlib.h>
  #include "bool.h"
  #include "check.h"
  #include "stack.h"
  
  #define CHECK_ELEMENT CHECK_INT
  
  int main( void )
  {
  	stack s = empty_stack();       	check_stack(s,"[]");
  	destroy_stack(s);
  	return 0;
  }
If you compile atest.c and link it with stack.o via:
  gcc atest.c stack.o -o atest
then run it via:
  ./atest
It produces no output (indicating that it passed the does an empty stack display as "[]" test).
A better way of arranging to build and run atest into the tests is to edit the Makefile, add atest to the tests macro near the top, and add:
  atest:	atest.o stack.o
  atest.o:	bool.h check.h stack.h
near the bottom of the Makefile (perhaps after the test5 rules for neatness). Having done that, to compile all tests (including atest.c) and check them all, simply:
  make
This should report something like:
  gcc    -c -o atest.o atest.c
  gcc   atest.o stack.o   -o atest
  ./checker test1 test2 test3 test4 test5 atest
  test1 ok
  test2 ok
  test3 ok
  test4 ok
  test5 ok
  atest ok
Ok, having built the infrastructure, let's write the interesting part of autotest, the part that turns our operation string like 10 20 - - (meaning push 10, push 20, pop, pop) into C code, simulating the correct state of the stack before and after we perform our desired stack operations. Approaching this in stages, first let's add the following empty function:
  #
  # my $error = gentest( $outfh, $opstr, $maxdepth ):
  #	Generate the tests for the given $opstr, simulating what the
  #	stack should contain as the tests run.
  #	Returns undef if everything should be fine, or
  #	a specific error message (eg. "stack underflow")
  #
  sub gentest ($$$)
  {
    my( $outfh, $opstr, $maxdepth ) = @_;
    # WRITE ME...
    return undef;
  }
and alter the main code to read as follows (here we've added a gentest() call and changed the final print statement):
  my $name = "atest";
  open( my $outfh, '>', "$name.c" ) ||
	die "autotest: can't create $name.c, $!\n";
  preamble( $outfh );
  my $error = gentest( $outfh, $opstr, $maxdepth );
  postamble( $outfh );
  close( $outfh );
  print "compile $name.c via 'gcc $name.c stack.o', ".
      "then run ./a.out, the expected result is ". ($error//"OK"). "\n";
Next, let's flesh out the structure of the body of the gentest() function: we won't yet generate the desired C code - in fact we won't yet generate any output to the filehandle. But we will simulate the stack in Perl, parse the operation string one token (number or "-") at a time, push and pop values onto/from our simulated stack, and detect when stack overflow or underflow should occur.
    my @stack;	             # our simulated stack, maxdepth $maxdepth
    while( $opstr =~ s/^(\d+|-)\s*// )
    {
      my $op = $1;
      if( $op =~ /^\d/ )
      {
    	push @stack, $op;
    	my $depth = @stack;
	if( $depth > $maxdepth )
	{
	  return "stack overflow";
	}
      } elsif( $op eq '-' )
      {
	if( @stack == 0 )
	{
	  return "stack underflow";
	}
    	my $expect = pop @stack;
    	my $depth = @stack;
      } else
      {
        die "logic error: number/- expected, $op found\n";
      }
    }
Putting this function together, adding it (and the call) to autotest - making autotest-v2. You can download the whole thing, with a few extra comments, via this autotest-v2 link.
If we run autotest-v2 with any valid sequence of stack ops the generated atest.c file is unaltered - because, remember, we've not yet printed out any C code in gentest - but if you give an invalid sequence of stack ops (either too many pops, or too many pushes, causing maxdepth to be hit), the Perl code will tell you that your example is expected to underflow or overflow. For instance, these should be ok:
  ./autotest-v2 '10' 1
  ./autotest-v2 '10 -' 1
  ./autotest-v2 '10 20' 2
  ./autotest-v2 '10 20 -' 2
  ./autotest-v2 '10 20 - -' 2
whereas all these are expected to fail, either overflowing or underflowing the stack:
  ./autotest-v2 '10 20' 1
  ./autotest-v2 '-' 1
  ./autotest-v2 '10 - -' 2
  ./autotest-v2 '10 20 - 30 - - -' 2
Ok, now we must actually make gentest() emit some valid C code. In pseudo-code terms, we want:
  - When pushing a number onto the stack, do 2 things:
    1. emit a C push call
    2. check for overflow - was the stack full before the push?
       - if overflow will occur, emit a comment telling
         the reader to expect stack overflow at this point.

  - When popping a number off the stack, do 2 things:
    1. check for underflow - was the stack empty before pop?
       - if underflow will occur, emit a C pop() call and a
         comment telling the reader to expect stack underflow at this point.
    2. emit a C pop call that checks that the value popped was the correct one.

  - After a push or a pop, emit a C call to check that the stack displays
    as the correct string. using the simulated Perl @stack to work
    out what the correct displayable form of the stack is.
Concentrating first on the push case, our existing structure was:
  push @stack, $op;
  my $depth = @stack;
  if( $depth > $maxdepth )
  {
    return "stack overflow";
  }
We augment this with 2 print statements as follows:
  push @stack, $op;
  print $outfh "\tpush($op, s);      \t\t";
  my $depth = @stack;
  if( $depth > $maxdepth )
  {
    print $outfh "/* <--- STACK OVERFLOW HERE */\n";
    return "stack overflow";
  }
Now concentrating on the pop case, our existing structure was:
  if( @stack == 0 )
  {
    return "stack underflow";
  }
  my $expect = pop @stack;
  my $depth = @stack;
We augment this with 3 print statements as follows:
  if( @stack == 0 )
  {
    print $outfh "\t(void)pop(s);\t\t\t";
    print $outfh "/* <--- STACK UNDERFLOW HERE */\n";
    return "stack underflow";
  }
  my $expect = pop @stack;
  my $depth = @stack;
  print $outfh "\tCHECK_ELEMENT(pop(s), $expect);\t";
Here, we handle the underflow case first, emitting a pop() instruction together with a comment that we expect the pop() to cause stack underflow. We discard the pop() return value because we do not expect pop() to return a value, but rather we expect pop() to fail a precondition and abort.
Then, given a non-empty stack, we emit a pop() call which checks that the value popped is the expected value (popped off the Perl simulated stack).
After the push and the pop code, we calculate the expected displayable form of the stack and then check that the stack displays correctly, by emitting a check_stack() call:
  my $stkstr = join(',', reverse @stack);
  print $outfh qq(check_stack(s,"[$stkstr]");\n);
Putting this all together, gentest()'s body becomes:
  while( $opstr =~ s/^(\d+|-)\s*// )
  {
    my $op = $1;
    if( $op =~ /^\d/ )
    {
      push @stack, $op;
      my $depth = @stack;
      print $outfh "\tpush($op, s);      \t\t";
      if( $depth > $maxdepth )
      {
      	print $outfh "/* <--- STACK OVERFLOW HERE */\n";
      	return "stack overflow";
      }
    } elsif( $op eq '-' )
    {
      if( @stack == 0 )
      {
      	print $outfh "\t(void)pop(s);\t\t\t";
      	print $outfh "/* <--- STACK UNDERFLOW HERE */\n";
      	return "stack underflow";
      }
      my $expect = pop @stack;
      my $depth = @stack;
      print $outfh "\tCHECK_ELEMENT(pop(s), $expect);\t";
    } else
    {
	die "logic error: number/- expected, $op found\n";
    }
    my $stkstr = join(',', reverse @stack);
    print $outfh qq(check_stack(s,"[$stkstr]");\n);
  }
  warn "error: leftover rubbish in opstr: $opstr\n" if $opstr;
  return undef;
Putting this all together, we get autotest-v3. You can download the whole thing, with a few extra comments, via this autotest-v3 link.
If we run autotest-v3 with any valid sequence of stack ops the generated atest.c file should now contain a correct sequence of stack tests. For instance, if you run:
  ./autotest-v3 '10' 1
the core of atest.c will read:
  stack s = empty_stack();        check_stack(s,"[]");
  push(10, s);                    check_stack(s,"[10]");
  destroy_stack(s);
and if you compile atest.c and run it via make it should work, passing all those tests.
If we instead run
  ./autotest-v3 '10 -' 1
the core of atest.c will read:
  stack s = empty_stack();        check_stack(s,"[]");
  push(10, s);                    check_stack(s,"[10]");
  CHECK_ELEMENT(pop(s), 10);      check_stack(s,"[]");
  destroy_stack(s);
Again, compile and run that via make all tests will pass.
If we try to cause stack underflow (popping an empty stack), as in:
  ./autotest-v3 '-' 1
then autotest warns us that the expected result is stack underflow, and the core of atest.c will read:
  stack s = empty_stack();       	check_stack(s,"[]");
  (void)pop(s);			/* <--- STACK UNDERFLOW HERE */
  destroy_stack(s);
and sure enough, if run, this will trip an assertion inside pop() that enforces the stack must be non-empty precondition.
We can also trigger overflow, but note that stack.h currently hardcoded the max depth to 100, so if we really want to trigger overflow we would have to write something like:
  ./autotest-v3 '1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46..
  47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95..
  96 97 98 99 100 101' 100
If you do this, autotest should report that the expected result is stack overflow, but go on and generate atest.c anyway. If you compile that and run it, it should indeed trigger overflow when element 101 is pushed.
Of course, if, instead, we tell autotest to produce a C test program assuming the stack maxdepth was 1 and we push two elements onto it via:
  ./autotest-v3 '10 20' 1
Then, as expected, autotest reports the expected result is stack overflow and writes atest.c expecting that the second push() will abort.
But of course, if you actually compile and run atest - with the real stack depth hardcoded as 100 - it will not behave as autotest expected it to: it will push 2 values onto it's up-to-100 deep stack and experience no stack overflow.
This is a subtlety left for you to explore. The thought occurs that, if empty_stack() was altered to take the maximum depth of that stack as a parameter, and we passed the desired max depth to our empty_stack() call, I imagine that it would behave as expected. But we're not here to modify our stack ADT's interface, just to explore tools that we can build.
We could extend autotest in various ways:

Most obviously, adding code into autotest that automatically compiles and links atest.c, runs it via checker, and then deletes the executable.

We could add extra features to our operation-string little language, perhaps a range operator - 1..10 could mean: push 1, push 2... push 10 - or even some form of loop - 10x(20 -) could mean: push 20, pop it off, repeat 10 times.

We could let one invocation of autotest take several operation-strings, generating, compiling and testing each one in turn.

At this point, we probably wouldn't bother to keep any of the generated C test programs - we'd build them on the fly, compile them, run them, and delete them.

One could imagine a whole battery of stack tests could then be built up and run via this method, forgetting all about the automatically generated C test programs (at least until one needed to remember the details again, eg. to debug or extend autotest itself). But we've done enough here.

We've shown here that one can build simple code-generator tools like autotest, or the various versions of our tinytools, in a modest amount of time. autotest-v3 is approx 110 lines of Perl, of which only 72 are actual code (the rest are blank lines and comments). I originally wrote autotest-v3 in less than an hour - probably half an hour. If we ignored the subtleties of detecting expected stack underflow and overflow, the core algorithm in gentest() could be written in 15 minutes. This is not a long time in programming!
This is just another example of spending a small amount of time to build a tool that expresses some regular pattern in what you're doing. This is the lesson of this article: look for patterns, get bored easily, build ad-hoc tools to exploit patterns. Finally, your tools don't have to be perfect - just good enough to save you time!

d.white@imperial.ac.uk
Back to PSD Top
Written: February 2016