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.

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:
The tree looks like:
and is converted to

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:

fcn composeWith(x) {  // look for “_”: f().g(_).h(), f(1,_,3)
      { 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
      if (args[n].objs.len() != 1) bitch(“_.* not good”,self);
      args[n] = x;

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:

   println(beers(n), ” on the wall, “, beers(n).toLower(),
      n==0 and
      (“Go to the store and buy some more, 99 bottles of beer”)
      or (“Take one down and pass it around, ” +
      ” 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”),
(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”) :
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);
      fcn(n,x,results){results[n].append(x); n+1},0,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())
       // L( L(1,3,5) ) –> T(L(1),L(3),L(5))
      fcn(n,x,results){results[n].append(x); n+1 },0,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))

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))

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))

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

Queen of the Races

The Queens N puzzle has lots of opportunity for parallelism so I thought I’d see what my dual core Windows system could do. Using the code from the previous post, pretty much what I’d expect: Two cores, two threads is as good as it gets, adding more threads doesn’t do any good if there aren’t any cores to support them.

724 solution(s) : 1 threads : 15 seconds
724 solution(s) : 2 threads : 9 seconds
724 solution(s) : 3 threads : 10 seconds
724 solution(s) : 4 threads : 10 seconds
724 solution(s) : 5 threads : 9 seconds


The code is simple:

  • Two job queues: pending and solutions
  • Start a thread:
    – The thread reads from the pending queue and solves a queens n puzzle, starting at the second row (thus multiple threads are solving different puzzles).
    – Write the solution the solutions queue.
    – Repeat
  • Write N puzzles to the pending queue.
  • Wait for N solutions to show up in the solutions queue (each “solution” is a list of zero or more solutions for the starting board position).
  • Print some stats
  • Start another thread and repeat

While it is possible, with this code, for one thread to do all the work (by hogging the input queue), that is unlikely (the thread would have to solve a puzzle really fast to read the next puzzle before another thread got it).

