I’ve been having a lot of name-related problems, lately. Not my own name, but the names of various things I have to work with. Nothing unexpected: in the computer world, we tend to use names everywhere.

Every time there are objects to be manipulated by programmers, there’s a way to give names to these objects. It could be the “id” attribute in XML, it could be the name of a file in a filesystem, it could be the name of a variable or member in a program, or it could be the hostname of a web site… A name is, in theory, a set of characters from a predetermined alphabet (that varies based on the application) which is bound to an entity of some sort. Once you hold the name, you can get the associated entity directly.

This theoretical definition leads to two distinct issues:

• There’s only a small number of acceptable names around. Of course, generic names like “clxbpf8990″ can be used (and if you look at the ids generated by generate-id() in XSLT, this is exactly what happens) but the entire point of a name is to allow people to retrieve content based on the name. As far as the internet goes, there’s only a finite number of names any user can remember—and web users have become increasingly reliant on google and the recently added Firefox 3.0 address bar to find sites with non-obvious names. How do we handle the inevitable collisions?
• A programmer in Australia has a global variable named Foo in a C program. A programmer in Sweden, working on a different C program, also has a variable named Foo. Should the two collide? What about machine names on local networks? User names on the same machine? Not all names are global, which means that the scope of names has to be determined, and ways of handling collisions between local scopes must be invented.

Yet, it’s not all about collision. The most important element of naming is the ability to find the data bound to a name. This is what directories are for.

The simplest form of directory is the phone directory: you have a name on the left, and a phone number on the right. The directory also happens to be sorted by ascending key order so that dichotomic search can be used to find a given name in logarithmic time (how clever—in the age of search engines, we tend to forget logarithmic search times existed since the days of dictionaries and encyclopedias). Such directories exist in the computer world. The simplest would be the classic user directory, accessed through LDAP (Lightweight Directory Access Protocol) or perhaps ActiveDirectory, but these are not the most frequently encountered by the common user. Another simple example is /etc/passwd:

username:!:100:100:office:/home/username:/usr/bin/sh

User name is on the left, various user-related information is to the right.

Domain Name System

Let’s crank the complexity lever up a little bit. What classic directory format do we use several times a day? The Domain Name System (which most of you know as DNS). Everyone sends out queries to a DNS server, asking for the IP associated with a name. That is, when you type “www.nicollet.net” in your browser, the browser needs to know what server to connect to. The problem is that looking for a server is done by routers, which are usually not very smart: they have routing tables based on masking the IP address (whether that address is IPv4 or IPv6) so they need that address to begin with. So, the browser instead resolves the domain name to an address. This involves looking at the local “hosts” file to see if a definition exists (for instance, “localhost” tends to be bound to the loopback address “127.0.0.1″), then queries any local name services the operating system may provide (this allows you to connect to an HTTP server running on another machine on your network by using that machine’s name, without having to set up a local DNS server or registering with a public one), and finally sends out a query to a DNS server somewhere on the internet (the address of the DNS server is either provided by the ISP itself, or manually entered by the user in a configuration wizard or file). The DNS then returns the address for the domain.

This is where two of my recent name problems came from. As you might remember, one week ago I had to move my blog from one server to another, and in the process, I had to change the DNS entry so that reads who typed in “www.nicollet.net” connected to the new server instead of the old one.

The first issue was that DNS propagation is not instantaneous. Back in the days when the intertubes were often clogged, caching played a big role in avoiding too many DNS queries moving up to the reference DNS server for a given top-level domain. The downside is that when you type in “www.nicollet.net”, you’re not really asking the reference DNS server for domains ending in “.net”, you’re asking the DNS server provided by your ISP, which may decide that its copy of the “www.nicollet.net” address binding is correct, without even asking the reference server (this is what caching is for). So, it took about five hours for all visitors to be correctly redirected to the new website. If any of you posted any comments, they went to the old website and were lost along with it—sorry. Of course, as you can expect, this can get a lot more problematic once you have a highly interactive website. So, you tend to choose an IP address and stick with it (or, if you have to change it, then you have it forward everything to the new one until nobody uses it anymore).

This also meant that any e-mails sent to foobar@nicollet.net were routed to the old MX binding, “mx1.ovh.net” (for those who wonder, a DNS entry contains several bindings: a web browser would look at the main binding for that domain, while a mail delivery program would look for the Mail eXchange binding) even though I was expecting them on the new MX binding, “nicollet.net”.  This took a short while to be sorted out.

The second issue was with the name of the server. See, being listed in a directory doesn’t change your name: it merely gives you a name by which you can be found. So, the name of the famous emperor of Wei is still Cao Cao, despite being posthumously named Wu. And the name of my new server still was r17474.ovh.net despite being now referred to as nicollet.net by the DNS. Then, of course, when some mail arrived for the user foobar@nicollet.net, my qmail-powered server quite naturally answered “there’s no user named foobar@nicollet.net here, please go away” in perhaps not so polite terms. So, I still had to convince my server that it was now known as “nicollet.net” so that the mail delivery could work. Nothing that the “hostname” UNIX command couldn’t solve.

What about local area networks? How come that you can access another machine on your network by using its name? There usually isn’t a central naming service which can be queried by computers on a LAN, and it wouldn’t be practical because it would have to be manually configured on every new computer. Instead, computers on a LAN use NetBIOS to set up local directories: whenever a new computer is hooked up to the network, it broadcasts its hostname and address to everyone else, and everyone else writes down the association in a local directory. Conflicts are resolved quite simply: if two computers have the same name, the last to broadcast is the one that everyone else remembers (this is quite useful if you have to move from an office to another and get a new IP as a consequence).

Names in Languages

Programming languages all provide the user with ways of naming entities that are significant, both for documentation purposes (it’s easier to understand what a value is when it has a reasonable name) and for cross-referencing data defined in one place and used in another.

