Cerrisian Blog

I figured this out talking to my friend Daniel earlier this week.

In cleanroom software development, a usage model is created of the expected use of the system. This includes states of usage, system stimulus and probability. It’s basically a markov chain of usage from the user perspective.

This model is used to generate test cases, which consist of lists of stimulus inputs. To be complete, stimulus must include everything that can happen to the software, timing differences, OS interleaving, hardware failures, etc. Often times specific classes of test cases are generated to test features of the product that are unlikely to be encountered in practice but that must provide high levels of robustness.

These test cases are a very small subset of the infinite possible number of test cases from any usage model. Because the model is formalized, specific measurements of reliability can be generated from testing.

Exploratory testing, specifically as professed by the context driven school of testing, acknowledges the same limitations. There are an infinite number of possible test cases to execute in a finite amount of time.

Instead of front-loading the model design process to generate test cases, an exploratory tester actively develops a model of usage as she tests, taking into account risk of potential failure, etc.

This reminds me of the contrast between extreme programming and the design part of cleanroom. Both use an incremental approach to software release, peer reviews and strong specifications (in the form of unit tests in XP, box models in cleanroom). Extreme programming does this actively as the software is made and running, while cleanroom creates it “on paper” before code is generated. In the same way, exploratory testing generates the model actively against the running system, while cleanroom creates the model “on paper” before hand.

Exploratory testing is a heuristic approach of covering a sample the most important test cases to report quality related information while cleanroom is a formalized approach to do the same thing.

So, I’ve been having some crazy ideas on how to teach a programming class. First, I’d used a spaced repetition selection for homework and potentially quiz questions.

Each homework would be cumulative, with the majority of the questions coming from the current chapter and the previous chapter, but with problems selected from even earlier chapters either weighed so that they increase in difficulty over time or based on what students had trouble with. To aid in this, certain classes of problems would be randomly generated from a homework question bank, which would be a database that ran on my desktop.

Tests would work similarly, potentially with questions randomly selected from the bank for each test, so that each student got an individualized problem. Problems would be identified using a hashcode and solutions to the problems would also be automatically generated.

Tests would include a live coding part done in a lab. Homework assignments would be turned in to subversion.

So, the basic idea for a contest with Engineering Challenge is to have the student teams working at computers with software to create robot AIs. These computers act as clients to a central server which displays results and matches between the AIs. This is the core of the competition.

This networked setup can also be used during the training/warmup session. Each client has a number of simple directions and scenarios built in that it auto grades. As students complete the automatic training, a status message is sent to a different server that allows the facilitators to see which students are behind and need help.

These scenarios are built in a constructivist manner to guide the students through all the features necessary for the competition.

Before the students begin, they input their names, team name, school and possibly seating position so that this information shows up in the necessary displays.

This is more complicated, but it should make running the contest a snap.

The canonical form of requirements or “behaviors” in Behavior Driven Design is something like:

GIVEN <situation> WHEN <condition> THEN <predicate>

Where <situation> describes the state of the system and <condition> describes what’s actually happened to cause the system to express a behavior. <predicate> verifies that the correct behavior occurred.

Uncle bob says that this is a finite state machine in English, which is true, but it also has a similarity to the black box specifications of cleanroom:

Now, this is a step before the finite state machine, that’s called a “state box” in Clean Room parlance.

Clean Room separates this stimulus history driven black box from the state machine to maximize the flexibility in allowed implementations. The idea is to start with some natural language entries in the black box description and go through discussion with the client, as this is happening, stimulus histories are generated using combinatorics to make sure that all possible histories are covered.

This guarantees something called “referential transparency”, which basically means that the black box specification is complete and preserved at all levels of “detailing” and implementation.

This doesn’t deal with the ambiguity of human language, but gives specifications some structure that should help turn it into procedure and code.

Test Driven Development (TDD) creates code from concrete examples of inputs and expected results (outputs/state changes).

Clean room software engineering creates code and design from stimulus history and expected responses. It’s the same concept but with additional mathematical rigor.

What do you do if you have an existing implementation that does what you want but the code is messy? First, find a testable interface against the old code, then create a set of test cases against it (potentially automatically generated) and use that as your test oracle when doing code implementation.

Here’s an example. Say that you have an awesome algorithm implemented in some horrid code on a platform that isn’t very portable, say some code in MATLAB that calculates the cuteness of kittens. Now you want to have this implementation in a language that’s deployable, say NumPy. Now, the code is horrible so you cry every time you see it, but it’s correct because it was written by the foremost psycho-physicist specializing in feline cuteness.

So you whip up a test case generator that feeds in a bunch of pictures of kittens and uses the MATLAB code’s results as ground truth. From there you basically have a complete black box description of the system and can hack away.

