Higher-Order

Don’t know what Jeene is? It will make your JavaScript code run faster read the intro first,
then come back to this!

Performance examples

I was curious about the performance gains of functions specialized via Jeene, so I ran a simple performance example in Firefox 2 and 3; Safari 3.1.2; Opera 9.52; SquirrelFish Extreme (the new JIT); IE 6, 7 ; Google’s Chrome and finally, TraceMonkey. All with great results! You can run the simple example here.

The test executes the string concatenation example from the previous post. The actual example is not that interesting; what is interesting is that Jeene works in all current popular JavaScript implementations and that it gives good performance boosts also in the new JITs: V8, TraceMonkey and SquirrelFish Extreme. The figures include the time it takes to specialize the function, so they are actual performance gains. (Note that the Windows and Mac tests were on different hardware).

• Firefox 2: (Windows Vista)
  1. Without specialization: 1430ms;
  2. With specialization: 635ms;
  3. Specialization reduces time by approx. 56%.
• Firefox 3: (Mac)
  1. Without specialization: 386ms;
  2. With specialization: 230ms;
  3. Specialization reduces time by approx. 40%.
• Opera 9.52: (Mac)
  1. Without specialization: 502ms;
  2. With specialization: 251ms;
  3. Specialization reduces time by approx. 50%.
• Firefox 3.1 – TraceMonkey (Mac)
  1. Without specialization: 302;
  2. With specialization: 152ms;
  3. Specialization reduces time by approx. 50%.
• Chrome – V8: (Windows Vista)
  1. Without specialization: 227ms;
  2. With specialization: 83ms;
  3. Specialization reduces time by approx. 63%.
• IE6/7 (approx. the same numbers) (Windows Vista)
  1. Without specialization: 2672ms;
  2. With specialization: 1485ms;
  3. Specialization reduces time by approx. 44%.
• Safari 3.1.2 (Mac)
  1. Without specialization: 378ms;
  2. With specialization: 157ms;
  3. Specialization reduces time by approx. 58%.
• WebKit nightly — SquirrelFish Extreme (Mac)
  1. Without specialization: 247ms;
  2. With specialization: 94ms;
  3. Specialization reduces time by approx. 61%.

What can Jeene do right now?

Specialize JavaScript functions written in simplified JavaScript which contain
the following constructs (note as of now you can only specialize with primitive values,
e.g., strings and numbers; this will be fixed soon):

• variables which occur in the function’s formal parameter
• literals and constants (“abc”, 42, true, null)
• simple assignment ‘=’
• and, or, not logical operators ‘&&’, ‘||’, ‘!’
• plus and minus binary operators (‘+’ and ‘-’); by default it assumes ‘+’
  to be associative, which is not sound in general but is for common case uses (ask me for details)
• return statements

What Jeene can’t do right now (i.e., what I am working on).

Some of these are easy, others are harder and need careful analysis.