On the one hand, you have the static compile-time approach. This is the easiest to work with by far, because all the nitty-gritty details are written down in the documentation of the compiler and the build scripts of your application. For instance, most compilers allow the definition of “include paths”, a list of locations on the filesystem where the definitions of objects can be found. When the compiler needs something (an included file in C or C++, a class in Java or Actionscript, a module in Objective Caml), it will look for an appropriately named file in all these locations.

Let’s consider the Objective Caml compiler, “ocamlc”. Whenever a source file contains a reference to another module (by using a symbol in a module context, such as “ModuleName.member” or “Functor(ModuleName)” or “open ModuleName” or something like that), the compiler looks for the compiled interface of that module. This is done by looking for the file “moduleName.cmi” (which is generated manually by running “ocamlc moduleName.mli”) in all the locations configured with the compiler: first, the current directory, then paths specified through the environment variables, then include paths specified with the -I command-line argument. If you’re only compiling the module (flag -c), the result is a cmo file (or cmx file with “ocamlopt”). At link-time, you must then specify all the cmo files required by the program, and the compiler resolves all links based on the name of the cmo file (for simplicity, it’s possible to group together several cmo files as a single cma file : they are simply concatenated together, so using the cma library is equivalent to adding all the cmo files it contains manually).

Java goes a short step beyond this by eliminating the need for a link step. When you import a java class, using the “import abc.def.Foobar;” statement, java understands that by looking at the relative path “abc/def/” it will find either a “Foobar.class” or a newer “Foobar.java” that it can compile to “Foobar.class”. Here, the path is specified relative to one of the include paths (which Java calls classpaths) and can be a normal filesystem path or a path within a JAR archive.

C and C++ are both the simplest and the most complex. In these languages, every reference is explicit. The first step is compilation, where files are included in other files by specifying the relative path. The second step is linking, where libraries and objects are included by specifying the relative path. At each step, additional locations can be specified to look for headers.

PHP has an interesting dual approach to things. On the one hand, its normal cross-file interpretation system consists in include() and require() statements which look for the named file in any of the specified include paths for PHP, which makes it look like SH, C and C++. On the other hand, PHP has also introduced functionality for resolving class names: when a class is used (”ClassName::Member”, “Foobar extends ClassName” or “new ClassName”) but the class is not defined, a special function is called. This lets the user specify an alternative loading scheme, such as looking for a file named ClassName.php and including it. The Zend Framework makes heavy use of this, meaning that the inclusion approach is specified once in index.php (or a common configuration file) and then no other inclusion is used for class filed (arguably, Zend_View still includes phtml files explicitly).

On the other hand, there’s runtime access. This is harder to work with, because there’s less documentation available. Sure, some concepts, such as dynamic linking, are fairly well-documented mechanisms that look for the named file in the current directory first, then in other directories specified as environment variables or system-wide configuration elements (in the case of java, in the classpath, for example). However, even then, some programs insist on working on their own.

I recently had an issue with Alfresco, namely alfresco-mmt.jar which terminated with a ClassDefNotFound exception. Looking for solutions on the internet, I found out that the class it was looking for was defined in a JAR nearby, so I adapted the classpath when running the jar so that the class could be found. Except it couldn’t. The problem with this was that the exception did not specify where the class loader had been looking for the class (or perhaps it did internally, but as an end user with no access to the source code or, probably, a debugger, I couldn’t see it), so I had no way of understanding where the JAR with the class should have been placed. It turns out, the application loaded the JAR from inside its own JAR, so I had to place it there.

There comes a time in every programmer’s career when the question of Object-Oriented Programming crops up. Various sources attempt to explain Object-Oriented Programming, though subtle nuances exist that often make such definitions incompatible with each other. Even worse, every programmer usually builds over the years his own version of what OOP really is about, and severe clashes can happen as a consequence.

Wikipedia’s approach is a quite pragmatical one: it accepts the existence of multiple definitions, and merely attempts to explain those concepts that are shared by most. Some define the core of OOP as the ISP, LSP, OCP, DIP and SRP acronyms principles. Others take a build-your-own approach from a set of basic premises. It only seems fair that I could get my own stab at it as well.

Object-Oriented Programming is usually used to refer to two distinct yet related concepts:

• A set of tools that can be used for design and for programming: classes, objects, messages, inheritance, code metrics, design patterns…
• The ways in which that set of tools may be used to construct software that guarantees certain benefits, such as low-cost maintenance or reuse of existing code.

It is impossible, and foolish, to separate the two. Using classes, objects and the other tools without proper discipline or skill does not bring any of the benefits that are associated with OOP—even worse, programmers who come expecting proper OOP use of these tools will be surprised and will often have a lot to do to correct the situation. No single Object-Oriented concept is a magic bullet capable of working wonders on its own.

Today, I’ll discuss the tools. The next article in the series will deal with the mindset.

Object-Oriented tools are language-independent and implementation-independent. Most languages have their own ways of providing support for these tools, and they can sometimes even be used in those languages that don’t provide any kind of helpful support. Considering Object-Oriented Programming as “What happens in Language X” often leads to trying to replicate language X features in language Y, even though language Y also provides support for OOP in a different way. Besides, since programming languages seldom provide the entire OOP toolset out of the box, restricting oneself to a single language also reduces the horizon of potential tools.

Objects

One thing everyone manages to agree on is that Object-Oriented Programming is about objects—what objects are, or how they should be used, is already a matter of disagreement in certain places. My own take on objects is that you don’t need to know what they are, you merely need to know how to manipulate them. This means that an OOP object can be implemented as a Java object, an Objective Caml abstract type or a C structure, as long as it behaves like OOP objects should.

