Avoiding late binding with trampolines

Consider the toBool method. Every object has one because everybody inherits from Object and Object has it. An object can override toBool to add its own functionality. Standard stuff. Also standard stuff in late bound languages is delaying resolution of methods to runtime: obj.toBool() or if(obj) both invoke the toBool method (directly or indirectly). If the compiler can determine obj’s type, it can call the method directly (with static linking). If it can’t, (eg obj is a variable or function parameter) (remember that this is an untyped language), it has to be punted to runtime when obj is in play and the VM can ask obj to find and run obj’s idea of toBool. This usually involves a query into a hash table, which quick but has a bit of overhead.

But, what if the compiler said “oh, a call to obj.toBool. I don’t know what obj is but I’ll call Object.toBool and let Object figure out what to do”? We get rid of the overhead of a table query but how is Object to be expected to know how to deal with this? Enter trampolines. Object.toBool gets called and says “I’m a generic low level routine that typically just does a default action (like saying “I can’t do that”) but now I need to do something”. That something is to bounce the toBool call out to obj via a trampoline.

Here is an example: fcn f(a) { a.toBool() }
And the compiler output:

Late bound

Fcn: f Prototype: L(“a”)
Code (code: 5 bytes, strings: 7 bytes)
    0:210 arg0
    1:122 reCallZ(toBool)
    4:  0 done

Statically linked

Fcn: f Prototype: L(“a”)
Code (code: 4 bytes, strings: 0 bytes)
    0:210 arg0
    1:119 callOMethodNZ(3:toBool)
    3:  0 done

In addition to one less byte of code, the string “toBool” is not needed.

But how? When obj is built, it has back linkage to Object (so the inheritance from Object works). As part of building obj, Object updates tables to include the trampolines. The trampoline is a small table
   Byte trampolines[15];  // 0xff means no bounce
in each object. (It is important to note that the trampoline table is per object, not per instance. So, while there may be zillions of instances floating about, there is less than one hundred objects & trampolines).

When Object wants to bounce a method call:
   static Instance *
   Object_toBool(Instance *self,pArglist arglist,pVM vm) {
      Instance *r=obounce(self,arglist,TO_BOOL,MIX_TO_BOOL,vm);
      if (r) return r;
      return cantConvertError(self,”toBool”,vm);
   }
obounce does the work:
   Instance *obounce(Instance *self,
          pArglist arglist, int tix,int mix, pVM vm){
      ZKL_Object *obj = OBJECTI(self);
      int         n   = obj->trampolines[tix];
      if (n != 0xff)
        return obj->methodTable[n].method(self,arglist,vm);
      return 0;  // no can do
   }

This is all cool and groovy, so I picked nine methods (toBool, toInt, toFloat, BaseClass, len, isType, isInstanceOf and [] (two methods)) that a scan of a bunch of source code showed being used a lot and compiled up the compiler (9,500+ lines) and took a look. Oh, woe is me! The compiled code (94KB) is about 2% smaller and runs about 3% faster (compiling the parser, which is the big Kahuna at 4,500 lines). I have several guesses as to what is going on, from those methods are just not used that much (best guess sans profiling), too much overhead, to hash tables are pretty good (they are single probe (gperf) but there is overhead).

The fly in the ointment are proxy objects: classes and lazies. Classes because a function can implement/override a method a class method (for example, toInt, toBool). When a lazy object is on the receiving end of a trampoline, it has to decide if the method call needs to force evaluation or not. And avoid infinite loops (by trampolining back through Object). In addition, the BaseClass method always “tunnels” under any proxy behavior (ie no bounce). It is pretty twitchy and twisty enough that it makes my head hurt.

Advertisements
Posted in Uncategorized | Leave a comment

Composing compositions

A note on how I parse compositions (see previous–2 post).

There are several ways to do this, I choose to post process the AST (Abstract Syntax Tree); I scan expressions for “:” and, if found, rewrite that node. Using the previous example:
    List(1,2,3).xplode():String(_):List(_)
The tree looks like:
Expression
    List(1,2,3)
        xplode()
    :
    String(_)
    :
    List(_)
