Introduction

In most written media,  time progresses as you move down a page:  mainstream computing languages are no different.   Anonymous Closures are a language mechanism that,  effectively,  lets programmers create new control structures.  Although people associate this power with exotic dynamic languages such as FORTH,  Scheme and TCL,   closures are becoming a feature of  mainstream languages such as Javascript and PHP (and even static languages such as C#.)

Although this article talks about issues that you’ll encounter in languages such as C# and Scheme,  I’m going to focus on Javascript written on top of the popular JQuery library:  I do that because JQuery is a great toolkit that lets programmers and designers of all skill levels do a lot by writing very little code.  Because JQuery smooths away low-level details,  it lets us clearly illustrate little weirdnesses of its programming model. Although things often work “just right” on the small scale,  little strange things snowball in larger programs — a careful look atthe  little problems is a key step towards the avoidance and mitigation of problems in big RIA projects.

Time In Programming Languages

Absent control structures,  execution proceeds from top to bottom in a computer program,  consider:

01 document.write('Hello');
02 document.write(' ');
03 document.write('World!');

Today’s languages are based on structured programming,  which encourages to use a limited number of control structures,  such as conditional expressions

04 if(happy=true) {
05    document.write('Hello');
06 } else {
07    document.write('Goodbye Cruel');
08 }
09
10 document.write('  ');
11 document.write('World!');

and loops

12 var sum=0;
13 for(i=0;i<x.length;i++) {
14   sum += x[i];
15 }

With GOTO expunged from the programming canon,   execution proceeds from top to down,   except for a limited number of  control structures that let us return to the beginning or jump to the end of a block.  It’s a simple and intuitive model that we don’t often think about,  but it’s easy to write code that breaks this model when programming with closures.

Emulating Foreach() in Javascript with Closures

Popular languages such as PHP and C# have a foreach() statement that loops over the elements of a collection without the need to keep track of a counter variable.  Popular Javascript frameworks such as JQuery and Dojo implement foreach functions;  with the magic of closures,  we can get an effect similar to a built-in foreach construct.  For instance,  in JQuery,  we can write

16 var sum=0;
17 $.each(x,function(i,val) {
18    sum += arg;
19 });

In this case,  the second argument of the $.each (JQuery.each) function is a anonymous function.  The special property it has,  as a closure,  is that the anonymous function has access to variables in the enclosing scope,  namely sum.  This allows the code in 16-19 to look and work a lot like the code in 12-15,  despite the fact that line 18 is in a different function than line 16.

As an aside,  this kind of higher-order function is often simple to implement;  although the real $.each() function is capable of iterating over a wide variety of types (thus more complex),  a function that can iterate over arrays is as simple as

20 function foreachArrayElement(arr,loopBody) {
21    for(i=0;i<x.length;i++) {
22       loopBody(i,x[i])
23    }
24 }

Breaking The Conventions of Time

Although you’ve got other choices,  closures are  a popular and concise way to write callbacks for aysnchronous communication.  Suppose that we want to GET a packet of JSON data from a server and update a user inteface.  In JQuery we could write:

25 $.get("JsonService", {}, function(data, textStatus) {
26     var obj=JSON.parse(data);
27     someUIElement.update(obj);
28  });
29
30 ... do more stuff ...

Note that time isn’t progressing downward in this script anymore.  We got from line 25 directly to line 30.  The code between 26-28 only executes when data gets back from the server.  In this case,  this behavior is caused by the asynchronous nature of XMLHttpRequest,  for which $.get() is  wrapper.  Similar behavior can be had by attaching an event handler to a DOM object,  or even by adding a function reference to an object or the global scope,  causing the anonymous function to execute when some other function,  defined elsewhere,  executes.

“Race Conditions” In Asynchronous Communication

Although it’s not wrong to break the conventions of time,  doing so risks the introduction of tricky and subtle errors.  Suppose we’re building an AJAX application where we’d like to cache an object,  retrieving the object only if we don’t have a copy in cache.  One obvious approach is to write

31 if (cachedCopy==undefined) {
32  $.get("DataService",{},function(data,textStatus) {
33       cachedCopy=data;
34       updateUIOne(data);
35   }
36 } else {
37   updateUIOne(cachedCopy);
38 }
39
40 updateUITwo();

UpdateUIOne(data) populates the user interface with the data.  UpdateUITwo() makes some other change to the user interface.

Unfortunately,  this code has a potential bug that’s hidden by the conventions of time.  When data is in the cache,  line 37 executes before line 40,  so that updateUIOne(data) is called before updateUITwo().   When data is not in the cache,  line 40 executes before 33 (communication callbacks don’t run in Javascript until the code being run returns to the browser.)  It’s all fine if the order in which you run updateUIOne and updateUITwo doesn’t matter — and it’s a disaster if it does…  This kind of code does one thing sometimes and does another thing other times:  code of this type is difficult to test,  and leads to the kind of bug that drives people to drink.

The real answer to these problems is to take a systematic approach to asynchronous communication:  any strategy based on band-aids that work here or these is going will eventally break down under the weight of growing requirements.  That said,  I’ll offer a few strategies for patching this kind of problem:

1. If we could move updateUITwo() from line 40 to before line 31,  updateUITwo() and updateUIOne() could be run in a consistent order.
2. Modifying updateUIOne(data) to call updateUITwo() after it completes also results in a consistent order
3. We can schedule UpdateUIOne to run AFTER the executing code returns to the browser,  by replacing line 34 with

41    setTimeout(function() { updateUIOne(data) },1);

Structural Instability

Let’s consider another example where the conventions of time are treacherous:  suppose we need to retrieve three chunks of data from the server

42 $.get("Chunk1Server",{},function(data1,textStatus1) {
43   UpdateUIOne(data1);
44   $.get("Chunk2Server",{},function(data2,textStatus2) {
45       UpdateUITwo(data2);
46        $.get("Chunk3Server",{},function(data3,textStatus3) {
47            UpdateUIThree(data3);
48       });
49    });
50 });

Note that this specific chunk of code executes exactly the way that it looks.  Although there are some gaps,  execution proceeds progressively from line 42 to 47.  The “nested closure” idiom is common in Javascript code,   probably because it looks a lot the synchronous code that does the same job,  but it’s treacherous:  a tiny change in the code can break the conventions of time,  causing strange things to happen.  This property is called structural instability.

For example,  the above code might return directly to the browser,   eliminating the possibility of the “race conditions” seen in the last section. If we add the following line:

51 UpdateUIFour();

we’ll find that UpdateUIFour() runs ~before~ the other other functions.  This isn’t bad behavior if we expect it,  but could have spooky effects if we don’t.  This example is trivial,  but similar mistakes can be made in any of the closures,  resulting in errors that can be quite baffling.

The structural instability of nested closures pushes complex AJAX applications towards other styles of coding,  such as a state-machine organization.

Order Of Arguments

This is small compared to the other issues,  but the order of arguments of callback functions can add to the the confusions around the time:  The $.get() function provides a good example,  since it support four parameters:

51 $.get(url,parameters,callback,type);

all of the parameters,  except for the url,  are optional.   It’s generally good to put less used optional parameters towards the right,  but placing the type declaration after the callback disturbs the flow of time and hurts readability.  If you choose to have the return data parsed as JSON format,

52 $.get(targetUrl,{},function(data,textStatus) {
53    ... handler code ...
54 },"json");

you’ll see that the type specification occurs after the callback.  This,  by itself,  adds a small amount of confusion,  but when you’ve got multiple nested closures or if you were computing the values defined after the callback,  code becomes immediately difficult to understand.

Event Handlers And “COMEFROM”

In 1973 R. Lawrence Clark kiddingly introduced a COMEFROM statement in response to Edgser Dijkstra’s famous “GO TO Considered Harmful”,  from the associated Wikipedia Article,  I take an example of a program in a hypothetical BASIC dialect that uses COMEFROM:

55 COMEFROM 58
56 INPUT "WHAT IS YOUR NAME? "; A$
57 PRINT "HELLO, "; A$
58 REM

COMEFROM is a bit disturbing because it involves an “action at a distance:”  line 55 modifies the behavior of line 58.  A person looking a line 58 in isolation would have a hard time understanding what happens in the program when execution reaches line 58.

The use of event handlers,  both built in and custom,  has an effect similar to COMEFROM.  Consder the common example

59 $("#activeButton").click(function() {
60    ... handle button click...
61 }

Once more,  the code at line 60 will execute after the code that follows line 61.  Line 59 modifies the behavior of a built-in UI element,  which might be defined like

62 <input type="button" id="activeButton" value="Button X">

Looking at line 62 alone,  it’s impossible to tell what what happens when you click on the button;  an “onClick” handler in line 62 would be more immediately obvious in function.  That said,  events are a proven model for GUI programming that introduces a useful decoupling between the parts of a system — a looser coupling that lets us build bigger systems.  In the context of JQuery,  it’s great to be able to write something like

63 <div class="SpecialArea">... content ...</div>

Javascript code can then use the $() function to attach styles,  event handlers and to manipulate DOM elements inside the .SpecialArea to give the area specific behaviors and appearance.  This lets a developer provide a powerful but easy-to-use abstraction to a designer:   adding a single class specification lets us reuse tens of CSS specifications and several event handlers.   This is a big win,  but we can’t forget the hidden COMEFROM that’s implied.

Events are dynamically added and removed,  even in static languages such as Java and C#.  Although this dynamism adds flexibility,  it comes at a cost.  IDEs such as Eclipse and Visual Studio can do a great job of helping programmers understand static method calls:  for instance,  you can click on the name of a method and see a list of places where this method is called.  Because events aren’t amenable to static analysis,  inappropriate use (or even appropriate use) of events impair some of the tools we have for understanding programs.

Events are a great tool,  but programmers need to understand the weirdness that underlies them.  Used deliberately,  events can provide a concise and scalable way to move information and direct control in an application.  Poorly used events can cause software to degenerate to “spaghetti code”.

Conclusion

Closures are a powerful and concise way to express your intentions to a computer:  however,  closures break some of the intuitive assumptions that people use to understand software — specifically,  the idea that time moves downward through the execution of a procedure.  This leads to a kind of structural instability,   where software that’s perfectly simple and clear at a simple level can suddenly get much harder to understand when several complications converge.  This article uses JQuery-Javascript as an example not because JQuery is bad,  but because it’s good:   it’s a tool that helps beginning (and advanced) programmers accomplish a lot with little code.  Yet,  as we build increasingly complex applications,  we need a clear understand of the big and little weirdnesses of RIA programming.

The Garmin eTrex series are popular handheld GPS units.  The eTrex H is a inexpensive unit with excellent sensitivity and accuracy,  and the eTrex Vista HCx is a favorite of OpenStreetMap contributors because it accepts a microSD card which can hold OSM maps.  I intended to use my Vista HCx to contribute to OSM and to georeference photographs,  but I was shocked to discover that eTrex units remove time information from saved tracks. This means that saved tracks aren’t useful if you want to georeference photographs with an application like GPicSync.  There’s a simple solution to this problem:  avoid using saved tracks,  and download the “Active Track” instead.

Saved Tracks

The eTrex units “dumb down” saved tracks by (i) reducing the number of points, (ii) removing time information,  and (iii) applying spatial filtering.  A saved track looks like this in Garmin MapSource:

This track could be useful for mapping,  but lacking time information,  it can’t be used to reference events that occur at a particular moment in time.  Although the eTrex has a number of menu items for configuring the active track (to,  for instance,  increase the sample rate at which points are taken) there are no options that influence the information stored in saved tracks.

What’s in your eTrex?

Once you’ve loaded tracks from your eTrex, you’ll see that there are both saved tracks and a collection of “active logs”:

You’ll usually find more than one active log:  new ones are created in order when the unit is power cycled or the track is otherwise reset.  Active logs respect the sampling rate you’ve specified,  keep timestamps,  and are less filtered than saved tracks:

Conclusion

Avoid saved tracks if timestamps matter to you.  You’ll lose the advantage of using saved tracks to organize your tracks,  but this should matter little if you’re georeferencing photographs:  GPicSync looks at all of the tracks in the .gpx file and uses timestamps to match everything up.

A collection of car pictures under a Creative Commons license,  it was built from a taxonomy that was constructed from Dbpedia and Freebase.  My editor and I then used a scalable process to clean up the taxonomy,  find matching images and enrich image metadata.  As you can imagine,  this is a process that can be applied to other problem domains:  we’ve tested some of the methodology on our site Animal Photos! but this is the first site designed from start to finish based on the new technology.

Car Pictures was made possible by data sets available on the semantic web,  and it’s soon about to export data via the semantic web.  We’re currently talking with people about exporting our content in a machine-readable linked data format — in our future plans,  this will enable a form of semantic search that will revolutionize multimedia search:  rather than searching for inprecise keywords,  it will become possible to look up pictures,  video and documents about named entities found in systems such as Freebase,  Wikipedia,  WordNet,  Cyc and OpenCalais.

In the next few days we’re going to watch carefully how Car Pictures interacts with users and with web crawlers.  Then we’ll be adding content,  community features,  and a linked data interface.   In the meantime,  we’re planning to build something at least a hundred times bigger.

Quite literally, thousands of people have contributed to Car Pictures,  but I’d like to particularly thank Dan Brickley,  who’s been helpful in the process of interpreting Dbpedia with his ARC2 RDF tools,  and Kingsley Idehen,  who’s really helped me sharpen my vision of what the semantic web can be.

Anyway,  I’d love any feedback that you can give me about Car Pictures and any help I can get in spreading the word about it.  If you’re interested in making  similar site about some other subject,  please contact me:  it’s quite possible that we can help.

Introduction

Languages such as LISP,  ML,  oCaml F# and Scala have supported first-class functions for a long time.  Functional programming features are gradually diffusing into mainstream languages such as C#,  Javascript and PHP.   In particular,  Lambda expressions,  implicit typing,  and delegate autoboxing have made  C# 3.0 an much more expressive language than it’s predecssors.

In this article,  I develop a simple function that acts on functions:  given a boolean function f,  F.Not(f) returns a new boolean function which is the logical negation of f.  (That is,  F.Not(f(x)) == !f(x)).   Although the end function is simple to use,  I had to learn a bit about the details of C# to ge tthe behavior  I wanted — this article records that experience.

Why?

I was debugging an application that uses Linq-to-Objects the other day,  and ran into a bit of a pickle.  I had written an expression that would return true if all of the values in a List<String> were valid phone numbers:

[01] dataColumn.All(Validator.IsValidPhoneNumber);

I was expecting the list to validate successfully,  but the function was returning false.  Obviously at least one of the values in the function was not validating — but which one?  I tried using a lambda expression in the immediate window (which lets you type in expression while debugging) to reverse the order of matching:

[02] dataColumn.Where(s => !ValidatorIsValidPhoneNumber(x));

but that gave me the following error message:

[03] Expression cannot contain lambda expressions

(The expression compiler used in the immediate window doesn’t support all of the language features supported by the full C# compiler.)  I was able to answer find the non matching elements using the set difference operator

[04] dataColumn.Except(dataColumn.Where(Validator.IsValidPhoneNumber).ToList()

but I wanted an easier and more efficient way — with a logical negation function,  I could just write

[05] dataColumn.Except(F.Not(Validator.IsValidPhoneNumber).ToList();

Try 1: Extension Method

I wanted to make the syntax for negation as simple as possible.  I didn’t want to even have to name a class eliminate the need to name a class,  so I tried the following extension method:

[06] static class FuncExtensions {
[07]    public static Func<Boolean> Not(this Func<Boolean> innerFunction) {
[08]       return ()  => innerFunction();
[09]    }
[10]    ...
[11]   }

I was hoping that,  given a function like

[12] public static boolean AlwaysTrue() { return true };

that I could negate the function by writing

[13] AlwaysTrue.Not()

Unfortunately,  it doesn’t work that way:  the extension method can only be called on a delegate of type Func<Boolean>.  Although the compiler will “autobox” function references to delegates in many situations,  it doesn’t do it when you reference an extension method.  I could write

[14] (Func<Boolean> AlwaysTrue).Not()

but that’s not a pretty syntax.   At that point,  I tried another tack.

Try 2: Static Method

Next,  I defined a set of negation functions as static methods on a static class:

[15] public static class F {
[16]    public static Func<Boolean> Not(Func<Boolean> innerFunction) {
[17]       return () => !innerFunction();
[18]    }
[19]
[20]    public static Func<T1,Boolean> Not<T1>(
[21]       Func<T1,Boolean> innerFunction) {
[22]          return x =>!innerFunction(x);
[23]    }
[24]
[25]    public static Func<T1, T2,Boolean> Not<T1,T2>(
[26]       Func<T1, T2,Boolean> innerFunction) {
[27]          return (x,y) => !innerFunction(x,y);
[28]    }
[29]
[30]    public static Func<T1, T2, T3, Boolean> Not<T1,T2,T3>(
[31]       Func<T1, T2, T3, Boolean> innerFunction) {
[32]           return (x, y, z) => !innerFunction(x, y, z);
[33]    }
[34]
[35]    public static Func<T1, T2, T3, T4, Boolean> Not<T1, T2, T3, T4>(
[36]       Func<T1, T2, T3, T4,Boolean> innerFunction) {
[37]          return (x, y, z, a) => !innerFunction(x, y, z, a);
[38]    }
[39] }

Now I can write

[40] F.Not(AlwaysTrue)() // always == false

or

[41] Func<int,int,int,int,Boolean> testFunction = (a,b,c,d) => (a+b)>(c+d)
[42] F.Not(testFunction)(1,2,3,4)

which is sweet — the C# compiler now automatically autoboxes the argument to F.Not on line [40].  Note two details of how type inference works here:

1. The compiler automatically infers the type parameters of F.Not() by looking at the arguments of the innerFunction.  If it didn’t do that,  you’d need to write

   F.Not<int,int,int,int>(testFunction)(1,2,3,4)

   which would be a lot less fun.

2. On line [40],  note that the compiler derives the types of the parameters a,b,c, and d using the type declaration on the right hand side (RHS)

   Func<int,int,int,int,Boolean>

   you can’t write var on the RHS in this situation because that doesn’t give the compiler information about the parameters and return values of the lambda.

Although good things are happening behind the scenes,  there are also two bits of ugliness:

1. I need to implement F.Not() 5 times to support functions with 0 to 4 parameters:  once I’ve done that,  however,  the compiler automatically resolves the overloading and picks the right version of the function.
2. The generic Func<> and Action<> delegates support at most 4 parameters.  Although it’s certainly true that functions with a large number of parameters can be difficult to use and maintain (and should be discouraged),  this is a real limitation.

Extending IEnumerable<T>

One of the nice things about Linq is that you can extend it by adding new extension methods to IEnumerable.  Not everbody agrees,  but I’ve always liked the unless() satement in Perl,  which is equivalent to if(!test):

[42] unless(everything_is_ok()) {
[43]   abort_operation;
[44] }

A replacement for the Where(predicate) method that negates the predicate function would be convenient my debugging problem:

I built an Unless() extension method that combines Where() with F.Not():

[45] public static IEnumerable<T> Unless<T>(
[46]    this IEnumerable<T> input, Func<T, Boolean> fn) {
[47]       return input.Where(F.Not(fn));
[48]     }

Now I can write

[49] var list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
[50] var filtered = list.Unless(i => i > 3).ToList();

and get the result

[51] filtered = { 1,2,3 }

Conclusion

New features in C# 3.0 make it an expressive language for functional programming.  Although the syntax of C# isn’t quite as sweet as F# or Scala,  a programmer who works with the implicit typing and autoboxing rules of the compiler can create functions that act on functions that are easy to use — in this article we develop a set of functions that negate boolean functions and apply this to add a new restriction method to IEnumerable<T>.

Freebase is a open database of things that exist in the world:  things like people,  places,  songs and television shows.   As of the January 2009 dump,  Freebase contained about 241 million facts,  and it’s growing all the time.  You can browse it via the web and even edit it,  much like Wikipedia.  Freebase also has an API that lets programs add data and make queries using a language called MQL.  Freebase is complementary to DBpedia and other sources of information.  Although it takes a different approach to the semantic web than systems based on RDF standards,  it interoperates with them via  linked data.

The January 2009 Freebase dump is about 500 MB in size.  Inside a bzip-compressed files,  you’ll find something that’s similar in spirit to a Turtle RDF file,  but is in a simpler format and represents facts as a collection of four values rather than just three.

Your Own Personal Freebase

To start exploring and extracting from Freebase,  I wanted to load the database into a star schema in a mysql database — an architecture similar to some RDF stores,  such as ARC.  The project took about a week of time on a modern x86 server with 4 cores and 4 GB of RAM and resulted in a 18 GB collection of database files and indexes.

This is sufficient for my immediate purposes,  but future versions of Freebase promise to be much larger:  this article examines the means that could be used to improve performance and scalability using parallelism as well as improved data structures and algorithms.

I’m interested in using generic databases such as Freebase and Dbpedia as a data source for building web sites.  It’s possible to access generic databases through  APIs,  but there are advantages to having your own copy:  you don’t need to worry about API limits and network latency,  and you can ask questions that cover the entire universe of discourse.

Many RDF stores use variations of a format known as a Star Schema for representing RDF triples;  the Star Schema is commonly used in data warehousing application because it can efficiently represent repetitive data.   Freebase is similar to,  but not quite an RDF system.  Although there are multiple ways of thinking about Freebase,  the quarterly dump files provided by Metaweb are presented as quads:  groups of four related terms in tab-delimited terms.  To have a platform for exploring freebase,  I began a project of loading Freebase into a Star Schema in a relational database.

A Disclaimer

Timings reported in this article are approximate.  This work was done on a server that was doing other things; little effort was made to control sources of variation such as foreign workload,  software configuration and hardware characteristics.  I think it’s orders of magnitude that matter here:  with much larger data sets becoming available,  we need tools that can handle databases 10-100 times as big,  and quibbling about 20% here or there isn’t so important.  I’ve gotten similar results with the ARC triple store.  Some products do about an order of magnitude better:  the Virtuoso server can load DBpedia,  a larger database,   in about 16 to 22 hours on a 16 GB computer:  several papers on RDF store performance are available [1] [2] [3].  Although the system described in this paper isn’t quite an RDF store,  it’s performance is comprable to a relatively untuned RDF store.

It took about a week of calendar time to load the 241 million quads in the January 2009 Freebase into a Star Schema using a modern 4-core web server with 4GB of RAM;  this time could certainly be improved with microoptimizations,  but it’s in the same range that people are observing that it takes to load 10^8 triples into other RDF stores.  (One product is claimed to load DBPedia,  which contains about 100 million triples,  in about 16 hours with “heavy-duty hardware”.)   Data sets exceeding 10^9 triples are becoming rapidly available — these will soon exceed what can be handled with simple hardware and software and will require new techniques:  both the use of parallel computers and optimized data structures.

The Star Schema

In a star schema,  data is represented in separate fact and dimension tables,

all of the rows in the fact table (quad) contain integer keys — the values associated with the keys are defined in dimension tables (cN_value).  This efficiently compresses the data and indexes for the fact table,  particularly when the values are highly repetitive.

I loaded data into the following schema:

create table c1_value (
   id             integer primary key auto_increment,
   value          text,
   key(value(255))
) type=myisam;

... identical c2_value, c3_value and c4_value tables ...

create table quad (
   id             integer primary key auto_increment,
   c1             integer not null,
   c2             integer not null,
   c3             integer not null,
   c4             integer not null
) type=myisam;

Although I later created indexes on c1, c2, c3, and c4 in the quad table,  I left unnecessary indexes off of the tables during the loading process because it’s more efficient to create indexes after loading data in a table.  The keys on the value fields of the dimension tables are important,  because the loading process does frequent queries to see if values already exist in the dimension table.  The sequentially assigned id in the quad field isn’t necessary for many applications,  but it gives each a fact a unique identity and makes the system aware of the order of facts in the dump file.

The Loading Process

The loading script was written in PHP and used a naive method to build the index incrementally.  In pseudo code it looked something like this:

function insert_quad($q1,$q2,$q3,$q4) {
    $c1=get_dimension_key(1,$q1);
    $c2=get_dimension_key(2,$q2);
    $c3=get_dimension_key(3,$q3);
    $c4=get_dimension_key(4,$q4);
    $conn->insert_row("quad",null,$c1,$c2,$c3,$c4)
}

function get_dimension_key($index,$value) {
    $cached_value=check_cache($value);
    if ($cached_value)
        return $cached_value;

    $table="$c{$index}_value";
    $row=$conn->fetch_row_by_value($table,$value);
    if ($row)
        return $row->id;
    $conn->insert_row($table,$value);
    return $conn->last_insert_id
};

Caching frequently used dimension values improves performance by a factor of five or so,  at least in the early stages of loading.  A simple cache management algorithm,  clearing the cache every 500,000 facts,  controls memory use.  Timing data shows that a larger cache or better replacement algorithm would make at most an increment improvement in performance.  (Unless a complete dimension table index can be held in RAM,  in which case all read queries can be eliminated.)

I performed two steps after the initial load:

1. Created indexes on quad(c1), quad(c2), quad(c3) and quad(c4)
2. Used myisam table compression to reduce database size and improve performance

Loading Performance

It took about 140 hours (nearly 6 days) to do the initial load.  Here’s a graph of facts loaded vs elapsed time:

The important thing Iabout this graph is that it’s convex upward:  the loading process slows down as the number of facts increases.  The first 50 quads are loaded at a rate of about 6 million per hour;  the last 50 are loaded at a rate of about 1 million per hour.  An explanation of the details of the curve would be complex,  but log N search performance of B-tree indexes and the ability of the database to answer queries out of the computer’s RAM cache would be significant.  Generically,  all databases will perform the same way,  becoming progressively slower as the size of the database increases:  you’ll eventually reach a database size where the time to load the database becomes unacceptable.

The process of constructing b-tree indexes on the mysql tables took most of a day.  On average it took about four hours to construct a b-tree index on one column of quad:

mysql> create index quad_c4 on quad(c4);
Query OK, 243098077 rows affected (3 hours 40 min 50.03 sec)
Records: 243098077  Duplicates: 0  Warnings: 0

It took about an hour to compress the tables and rebuild indexes,  at which point the data directory looks like:

-rw-r----- 1 mysql root        8588 Feb 22 18:42 c1_value.frm
-rw-r----- 1 mysql root   713598307 Feb 22 18:48 c1_value.MYD
-rw-r----- 1 mysql root   557990912 Feb 24 10:48 c1_value.MYI
-rw-r----- 1 mysql root        8588 Feb 22 18:56 c2_value.frm
-rw-r----- 1 mysql root      485254 Feb 22 18:46 c2_value.MYD
-rw-r----- 1 mysql root      961536 Feb 24 10:48 c2_value.MYI
-rw-r----- 1 mysql root        8588 Feb 22 18:56 c3_value.frm
-rw-r----- 1 mysql root   472636380 Feb 22 18:51 c3_value.MYD
-rw-r----- 1 mysql root   370497536 Feb 24 10:51 c3_value.MYI
-rw-r----- 1 mysql root        8588 Feb 22 18:56 c4_value.frm
-rw-r----- 1 mysql root  1365899624 Feb 22 18:44 c4_value.MYD
-rw-r----- 1 mysql root  1849223168 Feb 24 11:01 c4_value.MYI
-rw-r----- 1 mysql root          65 Feb 22 18:42 db.opt
-rw-rw---- 1 mysql mysql       8660 Feb 23 17:16 quad.frm
-rw-rw---- 1 mysql mysql 3378855902 Feb 23 20:08 quad.MYD
-rw-rw---- 1 mysql mysql 9927788544 Feb 24 11:42 quad.MYI

At this point it’s clear that the indexes are larger than the actual databases:  note that c2_value is much smaller than the other tables because it holds a relatively small number of predicate types:

mysql> select count(*) from c2_value;
+----------+
| count(*) |
+----------+
|    14771 |
+----------+
1 row in set (0.04 sec)

mysql> select * from c2_value limit 10;
+----+-------------------------------------------------------+
| id | value                                                 |
+----+-------------------------------------------------------+
|  1 | /type/type/expected_by                                |
|  2 | reverse_of:/community/discussion_thread/topic         |
|  3 | reverse_of:/freebase/user_profile/watched_discussions |
|  4 | reverse_of:/freebase/type_hints/included_types        |
|  5 | /type/object/name                                     |
|  6 | /freebase/documented_object/tip                       |
|  7 | /type/type/default_property                           |
|  8 | /type/type/extends                                    |
|  9 | /type/type/domain                                     |
| 10 | /type/object/type                                     |
+----+-------------------------------------------------------+
10 rows in set (0.00 sec)

The total size of the mysql tablespace comes to about 18GB,  anexpansion of about 40 times relative to the bzip2 compressed dump file.

Query Performance

After all of this trouble,  how does it perform?  Not too bad if we’re asking a simple question,  such as pulling up the facts associated with a particular object

mysql> select * from quad where c1=34493;
+---------+-------+------+---------+--------+
| id      | c1    | c2   | c3      | c4     |
+---------+-------+------+---------+--------+
| 2125876 | 34493 |   11 |      69 | 148106 |
| 2125877 | 34493 |   12 | 1821399 |      1 |
| 2125878 | 34493 |   13 | 1176303 | 148107 |
| 2125879 | 34493 | 1577 |      69 | 148108 |
| 2125880 | 34493 |   13 | 1176301 | 148109 |
| 2125881 | 34493 |   10 | 1713782 |      1 |
| 2125882 | 34493 |    5 | 1174826 | 148110 |
| 2125883 | 34493 | 1369 | 1826183 |      1 |
| 2125884 | 34493 | 1578 | 1826184 |      1 |
| 2125885 | 34493 |    5 |      66 | 148110 |
| 2125886 | 34493 | 1579 | 1826185 |      1 |
+---------+-------+------+---------+--------+
11 rows in set (0.05 sec)

Certain sorts of aggregate queries are reasonably efficient,  if you don’t need to do them too often:  we can look up the most common 20 predicates in about a minute:

select
   (select value from c2_value as v where v.id=q.c2) as predicate,count(*)
   from quad as q
     group by c2
     order by count(*) desc
     limit 20;

+-----------------------------------------+----------+
| predicate                               | count(*) |
+-----------------------------------------+----------+
| /type/object/type                       | 27911090 |
| /type/type/instance                     | 27911090 |
| /type/object/key                        | 23540311 |
| /type/object/timestamp                  | 19462011 |
| /type/object/creator                    | 19462011 |
| /type/permission/controls               | 19462010 |
| /type/object/name                       | 14200072 |
| master:9202a8c04000641f800000000000012e |  5541319 |
| master:9202a8c04000641f800000000000012b |  4732113 |
| /music/release/track                    |  4260825 |
| reverse_of:/music/release/track         |  4260825 |
| /music/track/length                     |  4104120 |
| /music/album/track                      |  4056938 |
| /music/track/album                      |  4056938 |
| /common/document/source_uri             |  3411482 |
| /common/topic/article                   |  3369110 |
| reverse_of:/common/topic/article        |  3369110 |
| /type/content/blob_id                   |  1174046 |
| /type/content/media_type                |  1174044 |
| reverse_of:/type/content/media_type     |  1174044 |
+-----------------------------------------+----------+
20 rows in set (43.47 sec)

You’ve got to be careful how you write your queries:  the above query with the subselect is efficient,  but I found it took 5 hours to run when I joined c2_value with quad and grouped on value.  A person who wishes to do frequent aggregate queries would find it most efficient to create a materialized views of the aggregates.

Faster And Large

It’s obvious that the Jan 2009 Freebase is pretty big to handle with the techniques I’m using.  One thing I’m sure of is that that Freebase will be much bigger next quarter — I’m not going to do it the same way again.  What can I do to speed the process up?

Don’t Screw Up

This kind of process involves a number of lengthy steps.  Mistakes,  particularly if repeated,  can waste days or weeks.  Although services such as EC2 are a good way to provision servers to do this kind of work,  the use of automation and careful procedures is key to saving time and money.

Partition it

Remember how the loading rate of a data set decreases as the size of the set increase?  If I could split the data set into 5 partitions of 50 M quads each,  I could increase the loading rate by a factor of 3 or so.  If I can build those 5 partitions in parallel (which is trivial),  I can reduce wallclock time by a factor of 15.

Eliminate Random Access I/O

This loading process is slow because of the involvement of random access disk I/O.  All of Freebase canbe loaded into mysql with the following statement,

LOAD DATA INFILE ‘/tmp/freebase.dat’ INTO TABLE q FIELDS TERMINATED  BY ‘\t’;

which took me about 40 minutes to run.   Processes that do a “full table scan” on the raw Freebase table with a grep or awk-type pipeline take about 20-30 minutes to complete.  Dimension tables can be built quickly if they can be indexed by a RAM  hasthable.   The process that builds the dimension table can emit a list of key values for the associated quads:  this output can be sequentially merged to produce the fact table.

Bottle It

Once a data source has been loaded into a database,  a physical copy of the database can be made and copied to another machine.  Copies can be made in the fraction of the time that it takes to construct the database.  A good example is the Amazon EC2 AMI that contains a preinstalled and preloaded Virtuoso database loaded with billions of triples from DBPedia,  MusicBrainz,  NeuroCommons and a number of other databases.  Although the process of creating the image is complex,  a new instance can be provisioned in 1.5 hours at the click of a button.

Compress Data Values

Unique object identifiers in freebase are coded in an inefficient ASCII representation:

mysql> select * from c1_value limit 10;
+----+----------------------------------------+
| id | value                                  |
+----+----------------------------------------+
|  1 | /guid/9202a8c04000641f800000000000003b |
|  2 | /guid/9202a8c04000641f80000000000000ba |
|  3 | /guid/9202a8c04000641f8000000000000528 |
|  4 | /guid/9202a8c04000641f8000000000000836 |
|  5 | /guid/9202a8c04000641f8000000000000df3 |
|  6 | /guid/9202a8c04000641f800000000000116f |
|  7 | /guid/9202a8c04000641f8000000000001207 |
|  8 | /guid/9202a8c04000641f80000000000015f0 |
|  9 | /guid/9202a8c04000641f80000000000017dc |
| 10 | /guid/9202a8c04000641f80000000000018a2 |
+----+----------------------------------------+
10 rows in set (0.00 sec)

These are 38 bytes apiece.  The hexadecimal part of the guid could be represented in 16 bytes in a binary format,  and it appears that about half of the guid is a constant prefix that could be further excised.

A similar efficiency can be gained in the construction of in-memory dimension tables: md5 or sha1 hashes could be used as proxies for values.

The freebase dump is littered with “reverse_of:” properties which are superfluous if the correct index structures exist to do forward and backward searches.

Parallelize it

Loading can be parallelized in many ways:  for instance,  the four dimension tables can be built in parallel.  Dimension tables can also be built by a sorting process that can be performed on a computer cluster using map/reduce techniques.  A cluster of computers can also store a knowledge base in RAM,  trading sequential disk I/O for communication costs.  Since the availability of data is going to grow faster than the speed of storage systems,  parallelism is going to become essential for handling large knowledge bases — an issue identified by Japanese AI workers in the early 1980’s.

Cube it?

Some queries  benefit from indexes built on combinations of tables,  such as

CREATE INDEX quad_c1_c2 ON quad(c1,c2);

there are 40 combinations of columns on which an index could be useful — however,  the cost in time and storage involved in creating those indexes would be excessively expensive.  If such indexes were indeed necessary, a Multidimensional database can create a cube index that is less expensive than a complete set of B-tree indexes.

Break it up into separate tables?

It might be anathema to many semweb enthusiasts,  but I think that Freebase (and parts of Freebase) could be efficiently mapped to conventional relational tables.  That’s because facts in Freebase are associated with types,  see,  for instance,  Composer from the Music Commons.  It seems reasonable to map types to relational tables and to create satellite tables to represent many-to-many relationships between types.  This scheme would automatically partition Freebase in a reasonable way and provide an efficient representation where many obvious questions (ex. “Find Female Composers Born In 1963 Who Are More Than 65 inches tall”) can be answered with a minimum number of joins.

Conclusion

Large knowledge bases are becoming available that cover large areas of human concern:  we’re finding many applications for them.  It’s possible to to handle databases such as Freebase and DBpedia on a single computer of moderate size,  however,  the size of generic databases and the hardware to store them on are going to grow larger than the ability of a singler computer to process them.  Fact stores that (i) use efficient data structures,  (ii) take advantage of parallelism,  and (iii) can be tuned to the requirements of particular applications,  are going to be essential for further progress in the Semantic Web.

Credits

• Metaweb Technologies, Freebase Data Dumps, January 13, 2009
• Kingsley Idehen,  for several links about RDF store performance.
• Stewart Butterfield for encyclopedia photo.

I’ve got an IEnumerable<T> that contains a list of values:  I want to know if all of the values in that field are distinct.  The function should be easy to use a LINQ extension method and,  for bonus points,  simply expressed in LINQ itself

One Solution

First,  define an extension method

01   public static class IEnumerableExtensions {
02        public static bool AllDistinct<T>(this IEnumerable<T> input) {
03            var count = input.Count();
04            return count == input.Distinct().Count();
05        }
06    }

When you want to test an IEnumerable<T>,  just write

07 var isAPotentialPrimaryKey=CandidateColumn.AllDistinct();

Analysis

This solution is simple and probably scales as well as any solution in the worst case.  However,  it enumerates the IEnumerable<T> twice and does a full scan of the IEnumerable even if non-distinct elements are discovered early in the enumeration.  I could certainly make an implementation that aborts early using a Dictionary<T,bool> to store elements we’ve seen and a foreach loop,  but I wonder if anyone out there can think of a better pure-Linq solution.

Many Silverlighters use XAML to design the visual appearance of their applications.  A UserControl defined with XAML is a DependencyObject that has a complex lifecycle:  there’s typically a .xaml file,  a .xaml.cs file,  and a .xaml.g.cs file that is generated by visual studio. The .xaml.g.cs file is generated by Visual Studio,  and ensures that objects defined in the XAML file correspond to fields in the object (so they are seen in intellisense and available to your c# code.)  The XAML file is re-read at runtime,  and drives a process that instantiates the actual objects defined in the XAML file — a program can compile just fine,  but fail during initialization if the XAML file is invalid or if you break any of the assumptions of the system.

XAML is a pretty neat system because it’s not tied to WPF or WPF/E.  It can be used to initialize any kind of object:  for instance,  it can be used to design workflows in asynchronous server applications based on Windows Workflow Foundation.

One problem with XAML,  however,  is that you cannot write controls that inherit from a UserControl that defined in XAML.  Visual Studio might compile the classes for you,  but they will fail to initialize at at runtime.  This is serious because it makes it impossible to create subclasses that let you make small changes to the appearance or behavior of a control.

Should We Just Give Up?

One approach is to give up on XAML.  Although Visual Studio encourages you to create UserControls with XAML,  there’s nothing to stop you from creating a new class file and writing something like

class MyUserControl:UserControl {
      public MyUserControl {
      var innerPanel=new StackPanel();
      Content=innerPanel;
      innerPanel.Children.Add(new MyFirstVisualElement());
      innerPanel.Children.Add(new MySecondVisualElement());
      ...
}

UserControls defined like this have no (fundamental) problems with inheritance,  since you’ve got complete control of the initialization process.  If it were up to me,  I’d write a lot of controls like this,  but I work on a team with people who design controls in XAML,  so I needed a better solution.

Or Should We Just Cheat?

If we still want to use XAML to define the appearance of a control,  we’ve got another option.  We can move the XAML into a control that is outside the inheritance hierarchy:  the XAML control is then contained inside another control which doesn’t have restrictions as to how it is used:

The XamlPanelInnards.xaml.cs code-behind is almost completely empty:  it contains only the constructor created by Visual Studio’s XAML designer.  XamlPanel.cs contains a protected member called InnerControl which is of type XamlPanelInnards.  InnerControl is initialized in the constructor of XamlPanel,  and is also assigned to the Content property of the XamlPanel,  to make it visible.  Everything that you’d ordinarily put in the code-behind XamlPanelInnards.xaml.cs goes into XamlPanel.cs,  which uses the InnerControl member to get access to the internal members defined by the XAML designer.

Step-by-Step Refactoring

Let’s imagine that we’ve got an existing UserControl implemented in XAML called the XamlPanel.  We’d like to subclass the XamlPanel so we can use it for multiple purposes.  We can do this by:

1. Renaming XamlPanel to OldXamlPanel;  this renames both the *.xaml and *.xaml.cs files so we can have them to look at
2. Use Visual Studio to create a new “Silverlight User Control” called XamlPanelInnards.  This will have both a *.xaml and *.xaml.xs file
3. Copy the contents of OldXamlPanel.xaml to XamlPanelInnards.cs.  Edit the x:Class attribute of the <UserControl> element to reflect the new class name,  “XamlPanelInnards”
4. Use Visual Studio to create a new class,  called XamlPanel.cs.  Do not create a XamlPanel.xaml.cs file!
5. Copy the constructor,  methods,  fields and properties from the OldXamlPanel.xaml.cs file to the XamlPanel.cs file.
6. Create a new private field in XamlPanel.cs like

   private XamlPanelInnards InnerControl;

7. Now we modify the constructor,  so that it does something like this:

   public XamlPanel() {
      InnerControl = new XamlPanelInnards();
      Content = InnerControl;
      ... remainder of the constructor ...
   }

8. Most likely you’ll have compilation errors in the XamlPanel.cs file because there are a lot of references to public fields that are now in the InnerControl.  You need to track these down,  and replace code that looks like

   TitleTextBlock.Text="Some Title";

   with

   InnerControl.TitleTextBlock.Text="SomeTitle";

9. Any event handler attachments done from the XAML file will fail to work (they’ll trigger an error when you load the application.)  You’ll need to convert

   <Button x:PressMe ... Click="PressMe_OnClick">

   in the XAML file to

   InnerControl.PressMe.Click += PressMe_OnClick

   in the constructor of XamlPanel.

10. UI Elements that are defined in XAML are public,  so there’s a good chance that other classes might expect UI Elements inside the XamlPanel to be accessable.  You’ve got some choices:  (a) make the InnerControl public and point those references to the InnerControl (yuck!),  (b) selectively add properties to XamlPanel to let outside classes access the elements that they need to access,  or (c) rethink the encapsulation so that other class don’t need direct access to the members of XamlPanelInnards.
11. There are a few special methods that are defined in DependencyObject and FrameworkElement that you’ll need to pay attention to.  For instance,  if your class uses FindName to look up elements dynamically,  you need to replace

    FindName("Control"+controlNumber);

    with

    InnerControl.FindName("Control"+controlNumber);

So far this is a refactoring operation:  we’re left with a program that does what it already did,  but is organized differently.  Where can we go from here?

Extending The XamlPanel

At this point,  the XamlPanel is an ordinary UserControl class.  It’s initialization logic is self-sufficient,  so it can inherit (it doesn’t necessarily have to derive from UserControl) and be inherited from quite freely.

If we want to change the behavior of the XamlPanel,  for instance,  we could declare it abstract and leave certain methods (such as event handlers) abstract.  Alternately,  methods could be declared as virtual.

A number of methods exist to customize the appearance of XamlPanel:  since XamlPanel can see the objects inside XamlPanelInnards,  it can change colors,  image sources and text contents.  If you’re interested in adding additional graphical element to the Innards,  the innards can contain an empty StackPanel — children of XamlPanel can Add() something to the StackPanel in their constructors.

Note that you can still include a child XamlPanel inside a control defined in XAML by writing something like

<OURNAMESPACE:SecondXamlPanel x:Name="MyInstance">

you’re free to make XamlPanel and it’s children configurable via the DependencyObject mechanisms.  The one thing that you lose is public access to the graphical element inside the StackPanelInnards:  many developers would think that this increase in encapsulation is a good thing,  but it may involve a change in the way you do things.

Related articles

The community at silverlight.net has pointed me to a few other articles about XAML,  inheritance and configuring Custom XAML controls.

In a lavishly illustrated blog entry,  Amyo Kabir explains how to make a XAML-defined control inherit from a user-defined base class.  It’s the converse of what I’m doing in this article,  but it’s also a powerful technique:  I’m using it right now to implement a number of Steps in a Wizard.

Note that Silverlight has mechanisms for creating Custom Controls:  these are controls that use the DependencyObject mechanism to be configurable via XAML files that include them.  If you’re interested in customizing individual controls rather than customizing subclasses,  this is an option worth exploring.

Conclusion

XAML is a great system for configuring complex objects,  but you can’t inherit from a Silverlight class defined in XAML.  By using a containment relation instead of an inheritance relation,  we can push the XAML-configured class outside of our inheritance hierarchy,  allowing the container class to participate as we desire.  This way we can have both visual UI generation and the software engineering benefits of inheritance.

Last week I was looking at my web server log with the good old tail -f,  and found that several other bloggers had hotlinked the copy of the twitter fail whale that was in my old “What do you do if you catch an exception?” post.  It turns out that my copy of the whale currently ranks #1 in Google Image Search.  It’s not bringing in a vast amount of traffic,  but it seems to be really engaging people,  because Google blog search is finding a new reference to the image just about every day.

I’ve been spending a lot of time developing sites where that’s the whole idea:  to build virtuous circles where people find images,  put them on their sites,  link back to my site,  which attracts more visitors.  Sometimes you can succeed at this without trying,  but making a business out of it is a matter of being lucky consistently.

After that I broke down and joined twitter.  My username on twitter is paul_houle;  Right now it seems like a strange and lonely place,  but I can see some discipline in expressing oneself in 140 characters.  I’ve noticed quite a few characters already:  everything from the very corporate people who tweet in calculated sound bites to people that tweet like /dev/random.  Perhaps I can’t do anything about the “strange” bit,  but perhaps I can about the “lonely” part.  If you like the things that I blog about,  you’re certainly invited to follow me,  and I’m interested in following like minded people.

Introduction

Lately I’ve been working on a web application based on Silverlight 2.  The application uses a traditional web login system based on a cryptographically signed cookie.  In early development,  users logged in on an HTML page,  which would load a Silverlight application on successful login.  Users who didn’t have Silverlight installed would be asked to install it after logging in,  rather than before.

Although it’s (sometimes) possible to determine what plug-ins a user has installed using Javascript,  the methods are dependent on the specific browser and the plug-ins.  We went for a simple and effective method:  make the login form a Silverlight application,  so that users would be prompted to install Silverlight before logging in.

Our solutionn  was to make the Silverlight application a drop-in replacement for the original HTML form.  The Silverlight application controls a hidden HTML form:  when a user hits the “Log In” buttonin the Silverlight application,  the application inserts the appropriate information into the HTML form and submits it.  This article describes the technique in detail.

The HTML Form

The HTML form is straightforward — the main thing that’s funky about it is that all of the controls are invisible,  since we don’t want users to see them or interact with them directly:

[01] <form id="loginForm" method="post" action="">
[02]     <div class="loginError" id="loginError">
[03]        <%= Server.HtmlEncode(errorCondition) %>
[04]     </div>
[05]     <input type="hidden" name="username" id="usernameField"
[06]        value="<%= Server.HtmlEncode(username) %>" />
[07]     <input type="hidden" name="password" id="passwordField"  />
[08] </form>

The CSS file for the form contains the following directive:

[09] .loginError { display:none }

to prevent the error message from being visible on the HTML page.

Executing Javascript In Silverlight 2

A Silverlight 2 application can execute Javascript using the HtmlPage.Window.Eval() method;  HtmlPage.Window is static,  so you can use it anywhere,  so long as you’re running in the UI thread.  Our simple application doesn’t do communication and doesn’t launch new threads,  so we don’t need to worry about threads.  We add a simple wrapper method to help the rest of the code flow off the tips of our fingers

[10] using System.Windows.Browser
[11] ...
[12] namespace MyApplication {
[13] public partial class Page : UserControl {
[14]      ...
[15]        Object JsEval(string jsCode) {
[16]            return HtmlPage.Window.Eval(jsCode);
[17]        }

Note that Visual Studio doesn’t put the using in by default,  so you’ll need to add it.  The application is really simple,   with just two event handlers and a little XAML to define the interface,  so it’s all in a single class,  the Page.xaml and Page.xaml.cs files created when I made the project in VIsual Studio.

Note that JsEval returns an Object,  so you can look at the return value of a javascript evaluation.  Numbers are returned as doubles and strings are returned as strings,  which can be quite useful.  References to HTML elements are returned as instances of the HtmlElement class.  HtmlElement has some useful methods,  such as GetAttribute() and SetAttribute(),  but I’ve found that I get more reliable results by writing snippets of Javascript code.

Finding HTML Elements

One practical is problem is how to find the HTML Elements on the page that you’d like to work with.  I’ve been spoiled by the $() function in Prototype and JQuery,  so I like to access HTML elements by id.  There isn’t a standard method to do this in all browser,  so I slipped the following snippet of Javascript into the document:

[18]    function returnObjById(id) {
[19]        if (document.getElementById)
[20]            var returnVar = document.getElementById(id);
[21]        else if (document.all)
[22]            var returnVar = document.all[id];
[23]        else if (document.layers)
[24]            var returnVar = document.layers[id];
[25]        return returnVar;
[26]    }

(code snippet courtesy of NetLobo)

I wrote a few convenience methods in C# inside my Page class:

[27]   String IdFetchScript(string elementId) {
[28]        return String.Format("returnObjById('{0}')", elementId);
[29]   }
[30]
[31]   HtmlElement FetchHtmlElement(string elementId) {
[32]        return (HtmlElement)JsEval(IdFetchScript(elementId));
[33]   }

Manipulating HTML Elements

At this point you can do anything that can be done in Javascript.  That said,  all I need is a few methods to get information in and out of the form:

[34]       string GetTextInElement(string elementId) {
[35]           HtmlElement e = FetchHtmlElement(elementId);
[36]           if (e == null)
[37]               return "";
[38]
[39]           return (string)JsEval(IdFetchScript(elementId) + ".innerHTML");
[40]       }
[41]
[42]       void Set(string fieldId, string value) {
[43]            HtmlElement e = FetchHtmlElement(fieldId);
[44]            e.SetAttribute("value", value);
[45]       }
[46]
[47]       string GetFormFieldValue(string fieldId) {
[48]            return (string) JsEval(IdFetchScript(fieldId)+".value");
[49]       }
[50]
[51]       void SubmitForm(string formId) {
[52]            JsEval(IdFetchScript(formId) + ".submit()");
[53]       }

Isolating the Javascript into a set of helper methods helps make the code maintainable:  these methods are usable by a C#er who isn’t a Javascript expert — if we discover problems with cross-browser compatibility,  we can fix them in a single place.

Putting it all together

A little bit of code in the constructor loads form information into the application:

[54]        public Page() {
[55]            ...
[56]            LoginButton.Click += LoginButton_Click;
[57]            UsernameInput.Text = GetFormFieldValue("usernameField");
[58]            ErrorMessage.Text = GetTextInElement("loginError");
[59]         }

The LoginButton_Click event handler populates the invisible HTML form and submits it:

[60]      void LoginButton_Click(object sender, RoutedEventArgs e) {
[61]           SetFormFieldValue("usernameField", UsernameInput.Text);
[62]           SetFormFieldValue("passwordField", PasswordInput.Password);
[63]           SubmitForm("loginForm");

[64]       }

Conclusion

Although Silverlight 2 is capable of direct http communication with a web server,  sometimes it’s convenient for a Silverlight application to directly manipulate HTML forms.   This article presents sample source code that simplifies that task.

P.S. A commenter on the Silverlight.net forums pointed me to another article by Tim Heuer that describes alternate methods for manipulating the DOM and calling Javascript functions.

(Thanks skippy for the remote control image.)

I program in PHP a lot,  but I’ve avoided using autoloaders,  except when I’ve been working in frameworks,  such as symfony,   that include an autoloader.  Last month I started working on a system that’s designed to be part of a software product line:  many scripts,  for instance,  are going to need to deserialize objects that didn’t exist when the script was written:  autoloading went from a convenience to a necessity.

The majority of autoloaders use a fixed mapping between class names and PHP file names.  Although that’s fine if you obey a strict “one class,  one file” policy,  that’s a policy that I don’t follow 100% of the time.  An additional problem is that today’s PHP applications often reuse code from multiple frameworks and libraries that use different naming conventions:  often applications end up registering multiple autoloaders.  I was looking for an autoloader that “just works” with a minimum of convention and configuration — and I found that in a recent autoloader developed by A.J. Brown.

After presenting the way that I integrated Brown’s autoloader into my in-house frameowrk,  this article considering the growing controversy over require(),  require_once() and autoloading performance:  to make a long story short,  people are experiencing very different results in different environments,  and the growing popularity of autoloading is going to lead to changes in PHP and the ecosystem around it.

History:  PHP 4 And The Bad Old Days

In the past,  PHP programmers have included class definitions in their programs with the following four built-in functions:

• include
• require
• include_once
• require_once

The difference between the include and require functions is that execution of a program will continue if a call to include fails and will result in an error if a call to require fails.  require_ and require_once are reccomended for general use,  since you’d probably rather have an application fail if libraries are missing rather than barrel on with unpredictable results.  (Particularly if the missing library is responsible for authentication.)

If you write

01 require "filename.php";

PHP will scan the PHP include_path for a directory that contains a file called “filename.php”;  it then executes the content of “filename.php” right where the function is called.  You can do some pretty funky things this way,  for instance,  you can write

02 for (int i=0;i<10;$i++) {
03    require "template-$i.php";
04 }

to cause the sequential execution of a  namset of PHP files named “template-0.php” through “template-9.php.”  A required file has access to local variables in the scope that require is called,  so require is particularly useful for web templating and situations that require dynamic dispatch (when you compute the filename.)  A cool,  but slightly obscure feature,  is that an included file can return a value.  If an source file,  say “compute-value.php” uses the return statement,

05 return $some_value;

the value $some_value will be return by require:

06 $value=require "compute-value.php";

These features can be used to create an MVC-like framework where views and controllers are implemented as source files rather than objects.

require isn’t so appropriate,  however,  when you’re requiring a file that contains class definitions.  Imagine we have a hiearchy of classes like Entity -> Picture -> PictureOfACar,PictureOfAnAnimal.  It’s quite tempting for PictureofACar.php and PictureofAnAnimal.php to both

07 require "Picture.php";

this works fine if an application only uses PictureOfACar.php and requires it once by writing

08 require "PictureOfACar.php";

It fails,  however,  if an application requires both PictureOfACar and PictureOfAnAnimal since PHP only allows a class to be defined once.

require_once neatly solves this problem by keeping a list of files that have been required and doing nothing if a file has already been required.  You can use require_once in any place where you’d like to guarantee that a class is available,  and expect that things “just work”

__autoload

Well,  things don’t always “just work”.  Although large PHP applications can be maintained with require_once,  it becomes an increasing burden to keep track of require files as applications get larger.  require_once also breaks down once frameworks start to dynamically instantiate classes that are specified in configuration files.  The developers of PHP found a creative solution in the __autoload function,  a “magic” function that you can define.  __autoload($class_name) gets called whenever a PHP references an undefined class.  A very simple __autoload implementation can work well:  for instance,  the PHP manual page for __autoload has the following code snippet:

09 function _autoload($class_name) {
10    require_once $class_name . '.php';
11 }

If you write

12 $instance=new MyUndefinedClass();

this autoloader will search the PHP include path for “MyUndefinedClass.php.”  (A real autoloader should be a little more complex than this:  the above autoloader could be persuaded to load from an unsafe filename if user input is used to instantiate a class dynamically,  i.e.

13 $instance=new $derived_class_name();

Static autoloading and autoloader proliferation

Unlike Java,  PHP does not have a standard to relate source file names with class names.  Some PHP developers imitate the Java convention to define one file per class and name their files something like

ClassName.php,  or
ClassName.class.php

A typical project that uses code from several sources will probably have sections that are written with different conventions  For instance,  the Zend framework turns “_” into “/” when it creates paths,  so the definition of “Zend_Loader” would be found underneath “Zend/Loader.php.”

A single autoloader could try a few different conventions,  but the answer that’s become most widespread is for each PHP framework or library to contain it’s own autoloader.  PHP 5.2 introduced the spl_register_autoload() function to replace __autoload().  spl_register_autoload() allows us to register multiple autoloaders,  instead of just one.  This is ugly,  but it works.

One Class Per File?

A final critique of static autoloading is that it’s not universally held that “one class one file” is the best practice for PHP development.  One of the advantages of OO scripting languages such as PHP and Python is that you can start with a simple procedural script and gradually evolve it into an OO program by gradual refactoring.  A convention that requires to developers to create a new file for each class tends to:

1. Discourage developers from creating classes
2. Discourage developers from renaming classes
3. Discourage developers from deleting classes

These can cumulatively lead programmers to make decisions based on what’s convenient to do with their development tools,  not based on what’s good for the software in the long term.  These considerations need to be balanced against:

1. The ease of finding classes when they are organized “once class per file”,
2. The difficulty of navigating huge source code files that contain a large number of classes,  and
3. Toolset simplification and support.

The last of these is particularly important when we compare PHP with Java.  Since the Java compiler enforces a particular convention,  that convention is supported by Java IDE’s.  The problems that I mention above are greatly reduced if you use an IDE such as Eclipse,  which is smart enough to rename files when you rename a class.  PHP developers don’t benefit from IDEs that are so advanced — it’s much more difficult for IDE’s to understand a dynamic language.  Java also supports inner classes,  which allow captive classes (that are only accessed from within an enclosing class) to be defined inside the same file as the enclosing class.  Forcing captive classes to be defined in separate files can cause a bewildering number of files to appear,  which,  in turn,  can discourage developers from using captive classes — and that can lead to big mistakes.

Dynamic Autoloading

A. J. Brown has developed an autoloader that uses PHP’s tokenizer() to search a directory full of PHP files,  search the files for classes,  and create a mapping from class names to php source files.  tokenizer() is a remarkable metaprogramming facility that makes it easy to write PHP programs that interpret PHP source.  In 298 lines of code,  Brown defines three classes.  To make his autoloader fit into my in-house framework,  I copied his classes into two files:

• lib/nails_core/autoloader.php: ClassFileMap, ClassFileMapAutoloader
• lib/nails_core/autoloader_initialize.php: ClassFileMapFactory

I’m concerned about the overhead of repeatedly traversing PHP library directories and parsing the files,  so I run the following program to create the ClassFileMap,  serialize it,  and store it in a file:

bin/create_class_map.php:
14 <?php
15
16 $SUPRESS_AUTOLOAD=true;
17 require_once(dirname(__FILE__)."/../_config.php");
18 require_once "nails_core/autoloader_initialize.php";
19 $lib_class_map = ClassFileMapFactory::generate($APP_BASE."/lib");
20 $_autoloader = new ClassFileMapAutoloader();
21 $_autoloader->addClassFileMap($lib_class_map);
22 $data=serialize($_autoloader);
23 file_put_contents("$APP_BASE/var/classmap.ser",$data);

Note that I’m serializing the ClassFileMapAutoloader rather than the ClassFileMap,  since I’d like to have the option of specifying more than one search directory.  To follow the “convention over configuration” philosophy,  a future version will probable traverse all of the directories in the php_include_path.

All of the PHP pages,  controllers and command-line scripts in my framework have the line

24 require_once(dirname(__FILE__)."/../_config.php");

which includes a file that is responsible for configuring the application and the PHP environment.   I added a bit of code to the _config.php to support the autoloader:

_config.php:
25 <?php
26 $APP_BASE = "/where/app/is/in/the/filesystem";
   ...
27 if (!isset($SUPPRESS_AUTOLOADER)) {
28    require_once "nails_core/autoloader.php";
29    $_autoloader=unserialize(file_get_contents($APP_BASE."/var/classmap.ser"));
30    $_autoloader->registerAutoload();
31 };

Pretty simple.

Autoloading And Performance

Although there’s plenty of controversy about issues of software maintainability,  I’ve learned the hard way that it’s hard to make blanket statements about performance — results can differ based on your workload and the exact environment you’re working in.  Although Brown makes the statement that “We do add a slight overhead to the application,”  many programmers are discovering that autoloading improves performance over require_once:

Zend_Loader Performance Analysis
Autoloading Classes To Reduce CPU Usage

There seem to be two issues here:  first of all,  most systems that use require_once are going to err on the side of including more files than they need rather than fewer — it’s better to make a system slower and bloated than to make it incorrect.  A system that uses autoloading will spend less time loading classes,  and,  just as important,  less memory storing them.  Second,  PHP programmers appear to be experience variable results with require() and require_once():

Wikia Developer Finds require_once() Slower Than require()
Another Developer Finds Little Difference
Yet Another Developer Finds It Depends On His Cache Configuration
Rumor has it,  PHP 5.3 improves require_once() performance

One major issues is that require_once() calls the realpath() C function,  which in turn calls the lstat() system call.  The cost of system calls can vary quite radically on different operating systems and even different filesystems.  The use of an opcode cache such as XCache or APC can also change the situation.

It appears that current opcode caches (as of Jan 2008) don’t efficiently support autoloading:

Mike Willbanks Experience Slowdown With Zend_Loader
APC Developer States That Autoloading is Incompatible With Cacheing
Rambling Discussion of the state of autoloading with XCache

the issue is that they don’t,  at compile time,  know what files are going be required by the application.  Opcode caches also reduce the overhead of loading superfluous classes,  so they don’t get the benefits experienced with plain PHP.

It all reminds me of the situation with synchronized in Java.  In early implementations of Java,  synchronized method calls had an execution time nearly ten times longer than ordinary message calls.  Many developers designed systems (such as the Swing windowing toolkit) around this performance problem.  Modern VM’s have greatly accelerated the synchronization mechanism and can often optimize superfluous synchronizations away — so the performance advice of a decade ago is bunk.

Language such as Java are able to treat individual classes as compilation units:  and I’d imagine that,  with certain restrictions,  a PHP bytecode cache should be able to do just that.  This may involve some changes in the implementation of PHP.

Conclusion

Autoloading is an increasingly popular practice among PHP developers.  Autoloading improves development productivity in two ways:

1. It frees developers from thinking about loading the source files needed by an application,  and
2. It enables dynamic dispatch,  situations where a script doesn’t know about all the classes it will interact with when it’s written

Since PHP allows developers to create their own autoloaders,  a number of autoloaders exist.  Many frameworks,  such as the Zend Framework,  symfony,  and CodeIgniter,  come with autoloaders — as a result,  some PHP applications might contain more than one autoloader.  Most autoloaders require that classes be stored in files with specific names,  but Brown’s autoloader can scan directory trees to automatically  locate PHP classes and map them to filenames.  Eliminating the need for both convention and configuration,  I think it’s a significant advance:  in many cases I think it could replace the proliferation of autoloaders that we’re seeing today.

You’ll hear very different stories about the performance of autoload,  require_once() and other class loading mechanisms from different people.  The precise workload,  operating system,  PHP version,  and the use of an opcode cache appear to be important factors.  Widespread use of autoloading will probably result in optimization of autoloading throughout the PHP ecosystem.