Archive

Ozone Templating

Published
by
Victor Nicollet
on October 18, 2011
in Functional
. 0 Comments

There have been recurring requests about an in-depth explanation of how Ozone — our in-house OCaml web framework — handles HTML templates. So, here it is.

A template is usually understood by everyone to be « HTML with holes » that is filled using values from the application itself. It is, in a sense, a DSL that is restricted to describing how HTML should be built.

Here is an example of template Ozone could use, stored in file users.htm :

<h1>{t:users.title}</h1>
<ul class="userlist">
  {{list:
    <li id="{v:id}">
      <img src="{v:img}"/>
      <a href="{v:url}">{v:name}</a>
    </li>
  }}
</ul>

<script type="text/coffeescript" params="save_url">
list = @$.find 'ul'

save = =>
  ids = [];
  list.children('li').each ->
    ids.push $(@).attr 'id'
  @ajax save_url, ids

list.children('li').sortable
  change: save
</script>

<style type="less">
.userlist {
  list-style-type: none;
  li img {
    float: left;
    margin-right: 5px;
    width: 50px;
    height: 50px;
  }
}
</style>  

The template for a sortable list of users contains three things:

  • A piece of HTML, which is the actual « HTML with holes » to be filled later. The holes are marked in orange.
  • A piece of CoffeeScript, which will be extracted from the template file, compiled to javascript and appended to a site-wide javascript file. It will be replaced, in the template, by a hole that will call the extracted javascript with additional parameters provided by the application (in orange).
  • A piece of LESS CSS, which is compiled to CSS and appended to a site-wide CSS file.

These are not sections — they can appear in any order as long as the elements and attributes are respected so the pre-build tool can identify and extract the CoffeeScript and CSS bits.

Let’s examine each of them in order.

The HTML Template

This is the meat of the template. In order to improve application performance, loading the templates is a multi-step operation that involves intermediary storage formats.

The first step consists in reading in all the necessary templates, parsing them to determine that no variables are undefined, and storing them as a JSON blog in the underlying CouchDB database. This is a manually triggered operation that happens whenever we modify the templates (it’s part of our deployment procedure). This step may also involve a bit of cleanup, such as removing semantically irrelevant spaces from the HTML (this cannot be done earlier, because some templates are plaintext instead of HTML, and only the application knows which is which).

The second step happens whenever a new instance of our application begins — maybe it died and needed to restart, maybe Apache decided it needed another worker process to handle a surplus of request, or maybe we added a new server to our web farm. The startup process of our application server does not read anything from the disk — instead, it will read in all the template data from the database, along with all the other bits of configuration: internationalization strings, third party API keys, feature branch triggers, and so on. Then, it will compile every template down to optimized closure-based opcodes for a hole-filling virtual machine.

The third step happens whenever a bit of HTML needs to be rendered. The application provides the hole-filling virtual machine with a data object and a « writing stream » which is either the HTTP request stream or a JSON serializer stream, depending on whether the request is normal HTTP or AJAX. This is an extremely fast operation where no parsing or checks are performed.

On the application side, loading a template involves three things:

  • Declaring the type of the data object expected by the template.
  • Declaring the source file from the template (as a function of the language).
  • Declaring the hole-to-value mapping  to be used.

Here’s that loading code for the above template file:

module User = Loader.Html(struct
  type t = <
    id   : Id.t ;
    url  : string ;
    img  : string option ;
    name : string
  > ;;
  let source  _ = "users/list"
  let mapping _ = [
    "id",   Mk.esc (fun x -> Id.to_string (x # id)) ;
    "url",  Mk.esc (fun x -> x # url) ;
    "img",  Mk.esc (fun x -> BatOption.default img404 (x # img)) ;
    "name", Mk.esc (fun x -> x # name)
  ]
end)

module UserList = Loader.Html(struct
  type t = <
    users : User.t list
  > ;;
  let source  _ = "users"
  let mapping lang = [
    "list", Mk.list (fun x -> x # users) (User.template lang)
  ]
end)

One view is defined and loaded for every independent piece of HTML in the template. Here, there is an User view which represents the list item for a single user, repeated zero, one or more times ; and there is the UserList view representing the wrapper in which those list items will be placed.

The {v:foobar} syntax defines a variable hole. The corresponding view MUST define a mapping for that variable, or an error will occur at deployment time.

The {{foobar: }} syntax is a variant: in addition to declaring a variable hole, it also defines such a sub-view, which can be loaded using template/foobar as the path.

The {t:foobar} syntax defines a translation hole. The template engine will automatically load the corresponding term from the internationalization dictionary used to render the template.

The Mk.esc and Mk.list are binding instructions which are used to compile the template to a virtual machine. The common binding instructions are:

  • Mk.esc f applies f to the data object, which returns a string. That string is then HTML-escaped and output.
  • Mk.str f is the same as above, but the string is not HTML-escaped.
  • Mk.i18n f is the same as above, but the string is translated as an internationalization term.
  • Mk.list f t applies f to the data object, which returns a list of data objects compatible with template t. That template is then used to render those data objects in order.
  • Mk.list_or f t e is the same as above, but if the returned list is empty, it instead uses template e to draw a « list is empty » message.
  • Mk.sub f t applies f to the data object, which returns a single object compatible with template t. That template is then used to render the object.
  • Mk.sub_or f t e is the same as above, but f returns an optional type. If it is missing, then template e is used to render an « object is missing » message.
  • Mk.text f provides f with the current writing stream and internationalization object, so that it may directly write HTML to the output. This is how most rendering helpers such as « render a currency amount » are used.
  • Mk.box f is the same as above, but the writing stream supports the addition of arbitrary javascript code to be executed by the client as part of rendering the template. This is how javascript-dependent rendering helpers such as « render a datepicker » are used.

The data type is defined in the view itself, either explicitly (as I did above for the sake of clarity) or by using an existing type from your application — if the application already had an user module with the appropriate data type, I could have used that type instead.

By specifying views in this way, the data required to render a template is made available to the compiler for type-checking, and missing bindings are detected during deployment (usually to a local test server). This has made template-related errors exceedingly rare — once the HTML is done, it becomes extremely hard to use it wrong.

Although this feature is not currently in use, the virtual machine semantics also allow compiling it down to JavaScript. This would allow us to send the rendering code to the client as a one-time cost, and send a much smaller data package through AJAX whenever something new needs to be rendered.

The CoffeeScript Layer

We use CoffeeScript because it’s more elegant, shorter, and includes a compiling-to-javascript step that lets us detect syntax errors at deployment time. Yes, compile- and deployment-time are my favorite buzzwords, because I enjoy the feeling of safety that they bring.

As mentioned above, the actual CoffeeScript is removed from the template in a pre-processing step, and replaced with a hole that says « call JavaScript function #33 now » that happens to define a list of parameters matching the params attribute of the original script element.

So, starting with the script element from the example above:

<script type="text/coffeescript" params="save_url">
list = @$.find 'ul'

save = =>
  ids = [];
  list.children('li').each ->
    ids.push $(@).attr 'id'
  @ajax save_url, ids

list.children('li').sortable
  change: save
</script>

If this is the 33rd script tag encountered by the preprocessor, then it would append the following to the complete CoffeeScript file:

@j33 = (save_url) ->
  list = @$.find 'ul'

  save = =>
    ids = [];
    list.children('li').each ->
      ids.push $(@).attr 'id'
    @ajax save_url, ids

  list.children('li').sortable
    change: save

And it would be replaced in the template file with this:

{j:j33:save_url}

This syntax (which can be used manually, although it should be avoided) is a javascript hole, it runs the specified function and provides by-name values for the arguments. The parser would notice that we are declaring an HTML view instead of a JS/HTML view and complain about it, so we would have to go back and re-define it:

module UserList = Loader.JsHtml(struct
  type t = <
    users : User.t list ;
    save_url : string
  > ;;
  let source  _ = "users"
  let mapping lang = [
    "list", Mk.list (fun x -> x # users) (User.template lang)
  ]
  let script  _ = [
    "save_url", (fun x -> Json_type.String (x # save_url))
  ]
end)

I have used Loader.JsHtml instead of Loader.Html, and defined a secondary mapping that is specific to JavaScript parameters, and which uses the data object to return JSON values.

How is the JavaScript called? Well, it really depends on how your JavaScript library handles it. On non-AJAX HTTP, Ozone will try to inject all JavaScript calls in a script element at the end of the HTML body. In AJAX mode, Ozone allows you render a template to a JSON object representing both the HTML and the JavaScript together, and it is the responsibility of the code that made the AJAX request to receive that object, place the HTML wherever applicable, and then “run the JavaScript”.

By convention, the JavaScript is called using a client context as itsthis value. The client context is an object which may contain whatever the caller finds interesting to place there, along with a variable named $ which should be a jQuery selection containing the root element of the previously rendered HTML. Hence, @$.find 'ul' would select the list in the rendered HTML, instead of all the lists on the page.

The LESS CSS Layer

This is the least interesting of all three layers. The LESS CSS code is extracted, appended to a single file, and compiled to CSS (which, again, is an useful deployment-time syntax check). The point of this feature is simply to let the designer place element-specific CSS next to the element, instead of having it exist in an external file and cause trouble with asset garbage collection (can I remove this rule or is it still used anywhere?) External files still exist, though, for CSS rules that are not limited to a single template.

Bonus : the triple hash

How do I define some code that should be called when a button is clicked? Defining it directly in the onclick method is ugly, hard to read and does not let the application provide parameters, so what else can I do?

The solution is to use an intermediary global object that happens to be the same for the entire file — a pattern that stores any template-related JS in a global variable named after __FILE__ !

Yes, it is a hack, but it’s a simple and useful one.

The only difference is that __FILE__ is spelled ###.

<button type="button" onclick="###.frobnicate()">{t:frobnicate}</button>

<script type="text/coffeescript" params="message">
###.frobnicate = ->
  alert message
</script> 

Article Image © gdbg12 — Flickr

Let’s Whine About Google Dart

Published
by
Victor Nicollet
on October 12, 2011
in Functional
. 30 Comments

What’s wrong about 17259 lines of code ? asks Andrea Giammarchi, following the publication of a gist that shows an 18-line Hello-World application written in Dart, the new Google-sponsored browser-based language, and the corresponding 17259 lines of JavaScript that the Dart source code would be compiled to.

Yes, 17259 lines of code is quite terrifying, and reading through the code does make one ponder what those engineers at Google were smoking and how they can ever expect such a language to overtake JavaScript — or even manage to be used in the first place.

And then, there’s a loud WHOOSH: the sound of a point flying so high over the collective heads of Dart critiques that it will probably collide with some garbage in low earth orbit.

The point is that this is version 0.01 of a language designed for optimization through static analysis.

I’ll be the first to admit that there is no way for a Hello-World application to execute all those 17259 lines. This is known as dead code: pieces of functionality which might be useful to some applications but not to others, which is included because it’s easier for the developer, but which will never run.

I can understand why Andrea is upset. Dead code is a big no-no in JavaScript, because it has to be downloaded and parsed by every user, which costs bandwidth and slows down everything. No, wait. Let me correct that last statement. Dead code is a big no-no in JavaScript because the JavaScript language makes it impossible to have automatic dead code elimination.

In JavaScript, you can have a global function named foobar which is not even once referenced in the entire code base, and it would still be unsafe to remove it because at some point the code fetches a funcname variable through AJAX and executes window[funcname]() — and it just so happens that the server returns "foobar" on the night of the full moon. In short, there’s no way in hell an automated tool can remove a single line of code from JavaScript without breaking at least one possible program. That’s just the way JavaScript is — objects are key-value containers with string keys.

Of course, you could decide to follow rules that prevent such things from happening. There’s at least one convention, for instance, which is used by minifiers to try and be a little more than glorified whitespace removers: variable renaming. If you have a local variable in JavaScript, you can rename it and all its occurences and the change will never be visible outside the scope it was defined in because the variable itself is not visible outside. This lets you rename aQuiteLongVariableName to g, which makes your code lighter. And it breaks because one of your function uses eval on an arbitrary string provided by the server and which references aQuiteLongVariableName. So, the convention is « do not use eval » but it’s still a convention, not a language specification, so it has to be opt-in and clearly document its requirements.

Dart was designed not to have these issues, so it does not matter if version 0.01 of the Dart-to-JavaScript compiler fails to perform dead code removal: it can be implemented, and Google engineers would indeed be fools not to implement it before the 1.0 release.

There are also questions to be asked about the actual contents of those 17259 lines — when they will be used, will it make sense?

One of the first things that I notice is, as Andrea mentioned, the various global binding functions such as:

function $bind1_0(fn, thisObj, scope) {
  return function() {
    return fn.call(thisObj, scope);
  }
}

This is actually an extremely important optimization, but not related to speed — it’s about memory. To understand why, look at this code:

var div = document.createElement("div");
var message = "Hello";
div.onclick = function(){
  alert (message)
};

The anonymous function here is a closure: it must carry the variable message with it in order to access it when it is called. In any sane language, the interpreter would store a reference to that variable in the closure, and be done with it. JavaScript cannot (again, because of eval) so it has to store the entire scope that the function was defined in, which includes both message and div. In some versions of IE, having such a circular reference between a DOM element and a JavaScript value creates a memory leak which leads to massive performance degradation, but even in better browsers than IE, the function will keep this div alive for longer than is really necessary, thus consuming memory for nothing.

Dart has the ability to perform this scope analysis and determine that only the message needs to be included. The truckload of bind functions help implement this by utterly eliminating the JavaScript closure:

function onclick(message) {
  alert(message);
}

var div = document.createElement("div");
var message = "Hello";
div.onclick = $bind1_0(onclick,div,message);

Another critic from Andrea was the massive amount of wrappers around elementary functions, such as setting an array element to a value or adding two values together, which should bring JavaScript-from-Dart programs to a screeching halt becuse of all the involved overhead.

They won’t. Trust me. This isn’t the first time I have seen such wrappers, and I know what they are and why they exist. They are generic adapters — fallback operations to be used when the static analysis step cannot determine precisely the types of the objects involved.

Quick. Translate the following code from Dart to JavaScript by hand in an optimal manner:

swap(a,i,j) {
  var t = a[i];
  a[i] = a[j];
  a[j] = t;
}

Chances are, you answered something like this:

function swap(a,i,j) {
  var t = a[i];
  a[i] = a[j];
  a[j] = t;
}

You would be wrong. You are under the mistaken impression that, because it uses the []-syntax, the Dart function works with arrays when in fact it works with any object that defines that access operator.

So, on your second attempt, you would answer something like this:

function swap(a,i,j) {
  var t = ugly_getter.apply(a,i);
  ugly_setter.apply(a,i,ugly_getter.apply(a,j));
  ugly_setter.apply(a,j,t);
}

And you would be wrong again. The key property of Dart (as well as other languages which encounter the same problem — OCaml, C#, C++, Java… anything with generic polymorphism actually) is that it allows static analysis. Static analysis lets you determine what the types of those variables might be. Is the swap function ever called on something other than an array? Then only define version one. Is it called on many things, but most often arrays? Define both functions, and use the specific array-compatible one whenever you are certain an array will be passed. Is it never called? Remove it…

This kind of analysis is reasonably simple to perform, and has the benefit of being able to create both highly-optimized code for primitive types and short generic code for abstract types. And you can even help the compiler by annotating types.

Again, it does not matter whether Dart 0.0.1 actually performs these optimizations. What matters is that they are both possible and easy given the language design, and I expect them to be present in release 1.0

I am by no means a Google zealot or secret Dart admirer. In fact, from what I have seen so far, I would sooner loathe Dart than admire it — a bastard type-checking that relies on warnings? A bland java-like syntax for brace weenies? No actual support for immutable data structures? Blech. Give me JavaScript CoffeeScript anyday. I’ll switch to Dart when it takes over the world.

But the current crapstorm is just ridiculous. Come on, the guys at Google are pushing out a 0.0.1 proof-of-concept and you’re complaining that their optimizer isn’t acceptable? Please. I’m not even sure there’s an optimizer yet. From the language specs, it’s fairly obvious that many optimization avenues unavailable to JavaScript will be available to Dart, the only question is whether release 1.0 will have them or not. Wait and see — criticizing the optimization of a 0.0.1 compiler is just silly.

Article Image © Erich Ferdinantd — Flickr

No Personally Identifiable Information

Published
by
Victor Nicollet
on October 12, 2011
in People
. 0 Comments

With our hardware advances alone — computers can extract, store and analyze significantly greater amounts of data than a few years ago — it becomes easy for those who have data to actually use that data. And the software has improved, too.

There are many reasons to feel, if not unhappy, at least slightly uneasy about the direction our information society is taking.

Really? What could happen to me if my private information was used by people or organizations?

For one, many people value privacy on principle. I feel that it is my unalienable right to hide information from others as long as that information does not harm them, even if making that information public would not cause me any discomfort or trouble. Recently, Spotify started auto-publishing what users listened to directly on Facebook. Even if telling your friends what music you are listening to hardly qualifies as discomfort or trouble, the fact that Spotify and Facebook took the decision to share that information is outrageous. That is my decision, even if the subject is of minor importance in the grand scheme of things.

Grow a spine. Who cares if you listen to Nickelback? Are you an angsty teenager?

It’s not only about listening to Nickelback. There’s also the oppressed, the minorities, those in a position of weakness who would suffer greatly if their church group knew they were gay, if their employer knew they were looking for another job, if their government knew they were printing pamphlets, if their friends knew they voted for another party…

The Electronic Frontier Foundation has written again and again about the implications of privacy invasions. A simple cell phone that records your location information could cause a lot of trouble:

  • Did you go to an anti-war rally on Tuesday?
  • A small meeting to plan the rally the week before?
  • At the house of one “Bob Jackson”?
  • Did you walk into an abortion clinic?
  • Did you see an AIDS counselor?
  • Have you been checking into a motel at lunchtimes?
  • Why was your secretary with you?
  • Did you skip lunch to pitch a new invention to a VC? Which one?
  • Were you the person who anonymously tipped off safety regulators about the rusty machines?
  • Did you and your VP for sales meet with ACME Ltd on Monday?
  • Which church do you attend? Which mosque? Which gay bars?
  • Who is my ex-girlfriend going to dinner with?

Then don’t use a smartphone — don’t use tracking technology if you don’t want to be tracked.

Smartphones, I can do without, even though it seems these days most people cannot. But the internet? Not only does every site track what you do on that particular site, but there’s a growing tendency for some companies to track you across multiple unrelated sites — Google and Facebook are only the tip of the iceberg. We are still far from a solution for people to say « do not track me » let alone actually enforcing that solution.

Credit and debt cards follow the same principles — your bank or credit card company knows where your are buying from, and what amounts you are buying. Your phone company knows who you call, when, and for how long. And government agencies keep a lot of information about many things you do.

In isolation, all of that information is not very useful, but once the owners of these files start sharing them, they become a lot more distressing for us.

Distressing? Why?

Below the surface lies our old human habit of appearing to others as we wish to appear, which for most of us involves hiding some elements and sometimes lying about others. We are weak, boring, average, struggling and unhappy, but we wish to appear strong, interesting, exceptional, successful and happy ; and there are few, if any, whom we trust to see our real selves. Maybe the would would be a better place if everyone was fully honest with others — no secrets, no lies, just sincere honesty — but that is not how we are, and uncontrolled publicization of information about ourselves will make many of us unhappy.

But those are faceless corporations sifting through my data with automated tools. Even if they could judge me, I wouldn’t care.

You need health insurance, but the insurance tells you that since you buy medicine far more often than the average citizen — it’s right there on your credit card transaction history — there must be something wrong with your health, so you will need to pay more. And you spend a few hours explaining that the medicine was for an ailing family member, not yourself.

A prospective employer determines that because you did or said something silly back in college, you should not be hired, but never explains why you were rejected.

You are divorcing, and your spouse’s lawyer digs up some innocent information from your cell phone or internet history which, out of context, makes you look extremely bad.

Even faceless organizations can judge you based on information. In fact, they would rather collect and buy as much information as possible about you, because they assume that you would lie about it.

Wait, wait, wait. You’re assuming that my insurance company could find out about my credit card history.

Yes, I am assuming that, and I know it sounds like paranoia. But there are evil people out there who see those huge databases full of tasty personal information and will try to get their hands of them. This has already happened.

Hackers regularly attack web sites and extract personal information from their databases.

It started as a security breach on the PlayStation network and other Sony services that exposed the personal information of 100 million users. From there, it has mushroomed into broader, ongoing security troubles across the Sony empire that have spilled out into the wider world.

Lawyers have used the courts’ power to subpoena ISPs for personal information of potential offenders, without the courts’ consent.

To summarize the staggering chutzpah involved in this case: Stone asked the Court to authorize sending subpoenas to the ISPs. The Court said “not yet.” Stone sent the subpoenas anyway.

Recently, the German government used trojans to extract communication information present on computers.

[...] the German-based Chaos Computer Club announced it had examined a Trojan horse program allegedly spread by government officials to secretly spy on citizens’ Internet travels, e-mail, chat and more. The software, originally intended only to help officials intercept Internet phone calls through legal wiretaps, went far beyond those permissible purposes, the hacker group alleged.

Individuals, corporations, governments, everyone has done it and will probably do it again at some point. Just because something is illegal or forbidden does not mean it will not happen. Nor does it mean that laws cannot be later adapted or extended to allow previously forbidden behavior.

I do not trust groups of humans to act in a responsible and independent manner. If the underlying principles of a technology makes invasions of privacy impossible or very difficult, I will feel safe and secure. If the only guarantee is a promise, however strong or binding it may appear, then I might as well assume that there is no privacy.

What if they guarantee that there is no personally identifiable information collected ?

That is usually a promise — an intentional anonymization process that could be removed at a later point. But even assuming that they are honest and will remain forever honest, « personally identifiable » is hardly a concrete property of information. If you are the only person in your ZIP code born on a specific day, then ZIP code + birth date is a personally identifiable information about you. And indeed, 87% of the US population can be identified using only their ZIP code, birth date and gender.

Your facebook browsing history, never mentions your identity, but I can guess you who you are based on which Facebook profile you visit the most — yours — using a simple frequency analysis algorithm.

The only way to make sure that no personally identifiable data is stored is to make sure that it is deleted.

Article Image © Andrea Roberts — Flickr

On Escaping HTML

Published
by
Victor Nicollet
on October 11, 2011
in Dynamic
. 0 Comments

A common issue with web software is cross-site scripting attacks — the ability for a third party to inject HTML elements into pages displayed to other users, using scripts contained in those elements to capture user cookies or perform operations on their behalf.

The technical challenge in solving this is that whenever data is being output through a HTML page, it should be escaped — any special HTML characters should be turned into their non-special versions in order to be displayed verbatim. This is an ongoing effort: each new page and each new variable on a page involve the same amount of effort to be done.

Of course, the solution would be to decide that escaping string output should be a default behavior that must be explicitly overriden. This does create issues where HTML is escaped when it should not have been, but:

  • These issues cannot be used to perform attacks.
  • They are usually easier to reproduce and consequently to solve.
  • HTML usually comes from template files, which can be handled with a different default.

Indeed, I can guarantee that my software has zero vulnerabilities related to escaped HTML, because I have built into the type system the fact that HTML always comes from templates, and the method that injects variables into templates escapes them. If I try to use a string as if it were HTML, I get a compiler error.

Even without a type system, one can guarantee that the system would rather break at runtime than allow an injection, using the exact same design, with incompatible data structures for templates and strings that blow up when a string is used as a template:

class FilledTemplate {
  function __construct($html) {
    $this->_html = $html;
  }
  function html() {
    return $this->_html;
  }
}

class Template {
  function __construct($file) {
    $this->_template = file_get_contents($file);
  }
  function fill($values) {
    $replace = array();
    $with    = array();
    foreach ($values as $key => $value) {
      $replace[] = '{'.$key.'}';
      if ($value instanceof FilledTemplate) 
        $with[] = $value->html();
      else 
        $with[] = htmlspecialchars($value);
    }
    return new FilledTemplate(
      str_replace($replace,$with,$this->_template)
    );
  } 
}

Obviously, many languages and frameworks use non-escaped string output as the default behavior. This, in my opinion, is pure, broken insanity — I can certainly see that designing a safe way of constructing HTML is harder than just following the «HTML is strings, just use string functions» approach and telling the programmer to «always escape your variables, kid» but I still find it quite irresponsible for self-proclaimed Web Languages to rely on such a primitive and dangerous paradigm. The stupid kind of irresponsible. Yes, PHP, I’m looking at you.

Article Image © Freedom II Andres — Flickr

Pascal’s Triangle

Published
by
Victor Nicollet
on October 7, 2011
in Random
. 2 Comments

Grant Muller writes that Algorithms can Really Beat You:

I stared at the pyramid of numbers scribbled hastily in blue dry erase. The only thing clear to me in that moment was that I wouldn’t have this figured out in five minutes. Or even ten.

“Any number in the pyramid, or in this case tree array, is the sum of the two numbers above it,” the young man continued, “write a function that gets the value of any x, y coordinate in this structure.”

Sitting quietly in the middle of that article was an old friend of mine, Pascal’s Triangle, that I encounter every so often when doing nerdy things with equations.

The first rows in Pascal’s Triangle are 1, 11, 121, 1331 and 14641 — the most observant will notice that those are the values of 110, 111, 112, 113 and 114. In fact, if you consider the values of the sixth row, 1-5-10-10-5-1, they correspond to the number 161051, which is 115.

And the reason for this is the way in which Pascal’s Triangle is constructed: take a row, duplicate it, shift one copy to the left by one, and add them together.

  1 1           1 2 1         1 3 3 1
+   1 1       +   1 2 1     +   1 3 3 1
= 1 2 1       = 1 3 3 1     = 1 4 6 4 1

This is the same as saying that «any number is the sum of the numbers above it», or T(x,y) = T(x-1,y-1) + T(x,y-1). As an amusing side-effect of this construction method, the sum of all numbers in a given row is always a power of two — by adding two copies of the previous row together, you are multiplying that sum by two every time. Remember this tidbit, it will come in handy later on.

What does this have to do with the powers of 11 ? Well, to multiply by 11, you would multiply by 10 (which is easier: shift all the digits to the left) and add the original number. So, multiplication by 11 works in exactly the same way as the Pascal’s Triangle. Which is why the numbers are the same.

Another place where Pascal’s Triangle appears is binomial coefficients:

(a + b)2 = 1 a2 + 2 ab + 1 b2
(a + b)3 = 1 a3 + 3 a2b + 3 ab2 + 1 b3
(a + b)4 = 1 a4 + 4 a3b + 6 a2b2 + 4 ab3 + 1 b4

To expand (a + b)n, all you need to know is the values on row n of the Triangle. And the reason for this is exactly the same as the one for 11 (and in fact, 11 is a special case of the binomial formula where a=10 and b=1).

But that’s not all. Let’s discuss something entirely different for a second — the fun thing about math is precisely that you can start exploring entirely different venues and end up where you started anyway. So, suppose you have a N-bit integer, and you wish to count how many such integers have exactly M bits set to 1. This is number is known as «N choose M», and is fairly frequently found in mathematics. How do you do determine that number?

One way, the combinatorics approach, is to determine an algorithm that generates such a value, and count how many independent possible choices that algorithm had. My algorithm in this situation is «pick one bit at random, set it to 1, repeat M times»

For the first step, there are N possible bits to choose from.

For the next step, there are N-1 possible bits, and so on until only N-M bits are left. So, there are N × (N-1) × (N-2) × (N -3) … (N-M+1) possible runs for this algorithm. This can be written more concisely using factorials : N! / (N-M)!

But wait! This algorithm actually generates each set of bits several times: once for every possible order of selection of those bits — which is known to be M! for a set of M bits. So, the actual number of distinct runs of my algorithm is N! / ( M! × (N-M)! )

This is something we learn in high school in France, or at least we did back when I was still in high school.

The other way to determine this number is to solve that problem recursively: let’s say that there are C(N,M) different N-bit integer with M bits set to 1. For each such integer one of two possible cases happens:

  • It consists of a 0 followed by an (N-1)-bit integer with M bits set to 1. There are C(N-1,M) such integers.
  • It consists of a 1 followed by an (N-1)-bit integer with (M-1) bits set to1. There are C(N-1,M-1) such integers.

So, recursively, C(N,M) = C(N-1,M) + (N-1,M-1), with the edge cases being C(N,N) = C(N,0) = 1 (there’s only one integer with all-zeroes, and only one integer with all-ones). This is the same formula as Pascal’s Triangle !

T(x,y) = C(N,M) where y = N and x = M

So, here’s the pseudocode for a function that correctly computes T(x,y) far faster than the recursive version suggested by Grant, by using the factorial-based definition we found for C(N,M) :

function T(x,y) {
  var num = 1, denom = 1, start = y-x;
  for (i = 1; i <= x; ++i) {
    num = num * (start + i);
    denom = denom * i;
  }
  return num / denom;
}

Last question: what is C(N,0) + C(N,1) + … C(N,N) ? It is merely counting the number of N-bit integers that have any combination of bits set to 1. We know there are 2N integers. Remember when I told you the sum of the elements in a row of the Triangle was a power of two?

Yes, maths are fun like that.

Article Image © PhilosophyGeek — Flickr

Functional Programming

Published
by
Victor Nicollet
on October 6, 2011
in Functional
. 2 Comments

Yesterday evening, I was present at Paris Hackers, a meetup for Hacker News enthusiasts — and a «hacker» in this context is not someone who breaks into software systems, but someone who is passionate beyond words about how software works. But the definition is vague, and that vagueness is part of my surprise.

We had a little chat on the topic of recent buzzwords — concepts that people were interested in, but not everyone understood. One of them was Functional Programming. The speaker asked who knew enough about it to explain to the others, and I naturally raised my hand: I was taught functional programming formally, I taught it myself, I implemented a functional programming language, and I am using functional programming professionally on a daily basis.

My surprise was that I was the only one. I had sort of assumed that a majority of «hackers» would know what functional programming is. I will have to revise that definition.

« Having Functions »

Functional programming itself has a definition problem: depending on whom you ask, you can get two different definitions on functional programming. One definition is what I would call pure functional programming, and the other is better summarized as « having functions »

Of course all languages have something they call «functions» but I strongly believe that there is a list of minimum requirements before you are allowed to say that.

  1. You should be able to define a FOOBAR anywhere. At global scope. Inside a class. Inside another function. Inside an expression. It can be an anonymous FOOBAR, or it can be given a name, depending on the situation.
  2. You should be able to store a FOOBAR in a variable, pass it as an argument to a function, and return it from a function. If your language is strongly typed, it should have an easily described type as well.

Replace FOOBAR with «integer» or «string» and you will notice that without these requirements one can hardly say a language «supports integers» or «supports strings» — what if you could not store integers in variables, or write string literals as part of expressions?

These requirements are called «having FOOBARs as first-class citizens» by the way. In C for instance, functions and arrays are second-class citizens, and integers are first-class citizens. In JavaScript, functions are a first-class citizen.

Allowing functions helps make a language a lot more expressive. Let’s think of a quick example: performing an HTTP request and displaying the result in a window. In pseudocode that looks shamefully like JavaScript code, it would look like this:

function display(url) {
  var page = http(url);
  return new Window(page);
}

This function has an obvious limitation: if it takes five seconds to load the data through HTTP, then the program will freeze for five seconds and only then display the window. A better solution would be to make the request asynchronous: a window in a «loading» state is returned immediately, and a background process takes care of the HTTP requests and fills the window with the contents once they have been received.

A clean way of encapsulating this would be to let the http function handle the asynchronous behavior. The calling code would only need to provide a description of what needs to be done once the contents have been received. There are two ways of doing this in an object-oriented world.

Object-oriented solution #1: inherit from an http request class.

class GetPageRequest extends HttpRequest {

  // We need to know what window to put the contents in
  function GetPage(window,url) {
    super(url);
    this.window = window;
  } 

  // Override this function to react to the data being received
  function onSuccess(page) {
    this.window.setContents(page);
  }
}

function display(url) {
  var window = new Window(loading);
  var request = new GetPageRequest(window,url);
  request.runAsynchronous();
  return window;
}

Object-oriented solution #2: implement an «HTTP success event handler» interface.

class OnReceivePage implements IHttpRequestSuccessHandler {

  // What window do we need to fill ?
  function OnReceivePage(window) {
    this.window = window;
  }

  // Handle success (as previous example)
  function onSuccess(page) {
    this.window.setContents(page);
  }
}

function display(url) {
  var window = new Window(loading);
  http(url, new OnReceivePage(window));
  return window;
}

Both solutions are quite long, because object-oriented solutions involve a certain amount of syntactic overhead. In both cases, the only code that is actually relevant to our work is the contents of the onSuccess function. What if the language allowed us to define that function directly, and passing it to the HTTP request without any syntactic fuss?

Functional solution #1: local function definition.

function display(url) {
  var window = new Window(loading);
  function onSuccess(page) { window.setContents(page); }
  http(url, onSuccess);
  return window;
}

In fact, why bother with giving the function a name? Its contents are obvious enough, so it would be shorter and cleaner to just passing it to the HTTP request without any name.

Functional solution #2: anonymous function definition, or «lambda»

function display(url) {
  var window = new Window(loading);
  http(url,function(page) { window.setContents(page); });
  return window;
}

The latter example is syntactically correct JavaScript code, by the way. As you can see, the code is both shorter and more readable than the class-based version. In general, using inheritance or interface implementation to define a single method is always significantly more wasteful that using an anonymous function.

There’s a third requiremend that I left unvoiced. Look back at the previous examples again. Notice how the class-based examples have to store the window object explicitly, but the functional versions use the variable directly? This is known as «closures» : when defining a function inside a function, the defined function actually carries with it all the variables that were present when it was defined. Functional languages always have closures, because any non-trivial operation you might wish to place in an anonymous function will involve accessing data that was present near the definition.

In summary: functional programming involves the ability to manipulate functions as you would manipulate any other data type (define anywhere, store, pass, return…) and allows writing more concise programs whenever you need to pass, store or return some behavior to be executed later.

Examples of functional languages:

  • JavaScript
  • Lisp (including Common Lisp, Scheme …)
  • ML (including SML, OCaml, F# …)
  • Haskell
  • Ruby
  • C#

Examples of near-functional languages:

  • PHP only supports lambdas and closures since 5.3, and closure syntax is suboptimal.
  • Python has 99% support, the only issue is that only one-line lambdas are allowed.
  • XSLT 2.0 has no anonymous functions, but is otherwise functional. I kid you not.

Examples of non-functional languages:

  • Java
  • C
  • C++

Pure Functional Programming

This is the other definition of «Functional Programming» that you can hear, and the confusion is understandable: languages that match definition #2 have long been the only examples of definition #1 as well.

The relevant concept is purity: can the impact of a function on the rest of the program be described only in terms of its return type, and can the impact of the rest of the program on the function be described only in terms of its arguments?

Consider the signature of an interface method:

public int frobnicate(Foo f);

There are many ways in which that function can affect the rest of the program:

  • It could call a global function to perform changes in the global state, such as altering a singleton, setting a global variable, printing data to the screen, sending data over a socket…
  • It could change member variables of the object it is called on.
  • It could call methods on its argument.
  • It could return a new value that is then used by the calling code.

There are also many ways in which the rest of the program could affect the behavior of the function:

  • It could depend on global variables to decide what it should do.
  • It could read global state (user input, files, sockets…)
  • It could access the data of the object it is called on.
  • It could access the data of its argument.

The entries marked in bold can be deduced from the method signature: having a return type means you want to return something, being non-static means you wish to read the state of the object you are called on, having an argument means you want to read data from that argument. The other entries are possible, but not readily apparent in the signature.

Pure functional programming is the principle of least surprise: sure, those entries that are not in bold are possible, but it would be surprising if they happened, so they are in fact not allowed. A pure function can only read data from its arguments and can only write data by returning it.

Also, pure functions imply that data is immutable — if functions are not allowed to change anything, then they are not allowed to change data structures, so the data structures are by definition immutable.

By the way, pure functional programming is all about what you cannot do — so you could in theory write functional programming in any language just by following coding conventions to that end. In practice, immutability is quite hard to respect if there is no syntax for making it easier — you spend a lot of time creating manual copies of objects in order to change a single field.

Working with pure functions and immutable data structures involves both benefits and trade-offs when compared to non-pure programing. Think of it as a slider which goes between «0% Pure» and «100% Pure» and you pick one value for your entire program. Many algorithms and concepts get easier to understand, change and manipulate as the slider moves towards the 100% end, but there are some concepts that are intrinsically non-pure and actually get harder and harder to think about as your slider moves away from the 0% end. For instance, working with a persistent data store is an intrinsically mutable endeavor, and it’s hard (but possible) to think about it in pure terms.

I find that a slider value of 95% in a language that makes such a value possible is the optimal place to be — the 5% includes writing code that is truly non-pure (such as database manipulation, responding to HTTP requests…) as well as code that is non-pure on the inside but is actually pure from the outside (such as memoization and caching).

Article Image © Tim Olson — Flickr

Steve Jobs

Published
by
Victor Nicollet
on October 6, 2011
in Random
. 1 Comment

Today, the front page of Hacker News only mentions one topic.

1. Steve Jobs has passed away. (apple.com)
2. Steve Jobs has died (marketwatch.com)
3. The Steve Jobs I Knew (allthingsd.com)
4. President Obama on Steve Jobs: “He Changed the Way Each of Us Sees the World” (whitehouse.gov)
5. Bill Gates on Steve Jobs (thegatesnotes.com)
6. Thanks, Steve (samaltman.com)
7. Apple RIP Logo design (jmak.tumblr.com)
8. Sergey Brin on Steve Jobs (google.com)
9. Tim Cook: “No words can adequately express our sadness at Steve’s death” (arstechnica.com)
10. Larry Page on Steve Jobs (google.com)
11. Google’s Steve Jobs tribute (google.com)
12. Bill Gates Makes Statement on Steve Jobs (google.com)
13. Steve Jobs At Home In 1982 (digitaljournalist.org)
14. Steve Jobs and The Value of Saying No (betabeat.com)
15. The 313 Apple patents that list Steven P. Jobs among the group of inventors (nytimes.com)
16. Apple’s stock under Jobs: from $10 to $400 (cnn.com)
17. Daring Fireball: Steve Jobs Dies (daringfireball.net)
18. Steve Jobs: 1955–2011 (marco.org)
19. Steve Jobs, 1955 – 2011 (wired.com)
20. Statement by Apple’s Board of Directors (businesswire.com)
21. Bill Gates: “I Will Miss Steve Immensely” (allthingsd.com)
22. Steve Jobs Stanford Commencement Address: Death Is The Destination We All Share (immaturebusiness.com)
23. Obituary: Steve Jobs (economist.com)
24. BBC’s obituary for Steve Jobs (bbc.co.uk)
25. Barack Obama On Steve Jobs (allthingsd.com)
26. Tim Cook’s email to Apple employees about Steve’s passing (businesswire.com)
27. Thank You, Steve (laktek.com)
28. Larry Page on Steve Jobs (google.com)
29. “The way Steve Jobs described the computer—as a bicycle for the mind” (createdigitalmusic.com)
30. Steve Jobs: Thank you for the dream (dallarosa.tumblr.com)

I have not been an Apple user for a decade, but my programming career started when I was 14 with an old Macintosh Performa 450 and Hypercard. I guess a lot of what I am doing now would not have happened if not for Steve & Steve. How time flies.

Toppling the Stacks

Published
by
Victor Nicollet
on October 3, 2011
in Strategy
. 2 Comments

Everyone agrees that CSS is an overly verbose stream of boiling pain, but not everyone agrees on how it should be solved. Sass is one such solution — a language extension that supports standard CSS code natively, but provides several tricks that make the maintenance of stylesheets easier, not least of which being the ability to nest selectors:

.profile {
  color: black;
  .name { font-weight: bold; }
}

A compiler turns the above into standard CSS:

.profile { color: black; }
.profile .name { font-weight: bold; }

Typical usage of Sass is to write the former by hand, run the compiler, and move the resulting CSS file to wherever the browser can see it.

I successfully set up Sass on my development machine and uploaded the generated CSS to source control. This worked correctly for a few weeks.

Then came the time when I had to set up Sass on the deployment server, because not everyone on the team had the time or the operating system to set up Sass on their computer. It burst into flames almost immediately with an arcane stack trace:

.../rubygems/defaults.rb:40:in `exist?': Insecure operation - exist? (SecurityError)
    from .../rubygems/defaults.rb:40:in `default_path'
    from .../rubygems.rb:752:in `path'
    from .../rubygems/source_index.rb:59:in `installed_spec_directories'
    from .../rubygems.rb:1051:in `source_index'
    from .../rubygems.rb:243:in `activate_dep'
    from .../rubygems.rb:236:in `activate'
    from .../rubygems.rb:1307:in `gem'
    from /usr/local/bin/sass:18

I posted an issue to the GitHub issues tracker for Sass. The answer was underwhelming :

This looks like a Rubygems issue, not a Sass issue.

And the issue was closed.

Let me set things straight here: when a Sass user cannot use Sass, it is a Sass issue. Yes, the underlying technical cause of the issue is probably somewhere inside that «Rubygems» thing I sincerely know nothing about, or maybe it lies in the Debian package for it, or maybe I’m just setting up my environment variables badly and just need a clean diagnosis to fix that up, but Sass is not working. Even if you have absolutely no personal responsibility for the issue, pointers such as «ask about this on channel X or mailing list Y» are most welcome.

Now, I don’t expect nex3 to provide me with free support. This is an open source project, and there’s nothing unusual or wrong with having no technical support on open source projects. In fact, given the size of the technology stack sitting under Sass, this was probably the best thing to do in terms of project strategy — only cater to users who can get the underlying stack working on their own.

This is not a matter of fairness or ethics, but one of incentives. I have no need to keep debugging Sass — the path of least resistance is precisely to replace Sass with an equivalent working tool. Rewriting a handful of Sass rules over to Less CSS is easier for me than tracking down bugs in the Debian packaging of «Rubygems». And the deployment server runs Less without a hitch.

I shudder to think what would have happened had I locked myself into more esoteric Sass language features.

Article image © yimmy149 — Flickr

Node.js is Aquarius

Published
by
Victor Nicollet
on October 3, 2011
in Dynamic
. 0 Comments

@Ted Dziuba : your article on Node.js being cancer has brought many angry nerds with pitchforks to your door. You do make good points, and the best opinion is not one that everyone blindly agrees with, but one that gets everyone thinking — hopefully before they speak.

Scalability

I, too, would take issue with a statement like «Node.js is scalable because it is non-blocking» though not the same issue as you took. Being non-blocking does not help with scalability at all. Scalability is about how easily your system administrator can add a new machine to your web farm to soak up a heavier load than usual, and it’s all about two things:

  • Can you run multiple copies of your software in parallel? In-application sharing of data makes this harder. Some Java servers store the entire relevant state in application memory, so scaling is impossible. PHP stores session files on the disk by default, so scaling is only possible with server affinity (the same user always gets sent to the same server). A clean server with no in-application data sharing is easily duplicated, regardless of the language.
  • Is there a shared resource with sequential access? If you run a hundred thousand web servers, but all of them have to read-write the same physical drive, then your application will be no faster than that read-write speed. If you access a database that involves heavy locking, then your application will be no faster than the locking sequence can allow.

None of these are in any way improved or even affected by non-blocking semantics.

Node.js improves performance when serving multiple concurrent requests. It makes it no easier to scale, but it helps delay the point where scaling becomes necessary.

The typical explanation of how this happens is that if serving a request uses 10ms of processing things on the server («Work») and 10ms of waiting for database requests to complete («Wait»), then the ideal web server should be able to serve two concurrent requests in 10ms each by overlapping the processing time of one request with the database wait time of another. This is a pretty nice and simple idea, which is why everyone has been doing it for ages. The main difference is how it is done.

What the traditional UNIX world did is pop enough processes — that is the Unix answer to every problem, including having too many processes around. If your Work-time is 10ms and your Wait-time is 40ms, then by allowing up to four processes you are effectively recycling all the wait-time in a high concurrent load situation. This is why every CGI- or FastCGI-enabled web server in existence provides a configuration entry for the number of concurrent child processes.

Node.js does the same. With that same Wait/Work ratio of 40/10, Node.js will be serving four concurrent requests at the same time, because it cannot create processing time out of thin air.

What Node.js brings to the table is an architecture that performs, at the server level, what the traditional UNIX world did at the kernel level: scheduling. Whether this approach is significantly faster than a properly configured FastCGI setup is still a matter of debate, and I believe the answer here is simply that, as long as the Wait/Work time ratio does not push the number of concurrent processes higher than what the available memory allows, there will be no significant difference between FastCGI and Node.js in terms of blocking.

The UNIX Way

I once agreed with your stated opinion on the matter, but I got better. Here’s the thing: today, being an HTTP server is no more of a «responsibility» than reading from STDIN and writing to STDOUT. Make no mistake: being a production, internet-facing HTTP server is a responsibility, but that is not what Node.js is (or should be) trying to achieve.

Consider this: the production, internet-facing HTTP server must communicate with the actual application using one protocol or another. CGI is one such protocol, FastCGI is another, and HTTP is yet another — the fact that the same protocol is used for serving requests over the internet is not  a problem, it is actually a benefit because communicating through HTTP is a solved problem with a clean API in almost every single language out there.

There is now something I would jokingly call «The REST Way» which follows in the tracks of the UNIX Way in a cloudy fashion : small applications performing one task — dispatching internet requests, constructing responses, persistent storage, caching — running on any number of servers in any number of locations, and connected to each other through HTTP requests. In an nginx-Node.js-CouchDB stack, nginx is the dispatcher, Node.js constructs responses, and CouchDB provides persistent storage, and everyone «speaks» HTTP in the same way that Unix processes «speak» STDIN/STDOUT.

Article image © Patrick Janicek — Flickr

RS Latches

Published
by
Victor Nicollet
on September 12, 2011
in People
. 0 Comments


One of my oldest memories harkens back to 1989 — I was a four years old boy in communist Romania. My mother has a PhD in biochemistry, and her father and brother both had a PhD in physics, so it might seem quite unsurprising that I followed in their rational and scientific steps, but it would be hard to put the proverbial finger on how, precisely, that happened. This is what that specific memory is about.

It all started with my frequent stays at my grandparents’ house, a conventional second-floor flat in Bucharest, where my grandmother and grandfather took turns babysitting me while my parents were out hammer-and-sickling (well, laboratory-and-architecturing) the socialist ideal. My grandfather was intent on turning me into a bright scientific mind, so he asked my uncle to build me a computer. Nothing fancy, mind you : it had no operating system worth mentioning, no hard drive, and depended on magnetic tapes and 8″ floppies to actually work. My grandfather showed me a standard BASIC interpreter, and had me type in a program that displayed, line by line, an analog wall clock.

Fascinated, I started spending my days on that thing writing BASIC code, learning how to build increasingly complex programs, and starting my career as a programmer. Or so had my grandfather hoped. A few seconds after discovering computer programming, I discovered computer games, which were a far more fascinating novelty than displaying wall clocks on a screen. I promptly forgot about the BASIC interpreter and for nine long years, I assumed that programming computers was some sort of esoteric arcane art, invisible to the uninitiated, and remained entirely uninterested in it.

Instead, my breakthrough as a rational mind was triggered by the close proximity of two unlikely catalysts : one was a frequent diet of mecha anime (the quality of the Romanian dubbing was hilarious), and the other was a cupboard drawer full of bits and pieces that could, to a child’s mind, be spare parts out of which a robot could be built : wheels, small electrical engines, cables, batteries, microprocessors, light bulbs… as a matter of fact, once I had the basic understanding of how a batteries + cables + engine setup worked, I did build small uninteresting contraptions.

I became intensely interested in building a robot myself. Obviously, I did not have the technical skills or the willpower to follow through with this plan, but I would listen, entranced, to any explanations I would receive that were related to robot-building. My grandfather was writing a book on semiconductors at the time, so he showed me a large digital circuit and let me understand that this is what the brain of a robot would look like — only quite larger !

And so he started teaching me the elementary principles of digital circuits. We spent little time discussing the underlying technical details, and instead concentrated on the simpler abstractions of logical gates. This time, I was fascinated. I would grab a pen and paper and draw circuits for fun. The meaning of AND, OR, NOT, NAND, NOR and XOR are imprinted in my brain ever since I was five years old… there are few concepts remaining in my brain that have been there for so long.

My circuits behaved like mathematical functions : I would mentally set the input bits, and the output bits would contain the result, so I could build the truth tables that mapped input combinations to output combinations. I experimented with basic arithmetic functions, learning binary as I went. And then one day my grandfather showed me a circuit that I could draw from memory to this day : the RS latch.

The fun thing about the RS latch is that it cannot have a truth table. It is an entirely different beast from arithmetic “write input bits, read output bits” circuits in that it has a state. If you write 1 to the S input bit, the output becomes 1 and remains 1 until you write 1 to the R bit, at which point the output becomes 0, and so on. To say things differently, the S input bit stands for “Set” and sets the output to 1, and the R input bit stands for “Reset” and sets the output to 0. When both R and S are set to 0, then the latch output bit is equal to whatever it was previously set to.

The RS latch is a versatile little thing. It can be used to implement RAM (one of the first things I did with it), or it can be chained to create an incrementing counter.

After a while, my interest in digital circuits faded, but the effects it had on my character were permanent : I now had experience applying abstract rules to abstract concepts, and it was fun.

Article image © Cornelia Kopp — Flickr

1150 feed subscribers
(readers who polled a feed this week)