Cerrisian Blog

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.

Basic English increases semantic redundancy, I did not no this. Maybe that’s why it’s easier to understand writing that has a constrained vocabulary.

This I learned from Shannon’s paper.

After reading a few pages on Code Reading I’ve decided to start reading TinyPy as literature. That is, just read to understand and for enjoyment. Hopefully this will boost my code reading ability.

It also gives me a chance to play with CScope and Splint. Currently the TinyPy code doesn’t compile with gcc -ansi -pedantic, eventually I’ll change that it get to pass through splint with no errors.

I continue to be impressed with cscope’s interface and ability. I wish there was a similar tool for python. Huh, it looks like it may be able to do at least some stuff for python  (being a dumb “grep” without the ability to understand variables or functions).

I also eventually want to try:

• BLAST (Berkeley Lazy Abstraction Software verification Tool) — a software model checker for C programs based on lazy abstraction.
• Frama-C — A static analysis framework for C.
• Uno — A tool designed to find most common type of programming errors without generating too much output.

Just chatted in #python to get some ideas of what to try pythoscope on.

• Tornado
• Distribute
• Stuff in the python standard library
  • pydoc
• Circuits

I guess I’ll start with pydoc first since it probably could be accepted as a patch to python.

Issues found while initializing:

• Pythoscope needs the ability to exclude directories when initializing.
• Pythoscope needs to be optimized during initialization — memory use grows to over 800 MB looking at the python standard library. At which point my poor netbook starts to page like mad

After reading Cem Kaner’s and James Bach’s slides on exploratory testing I noticed a technique I didn’t know about before, active reading, which can be distilled into SQ3R. Basically when you have a document to read, start by skimming the headings/topic sentences, determine questions to ask, read the document to answer the questions, distill the information into proper recall and review it.

This fits into spaced repetition quite nicely. After the information is distilled for recall, input it into a spaced repetition system for review.

The emphasis in the exploratory testing slides is to use this technique to rapidly gain information from documentation such as user manuals, design specs, etc. This is important, but I wonder if it can be used in code reading.

For example, for the YAJII project it might be broken into steps like this:

• Scan the names of public classes
• Ask questions about functionality
  • What is the public API and how is it used?
  • What are the areas that are highest risk?
  • What are the inflection points where unit tests can easily be added?
• Read the code in detail while trying to answer these questions.
• Write unit tests and additional documentation to record the answers found.
• Reread the new documentation and unit tests, verifying against the code.

I’m going to try to do this in detail for my book on structured programming, even though I’ve read through it once, it’s very dense and some parts are hard to apply to modern programming languages. Some questions that I’ll want to answer (probably using my type system for objects book) are:

What are the terminologies used in structured programming and how do they relate to modern languages and object oriented programming? What techniques do they recommend for reading structured programs that can be applied to modern languages? What techniques need to be adapted? Are there techniques for unstructured program reading and modification that can be applied to modern languages?

Ok, so I’ve got YAJII to compile and have the javadoc to help with browsing, so now it’s time to do the static analysis.

I’ll start by doing a callgraph of the Main class in the testbed package. This seems to have been used for doing functional tesitng by the author, so it’s a good place to start.

This leads me to the DefaultIRCPeer class. The most interesting method there is the sendMessage method, with interacts with the private class MessageEventDispatcher.

I’ve been able to comment out the methods in this class, but it uses fireMessageReceivedEvent and fireMessageSentEvent from the IRCPeer class.

The fireMessage*Event methods call the EventDispatcher.fireEvent methods for the receive and send dispatchers. EventDispatcher.fireEvent simply delegates to an EventHandler class that then delegates to the listeners.

And now I’m going to switch gears and try to find a test server to use…