First, where do objects come from? Before you can manipulate them, you must create them. The easiest way of getting a brand new object in your program is to create it yourself from scratch. Writing the string “Hello” in your source code will automatically create a string object representing “Hello” when the program is run. Most programming languages provide means of creating certain categories of objects directly in the code: strings, integers, floating-point numbers, booleans, functions and classes are typical examples. Yes, functions and classes are, from an Object-Oriented Programming perspective, objects. Some programming languages also allow the creation of arbitrarily complex objects on-the-fly as a literal (the Objective part of Objective Caml allows this, for instance), but most languages only allow the creation of complex objects from classes. I’ll get back to this class business later.

Messages

The sole purpose of objects is to receive messages.A message is a one-shot two-way communication channel between a piece of code and an object. The code sends a request to the object, and the object sends a response to the code. What the response looks like is up to the object, two distinct objects may respond differently to the same request and even a single object may respond differently to the same request at two distinct points in time. Both the request and the response carry some data—this data is usually a set of objects. A request also has an identifier that helps determine what the request is about: a “getAccountBalance” identifier means that the request is about getting the balance of an account, while a “setDuration” means that the request is about changing the duration of something.

Not all objects can process all messages. For instance, one cannot expect a rubber duck to respond to a “getAccountBalance” message. So, not being able to process a message is a possibility to be considered—one of the main advantages of having language support for OOP is that statically typed languages can check at compile-time whether all messages are going to be processed successfully. But, again, more on that later.

At this point, most OOP manuals summon forth a class definition of some form and happily declare “this class describes sets of objects, its methods define messages that the object can receive”. I find that approach quite annoying, because it forevers equates in the minds of the readers object with instance of a class and message with class method—the consequence being that readers then find themselves at a loss when they encounter languages with class-less objects (such as Objective Caml) or class-independent implementations of Object-Oriented Programming (such as Service-Oriented Architectures).

Everything is an object

So, my example is going to be one simple piece of C pseudocode instead:

int squared(int x)
{
  return x * x;
}

printf("%dn", squared(10));

In C terms, this pseudocode defines a function that returns its squared argument, then outputs the square of 10 on the standard output.

In Object-Oriented terms, this creates a new object and gives it the name squared. It does so by using a “function literal” which creates a brand new object by specifying what the object does when it receives a “function call” message: in this situation, the behavior would be to extract an integer object from the request, send that integer a “multiply by yourself” message, then respond with the result. Our example then sends the “function call” message associated with the integer literal 10 to the squared object, then binds the response to another “function call” message sent to the printf object.

In other words, a plain old piece of C code without a single occurrence of the class keyword can be interpreted as an object-oriented program. This extends even further: any piece of imperative code can be interpreted as sending messages to objects. Going even further, even pure functional code without even a hint of imperative design can also be expressed as sending messages to objects: every function is an object that can process the “function call” message.

So, in languages without classes, you can usually find:

• Primitive objects : integers, booleans, floating-point numbers and similar kinds of values are objects which are created from literals. They accept a wide range of messages which correspond to their operators (add, multiply, subtract, boolean-and, boolean-or, and so on).

• Aggregate objects : C structures, OCaml record types, Javascript objects (ignoring the this keyword) that are a collection of sub-objects that can be accessed by name. They support “set value X” and “get value X” messages for every member X. They are created as literals by assigning the appropriate names with the appropriate initial values. They may or may not require preliminary definition of their type (for checking purposes in strongly typed languages) and extension of their contents by sending a “set value Y” message for an yet-undefined member Y.

• Functions : these objects accept only one message (”call function”). They are created as a literal which describes how the data is extracted from the request, what operations are performed on it, and what data is sent back as part of the response.

Semantic shifting

If Object-Oriented Programming was all about looking at previously written programs and noticing how they are Object-Oriented, there wouldn’t really be much of a point to doing it. The good news is that OOP is not only about observing objects within existing code: it can also be used to introduce brand new behaviors into existing objects. This happens by performing a semantic shift of what a message and an object is: you decide that a certain construct you just invented is an object, and that another construct is a message.

Let’s look at our C pseudocode example again:

int squared(int x)
{
  return x * x;
}

This can be interpreted as creating a new object, “squared“, which can handle the “function call” message. But it could also be interpreted as defining a new message, “squared“, which can be sent to integers. After all, since this is all a matter of interpretation, both interpretations can be correct at the same time: as long as squared(10) is a one-shot two-way communication channel between some code and the integer 10, it’s a message.

This semantic shift can be applied in almost all situations: a function with at least one argument can be seen as both an object that accepts a “call function” message, and as a message that can be sent to one of its arguments (with the other arguments as its associated data). So, now, you can go around and extend any of the objects that the programming language provides you with by creating the appropriate functions.

Polymorphism

Back to our “squared” message. That message can certainly be applied to integers, but it’s equally valid to apply it to floating-point numbers. Besides, if we (by some miracle, or perhaps some feature of the language) managed to create a new kind of object which also supported multiplication by itself (such as a complex number) then the “squared” message could also be sent to that object. This is because that message merely requires that the object it’s applied to supports multiplication by itself and so it can be applied to any such object. This is called polymorphism: when a message can be sent to any object, regardless of its nature, as long as it supports a certain set of operations. This provides the benefit of avoiding code repetition: you only define your “squared” message once, and then you can apply it everywhere. In a theoretical, ideal object-oriented programming language (the part is played here by Smalltalk, a very nice OOP language), you would just write this line once:

squared := [:x | x * x ]

Interfaces

The problem is that languages don’t play nice with the concept of polymorphism. To determine whether a program behaves correctly at runtime, the language uses a type system. This type system allows expressing certain constraints over the values, and some rules to determine which constraints imply that the program works.

The C type system is a fairly crude one. Every value has a type, with types being mutually distinct. So, you have the type of all integers, and the type of all floating point numbers. And a function argument has only one type. So, our polymorphism example, applied to two types, becomes:

int squared(int x)
{
  return x * x;
}

