Mythic Logos

Skipping version 3 entirely (let’s just not go there, shall we?), I have now a version 4 on the web. It currently does arithmetic without parentheses.

But what it does do is take the arithmetic expression(s) and parse them into trees, bottom-up with the computed values in the nodes and operations above. The graphics are not pretty just yet, but it works and it is completely in the browser–no server-side shenanigans. This is all thanks to jsxgraph; they just saved me months of work, work which, unlike parser writing, I had no desire to do.

Below the graph is a bunch of strange looking code–this is text that can be fed into graphviz for a different graph view.

The really nice thing about this version is that I define the grammar and behavior write in the index.html file. I have achieved separation of the general parser stuff from the behavior of the language I want to deal with.

This is the definition of arithmetic:

    var simpleParSet = {symbolDefinitions:{
                "+": {types:{infix:20}},
                "-": {types:{infix:20}},
                "*": {types:{infix:30}},
                "/": {types:{infix:30}},
                "^": {types:{infix:40}},
                "\u00AC": {types:{symbol:0}}
                }
    };
    
    var par = prattCrockford.makeTree(simpleParSet);

And to make a tree, the call is

tree = new par({str:"3+7*5^2"});

And that’s it. Tree defined. It has no behavior.

To add behavior, I have a seeder method that can install behavior into the nodes. This can be done globally across all parsers, across all trees for a language, or for a single tree. With prototype chaining this is easy; I call seeder at the level I want even though it is defined at the bottom of the chain. Awesome.

Once seeder is done, you can then call walker to walk the tree or shooter to walk the parse order. And that’s it.

Here is an example of the use of the seeder function to seed all of this language’s trees:

    var makeCompute = function (fun) {
        return function () {
            this.computedValue = fun (this.nodes.left.compute(), this.nodes.right.compute()); 
            return this.computedValue;
        }
    };
    par.prototype.seeder({
        "(number)" : function(sym) {
             sym.prototype.compute = function () {
                  this.computedValue = this.value; 
                 return this.value;};
        },
        "+" : function (sym) {
                sym.prototype.compute = makeCompute(function (l,r) {return l+r;});
        },
        "-" : function (sym) {
                sym.prototype.compute = makeCompute(function (l,r) {return l-r;});
        },
        "*" : function (sym) {
                sym.prototype.compute = makeCompute(function (l,r) {return l*r;});
        },
        "/" : function (sym) {
                sym.prototype.compute = makeCompute(function (l,r) {return l/r;});
        },
        "^" : function (sym) {
                sym.prototype.compute = makeCompute(function (l,r) {return Math.pow(l,r);});
        },

        "\u00AC" : function(sym) {
                sym.prototype.compute = $.noop;
        },
        "(end)" : function(sym) {
             sym.prototype.compute = $.noop;
        }
        },
        function (sym) {
            sym.prototype.compute = function () {this.computedValue = NaN; return this.computedValue;}
        }
    );

Notice how I created a helper function makeCompute that essentially reduces boilerplate code and allows one to specify just the differing behavior. All sorts of tricks like this can be used to make this more efficient. I also have a couple of $.noop’s for symbols that should not be processed (end of lines, for example). I will probably make a common convention to deal with them so that that boilerplate can be removed. I may remove them from the trunk of the tree altogether and only leave them in the source token stream.