This is the same as TDD, but you don’t do the work of figuring out the expected results from the inputs yourself.

I really should try this out on a project sometime, perhaps PyGP again.

I wonder how hard it would be port TinyPy to Haskell. It’d be an interesting exercise.

First I need to get my new documentation integrated into the tinypy project

I just time boxed a half hour to draw L-System trees and work on my project. That was extremely productive. I just wrote out by hand the L-System strings and corresponding trees for ten minutes. This was an interesting artistic exercise in itself, I got to see how different grammars made “bushy” “full” or “stringy” trees, and it gave my right brain a chance to work at the problem and make connections.

I realized I could implement my project using a turtle with a pen on its tail, this partially came from my lecture this evening in computer graphics with Semwal.

I quickly sketched out an algorithm that generates multiple turtles. After sketching it out, I saw an obvious simplification using code I already had. I didn’t have to worry about nested branches because it would already be parsed into lists. This allowed me to make multiple turtles much more cleanly and I could even execute them concurrently since they no longer would have shared state.

From there I rewrote the new algorithm and class and saw a few variables I missed. After adding them I realized that some could be grouped with pre-existing ones into a new class. This new class ended up not even being needed by the turtle class, but only the drawing class.

Doing design on paper is really important, even with TDD. Tomorrow I’ll implement it.

All this occured during a 30 minute time box, which is really a good technique, especially if I can force myself to do it for the first 5~10 minutes, after that it just flows.

This post is only to prove that I can blog about things besides open source. Hah!

Did a dry-run of my Master’s thesis proposal, it went well. I want to draw again, have fun with my Wacom table, ink, do stuff that other people can see. I’ll do frogs and butterflies next.

I’ve really been enjoying reading Man In Revolt by Emil Brunner, currently my microlite 20 is acting as a bookmark. Someday I’ll publish those enhanced rules I did up.

Complaining on internet communication medium is annoying. That’s my compliant.

I can’t was until my Sextus Empiricus book comes. It should be here within two weeks or so. I actually forgot where I ordered it from…

Some people write blogs where I just want to comment on every one of their posts. Not because I agree, but because I disagree

Let’s start with the next function up the call chain, tp_hash.

int tp_hash(TP,tp_obj v) {
    switch (v.type) {
        case TP_NONE: return 0;
        case TP_NUMBER: return tp_lua_hash(&v.number.val,sizeof(tp_num));
        case TP_STRING: return tp_lua_hash(v.string.val,v.string.len);
        case TP_DICT: return tp_lua_hash(&v.dict.val,sizeof(void*));
        case TP_LIST: {
            int r = v.list.val->len; int n; for(n=0; nlen; n++) {
            tp_obj vv = v.list.val->items[n]; r += vv.type != TP_LIST?tp_hash(tp,v.list.val->items[n]):tp_lua_hash(&vv.list.val,sizeof(void*)); } return r;
        }
        case TP_FNC: return tp_lua_hash(&v.fnc.info,sizeof(void*));
        case TP_DATA: return tp_lua_hash(&v.data.val,sizeof(void*));
    }
    tp_raise(0,tp_string(”(tp_hash) TypeError: value unhashable”));
}

Reformatting the lines we get:

int tp_hash(TP,tp_obj v) {
    switch (v.type) {
        case TP_NONE: return 0;
        case TP_NUMBER: return tp_lua_hash(&v.number.val,sizeof(tp_num));
        case TP_STRING: return tp_lua_hash(v.string.val,v.string.len);
        case TP_DICT: return tp_lua_hash(&v.dict.val,sizeof(void*));
        case TP_LIST: {
                          int r = v.list.val->len;
                          int n;
                          for(n=0; nlen; n++) {
                              tp_obj vv = v.list.val->items[n];
                              r += vv.type != TP_LIST ? tp_hash(tp,v.list.val->items[n])
                                  : tp_lua_hash(&vv.list.val,sizeof(void*));
                          }
                          return r;
                      }
        case TP_FNC: return tp_lua_hash(&v.fnc.info,sizeof(void*));
        case TP_DATA: return tp_lua_hash(&v.data.val,sizeof(void*));
    }
    tp_raise(0,tp_string(”(tp_hash) TypeError: value unhashable”));
}

Freshman style:

int tp_hash(TP,tp_obj v) {
    // Switch on type of pointer
    switch (v.type) {
        // None type has hash of 0
        case TP_NONE: return 0;
        // Hash number  based on value and size of tp_num struct
        case TP_NUMBER: return tp_lua_hash(&v.number.val,sizeof(tp_num));
        // Hash string based on value and length of specified string
        case TP_STRING: return tp_lua_hash(v.string.val,v.string.len);
        // Hash dictionary based on value of dictionary and size of void
        // pointer.
        case TP_DICT: return tp_lua_hash(&v.dict.val,sizeof(void*));
        case TP_LIST: {
                          // Start r at length of list.
                          int r = v.list.val->len;
                          int n;
                          // Iterate n through all items in list.
                          for(n=0; nlen; n++) {
                              // grab each item in list.
                              tp_obj vv = v.list.val->items[n];
                              // For each item, add hash to r if item not
                              // isn’t a list.
                              r += vv.type != TP_LIST ? tp_hash(tp, v.list.val->items[n])
                                                      : tp_lua_hash(&vv.list.val,
                                                                    sizeof(void*));
                          }
                          // Return hash for list.
                          return r;
                      }
        // Return hash of function object based on info
        case TP_FNC: return tp_lua_hash(&v.fnc.info,sizeof(void*));
        // Return hash of ??? object ?? based on value.
        case TP_DATA: return tp_lua_hash(&v.data.val,sizeof(void*));
    }
    // Otherwise, raise an exception.
    tp_raise(0,tp_string(”(tp_hash) TypeError: value unhashable”));
}

Finally, high level description.

/* Hash an arbitrary TinyPy object.
 *
 * None hashes to zero, dictionaries are hashable and lists are hashed
 * non-recursively.
 *
 */

Start with the basic function.

int tp_lua_hash(void const *v,int l) {
    int i,step = (l>>5)+1;
    int h = l + (l >= 4?*(int*)v:0);
    for (i=l; i>=step; i-=step) {
        h = h^((h<<5)+(h>>2)+((unsigned char *)v)[i-1]);
    }
    return h;
}

Annotate each line “freshman style”

int tp_lua_hash(void const *v,int l) {
    // declare i, step = l[ength] right shifted 5 + 1
    int i,step = (l>>5)+1;
    // if l[ength] >= 4: h[ash] = l[ength] + int value of v
    // otherwise: h[ash] = l[ength]
    int h = l + (l >= 4?*(int*)v:0);
    // For end of v until first step of v, go step by step negatively
    for (i=l; i>=step; i-=step) {
        // h[ash] = previous hash XOR (hash shift left 5 + has shift right 2)
        //                  + v as char[current step]
        h = h^((h<<5)+(h>>2)+((unsigned char *)v)[i-1]);
    }
    // Return hash
    return h;
}

Find instances of tp_lua_hash called in rest of the program

In dict.c function tp_hash(TP,tp_obj v)

case TP_NUMBER: return tp_lua_hash(&v.number.val,sizeof(tp_num));
case TP_STRING: return tp_lua_hash(v.string.val,v.string.len);
case TP_DICT: return tp_lua_hash(&v.dict.val,sizeof(void*));
// (...)
// Reformmated to allow for easier reading
tp_obj vv = v.list.val->items[n];
r += vv.type != TP_LIST ? tp_hash(tp,v.list.val->items[n])
                        : tp_lua_hash(&vv.list.val,sizeof(void*));

Aha! This implies that the parameter v is a void pointer to any TinyPy data type and that
l is the length of said data type in BYTES.

Let’s update our code snippet.

/* Hash an arbitrary TinyPy object.
 *   v is a void pointer that points to the TinyPy object to be hashed.
 *   l is the length/size of the object pointed to by the void pointer.
 */
int tp_lua_hash(void const *v,int l) {
  // Declare step to be 1 or 1/32nd the length, whichever is larger.
    // declare i, step = l[ength] right shifted 5 + 1
    int i,step = (l>>5)+1;
  // If the value is more than 4 bytes long (32 bits) add that to its length
  // as the initial value for the hash.
  // Otherwise start the hash as the length.
    // if l[ength] >= 4: h[ash] = l[ength] + int value of v
    // otherwise: h[ash] = l[ength]
    int h = l + (l >= 4?*(int*)v:0);
  // Take into account the hash values of each “step” of the value of v.
    // For end of v until first step of v, go step by step negatively
    for (i=l; i>=step; i-=step) {
        // h[ash] = previous hash XOR (hash shift left 5 + has shift right 2)
        //                  + v as char[current step]
        h = h^((h<<5)+(h>>2)+((unsigned char *)v)[i-1]);
    }
    // Return hash
    return h;
}

And I think we’re done. Didn’t have to go as deep as the examples in the
Structured Programming book I have, and I haven’t proven anything about how
good the hash is, but hey, now I understand what it’s doing.

There are a few additional simplifications I can make to the markup, using max() instead of “whichever is larger” and other mathematical notations, I’ll poke in the book sometime to see what they are.