• global variables (in general variables in the function’s closure)
• ‘var’ statements (i.e., local variable declaration and initialization)
• incrementing/decrementing assignments (‘+=’ and ‘-=’)
• ternary if, i.e., “exp ? v1 : v2″ operator
• comparison “===”, “!==”, “<”, “<=”, “>”, “>=”
• multiplication, division (‘*’,'/’)
• static/dynamic property lookup (‘.’ and ‘[‘)
• function calls (“fn()”)
• unary minus (‘-1′)
• typeof operator (‘typeof x’)
• function operator (‘function(){}’)
• expression statements, array and object literals
• expression statements, array and object literals
• ‘if’, ‘break’ statements
• ‘while’ and ‘for’ statements

New in latest svn commit

Jeene can now handle simple assignments of the form (x = exp) where x is a variable and exp is an expression. Further, formal parameters which are specialized disappear from the formal parameters in the specialized function, but now appear as local variables of that function (so that one can assign to them).

Consider this example:

Function.prototype.specialize = net.higherorder.jeene.Jeene.make();
source_fun = function(a,b,c) {
    c = a;
    return b+c;
};
var env = {a:3, b:2};
res = source_fun.specialize(env);

Result: 

(function (c) {var a, b;return 5;})

Note that the assignment c=a; can be eliminated and the static value of a is propagated to c so that the expression returned is static. Neat

Check back for more later…

This is a bit of an unusual posting. It was triggered because I am frustrated, having just written my third review for the journal TAAS, which I accidentally agreed to do reviews for at some point during my PhD studies. I still review papers on computational trust models which was the topic of my PhD dissertation. I have recommended ‘reject’ for all of these papers, not because these papers are any worse than most of what is being and has been published in that field (or what I’ve published myself); but because I accidentally started reading the book: Probability Theory: The Logic of Science by E.T. Jaynes, Cambridge University Press (June 9, 2003). This book radically changed the way I understand probability theory and its applications (which includes computational trust models). Once you read just the basic parts of his book (which is all I’ve read yet), you realize that much of the work being done in this area is waste; I will claim that it could all be done much simpler and with superior results if based on Jaynes formulation of probability theory (which according to Jaynes goes back to Jeffreys and Laplace).

During my PhD studies I was working on something called experience-based trust management. Fundamentally, this topic is about programs that reason about the behaviour of agents (other dynamic programs) in large open distributed systems (think Internet). Such reasoning is based on information, usually in the form of past interactions with agents or in the form of statements made by other agents about such interaction (i.e., reputation information).

After the first two years we had been working hard on creating a formal model for “computational trust” encompassing uncertainty, based on somewhat hardcore mathematical theory of complete lattices and monotonic functions, complete partial orders and continuous functions (domain theory) and even category theory. It was abstract, it was fun, it was warm, nice and cuddly; it turned out, however, to be essentially useless… Fortunately, after approximately two years I somehow realized this and started working on the same problems, but with a less abstract approach. At some point later I somehow came by the book of Jaynes. Now, I only wish I had read that book in 2004…

Anyway, I don’t know how you were taught probability theory (or worse, statistics) but the courses I took had abstract definitions (corresponds to what is on wikipedia) that seemed magical to a first year computer science student, and abstract but at least general later when I encountered measure theory. While this is all very interesting if one is interested in abstract mathematics, when one reads Jaynes account of probability one cannot avoid to think that Jaynes approach is overwhelmingly appealing: at first sight it intuitive and much is simpler; and once one gets into the later chapters, one learns that it is also more powerful, and in fact, the rules of probability theory is proven to be the unique set of rules that satisfy an absolutely reasonable set of qualitative desiderata (this is known as Cox’s theorem which is on wikipedia, but Jaynes’ exposition is much better in my opinion, a version is here (from page 13)).

I won’t even try to give an account of the book here, but only recommend it to anyone even remotely interested in scientific reasoning and logic, but also applied mathematics and computer science. There are some places that are mathematically challenging for your typical CS grad, but it still has value even if the advanced techniques and proofs are skipped. Read it before you submit any paper on trust

Here I will post a solution to the Fibers exercise… Post your solutions as comments.

Your code should at least pass the following simple test:

require 'fiber_stack'
require 'test/unit'

class FiberStackTest < Test::Unit::TestCase
      
  def test_simple
    fs = FiberStack.new
    assert fs.empty?
    fs.push 'a'
    fs.push 'b'
    assert_equal 2, fs.size
    
    assert_equal 'b', fs.pop
    assert_equal 1, fs.size
    assert_equal 'a', fs.pop
    assert fs.empty?
    assert_equal 0, fs.size
    
    assert_nil fs.pop
    assert fs.empty?
    assert_equal 0, fs.size
    
    fs.push 'c'
    assert_equal false, fs.empty?
    assert_equal 1, fs.size
    
    assert_equal 'c', fs.pop
    assert fs.empty?
    assert_equal 0, fs.size
  end
end

require 'test/unit/ui/console/testrunner'
Test::Unit::UI::Console::TestRunner.run(FiberStackTest)

with the following result:

krukow:~/Projects/private/Fiber/lib$ ruby run_stack.rb
Loaded suite FiberStackTest
Started
.
Finished in 0.002572 seconds.

1 tests, 15 assertions, 0 failures, 0 errors
krukow:~/Projects/private/Fiber/lib$

Have fun

As I’ve mentioned before, I advocate using a Model-View-Controller pattern for certain types of JavaScript-heavy web-app clients. In spite of recent licensing issues, I still think ExtJS is among the better libraries supporting MVC. For example, (if you don’t know what namespace/using are, please read this)

namespace('dk.okooko.model');
using(dk.okooko.model).run(function(m){
        
        m.OrderItem = Ext.data.Record.create([
          {"type": "int", "name": "id"},
          {"type": "int", "name": "product_id"},
          {"type": "int", "name": "quantity"},
          {"type": "int", "name": "order_id"},
          {"type": "date", "format": "d/m/Y-H:i", "name": "created_at"},
          {"type": "date", "format": "d/m/Y-H:i", "name": "updated_at"}
        ]);

});

The ‘Record.create’ function gives a way of succinctly creating constructor functions for model objects which are supported throughout the Ext functions; you can read more about it here.

If you are using Ruby on Rails at server-side (something which I have been doing quite a bit recently), then you realize that you are manually duplicating all the rails model classes in JavaScript. For example, here is the corresponding migration:

class CreateOrderItems < ActiveRecord::Migration
  def self.up
    create_table :order_items do |t|
      t.integer :product_id
      t.integer :quantity
      t.integer :order_id

      t.timestamps
    end
  end

  def self.down
    drop_table :order_items
  end
end

I was annoyed by this lack of dryness: whenever I changed the migration, I’d have to manually change the corresponding JS model. So I slapped together a really simple code generator which can create the model files from the rails models. It adds a method acts_as_jsmodel which is intended to be called by a rails model class, e.g.,

class OrderItem < ActiveRecord::Base
  belongs_to :order
  belongs_to :product
  has_one :order_item_status
  acts_as_jsmodel
end

So you can annotate model classes that you’d like to generate js models for. The acts_as_jsmodel causes a file to be written to public/javascripts/dk/okooko/model (generally, it depends on a constant APP_NAMESPACE).

Here is the code for the generator:

module Trifork
  module JSModel 
          
    JS_MODEL_DIR = "public/javascripts/#{APP_NAMESPACE}/model".gsub!('.','/')
    MODEL_PACKAGE = APP_NAMESPACE + '.model'
    def acts_as_jsmodel
      
      export_record "#{JS_MODEL_DIR}/#{self}.js" 
      rescue 
        nil
    end
      
    def export_record(fn)
      File.open(fn,'w') do |f|
        s =<<END
namespace('#{MODEL_PACKAGE}');
using(#{MODEL_PACKAGE}).run(function(m){
        
        m.#{self} = Ext.data.Record.create([
          #{self.to_record}
        ]);

});
END
        f.write s
      end
    end
      
      
    def to_record(spec = {},datefm=nil)
      spec[:exclude] ||= []
      keys = spec[:only] ? [*spec[:only]] : 
              (columns.map &:name).reject {|a| spec[:exclude].include?a}
      props = columns_hash
      
      keys.map do |k|
        p = props[k.to_s]
        if p.nil?
          raise "Property #{p} is not a column of #{self}"
        end
        {:name => p.name}.merge!(Trifork::JSModel::to_ext_type(p.type,datefm)).to_json
      end.join(",\n          ")
      
    end
     
    
    def self.to_ext_type(t,datefm)
      type = case t
      when :integer then 'int'
      when :string, :text then 'string' 
      when :boolean then 'bool' 
      when :datetime then 'date'
      else
        'auto'
      end
      res = {:type => type}
      res.merge!(:format => (datefm || 'd/m/Y-H:i')) if t==:datetime
      res
    end
    
  end
