Writing ML tests for ADTs


Let's test STACK of int

Consider the axioms for STACK of int, shown below as ML code:

We wish to write a collection of tests that will convince us that the axioms (ML code) are correct.

The best way to do this is to write our tests FIRST, before we write the code. The tests are goals... we describe how the code should behave, and then when we write the code the tests are there to be run, so we can see if we got the code correct.


A Test is an ML boolean expression

Before we can run some tests, we need to set up some test data to work on. We will do this by building some stacks using our canonical constructors: 


  val s0 = New;
  val s1 = push(s0,10);
  val s2 = push(s1,20);
  val s3 = push(s2,30);
Here we have created 4 stacks and named them. They look like this: 

       +----+----+----+----+----+---
   s0: |    |    |    |    |    |
       +----+----+----+----+----+---

       +----+----+----+----+----+---
   s1: | 10 |    |    |    |    |
       +----+----+----+----+----+---

       +----+----+----+----+----+---
   s2: | 10 | 20 |    |    |    |
       +----+----+----+----+----+---

       +----+----+----+----+----+---
   s3: | 10 | 20 | 30 |    |    |
       +----+----+----+----+----+---

Now that we have some stacks to operate on, we will apply the operations to them and see if the results are equal to what we expect them to be. Some simple tests are to see if the examination operations give correct values... for example if I run size on s2 above, I expect 2 as the result. Here are several simple tests: 

  size(s2) = 2;
  size(s0) = 0;
  size(s3) = 3;
  top(s2) = 20;
  top(s1) = 10;
When evaluated, I expect to see ML report "true" and I interpret that as the test passed. If it says "false" then I have a flag that some past of the code is not working as expected.

Now we can get more complicated. Here are more tests, where we check things like "push should make any stack get larger by one": 

  size(push(s3,40)) = size(s3) + 1;
  size(push(s3,40)) = 4;
Each test in this pair more or less does the same thing, just expressed slightly differently. As before, we expect to see "true" from the ML interpreter.

We should also check that the pop operation takes a stack and makes it shorter by one: 

  size(pop(s3)) = size(s3) - 1;
  size(pop(s3)) = 2;
  size(pop(s1)) = 0;
  size(pop(New)) = 0;
We should also check that the top operation works after pops are done: 
  top(pop(s3)) = 20;
  top(pop(s2)) = 10;
  top(pop(s1));
That last test will not generate a "true". We expect it to generate an exception.

We can toss in other tests as you see fit. The goal is to exercise the ADT operations in as many ways as you can to cover all the ways it might be used: 

  top(pop(push(push(pop(push(s3,40)),50),60))) = 50;
  size(pop(push(push(pop(push(s3,40)),50),60))) = 4;

I am not claiming that this collection of data points and test cases is thorough or exhaustive (e.g., we have not tested operation "empty" that appears in this ADT). I am giving them as an example of what I mean when I say put tests after your ML code for the ADT axioms. Part of your job is to create enough tests to be thorough and uncover any errors you may have in the axioms.


Final ML code for STACK with these tests

We put our tests at the end of the ML definitons that create the ADT. Then when the entire ML file is included and evaluated, if the code is well written, we see a lot of "true" reports from ML for the tests: 


datatype STI = 
   New  
   | push of STI * int ;

fun size (New) = 0
  | size (push(S,i)) = size(S)+1;

fun pop (New) = New
  | pop (push(S,i)) = S ;

fun empty (New) = true
  | empty (S) = (size(S)=0) ;

exception topEmptyStack;

fun top (New) = raise topEmptyStack 
  | top (push(S,i)) = i ;


(*---------------------------------------*)
(*   test data points                    *)
(*---------------------------------------*)

  val s0 = New;
  val s1 = push(s0,10);
  val s2 = push(s1,20);
  val s3 = push(s2,30);

(*---------------------------------------*)
(*   test cases                          *)
(*---------------------------------------*)

  size(s2) = 2;
  size(s0) = 0;
  size(s3) = 3;
  top(s2) = 20;
  top(s1) = 10;

  size(push(s3,40)) = size(s3) + 1;
  size(push(s3,40)) = 4;

  size(pop(s3)) = size(s3) - 1;
  size(pop(s3)) = 2;
  size(pop(s1)) = 0;
  size(pop(New)) = 0;

  top(pop(s3)) = 20;
  top(pop(s2)) = 10;
  top(pop(s1));

  top(pop(push(push(pop(push(s3,40)),50),60))) = 50;
  size(pop(push(push(pop(push(s3,40)),50),60))) = 4;