float squared(float x)
{
  return x * x;
}

The problem, of course, is that there is no way in the C type system to express the constraint “supports multiplication by itself”. So, although the semantics of “multiply the argument by itself” are clear, the C compiler cannot understand that it’s safe to define one such function. For that matter, the Java, C++ and Objective Caml type systems won’t let us define such a function either. This is one of the reasons I chuckle when I hear Java advocates tout Java as a “pure object-oriented programming language”: despite all the effort poured into creating a clean object model, a lot of elementary Java operations (including multiplication) are not messages, and several elementary Java types (including integers) are not objects. If you’re looking for a pure OOP language (you don’t need one to do proper OOP, of course), I strongly suggest Smalltalk.

Back to the point: languages that support OOP actively, yet have a static type system, provide the notion of interface to help with type-checking. An interface is a set of constraints and requirements, stating what messages can be received by the object, what data has to be sent as part of the request, and what data will be returned as part of the response. So, one can express an interface with a “multiply by” message, and the define the “squared” function to work on all objects with that interface: the language will then see that the interface provides the “squared” function with all it needs (namely, the “multiply by” message) and consider the types to be correct.

In Java, the interface and function would look like this:

interface Multipliable
{
  // Accepts "multiplyBy" message
  Multipliable multiplyBy(Multipliable);
}

Multipliable squared(Multipliable x)
{
  // Send "multiplyBy" message
  return x.multiplyBy(x);
}

Of course, we had to use explicit message names here, because the multiplication operator in Java is not a message supported by the type system. On the other hand, Objective Caml is a tad smarter, because it can guess the interface based on the messages being sent:

let squared x =
  x # multiplyBy x

