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.