and is converted to
DataRef
    List(
        String(
            List(1,2,3)
                xplode()

The core of algorithm is simple, being able to punt “can you compose this” to an individual node is nice (OO in action). Heterogeneous lists rock. Mutable data is nice. Static typing gets in your way. Special cases are not nice (and make up the majority of the code).

Code snippet (with some hand waving):
i := instance_left_of_:;
foreach dr in (Expression) {
   if (“:” != dr) break;
   dr = Expression.next();

   try {
     if(not dr.composeWith(i)) throw(Exception.NotFoundError)
   } catch(NotFoundError)
      { bitch(“Can’t compose %s (missing _?)”.fmt(dr),self); }
   i = dr;
}

If a node can compose what ever it is handed, it does, modifies itself and returns True. If it can’t, it returns False. If it doesn’t understand composeWith, the VM throws NotFoundError. This last feature (late binding) makes it really easy to extend what can be composed; just add a composeWith method to a node. Here are two examples:

DataRef:
fcn composeWith(x) {  // look for “_”: f().g(_).h(), f(1,_,3)
   objs.filter1(fcn(fc,x)
      { FcnCall.isInstanceOf(fc) and
        fc.composeWith(x) },x)  .toBool();
}

Function Call:
fcn composeWith(x){ // look for f(_), f(_.x) is bad
   if (False != (n := args.filter1n(
         fcn(dr){DataRef.isInstanceOf(dr) and
                 dr.objs[0]==”_”})))
   {
      if (args[n].objs.len() != 1) bitch(“_.* not good”,self);
      args[n] = x;
      return(True);
   }
   False
}

Posted in Uncategorized | Leave a comment

99 bottles of … You gotta be kidding me

I was reading Lambda the Ultimate and someone posted they had a program accepted by http://99-bottles-of-beer.net/. My reaction: a combination of “please tell me you are joking” and WTF?. But it is for real, over 1,400 programs in different languages that print out lyrics to 99 bottles of beer on the wall. If you are a language geek, it is worth looking at the “Top List”, there are some amazing stuff there, like Piet, a language of color, where the programs look like abstract art (no text). My favorite, of the “just show me some code” solutions is Haskell, it really shows the power of pattern matching: it is short, concise and clear.

99 bottles seems like it should be one of the most trivial programs but there a couple of things that make it “interesting”. Here are the last verses:

2 bottles of beer on the wall, 2 bottles of beer.
Take one down and pass it around, 1 bottle of beer on the wall.

1 bottle of beer on the wall, 1 bottle of beer.
Take one down and pass it around, no more bottles of beer on the wall.

No more bottles of beer on the wall, no more bottles of beer.
Go to the store and buy some more, 99 bottles of beer on the wall.

Here is my solution:

[99..0,-1].apply2(fcn(n){
   println(beers(n), ” on the wall, “, beers(n).toLower(),
      “.\n”,
      n==0 and
      (“Go to the store and buy some more, 99 bottles of beer”)
      or (“Take one down and pass it around, ” +
         beers(n-1).toLower()),
      ” on the wall.\n”)
});
fcn beers(n){
    (n==0 and “No more bottles” or (n==1 and
    “1 bottle” or “” + n + ” bottles”))
    + ” of beer”
}

Posted in Uncategorized | Leave a comment

Stream of Consciousness Programming

I’m something of a stream of consciousness programmer: I have a thing: fold, then spindle and finally mutilate it. Or: I want to do do this n times, so I’ll use a loop and do this stuff in it. And I like to code as I think. Of course, I make a horrendous number of errors but that is what I love about computers; the compiler will catch a bunch, the program crashes, you fix it, repeat until it works. No animals are harmed, you don’t have to throw away a half a sculpture and start over. (Of course, if you do nuke plant controls or flight systems, you live in a different world and don’t hire programmers like me.) So, I like the noun/verb/verb… style languages, which tend to be OO (as opposed to verb/verb/…/noun). An example is “abc”.toString(16).println() which converts a hex string to an int and prints it.  Compare to println(stringToInt(“abc”,16)). How you think about and formulate a solution will determine what works best for you.

Given that, OOP typically breaks down when you have to intermix methods and functions (ie things that are not a part of the object you munging). To me, those are “halting” moments that break the flow: foo.method.method, ah crap, what I want to do isn’t a method, back up, restart: f(foo.method.method …).

Another example: I want to create a function from some VM code. Actually, I want to create some functionality (add 1 to something) and wrap it in a function so I can pass it around (ie create a lambda the hard way). So I’ll create the code:
   code := Compiler.Asm.asm(“Int(1)\nsetX\narg0\nadd\ndone\n”);
and then create the function wrapper:
   f := self.fcn.build(T(“f”,”n”),code);
and test: f(5) –> 6, f(“foo”) –> “foo1”. All fine and dandy but why in the world do I create the used-only-once code variable? Because I don’t think “to create a function, I create a function shell, then create some code, then …” as in
   f := self.fcn.build(T(“f”,”n”),
          Compiler.Asm.asm(“Int(1)\nsetX\narg0\nadd\ndone\n”));
(it might be different if I could create the function shell and then add the code but I can’t).

What to do? Swipe an idea from functional programming: function composition. Not as in currying or creating an actual function of the composition, just as a syntactic device. (I’m sure other programming paradigms have done this, but FP is where it stuck in my brain). I use a colon (“:”) to compose two chucks. The second example becomes:
   f := Compiler.Asm.asm(“Int(1)\nsetX\narg0\nadd\ndone\n”) :
         self.fcn.build(T(“f”,”n”),_);
with the “_” showing where to put the code. Nice, the code now reflects my thought process (for better or worse). Or even:
   Compiler.Asm.asm(Int(1)\nsetX\narg0\nadd\ndone\n) :
       self.fcn.build(T(“f”,”n”),_) : f := _;

I can now use the colon as a “fat” dot to build a left to right stream of actions to an initial object.

Another simple example:
   List(1,2,3).xplode():String(_):List(_) –> L(“123”)

Posted in Uncategorized | Leave a comment

Side effects for fun and profit

Consider this infinite Fibonacci sequence:
       var fib = fcn(ab){a,b:=ab; ab.del(0)+(a+b); a}.fp(L(0,1));

Ask it for a Fibonacci number and you get the first one. Ask again and you get the next one and so on:
       > do(15){print(fib(),”,”)} → 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377
It never restarts, it just continues the same sequence:
       > fib() → 610
       > fib() → 987

How does it do this? By using a closure over a mutable list that holds two Fibonacci numbers. This list is the parameter to a function that uses it like a shift register: the value-to-be-returned is popped off the front of the list and sum of the two is appended (del(0) is the pop and +(a+b) is the append). The list and the function are bound together in a partial application (the fp()) so that every time the function runs, the parameter is the next number(s) in the sequence.

Posted in Uncategorized | Leave a comment

Side effects – Don’t leave home without them

For me, one of the coolest things about functional programming languages is using [arglist] pattern matching and recursion to concisely express an algorithm. However, there are other ways to juice the pomegranate. I was staring at the Pure code for zip/unzip and there is a lot of it (for a seemingly simple function). I was surprised. There is some short list checking (which I punt on) but there are pair and triple versions (Haskell has 3 .. 7 versions). I noticed that while zip and unzip are basically the same thing (zip takes lists, unzip takes a list of lists), the code is pretty different for each.

After a bunch of head scratching, I was able to implement versions that are basically the same code and handle all input “widths” (pairs, triples, quads, …). The following were key:

  • All methods & functions are variadic, the number of parameters is never fixed. This means I just look at the arg count to determine if it is zip2, zip3, zip4, etc.
  • Late binding. Methods are bound to their instance. So, if foo and bar are lists, foo.reduce and bar.reduce are unique methods, even though they perform the same operation on a list. Late binding allows me to call a method on an arbitrary object when that object is not known at compile time.
  • Implicit-ish looping. This algorithm is basically a nested loop processing a list while processing a list. The “reduce” method (aka foldl) keeps a rolling sum, which can be used as an loop value (index in this case).
  • Side effects. Mutable lists are used as “accumulators” to build the results.

    // zip(a,b…) –>
    //   L( L(a[0],b[0]…), …,  L(a[n],b[n]…) )
    // zip(L(1,2),L(3,4),L(5,6)) –> L( L(1,3,5), L(2,4,6))
    // zip is unzip(vm.arglist)
fcn listZip(lists){
   results := T.build(lists.len(),0,List);
   vm.arglist.apply2(“reduce”,
      fcn(n,x,results){results[n].append(x); n+1},0,results);
   results;
}

    // unzip(L(L(1,2),L(3,4),L(5,6))) –> L( L(1,3,5), L(2,4,6))
    // unzip(unzip(a)) –> a
    // unzip is zip(listOfLists.xplode())
fcn listUnzip(listOfLists){
   results := // T(L1(),L2() … Ln())
       T.build(listOfLists[0].len(),0,List);
       // L( L(1,3,5) ) –> T(L(1),L(3),L(5))
   listOfLists.apply2(“reduce”,
      fcn(n,x,results){results[n].append(x); n+1 },0,results);
   results;
}

Posted in Uncategorized | Leave a comment

Symmetry Symmetry

I was implementing the [un]zip family of functions (from Haskel, see List functions) and noticed this lovely symmetry: unzip(unzip(a)) –> a

One element lists:
listUnzip(L(L(1,2,3,4,5,6,7,8,9,0))) –> L(L(1),L(2),L(3),L(4),L(5),L(6),L(7),L(8),L(9),L(0))
listUnzip(L(L(1),L(2),L(3),L(4),L(5),L(6),L(7),L(8),L(9),L(0))) –> L(L(1,2,3,4,5,6,7,8,9,0))

Pairs:
listUnzip(L( L(1,2), L(3,4), L(5,6), L(7,8), L(9,0))) –> L( L(1,3,5,7,9), L(2,4,6,8,0))
listUnzip(L( L(1,3,5,7,9), L(2,4,6,8,0))) –> L( L(1,2), L(3,4), L(5,6), L(7,8), L(9,0))

Triplets:
listUnzip(L( L(1,2,3), L(4,5,6), L(7,8,9))) –> L( L(1,4,7), L(2,5,8), L(3,6,9))
listUnzip(L( L(1,4,7), L(2,5,8), L(3,6,9))) –> L( L(1,2,3), L(4,5,6), L(7,8,9))

Quads:
listUnzip(L( L(1,2,3,4), L(5,6,7,8))) –> L( L(1,5), L(2,6), L(3,7), L(4,8))
listUnzip(L( L(1,5), L(2,6), L(3,7), L(4,8))) –> L( L(1,2,3,4), L(5,6,7,8))

Posted in Uncategorized | Leave a comment