(* squared : (< multiplyBy : 'a -> 'b ; .. > as 'a) -> 'b *)

Another consequence of Objective Caml’s more expressive type system is that it allows retrieving the correct type. For instance, if you pass an integer into Java’s “squared” function, you would get back a Multipliable object, but you wouldn’t know if it was an integer or something else. This can be annoying, because you, as a programmer, know that it’s an integer, but the language won’t let you use it as such until you remind the compiler that it should trust you (and it will still check it at runtime). By contrast, Objective Caml types are parametric. An integer would probably have a “multiplyBy : integer -> integer” function, so the squared function would correctly return an integer.

But all of that is idle bickering about type systems that deviates from the purpose of the article.

Classes

A very important element of object-oriented programming is the notion of class. Earlier on, I said that objects could only be constructed at runtime by literals. That is, you create a new object and set its various properties right away. This, of course, makes it difficult to define categories of similar objects, because you have to define them one at a time and also make sure they share similar properties.

Another way of creating objects has been proposed in several programming languages, to the point of becoming (mistakenly) a synonym for OOP. A class is an object—even though some impure programming languages do not treat it as such—which defines a single message called a constructor. Upon receiving a constructor message, the class creates (by some arcane magic implemented by the compiler) a brand new object with a predetermined set of properties that are a combination of the data sent with the constructor message and the data provided when the class itself was created.

The exact syntax for sending the constructor message varies from language to language, but usually involves something along the lines of “new Classname(arguments)“.

In practice, a class defines two things:

• The data to be carried by the object. This data is either created from scratch by the constructor, gathered from the global scope, or extracted from the constructor message itself.
• The list of messages that the object can process, along with the code to perform said processing.

Again, the exact syntax for defining a class varies. In Objective Caml, the constructor message is described as part of the class name and used to initialize the values in the object, while the messages to be processed are called “methods”:

class vector2d (x,y) =
object
  val x = x
  val y = y
  method length = sqrt(x *. x +. y *. y)
end

let v = new vector2d (1.0,2.0) in
  v # length

[Edit : corrected small typo] In Java (as well as C++ and C#) the constructor is described as if it were a method, which can sometimes be confusing. Also, the language does not automatically guess which interfaces are implemented by a certain object, so they have to be specified as part of the class definition.

class Vector2d
{
  private float x;
  private float y;
  public Complex(float x, float t)
  {
    this.x = x;
    this.y = y;
  }
  public float Length()
  {
    return Math.sqrt(x * x + y * y);
  }
}

Vector2d v = new Vector2d(1.0,2.0);
v.Length();

In Javascript, classes are constructors, with methods being defined as part of that constructor’s prototype:

function vector2d(x,y)
{
  this.x = x;
  this.y = y;
}

vector2d.prototype.length = function()
{
  return Math.sqrt(this.x * this.x + this.y * this.y);
}

var v = new vector2d(1.0,2.0);
v.length();

Class extensions

In fact, classes support another message besides constructors: inheritance, or extension. When extending a class or inheriting from a class (two ways of expressing the same concept), one create creates a new class which imports all the contents of another class, then adds its own set of contents. Most type systems apply a subtype relationship to inheritance, meaning that a function which can operate on an instance of the original class can also operate on an instance of the inheriting class.

Inheritance is a strange beast: on the one hand, it behaves a little like interfaces (and is in fact the only way of replacing interfaces in languages that don’t have them, such as C++) to provide polymorphism but on the other hand it is a non-polymorphic way of extending the functionality of a class. It happens quite often that entire programs avoid using inheritance at all, because interfaces solve all their polymorphism needs and they do not need the extension features of inheritance.

A summary

Object-oriented programming introduces the following set of concepts:

• An object is a value manipulated by the program. Integers, booleans, strings, functions and classes are examples of objects. Objects are usually created using literals provided by the programming language.
• A program works by sending messages to objects. A message transmits a request (with arguments) to an object and the object responds with some data. Calling a function on an argument can be seen as sending a message, and calling a member function or method can also be interpreted as sending a message.
• An interface, in a statically typed programming language, represents a set of messages that an object must be able to process. This is used to ensure that a function argument can be used without causing a runtime error.
• A class is a special object which can receive constructor messages. Every constructor message constructs a brand new object that is returned as part of the response. Usually, an object created from a class is said to be an instance of that class.
• Classes can inherit from one another, which can be useful in some cases to extend its functionality in a non-polymorphic manner.

The next article in the series is here (starting on January 9, 2009).

It has recently come to my attention that a new unit testing framework for Javascript had become available : FireUnit is a Firefox extension that integrates with Firebug to allow automatic testing. It includes features such as pretty-printing of test results in the Firebug console and simulation of user-side events.

I’m marginally skeptical about this. I can see where the thing can be useful: you have a standalone data model that should evolve according to certain rules when manipulated in certain ways. In those cases, writing an unit test happens like in any other programming language and everyone is happy.

But, like in other programming languages, whatever is related to user interaction (reading input, displaying things) is inevitably much harder to test:

• it’s hard to determine whether a result is displayed correctly or if something’s off, it’s even harder to determine whether the result will be displayed correctly in other configurations (including, for instance, other browsers), and animations are hellish to check because of time-dependence,

• third party frameworks often allow ways of changing states but not of querying them (for instance, jQuery allows setting a movement queue for animation, but querying the current movement queue is harder, and does not allow checking whether an element is shown, hidden or in-between),

• many elementary errors rely on race conditions (press two buttons in short sequence while the server is busy) because of the lack of synchronization, and these are an order of magnitude harder to test than single-threaded behavior,

• most of the AJAX interaction has a lot of special cases that take a while to be mocked, because of all the possible server response issues and delays,

• like many user interfaces, JavaScript code on pages tends to change frequently as designers and usability experts change their minds about particular parts, making unit tests an investment harder to amortize

My opinion on this is: if your JavaScript codebase is mostly made up of libraries and isolated components that have a cleanly described API, you can test the “put this in, get this out” rules documented by the API using unit tests, and you will be happy. On the other hand, if your usage of JavaScript is one-shot dynamization of pages using adapted libraries (and I suspect the vast majority of JavaScript development occurs in these cases) then there isn’t really a lot to be tested: the test cases are very complex and would take a lot of time to be implemented to begin with, and might change the next day anyway.

My Christmas Gift of 2004, from my parents, was the nicollet.net domain name and some lightweight hosting. The old nicollet.net server (well, actually, small part of a server) served me well over the years, with over 100k visitors:

Total Visitors	107,104
Total Pageviews	1,318,695
Total Hits	1,650,862
Total Bytes Transferred	14.54GB
Average Visitors Per Day	74
Average Pageviews Per Day	911
Average Hits Per Day	1,141
Average Bytes Transferred Per Day	10.30MB
Average Pageviews Per Visitor	12
Average Hits Per Visitor	15
Average Bytes Per Visitor	145,756
Average Length of Visit	177sec

Not really impressive over such a long period, but until August 2008 the site didn’t contain much beyond a few files I needed on other computers, some pictures and documents I wanted to share, and perhaps small snippets about development that I uploaded once every two months.

Then, on August 2008, the blog started. I had recently uploaded a fresh install of Joomla! for managing my files, and since it more-or-less handled blog-like layouts, I tried to write a blog. That was a mistake, of course: the default install of Joomla!, even more so the 1.5 version with a lot less support for external modules and plug-ins. The best free component for comments I could find was Chronocomments, which didn’t work for all my visitors, but did work for many spammers: starting from November, I received more spam on my website than through all my mailboxes combined, totaling around 900 spam comments (and only 8 legitimate comments).

Either way, through some advertising (mainly, by writing useful things on my blog and then linking to my blog from forum threads where those articles would answer the question being asked) I managed to get a reasonable number of visitors (around 60 daily non-bot visitors).

The visitors for december are only counted up to the 22nd (for some reason, the log analysis tool doesn’t want to show more than that.

What now?

As of today (December 30th), I’m moving on to a new server. The old one supported PHP4 and an old version of MySQL, and didn’t have much in the way of freedom (only FTP access was allowed). The new one is a good old dedicated server running Debian Etch 4, on which I’ve installed myself Apache2, PHP5 and MySQL 5. I have also moved from Joomla! to Wordpress for my blog management software.

The transfer is not yet complete (I spent five hours yesterday converting all my blog articles from the old format to the new one) and I couldn’t transfer the comments. My e-mail address (firstname@nicollet.net) is down for the time being, because I have to install a new mail server myself and I won’t be able to get around it until the end of the week. I also have to re-upload my teaching material, which will also be done by next week.

The URLs are still a bit wonky (the DNS transfer was completed after Wordpress was installed, so the server still calls itself by its old name, r17474.ovh.net) but should be ironed out soon. The URL naming scheme I decided to use in Wordpress (nicollet.net/year/month/title) is different from the one in Joomla! (nicollet.net/blog/category/id-title) but I am in the process of setting up the appropriate redirections from the old site to the new one so that no articles are lost.

As far as the RSS feeds, however, I’m afraid they’ll be discontinued (partly because of the silly URL structure in Joomla! and partly because the structure of the new blog version itself has somewhat changed, and now includes articles independent of the current day, such as this one). Make sure you scroll to the bottom of the page and get the new global feed (or just click here).

Happy new year, and good reading!

The C++ language provides two flavors of functions: member functions and non-member functions. A function is something which is used like this:

result = function(arguments);

By contrast, a member function is used like this:

result = object.function(arguments);

Because of this, it’s impossible to use member functions and non-member functions in the same way: where a non-member function can be called on its own (provided that you have the arguments for it), a member function also requires an object on which it is called.

The Window Procedure Problem

This can be quite confusing to beginners, for instance when defining the window procedure in the Win32 API: this requires defining a non-member function with a certain set of arguments, and then providing a function pointer (referencing that function) to the API for registering it with a window. This usually looks like this:

LRESULT CALLBACK MyWndProc(HWND, UINT, WPARAM, LPARAM)
{
  // Implementation
}  

int APIENTRY WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
    WNDCLASS wc;  

    wc.lpfnWndProc = (WNDPROC) MyWndProc;  

    // Register the other WNDCLASS properties 

    RegisterClass(&wc);
}

A question that is often asked on beginner forums is, how do I use a member function of my Window C++ class as a window procedure?

This is, of course, impossible. The main reason why it’s impossible is that it doesn’t make any sense: a window procedure, in the Win32 API, is a procedure that will be called on every window of that window class. By contrast, a user-defined Window C++ class tends to have a “one instance = one window” approach to things, so that even if the same function is called for every window, the object on which it is to be called is different, leading to the question of how those objects are specified to the Win32 API.

A New Hope

Of course, the user could add the constraint “one window = one Win32 window class”, which means that a given window procedure will only ever be called for a single window (the question of whether using a window class to create a single window is an abuse of window classes is best left alone). Then, common sense would imply that a member function could be used as a non-member function as long as the object on which it is called is provided:

class MyWindowClass
{
public:
  LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM)
  {
    // Implementation
  }
}; 

int APIENTRY WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
    MyWindowClass windowInstance;
    WNDCLASS wc;  

    wc.lpfnWndProc = (WNDPROC) windowInstance.WndProc;  

    // Register the other WNDCLASS properties 

    RegisterClass(&wc);
}