end

You can download the files from this entry here.

I’ve recently moved my blog to http://blog.higher-order.net. In this transition I used WordPress’ feature of importing blog content from my old blog: higher-order.blogspot.com. Unfortunately all the line-breaks from the pre-formatted JavaScript source code disappeared in the process, and so, I will have to insert it manually.

This whole process reminded me that I would really prefer to have syntax-highlighting for code-sniplets in the blog. A little bit of searching lead to GNU Source-highlight. After a little fight with the make system, I managed to install it on Mac OS X — it is looks really neat (even in the default style), and it’s simple to use.

However, the main reason I’m using this tool is not presentation: When writing the source code presentation manually in HTML one has to remember to escape characters like <. This means that the transformed source (i.e. the HTML-fragment) is no longer a syntactically correct program in the programming language of the code-snipplet, which means we can’t just paste it into an interpreter to check if it works. Sometimes this leads to people posting code which isn’t even syntactically valid… If you instead maintain a file which holds the syntactically correct source code (and using a smart editor you will immediately see stupid syntax errors instead of having blog-readers find those errors). You can then compile the source code to HTML using the Source-highlight tool. This is significantly less error prone, and the quality improves.

Here is the namespace function from a previous post.

function namespace(spec,context) {
   var validIdentifier = /^(?:[a-zA-Z_]\w*[.])*[a-zA-Z_]\w*$/,
       i,N;
   context = context || window;
   spec = spec.valueOf();
   if (typeof spec === 'object') {
      if (typeof spec.length === 'number') {//assume an array-like object
         for (i=0,N=spec.length;i<N;i++) {
             namespace(spec[i],context);
         }
      }
      else {//spec is a specification object e.g, {com: {trifork: ['model,view']}}
         for (i in spec) if (spec.hasOwnProperty(i)) {
            context[i] = context[i] || {};
            namespace(spec[i], context[i]);//recursively descend tree
         }
      }
   } else if (typeof spec === 'string') {
          (function handleStringCase(){
              var parts;
              if (!validIdentifier.test(spec)) {
                throw new Error('"'+spec+'" is not a valid name for a package.');
              }
              parts = spec.split('.');
              for (i=0,N=parts.length;i<N;i++) {
                  spec = parts[i];
                  context[spec] = context[spec] || {};
                  context = context[spec];
              }
           })();
    }  else {
       throw new TypeError();
   }
}