N := 10; pin := Thread.Pipe(); pout := Thread.Pipe();
do(5){  // test with one to five threads
   fcn(pin,pout) { // create a puzzle solving thread
      foreach job in (pin) { pout.write(job()); }

   time := Time.Clock.time;
   foreach c in ([1..N])
       { pin.write(queensN.fp(N,2,T(T(1,c)))); }
          { len() == n }.fp(pout.len,N));
   queens := pout.walker().cat();

   println(“%s solution(s) : %s threads : %s seconds”
   pout.open();         // reopen output queue
pin.close();    // let the threads exit

Posted in Uncategorized | Leave a comment

Queen for a day

I was reading the Pure manual (“Pure is a modern-style functional programming language based on term rewriting”) trying to learn the basics of functional programming (which, for some reason, I find very difficult) and saw this nice solution to the Queens N puzzle (Wikipedia article with a nice animation of the backtracking algorithm):

queens n       = search n 1 [] with
search n i p = [reverse p] if i>n;
= cat [search n (i+1) ((i,j):p)
| j = 1..n; safe (i,j) p];
safe (i,j) p = ~any (check (i,j)) p;
check (i1,j1) (i2,j2) = i1==i2 || j1==j2 ||
i1+j1==i2+j2 || i1-j1==i2-j2;

Your basic brute force algorithm:

  • Put a queen in the first row
  • Put a queen in the next row, where it isn’t attacked
  • Continue until there is a queen on every row
  • Otherwise, backup one row and try the next column


For example, here a failure on a 4×4 board (BTW, 4×4 is smallest size with a solution (there are 2), other than a 1×1 board)

For the first row, there can be a queen in every column, I’ll pick column 1 (1,1).
q12For the second row, there two possibilities: (2,3) and (2,4). If (2,3) is used, all of row 3 is under attack so there is no solution using these two positions. We would then try (2,4) (which also isn’t in a solution). Then back up the first row and try a queen in the second column (which does have a solution).

Ok, can I duplicate this algorithm in zkl? Well, no, I don’t have list comprehensions,  so I have to figure out how to fake around that.

But first, some simple things:
A queen attacks a square if they are on same row, column or diagonal. The diagonal is the interesting part: A diagonal is 45º so the line formula y = mx+b is y = ±1x + b –> y ± x = b. If a queen at (u,v) is on the same line then u ± v = b –> y ± x = u ± v, which is the “checks” code.
A square is “safe” if isn’t being attacked, for us, that means checking every square in a row to see it is being attacked and, if it isn’t, it is safe. My code (in zkl) is:
   not qs.filter1(isAttacked,a,b)
where qs is a list of queens in (row,col) pairs (eg L(L(1,1),L(2,3)) for two queens), a,b is the square in question and isAttacked is a function of three parameters: a queen pair, an x and a y and returns True if the queen attacks the square (kinda bass-ackwards but fits the data formats). So, anyway, filter1 checks each queen in qs to see if it attacks (a,b) (and stops at the first positive (the 1 in filter1)).

Now the hard part, the decent. What I do is build a row by putting a queen on every safe square:

The first line generates a list of safe squares by column and the second line converts the column into a (row,column) pair and adds it to the list of queens already on the board. From the above picture, the second row would be: L(L(1,1),L(2,3)) and L(L(1,1),L(2,4)). Filter removes all the unsafe columns and safe.fpM builds a version of safe (call it isSafe’) that takes one parameter, the column. This is partial function application; I “fix” the first and third parameters so that a call to isSafe’(1) is actually isSafe(row,1,queens). (I have to do this because lambda functions are not lexically scoped and thus don’t see variables that are next to them).

If the row I just built is the last row, it is a solution and I’m done. Otherwise, I have to look at the next row:
Here, for each set of queens, I recurse to the next row. Again, .fp builds a new function such that f’(queens) is actually f(N,row+1,queens). This results in a list of [partial] solutions and empty lists if there isn’t a solution.

Now that I have a list (of lists) of solutions (and empty lists for non-solutions) for each set of queens, distill that down to a single list of solutions and backtrack:
And we are done.

fcn isAttacked(q,a,b)
{ x,y:=q; (x==a or y==b or x+y==a+b or x-
y==a-b) }
fcn isSafe(a,b,qs){(not qs.filter1(isAttacked,a,b))}
fcn queensN(N=8,row=1,queens=T){
qs := [1..N].filter(isSafe.fpM(“101”,row,queens))
if (row == N) return(qs);

queens := queensN(4);
println(queens.len(),” solution(s):”);

2 solution(s):


Here is the second solution. After the first row, there is only one possibility for each subsequent row.

q31  q32  q33  q34


What if we want only one solution? Again, borrowing from the Pure examples, it is easiest (and simpler and way faster) just to avoid the backtracking headaches altogether by throwing an exception with the first solution:

fcn queensN1(N=8,row=1,queens=T){
if (row > N) throw(Exception.Msg(queens));
reg queens;
try {queensN1(8)}catch(Msg){queens=__exception.payload}
println(“A solution: “,queens);

A solution: L(L(1,1),L(2,5),L(3,8),L(4,6),L(5,3),L(6,7),L(7,2),L(8,4))

(apply2() is the same as apply but throws away the results, which we don’t care about as we are just using apply to loop/recurse over the sets of queens)

Posted in Uncategorized | Leave a comment

A threaded web server in 60 lines

I wrote this toy web server to play with sockets and threads. The web pages are actually in the code, just to make it easy (and self contained). One thread listens for incoming requests and forwards the request to a thread pool. The worker threads read from a request queue, the thread whose read succeeds gets the job. It then processes the request, writes the response and goes back to reading the request queue.

I added a CGI form to play with blowing apart a CGI query string into a hash table (2 lines but doesn’t handle all character encodings) and giving the threads a little more to do.

You can download the source from http://zenkinetic.com/Documents/httpServer.zkl (use Save As, otherwise the embedded HTML will really messes things up).


const PORT = 8080;

  /* ******************************************************** */
  /* ********************** The Server ********************** */
  /* ******************************************************** */

    // A class to process requests from clients (eg browsers)
    // in a thread. Requests are received via a pipe,
which feeds all Servlet threads.
class Servlet {
   fcn init(jobPipe) { self.launch(jobPipe); }
   fcn liftoff(jobPipe) {
      while(1) {    // read request, write response, repeat
         socket := jobPipe.read();
         if(socket.wait(60) != 1)    // what is Chrome doing?
            { socket.close(); continue; }
         if (request := socket.read())
try { processRequest(request,socket); } catch {}
   fcn splashdown(h,e)
{ println(“Servlet died before its time”); }

    // map requested page to fcn
var getMap = D(“/”,homePage, “/favicon.ico”,favicon,

fcn processRequest(request,socket) {
   println(“vvvvvvvvv “,vm,”\n”,
   req := request.text.split(“\r\n”);
   method,page := req[0].split();

   response := “”;
   switch(method){      // GET, HEAD, POST, etc
      case(“GET”) {
         response =
            ( if (n:=page.find(“?”)) cgi(page[n+1,*]) else
                               getMap.find(page,homePage)() );
      case(“HEAD”) { response = responseHeader(); }
//      else do something
   socket.write(response); socket.close();    // no Keep-Alive

      //////////////// Start the server ////////////////////

var jobPipe = Thread.Pipe();    // a queue of requests
do(SERVLET_THREADS) { Servlet(jobPipe) }  // start threads

    // Create the HTTP server listen socket
    // Sits here forever passing client HTTP connects
to Servlets
serverSocket := Network.TCPServerSocket.open(PORT);
println(“HTTP server started at “,
    serverSocket.addr, “:”, serverSocket.port);
serverSocket.listen(fcn(socket) { jobPipe.write(socket); });

/* ******************************************************** */
/* ********************* The Web Site ********************* */
/* ******************************************************** */

fcn cgi(queryString) {   // GET /?value=8&fact=calc HTTP/1.1
   args := queryString.replace(“+”,” “);
   args = args.split(“&”).apply(“split”,”=”).toDictionary();
   try {
      x := BigNum(args[“value”]);
      if (x > 0) return(homePage(x,”%,d”.fmt(factTail(x))));
   } catch {}

The rest of the code (the web site) is in the download link.

Posted in Uncategorized | Leave a comment