The hope here is that C++ will somehow detect that “object.function” can be used in the form “result = object.function(arguments)” and therefore behaves just like a normal function. Of course, this doesn’t work: C++ doesn’t support closures.

Closures

By default, a C++ function pointer (the data type used to manipulate functions beyond simply calling them right away) is just a pointer to a function. This means that it can only point at a finite set of values, which happens to be the set of all available non-member functions (of the appropriate type) within your application. It does not carry any other values.

The problem is that “object.function” is not a non-member function defined within the application: it’s a member function being applied to an object. There is no way for the compiler to detect and define this function at compile-time automatically: you could have any number of objects created and destroyed within your application at runtime, and “object.function” will do a different thing for every one of these objects (because this is how member functions work, after all: behave differently on every object).

In short, there’s no workaround for the fact that “object.function” is the association of a member function (”function”) and a piece of data (”object”), and that no built-in C++ type can store both a function and a piece of data (this is commonly known as a closure, and C++ does not support these).

Of course, since closures are a fairly useful tools, a set of replacement tools have been provided: you still can’t use a normal function pointer (or member function pointer) to represent them, but you can use another variable, or another type.

The most elementary example was known from C. C APIs that let you define callbacks usually let you define callback data as well (unless they are brain-dead, which sometimes happens with C APIs). Callback data is the “data” part of the closure, while the callback itself is the “function” part of the closure. It all starts with a callback function that takes an additional “data” argument:

void myCallback(void *callbackData)
{
  MyObjectType &object = *reinterpret_cast<MyObjectType*>(callbackData);
  object.function();
} 

MyObjectType bobby;
hypotheticalAPI(myCallback,&bobby); 

MyObjectType timmy;
hypotheticalAPI(myCallback,&timmy);

Here, the ‘hypotheticalAPI’ function stores the callback and data together, then calls the callback function with the associated data as its first argument. This means that the “myCallback” function will call either “bobby.function()” or “timmy.function()” depending on which callback is activated.

This is actually the way the Win32 API is intended to work. The difference here is that you don’t pass another argument this way, but instead associate the callback data to the handle of the window. This works more or less like this:

class MyWindowClass
{
public:
  LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM)
  {
    // Implementation 
  }
};  

LRESULT CALLBACK MyWindowClassWndProc(HWND h, UINT i, WPARAM w, LPARAM l)
{
  MyWindowClass &object =
    *reinterpret_cast<MyWindowClass*>
      (GetWindowLongPtr(h, DWLP_USER)); 

  return object.WndProc(h,i,w,l);
}  

int APIENTRY WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
    MyWindowClass windowInstance;
    WNDCLASS wc;   

    wc.lpfnWndProc = (WNDPROC) MyWindowClassWndProc;   

    // Register the other WNDCLASS properties  

    RegisterClass(&wc);  

    HWND h = CreateWindow( /* args */ ); 

    SetWindowLongPtr(h, DWLP_USER, reinterpret_cast<LONG_PTR>(&windowInstance));
}

The SetWindowLongPtr function is used to associate the address of our windowInstance object to the window handle. The window procedure we register then uses the GetWindowLongPtr function to retrieve the windowInstance object, and calls its member function with the correct arguments.

Functors

Aside from the old C trick, C++ also provides the user with the ability to overload “operator()”, which means the ability to have any object behave like a function. And since objects can carry arbitrary amounts of data, having them behave like closures is a very simple task. The most naive implementation of this happens in the standard library itself: instead of having the various algorithm functions (transform, accumulate etc) take function pointers, these functions take an arbitrary type as the operation to be applied. This way, any object with a correctly implemented “operator()” can be used:

struct multiplyBy
{
  int lhs;
  int operator(int rhs) const { return lhs * rhs; }
  multiplyBy(int lhs) : lhs(lhs);
}; 

std::transform(std::istream_iterator<int>(std::cin),
               std::istream_iterator<int>(),
               multiplyBy(10),
               std::ostream_iterator<int>(std::cout,"\n"));

The implementation is quite simple: instead of defining a function pointer argument, use an arbitrary type parameter:

template<typename F>
int apply_twice(int value, F f)
{
  return f( f(value) );
} 

apply_twice(5, multiplyBy(2));
// Output : 20

However, this requires compile-time resolving of the function: since the type of the functor is a template argument, the same function template cannot be made to accept, at runtime, both a normal “int (*)(int)” function and a “multiplyBy” instance.

