There are two main execution models for web scripts. One model is to have the web server (apache, IIS) start a new instance of the script when a request for that script is found. The script then executes from beginning to end, performing its entire initialization, response and shutdown cycle. Caching may occur at both the bytecode level (to avoid parsing the source file several times) and explicitly in the code (querying a cache system for existing data). The other model is to have the web scripts run as a process in cooperation with the web server.

In this other model, initialization is performed only once, and the data is then kept in memory, which allows more in-memory caching opportunities. For example, views.

A view is a function which reads data and outputs a formatted document based on that data. Of course, language and design considerations might turn the view into an object or module, but the general concept of “data goes in, document comes out” remains constant in all situations. A “user profile” page would be a view for a social networking site, reading user data from the data model and writing it as a document.

A view helper is a function which reads data and outputs a formatted sub-document—the main difference is that instead of being sent to the user directly, the view helper is instead incorporated into a document. That is, view helpers are used to help views render the data. For instance, a “friend” view helper would read the data for a single friend and output it both on the “user profile” and the “view all friends” pages.

A simplistic illustration in Objective Caml (this language choice will be explained later on, although by reading the ‘monad’ word in the title you would have guessed that functional programming would be involved today):

let showFriend(friend) =
  print "<img src='/images/";
  print (User.id friend);
  print ".png'/><span>";
  print (User.name friend);
  print "</span>" 

let showUserPage(user) =
  print "<html><head><title>";
  print (User.name user);
  print "</title></head><body>";
  print "<h2>Friends (";
  print (string_of_int (List.length (User.friends user)));
  print ")</h2><ul>";
  List.iter
    (fun friend ->
      print "<li>";
      showFriend(friend);
      print "</li>")
    (User.friends user);
  print "</ul></body></html>"

This is, of course, very simple. It’s quite probable that a complex page could use hundreds of view helpers to further improve code reuse.

There’s a problem with this approach, however. If the logic is pushed to the extreme, a page will be composed of hundreds of function calls that each append a very small number of characters to the final document. This can reduce program performance because of multiple concatenation options.

This limitation is already present in the simple example above: instead of printing a friend as “<li><img src=’/images/”, “.png’/><span>” and “</span></li>”, it prints the individual “<li>” and “</li>” separated from the rest. The compiler can do nothing about this, because it has no reason to know that print “a”; print “b” is equivalent to print “ab”.

Monads

It’s possible, however, to provide the compiler with this information: monads allow the programmer to represent a function with side-effects as a non-function type, which can then be pre-processed when the script is initialized so that it is always used in an optimized state.

Let’s consider the following situation:

A view is something that reads data and outputs a document. It’s not a function, but it can be converted to such a function after an optimization process.
The function “show” creates a view which outputs the passed string: show “text” reads data and outputs “text”.
The function “call” creates a view which calls a function on the passed data and outputs the result: call func outputs func(data).
The operator “++” creates a view from two views. The two views are rendered with the same data one after another.
The function “foreach” creates a view which calls a function, then calls another function on every element in the returned data set, then concatenates the resulting views using “++”.

Then, the above code will look like this:

let showFriend =
     show "<img src='/images/"
  ++ call User.id
  ++ show ".png'/><span>"
  ++ call User.name
  ++ show "</span>" 

let showUserPage =
     show "<html><head><title>"
  ++ call User.name
  ++ show "</title></head><body>"
  ++ show "<h2>Friends ("
  ++ call (fun user -> string_of_int (List.length (User.friends user)))
  ++ show ")</h2><ul>"
  ++ foreach User.friends
     (   show "<li>"
      ++ showFriend
      ++ show "</li>" )
  ++ show "</ul></body></html>"

Notice how foreach looks idiomatic and quite similar to typical imperative languages, and how showFriend is used just like any other view. Now, both showFriend and showUserPage are values, not functions, so they are evaluated at initialization time instead of every time they are called. This makes it possible to optimize things as necessary once and for all.

A non-optimized version of the above would simply perform concatenation:

let (++)    f g x = f x ^ g x
let show      s x = s
let call      f x = f x
let foreach l f x = String.concat "" (List.map (l x) f)

An optimized version could use a complex type: a view is a list of things to print, and consecutive “show a constant string” instructions can be collapsed through concatenation at initialization time.

type instr =
  | S of string
  | C of (data -> string)
  | F of (data -> data list) * instr 

let (++) f g =
  List.fold_right (fun instr acc ->
    match instr, acc with
      | S a, S b::t -> S (a^b)::t
      | i  , a      -> i :: a) f g 

let show s = [C s]
let call f = [V f]
let foreach l f = [F (l,f)] 

let rec render v x =
  List.iter (function
    | S s     -> print s
    | C f     -> print (f x)
    | F (l,f) -> List.iter (render f) (l x)) v

Since the “++” concatenation function collapses consecutive constants, the two views above would look like this:

[S "<img src='/images";
 C User.id;
 S ".png'/><span>";
 C User.name;
 S "</span>"]

[S "<html><head><title>";
 C user.name;
 S "</title></head><body><h2>Friends (";
 C (fun user -> string_of_int (List.length (User.friends user));
 S ")</h2><ul>";
 F (User.friends, [S "<li><img src='/images";
                   C User.id;
                   S ".png'/><span>";
                   C User.name;
                   S "</span></li>"]);
 S "</ul></body></html>"]

So, the definition of the friends view has been inlined in the user view, and the constant “<li>” and “</li>” have been collapsed.

Nicollet.Net

Monad-Based View Optimisation

Monads

0 Responses to “Monad-Based View Optimisation”

Leave a Reply Cancel reply

New Here? Read These First!

Recent Comments

Recent Ramblings

The Good Old Days