Anyway, now that we have the seeder function, now what?

        tree = new par({str:"3+4\n7*5^2+1});
        $.log(tree.walker("compute"));

The return value will be an array of the computed values of the different arithmetic expressions in the input: [7, 176]

And that is how to write a parser. I can continue to add behaviors of all kind, using the behavior data I already generated, and even remove behaviors later if I want or overwrite. I have complete flexibility and power on how to make my trees behave.

Now I need to add parsing behaviors.

Tired of infinite loops? Infinite recursion got you stuck? Tired of introducing meaningless count variables just beat the scourge of an unresponsive script?

Then I’ve got the tool for you. Hot off the assembly lines, tested thoroughly in rugged environments across the landscape, $.maxStop() will stop the horizontal eight in its tracks!

To use:

if ($.maxStop() ) {return;}  //in a loop replace return with break

Kills recursion and infinite loops.

Here is the code for the plugin:

$.maxStop = $.maxStop || (function () {
    var count, max;
    var defaultMax = 1000; 
    ret = function (numMsg) {
        if (typeof numMsg === "number") {
            if (numMsg >0) {
                if (numMsg !== max) { //
                    count = -1; 
                    max = numMsg;
                }
            } else if (numMsg <0 ){
                count += numMsg;
            } else {
                if (max !== defaultMax) {
                    count = -1; 
                    max = defaultMax;  //0 resets to default max. 1 is minimal count
                }
            }
        } else if (typeof numMsg === "string") {
            $.log(numMsg, ":", count, "/", max); 
        }  else if (numMsg) {
            $.log(count, "/", max, numMsg);
        }
        count += 1;
        if (count <= max) {
            return false;
        } else {
            return true; 
        }
    };
    return ret;
})();

So the function takes in a number, a string, else, or ignores. A number will set the maximum and if it actually changes, reset the count. What’s great is that you can use this one statement as demonstrated below in a repeating situation and it won’t reset. So in a single statement, you can set how much iteration you can tolerate and check whether it has been done.

The string will put it in debug mode. It will print current count and a message. You can output any object state by stringifying; see example.

Anything else will also put in debug and prints to console the object for clicking through and examining.

Each call will add 1 to the counter–hence resetting counter to -1. And then return true if stoppage is needed, false otherwise.

Here are some examples:

$.stringify = $.stringify || function (obj) {  //encapsulate for older browsers not to choke without JSON.stringify method
    if (JSON && JSON.stringify) {
        return JSON.stringify (obj);
    } else {
        return "no JSON; upgrade broswer!";
    }
}

$.tests.load("$.maxStop", [
    function () {
        $.maxStop(10); 
        var localCount = 0; 
        while (1) {
            if ($.maxStop($.stringify({localCount:localCount})+"loop going")) {$.maxStop("loop will terminate"); break;}
            localCount += 1;
        }
        return ["while", localCount, 10];
    }, 
    function () {
        var count = 0;
        var f = function me () {
            if ($.maxStop(0)) {$.maxStop("recursion stopping"); return;} 
            count+= 1; 
            me(); 
        } 
        f(); 
        return ["recursion", count, 1001];
    }, 
    function () {
        $.maxStop(30); 
        var count = 0;
        var f = function me () {
            if ($.maxStop()) {$.maxStop("recursion"); return;} 
            count+= 1; 
            me(); 
        } 
        while (1) {
            if ($.maxStop()) {$.maxStop("loop"); break;}
            f(); 
            count += 1;
        }
        $.maxStop(0); //restores it for actual use later. 
        return ["while and recursion", count, 30, "this shows the same maxStop is being used"];
    }, 
    
]);

So enjoy and be careless! $.maxStop() has got your back.***

***not good to leave this in actual code, particularly for loops/recursions that could be huge. It should be an unnecessary function call in production code.

So I am yet again refactoring my code. I hope this is the last time and then I can get into adding behavior.

I did manage to separate all the behaviors and now have seeders, walkers, and shooters working in version 3. But I broke my index page; it is all in Firebug debugging. So waiting until version 4 for the next release.

But as I was doing this, I noticed that I kept passing the parser or the tree around and wondering whether they were in scope when I needed them. And getting confused as to which one I needed. To help highlight what I needed, I decided to make these methods of the objects. And now with my insight of prototype, I decided to attach them to the underlying constructor. The only problem was, well, there was no constructor.

And then it became clear to me that a lot of the fog of my code seems to be coming from that. What prototyping allows one to do is separate the process from the details. And I failed to do that consistently. And so it becomes a mess.

Take as example the tokenizer object. I have struggled with how to make it customizable within the code. So I was making a tokenizer for each parser and passing in options. I think it is fine to still pass in options for initialization, but it might also be nice to switch out relevant components on the fly.

So by putting generic default behavior in the prototype, we can do exactly that. And furthermore, we can overwrite it locally for a short time and then remove it with the delete keyword.

As an example:

var f = function () {};
var g = new f();  //g now uses f.prototype for inheritance. g is an empty object except for that. 
f.prototype.say = "hi"; 
console.log(g.say); //hi
g.say = "bye"; 
console.log(g.say); //bye
g.say = undefined; 
console.log(g.say); // undefined in gray box
g.say = "back";
console.log(g.say); //back
delete g.say; 
console.log(g.say); //hi

So in our tokenizer, we can have a property for applying the regex as a prototype. This could chunk words, numbers, special characters. But then we hit a comment such as //whatever !!$#!@#$

This comment should be slurped up without pause until the end of the line. Now one can just replace the regex and the next token will be the comment string. No fuss, no muss. And when done, we delete the local override and the tokenizer goes back to its usual parsing. One can envision much more complicated scenarios in which a whole slew of behaviors suddenly morph. That is the power of prototyping.

Of course, this is incredibly dangerous. But when trying to be generic, you either need this or a 10,000 line program. I will stick with the 1000 line kind of program.

Today I have gotten to a point for another version in stone to go back to. It features a sequence of evaluations of an expression with boxes showing what will be evaluated, bolded numbers showing what was evaluated, and a grey last number showing that that number is where uncertainty lies. It also uses engineering notation (more or less scientific notation for massive/minuscule numbers and normal numbers for ordinary numbers). Or to say it another way, engineering notation tries to have as few symbols on the page as possible. That’s actually how I implemented it.

After tonight, I will do a massive refactoring of the code. I am now seeing the trees for the branches, so to speak.

One of my big stumbling blocks in understanding parsing was how to separate each of the pieces. I think I now understand how to do that separation. Hence the major refactorization. All of this is based on Crockford’s article on Pratt parsing. Great article.

So here is my ordering:

1. Tokenizer. This takes a string and parses it into tokens. This is fairly straightforward. We are taking a one-dimensional object and breaking it into tiny pieces.

   For me, I have a reg ex that separates the string into words with non-leading numbers allowed, but not underscores or other symbols; into numbers with possible E notation; and one character symbols. This tokenizer does not tokenize all at once. It tokenizes as the parsing happens. It also has the facility to recognize stings of symbols that form a sensible pattern. That is loaded up on a per-language basis. Otherwise, it is all generic.

   For example if the language has the symbols “=” and “+=” and “+”, then Tokenizer will tokenize “3 + as += as6a -=8” into 3, +, as, +=, as6a, -, =, 8 assuming “-=” was not in the language.

   Information on where the match happened in the raw string and the raw match itself is put into the generated node.

2. Parser. This takes tokens and converts each token into a node. The node is prototyped on a symbol. This prototyping is what I was not appreciating and merits further explanation below.

   Each token is parsed by looking up its type in a symbol table and then instantiated. It inherits through the prototyping the methods for telling it what it to do if it is sitting by itself (like a number or a prefix operator) or if it is with company (like a + in between, focus on there being somebody to the left).

   The algorithm then goes through sucking up tokens and pairing them up based on a notion of binding powers. I am still wrapping my head around this and Crockford discusses it well. But essentially, we start at the beginning of an expression with the presumption that that token is happy with no one to the left. Then we proceed to the next token and we see whether the two tokens can make a connection (4 + 5 would lead to 4 for a first token, + saying that it looks to the left and we’re good; a prefix such as -3 would have – start sucking the 3 up earlier and the – says it knows what to do). And then we continue that, trying to figure out what binds more strongly than what. That is the tricky part, but it comes out pretty nicely.

   Crockford hard-coded the binding power levels. What I did was setup objects in an array where each level of the array corresponds to another binding power level and each object holds the symbols and their types.

   Anyway, we have that tokens get matched up with each other. Let’s say we are looking at 4+5. The node t(+) has a property called this.sub = [t(4), t(5)]. So I have an array with the related nodes to the left and right for the +. This node may itself be in another node and so this is how we make a tree of an expression. And then we can assemble these expressions into a tree itself, perhaps a linear array mimicking the vertical line of descent when we write lines of code.

   So a node might have the properties sub =[list of nodes], type, raw string, other separators it used (for example “[” will have a matching “]” but at most one node will be created so one could have info about where and what the end match was. One could have a container node attached to the primary expression node and have nodes created for each separator that lives in the tree only through the container.

   As we parse, we can also put each token that we come across into a flatList so that we can get a sense of what was written. This deals with the trouble, say, of reassembling what parentheses were used in writing down an arithmetic expression or, more usefully, replacing bits of an expression with its value and having the rest be the original. Note that we cannot evaluate along a flatList, but we can do stuff after the evaluation through the tree has been done.

   So this tree structure, which I have built already, is what I want to refactor the noise out of. My tree has a variety of extra “features” like termites eating out a tree.

3. Seeder. To actually do something with the tree, we need to give the symbols something to do. Crockford’s article stopped at that point. He built the trees with an “arity” feature and printed out the tree of the code. He was writing a short article to people who probably understood what to do with a tree. I did not. To me, much of the difficulty is still present in that tree. But at least we now have the 2-D structure.

   To give behavior, this is where the prototyping really shines. We need access to the symbol table. Remember, each node is an instance of a symbol. In other words, symbolTable[“+”] is a function used with the new command: new symbolTable[“+”] creates a node of type “+”. That means any objects in the new SymbolTable[“+”].prototype will become properties of the node. So we can attach actions to this prototype and presto, we have active nodes across our tree. As long as these functions keep the domino effect going, we can start at the top of the tree and evaluations will trickled done.

   For example, let’s say we define evaluate as a method on each of the nodes, i.e.,

    SymbolTable["+"].prototype.evaluate = function () {
         var left = this.sub[0].evaluate();
         var right = this.sub[1].evaluate(); 
        return left + right;
   }; 
   SymbolTable["(number)"].prototype.evaluate = function () {
         return this.value;  // (number) is the type for a number and they all have an innate value given in the tokenizing phase
   }
   

   I haven’t tried this, but I think I just defined addition for this. And we could define these prototypes within a closure if we say wanted to create a tree of values or a list of instructions as I did in version 2 above. All of it can be self-enclosed. And notice that we are populating the behavior of the nodes after the tree is in existence, but we are not walking the tree to add this functionality. Awesome.

4. Walker. The seeders above do nothing unless one starts walking.

   If we have a list of boughs (expressions) of our tree, we can walk along each bough by calling the function of the top node in each bough and allowing it to call its sub node’s functions. When done, we do the next bough and so on down the list until we are done.

5. Shooter. Walk in a straight line.

   If we want to and if it is appropriate (no loops, no function definitions), we can take the evaluated walked tree and go over our flatList and get an impression of how that original string gets evaluated as the tree is walked. More for pedagogy than function, I think.

So that is my current understanding. The breakthrough tonight was understanding the power and role of prototyping. Wow. That stuff is awesome.

As I do more, I feel closer and closer to realizing my long-time dream (from high school, really), of writing a math parser environment for the exploration of math. I see now how to emulate a calculator, a programming language, and I think markup languages. Even in this version 2, it is already of use to students in highlighting and seeing how things are evaluated.

My idea for the programming side is to have two versions. One version has no non-linear leaps, no loops, no function definitions. Just straight evaluation. I call this safe code (calculator code?) and it allows instructors, say, to load the student code and run it in a batch to evaluate results. Or even a server-side auto-checker such as node.js (I want a server that understands javascript).

And then a second version which has the non-linear stuff that can cause troubles. Still no access to DOM and security issues, but the potential for crashing, I suppose. This would be for defining new functions. For example if my default does not have an integrator function, then it could be defined in this more capable language which would be Good Mathematicized Javascript (cos would be a global function, for example!).

This is such fun.