Boost.Function

The obvious solution, then, would be to use runtime polymorphism provided by virtual functions: make a base “function” class where “operator()” is virtual, then create a derived class template which, given a functor (or normal function pointer) wraps around that functor so that it can be used wherever the base class can. The boost library actually goes a little bit further in this respect: it provides a clean way of specifying the type of the wrapped function, and handles the memory allocation of the underlying base class, so that the functions become value types:

int apply_twice(int value, boost::function<int(int)> f)
{
  return f( f(value) );
} 

boost::function<int(int)> multiplyBy(int i)
{
  return boost::bind(std::multiplies<int>, i);
} 

apply_twice(5, multiplyBy(2));

Boost.Function also handles member functions out of the box:

struct integer
{
  int value;
  integer(int value) : value(value) {}
  int add(int other) { return value + other; }
}; 

integer i = 3;
boost::function<int(int)> add3 = boost::bind(&integer::add, i); 

apply_twice(5, add3);

The documentation for version 1.37.0 is available here :

http://www.boost.org/doc/libs/1_37_0/doc/html/function.html
http://www.boost.org/doc/libs/1_37_0/libs/bind/bind.html

A program has an object, which it needs to convert to a string. On the one hand, converting to a string is often more efficient by appending the individual sub-strings to an output channel, because the output channel is optimized precisely for that (it allocates a large memory buffer which is gradually filled) whereas string concatenation cannot reuse the memory space of one operand nor over-allocate memory for it. On the other hand, writing the string to an output channel means there will be no means of retrieving that string, because it has been output and therefore left the program.

This has led, in many languages, to the development of a channel-like object that outputs to a string instead of sending out the data. Java has java.lang.StringBuilder, C++ has std::stringstream and .NET has System.IO.StringWriter. In this regard, PHP takes a quite original route.

PHP has always heavily relied on inline tags to construct output. This means that unlike Java,  C++ or .NET programs, a typical PHP script will be regularly interrupting its normal execution process to include some raw text that is immediately output back to the user:

Hello, <?=$_SERVER['REMOTE_ADDR']?>!

Where other languages usually include text as string literals (or text loaded from external configuration files) and output these by manually sending them to a stream:

std::cout << "Hello, "
          << getenv("REMOTE_ADDR")
          << "!";

Explicit output means that it’s possible to replace std::cout with a custom string stream (or a polymorphic ostream parameter) to create a string from the output instead of directly sending it to standard output. Implicit output means there’s no “I’m writing this to standard output” indicator to replace. Sure, PHP does support the standard “use literals and print-to-string” option, using the traditional echo, print and printf functions, and it’s possible to write a program without ever using a single line of inline HTML, but it’s not an encouraged practice: quite to the contrary, Zend_View actually relies on inline HTML with its phtml files.

The PHP solution is known as output buffering. Instead of allowing additional output channels in addition to the normal “standard output” global channel, PHP allows replacing the global channel with another. This is done by using ob_start(), and is ended by either ob_get_clean() or ob_end_flush(). The former returns whatever was output since the global channel was replaced as a string, the latter outputs it to the previously active global channel. Both then restore the previously active buffer, which makes it possible to create a stack of temporary replacements of the global output channel.

This has several interesting properties. The first is that now, it is preferable to print out any kind of data either using print/printf or using inline HTML, depending on the nature of what is being output, instead of manually concatenating a string, returning it through several layers of functions, and finally printing it at some point:

<?php 

ob_start();
foreach( $data as $row )
  printf("<li>%s</li>", $row );  
printf("<ul>%s</li>", ob_get_clean());

Output buffering can also be used to capture inline HTML, of course:

<? ob_start(); ?>Hello, <?=$_SERVER['REMOTE_ADDR']?>!<? print md5(ob_get_clean()); ?>

Another interesting consequence is that now, it’s possible to prevent any output from being sent before the headers have all ben generated.This is because, by default, PHP streams data to the user as soon as it becomes available, and the HTTP response headers are, by definition, to be sent before everything else, which means the first time PHP detects an output it will send all the headers registered so far, then ignore any further headers with a warning. By starting the very first script with an ob_start(), all output is buffered until ob_end_flush() is manually called, which allows all headers to be completed beforehand without risk of accidental sending.

Any function which usually prints out data directly (such as fpassthru()) can also be captured by this.

Last but not least, output buffering allows output filtering: an optional argument to ob_start can be a function used to process the data before it’s output: when the output is extracted (sent to the previous output, or as a string) the function is called on the data and the return value is used instead. So, the above example is equivalent to :

<? ob_start('md5'); ?>Hello, <?=$_SERVER['REMOTE_ADDR']?>!

Note that all buffers are flushed in order when the script ends, so there’s no risk of forgetting to flush a buffer and having no output.

More information about output buffering is available in the PHP manual.

And until next time, Joyeux Noël.

Exceptions make the control flow of a program quite complex, since any call could possibly create an exception and thus leave the currently executing function. Even with a garbage collector, certain resources (such as files) have to be manually released. Some languages use destructors and RAII (for instance, C++) to handle scope-based release, others use an explicit using(){} or finally {} block to also add a scope to such resources.

None of this exists in OCaml.

It can be rather easily reconstructed using existing language semantics, however:

let scoped user resource clean =
  try
    let result = user resource in
    clean resource ;
    result
  with exn ->
    clean resource ;
    raise exn 

let with_input name f =
  scoped f (open_in_bin name) close_in 

let with_output name f =
  scoped f (open_out_bin name) close_out

It is a good idea (as far as code extension and maintenance) to separate responsibilities as much as possible, and to restrict use of shared data. Consider a situation where a video game developer is writing an Opponent object: that opponent should be able to shoot a Rocket. However, a rocket object on its own does not have a lot of purpose: it needs to be handled by the model code so that it moves around and explodes when it hits something, and it needs to reference some audio and video resources. The problem is that the opponent object cannot and should not have access to either the model code (quite the opposite: model code has access to the opponent instead) or a resource management entity able of providing rocket-related assets.

Of course, if the objective was to keep code as simple as possible, a quick solution is possible: make the resource management entity and the model code globally accessible, and let the opponent code access them. Even without going as far as globals, one could provide the opponent code with references to them. But the problem of separation is quite annoying, because now the opponent has more powers over the game than it should—if all that is required is to shoot rockets, then the opponent should only be provided with the ability to shoot rockets. This also makes the “shoot rocket” logic independent of the opponent (because it has to somehow be provided by the model  code) and thus more easily reusable.

In a pure object-oriented approach, there’s at least one easy answer: provide the opponent code with an instance implementing all the operations it ever needs to perform, including the “shoot rocket” operation. The opponent then calls the appropriate methods of that instance, and the instance is actually an adapter that forwards the calls to the appropriate sections of the model code.

There are two ways of eliminating the dependency of a module User on a module Used (though they may not be applicable in all cases):

• Hide the model Used behind an interface IUsed and have User call methods of IUsed.
• Have Used accept messages as a data type independent of both Used and User, have User return the necessary messages, and forward the returned messages to Used.

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.

Annealing is a process to harden metals: by repeatedly heating and freezing metal, atoms within the metallic structure are dislodged and then moved back into place, which moves those atoms that were not part of a regular structure to more correct positions, resulting in a stronger metal piece.

The underlying process is that of energy reduction: an atom in a non-regular position within a crystalline lattice has a high potential energy, but is kept into place because it has reached a local energy minimum (so moving away requires more energy than it has). By imcreasing the available energy, the atom is allowed to move out of the local minimum, and so it ends up in a location with lower energy (with a reasonable probability, though this is by no means certain). By applying this process a high enough number of times, the global minimum can be reached.

Simulated Annealing

In computer science, that process can be applied to minimization techniques: instead of exploring the problem space completely, annealing is simulating by moving around randomly in that space. In order to move towards minima, every move which increases the value can be canceled with a certain probability that increases as time passes.

For example:

let annealing steps energy initial =
  let rec aux n best best_energy current =
    if n = 0 then best else
      let current = random_move current in
      let new_energy = energy current in
      if new_energy < best_energy then
        aux (n-1) current new_energy current
      else if Random.int steps < n then
        aux (n-1) best best_energy best
      else
        aux (n-1) best best_energy current
  in aux steps initial (energy initial) initial

This is by no means the only possible approach: other variations can involve checking whether the move is upwards since the last position (instead of the best position so far) or using a different probability approach for preventing up-moves.

Genetic Computing

A common problem found in simulated annealing and genetic algorithms is the implementation of solutions as programs: since these approaches require the ability to randomly mutate a solution, and a program is usually a fickle and weak construct that can easily die if one of its parts is forcibly removed, representing programs as randomly altered entities is difficult.

One possible solution is to consider stack based-languages: these languages have very light syntax requirements and can be represented mostly as a sequence of words. Besides, the only way for a program in these languages to die is to underflow the stack (which can be easily solved by stating that reading from an empty stack yields a reasonable value, such as zero or one. My concept was to use a language which reads a single integer variable ‘x’ and manipulates a stack ’s’, and outputs a stack of numbers. These numbers are then multiplied together to yield the final result. The available instructions are:

let operations =
  [|
    "nop", (fun (s,_) -> s);
    "pop", (fun (s,_) -> !s) ;
    "dup", (fun (s,_) -> t s :: s);
    "div", (fun (s,_) -> (t s /. t !s) :: !!s);
    "two", (fun (s,_) -> 2. :: s);
    "mul", (fun (s,_) -> (t s *. t !s) :: !!s);
    "add", (fun (s,_) -> (t s +. t !s) :: !!s);
    "cos", (fun (s,_) -> cos (t s) :: !s);
    "sin", (fun (s,_) -> sin (t s) :: !s);
    "sub", (fun (s,_) -> (t s -. t !s) :: !!s);
    "min", (fun (s,_) -> min (t s) (t !s) :: !!s);
    "max", (fun (s,_) -> max (t s) (t !s) :: !!s);
    "avg", (fun (s,_) -> ((t s +. t !s) *. 0.5) :: !!s);
    "var", (fun (s,x) -> x :: s);
    "bra", (fun (s,_) -> (if t s > 0. then t !s else t !!s) :: !!!s);
    "zer", (fun (s,_) -> 0. :: s);
    "one", (fun (s,_) -> 1. :: s);
    "neg", (fun (s,_) -> -1. :: s);
    "opp", (fun (s,_) -> -. (t s) :: !s);
    "dp2", (fun (s,_) -> t s :: t s :: s);
  |]

I have altered the meaining of ‘!’ to represent the tail of the list (or, if the list is empty, the empty list), and defined ‘t’ as the top of the list (or 0. if the list is empty).

The evaluation algorithm is extremely straightforward:

let run p x =
  List.fold_left ( *. ) 1.
    (Array.fold_left (fun s (_,o) -> o (s,x)) [] p)

I then apply simulated annealing to such programs (using a program size of 10 instructions) for 10000 iterations. The energy function is simply the error between the value computed by the program and the expected value. For instance, with the function ‘fun x -> x’, simulated annealing gives me the program:

cos dup pop nop bra cos dp2 nop var nop

Which can be rewritten as:

let t = cos (if 0 > (cos 0) then 0 else 0) in t *. t *. t *. x

This is a fairly convoluted way of saying “x”. Another example, with the function ‘fun x -> x +. x *. x’:

max bra one dup nop max add var add var

The infix form here would be:

((if max 0 0 > 0 then 0 else 0) + (max 1 1) + x) * x

Which is just ‘(1+x)*x’.