Monty hall and Bayesian probability theory

Jeff Atwood discusses the “Monty hall” problem. I made a comment about why I believe people’s intuition is often wrong when presented with the problem: I believe it is due to the way probability theory is taught in schools and universities. The notion of probability simply as an extension of classical logic as presented by Edwin Jaynes matches intuition much more closely. To solve the Monty Hall problem we need three simple principles (which apply to a wide range of problems):

• Probability is about information. Forget notions of “random” experiments, e.g., the outcome of throwing a die is about the laws of physics - there is no magical randomness built into the die causing it to come up with each side equally often “in the long run” (what ever that means). If we know the laws of physics and have enough information about the experiment we might assign other probabilities to the outcomes. This means that if new information is obtained the probability changes!

• In the name of science, we shall not make any unwarranted conclusions, and we promise to use all the information at hand, not deliberately discarding information (for what ever reason).

• We use the laws of probability theory.

The first point is where the problem lies. In fact the probabilities are just a formalization of the information we have. This is why we always condition the probability on some information e.g., P(A | I) is the probability of proposition A given the information I.

Let’s solve Monty Hall using the principles presented in Jaynes’ book. Notice that these techniques are completely general and can solve many different problems of this nature; the key in Monty Hall is not to make any unjustified conclusions, but simply consider all the information at hand!

Lets name the doors A, B and C, and let us assume that we initially selected door A (the argument applies for any other initial choice as well). Let us write I for the information we have initially (before opening any doors) - this includes the rules of the game. More precisely I is the conjunction of statements:

* We have chosen door A.

* The host knows where the car is, and may only open a door that does not contain the car.

* The host may not open the door we selected (A) (even if it does not contain the car).

We formalize the information I in probability equations below. Let us consider three mutually exclusive and exhaustive propositions

A = the car is behind door A;

B = the car is behind door B;

C = the car is behind door C

By the principle of indifference, given only the initial information, I, we have

P(A | I) = P(B | I) = P(C | I) = 1/3

Notice also that so far intuition is completely clear.

Let us now assume that the host opens door C. Let H be the statement:

H = the host opened door C

(the argument is similar for any other choice). The important point here is that we are given additional information beyond our prior information, I. Now let us first derive the correct solution, we then analyze where peoples intuition usually goes wrong.

By the rules of probability theory (specifically Bayes theorem) we have

P(A | HI) = P(A|I) P(H | AI)/P(H|I)

The quantity P(A|HI) is what we are interested in: the probability of the car being behind door A given all the information available to us.

We know P(A|I) is 1/3 so we can focus on P(H|AI) and P(H|I) - notice these are both probabilities about the host’s actions - probabilities that are very relevant to the problem (by the equation above), but also probabilities that most people would not consider to analyse (because probability is taught the way it is)! The former is the probability of the host opening door C given the car is behind door A; the latter is the a-priori probability of the host opening door C given only the information I. The former, P(H|AI), is the most simple: given we know that the car is behind door A what is the probability of the host opening door C. Since we have no information about which door the host opens when the car is behind the door we selected, the principle of indifference applies and we have:

P(H|AI) = P(not H|AI) = 1/2

Now consider P(H|I): the a-priori probability of the host opening door C. Since propositions A, B and C are mutually exclusive and exhaustive, the rules of probability theory imply

P(H | I) = P(H | AI)P(A|I) + P(H | BI)P(B | I) + P(H | CI)P(C | I)

We know that P(H | CI) = 0 because by information I, the host may not open door C if the car is behind door C. We already figured out P(H | AI) and P(A|I) so the first term is 1/2*1/3 = 1/6. Also we know P(B | I) = 1/3. Now we can focus on P(H | BI): the probability of host opening door C when the car is behind door B and we have chosen door A. But here the rules of the game are clear: the host must open door C in this case since he may not open A and may not reveal the car. Hence P(H | BI) = 1. We get:

P(H | I) = 1/6 + 1*1/3 = 3/6 = 1/2.

We now have all the quantities needed to calculate P(A | HI):

P(A | HI) = 1/3 * [(1/2)/(1/2)] = 1/3. Hence P(B | HI) = 2/3 and we should switch doors!

The technique is completely mechanical. I have not used any clever arguments or mathematical ingenuity: only the rules of the game, the principle of indifference and the laws of probability theory. All calculations could be performed by a machine with these inputs.

So where does our intuition go wrong? Two places, I believe. First because of schooling our intuition tells us that somehow we can only reason about “random” events. Instead we should focus on information e.g., ‘the car is placed “at random” behind a door’ versus “we are given the information that there is a car behind one door and sheep behind the two others.” Once we free ourselves to consider probabilities as expressing the information we have available, it is natural that the probabilities change when we obtain more information. This is crucial. The second, I believe, is a consequence of the first: most people seem to identify the following two statements in the Monty Hall problem:

* the host opens door C

* the car is not behind door C

But these two pieces of information are not equivalent when we know the rules of the game (i.e. given our prior information). Considering them equal would violate our commitment to science, to be objective and to consider all the information at hand

To illustrate let us analyse a variant of Monty Hall where “H” means the latter instead.

Given this alternate piece of information, our first step is still to apply Bayes theorem so:

P(A | HI) = P(A|I) P(H | AI)/P(H|I)

We still have P(A|I) = 1/3. P(H|I) is the probability that the car is not behind door C given our initial information. Since H = not C, and since A, B, C are mutually exclusive and exhaustive, the rules of probability theory imply

P(H | I) = P(not C|I) = P(A or B|I) = P(A|I) + P(B|I) = 2/3

Now P(H | AI) is calculated by classical logic: since A implies not C we have P(H | AI) = 1. Hence:

P(A | HI) = 1/3 * 1/[2/3] = 1/2

Which is the false result that most people’s intuition prefer. This is the correct conclusion, but for a different game than Monty Hall, namely the game without a host where you simply get an additional information about where the car is not.

Notice that we easily analysed both variants of the game using simple probability theory, and in its interpretation as an extension of classical logic, the intuition follows along nicely. The key is to use all the information at hand, not discarding any information that could be of relevance to the problem (i.e. we got the information that host selected C, not that door C had a sheep behind it).

Posted in General, model view controller | Comments Off

One aspect of lazy computation

I’ve often needed to do a combination of filtering and mapping on arrays. E.g. in a Ruby on Rails app, I might have a list of “RecurringActivation” model objects which have a product_id and an integer period. Now I would like a list of product_ids where the current time “matches” the period; in code this might be:

#version 1 - 'functional'
cur_period = Time.now.month - 1
RecurringActivation.find(:all, :select => "product_id, period").select { |r|
  cur_period % r.period == 0
}.map &:product_id

#version 2 - 'imperative'
cur_period = Time.now.month - 1
result = []
RecurringActivation.find(:all, :select => "product_id, period").each { |r|
  result << r.product_id  if cur_period % r.period == 0
}

In the first version I compose functions (methods) ’select’ and ‘map’: the blocks have no side-effects, and this is why I call it ‘functional.’ This is shorter and more clear. Of course, this is implemented by the library using iteration and imperative assignment, but at least my code feels functional.

In the second version I use ‘each’ with a block that does both filtering and ‘mapping’ in one step: I add the product_id explicitly to the products array for each object which satisfies my criterion.

Notice that the first version first produces a complete filtered list which is then passed on to the map method which produces a complete mapped and filtered list: the list is iterated twice, and an intermediate array containing only the filtered objects exists in memory and is later collected as garbage. In the second version the list is only iterated once, and such an intermediate array of filtered objects is never allocated. Hence one might choose the latter for performance reasons.

Now consider the same in Clojure or any lazy functional language. We might have (no active record here):

krukow:~/Projects/private/okooko-prod/tmp$ cl
Clojure
user=> (def recurring_activations '({:product_id 1 :period 2}
                                    {:product_id 2 :period 3}
				    {:product_id 3 :period 2}))
#'user/recurring_activations
user=> (def res
         (map #(do (println "map") (:product_id %))
             (filter #(do (println "filter") (= 0 (mod (:period %) 2)))
                 recurring_activations)))
#'user/res
user=>

Nothing has been mapped or filtered yet since Clojure is fully lazy. So res is now a lazy seq which will compute exactly what is needed on demand. Now think about what will happen if I just peek at the first element of res… In a non-lazy language, already the entire recurring_activations list would have been filtered (printing “filter” three times), then that result would have been mapped (printing “map” twice) and finally the first element would be looked up. So the output would be
“filter”
“filter”
“filter”
“map”
“map”
(return first element of list).

What happens in Clojure? It prints “filter” “map” and gives the first element:

user=> (first res)
filter
map
1
user=>

In effect we don’t need an intermediate list containing the filtered elements which is then garbage collected. Notice also that if we just look at the entire list (recomputing res first) we get:

user=> res
(filter
map
filter
filter
map
1 3)
user=>

So the side effects are evaluated in a different order than had we realized the entire filtered list first. This can be counter intuitive when one is used to eager languages (which all mainstream languages are); however, once understood laziness can be extremely powerful and elegant.

In effect, in lazy languages we can compose functions that work on entire sequences, e.g., map and filter, to obtain a lazy sequence which evaluates the all of the composed functions on each element in sequence.

If that sounded abstract and poorly phrased, I can try to say it more concretely: In Ruby (or Java) I would need to write a new function: filter_and_map taking two “blocks”/”procs” and a list, then using e.g. “each” on the list and apply first the filter “proc” then the map “proc” — the existing functions “map” and “select” can’t help me. In Clojure (or Haskell) I can simply compose the existing library functions filter and map to obtain the same thing:

(def filter_map
	(comp (partial map :product_id)
	          (partial filter #(= 0 (mod (:period %) 2)))))

or just use it inline

user=> (def res
	(map :product_id
	 (filter #(= 0 (mod (:period %) 2)) recurring_activations)))
#'user/res
user=> res
(1 3)
user=>

Posted in Clojure, performance | No Comments »

Clojure event sourcing

Event sourcing:

Event Sourcing ensures that all changes to application state are stored as a sequence of events. Not just can we query these events, we can also use the event log to reconstruct past states, and as a foundation to automatically adjust the state to cope with retroactive changes.

I recently watched an InfoQ interview with Greg Young where he discusses an interesting architecture that uses event stream processing. I thought their architecture sounded very interesting, but I did not go into ‘research mode’ to dig into it. Later I came by Jonas Bonér’s blog on “Real world scala” and saw an example of event sourcing using actors in Scala. I thought it would be a good exercise to implement a similar example in Clojure, and perhaps it would also be interesting to compare the solutions and see the effect of the languages on the implementation.

As Clojure focuses on concurrency it was natural to start thinking about what ‘concurrent’ event sourcing would mean and how to implement it.

Sequential Clojure implementation. For context, read Fowler’s article on event sourcing, and for comparison Jonas Bonér’s Scala implementation.

Modeling. Scala uses classes and actors for modeling ships and their state. A ship is an actor that receives events (messages) and reacts to those by updating its internal state, i.e., its location (e.g., departure event, arrival event).

Clojure has agents which are similar to actors. Agents are simpler and there are more functions that act on agents than on Actors; for example, in Clojure it is possible to directly read the state of an agent (using (deref x) or @x) — this is not possible with actors since they are distributed (at least programmed as if they were distributed).

I’ve used two additional Clojure features in implementing event sourcing: watchers and meta-data. Watchers are a form of callback attached to agents. The callback is called synchronously with the agent actions and “derefs of the agent in the callback will see the value set during that action.” I am using watchers to record the events that are sent to each ship. This decouples the code dealing with event storage from the state-changing functions sent to agents. The state of an agent is the location of the ship it represents. So we can get the location of a ship at any time simply by deref’ing the agent representing the ship (with actors this is more complex as one has to send a message to the actor and receive a message with the answer). I decided to use meta data attached to the location to represent the event that caused a move to that location. For example

user> @(first agents)
{:country "At sea", :city "At sea"}
user> ^@(first agents)
{:agent 0, :time #<Date Sun Feb 22 19:49:59 CET 2009>, :type :depart_for,
:loc {:country "Sweden", :city "Malmö"}}
user>

In general, I think it is possible to implement sequential event sourcing reasonably elegantly in Clojure using agents, watchers and metadata. The agents store the state that can change, the watchers record the events that cause the changes by looking at state meta data. The invariant should be that if an agent moves from state s1 to state s2 then (meta s2) should store the event that caused a transition from the s1 to state s2. Then if one knows the initial state, and all the events it is possible to reconstruct the entire sequence of states.

Our watchers are quite simple: (notice the cool syntax #(meta @%). A shame I couldn’t write #(^@%) it looks like I’m swearing! that would be cool)

;;Record event history
(def events (atom (map #(meta @%) agents))) 

(defn event_logger
  [idx a changed]
  (if changed
    (swap! events conj (meta @a))))

(defn add-watchers []
  "associate a watcher with each agent
   the watcher logs the events for that agent"
  (dotimes [i NUM_SHIPS]
    (add-watch (agents i) i event_logger)))

Concurrent event sourcing A natural question to ask for Clojure is “what if there are multiple concurrent event sources?” Is it still possible to do event sourcing? I don’t think so; at least not is a manner as powerful as with sequential events. Since Fowler defines event sourcing as ensuring “(…) that all changes to application state are stored as a sequence of events.” We already have a problem: when events can occur concurrently one must serialize them in order to store them as a sequence. One could try and timestamp all events and store them as a set, but this is sensitive to timing an scheduler issues. Even if stored as a set of timestamped events, how would one replay these events in a way that ensures that the global program states are the same in the replayed program? This would be dependent on thread scheduler timings.

It is of course possible to do the less advanced use cases of event sourcing, e.g. event querying and analysis (I guess that is concurrent event stream processing).

Anyway, if anyone is still reading the Source file link.

Posted in Clojure, General, instanceof | No Comments »

Understanding Clojure’s PersistentVector implementation

One of the unique features of Clojure is that the core data structures are persistent (immutable with efficient structural sharing). This includes data structures Vector and Map that are mutable in most other languages. To be useful, operations on persistent data structures need to have performance characteristics that are similar to their mutating counterparts; e.g., the cost of random access on a persistent vector (put/get) needs to be comparable to random access to a mutable vector. Clojure manages to achieve this. Here we focus on understanding the Clojure implementation of Vector: PersistentVector.

The basics. PersistentVector stores its elements in arrays, each array having at most size 32. One can think of the arrays as forming a wide balanced tree with each node having at most 32 children. Here is an example of what a size 32² = 1024 PersistentVector tree might look like.

The root of the tree is a pointer to a size-32 array (”blue”) which has 32 children (”red”). The 32 red arrays each have 32 references to actual 1024 objects stored in the PersistentVector.

Fetching elements (get). The key to understanding PersistentVector is to look at the binary representation of the numbers that index the vector. Java uses 32 bits for ints with signed two’s-complement representation. Examples:

One can think of this binary representation as divided into chunks of 5 bits, represented in colors here. These “chunks” are mapped to levels in the tree: for example, when fetching the element at 16, one looks at the the “blue” bits (00000) — this determines the index at the root child array (0); following that pointer, the “red” bits (10000) determines the index at the first level (16). When fetching index 49 the blue bits index to 1 and the red bits index to 17.

In this case the depth of the tree is 2: the cost of lookup is following two pointers and some bit computation. In general the cost of lookup is proportional to the height of the tree, i.e., O(log₃₂ n) where n is the number of elements in the vector. In practice the height is no more than 7.

Fetching the n’th element in PersistentVector is done with the nth method.

public Object nth(int i){
 if(i >= 0 && i < cnt)
 {
  if(i >= tailoff())
   return tail[i & 0x01f];
 Object[] arr = root;
 for(int level = shift; level > 0; level -= 5)
   arr = (Object[]) arr[(i >>> level) & 0x01f];
 return arr[i & 0x01f];
 }
 throw new IndexOutOfBoundsException();
}

Ignoring the ‘tail’-part, the code uses an instance variable: shift which is determined by the height of the tree: shift = 5*(h+1) where h is the height of the tree (defined here as 0 for an empty tree). Another way to think of the shift variable is that it determines how many bits to right-shift the bit representation of an integer to move for a certain block (color) of interest to be the rightmost block. For example shifting 0000110001 (49) with 5 gives 00000000001 which is exactly the “blue” index.

In general shift determines the right-shift needed to access the root index, i.e., for the block of bits that index into the root array to become the right-most block. The tree is searched from the most significant blocks (root, and it’s children) towards the least significant blocks (the “high levels” or leaves). Notice that for any integer i, if we mask i’s bit representation with 00…011111 we get the five right-most bits of i. The expression i & 0×1f does this as 0×1f is 011111.

Insertion (put).
Insertion is more tricky. Here we consider only the ‘cons’ method which appends an element to the end of the vector. The method which replaces the element at an index is easy once ‘cons’ and ‘nth’ is understood. Of course, since PersistentVector is immutable ‘cons’ really returns a new PersistentVector object which is equal to the old one except that it has the new element at the end. With cons, the tree grows only in a balanced way: elements are added at the deepest level at the rightmost array. If the PersistentVector contains a number of elements which is a power of 32 (e.g., 1024 = 32²), the height of the tree is increased by one and there is now “room” for 32 times more elements. In our example from before, suppose we add an element at the end of the vector. We obtain this tree:

Notice that the entire old PersistentVector is shared with the new PersistentVector! No copying is involved in this particular case.

The tail… Actually (to be precise) this happens not exactly at powers of 32 but slightly delayed: at the insertion of the 33rd element after a power of 32. E.g., 1024 + 33 = 1057. As you can see from the figure above, an entire size-32 array is inserted at the lower right-most position (instead of a size 1 array with the new element). This is an optimization. There is a special instance variable tail of size at most 32. The tail array is a sort of buffer where elements are appended until a full size-32 array can be placed in the tree. This makes “batch” insertion faster: suppose you creating a new PersistentVector from another collection type, e.g., a LinkedList. Since PersistentVector is immutable this is done by starting with the empty vector and then repeatedly ‘cons’ing elements from the LinkedList to obtain a new vector. E.g.,

static public PersistentVector create(List items){
	PersistentVector ret = EMPTY;
	for(Object item : items)
		ret = ret.cons(item);
	return ret;
}

This also explains the ‘tail’ code in the nth method above: If we a getting an element which happens to be located in the tail buffer at present (there can be from 0 to 32 elements with this property), we simply access it directly. This is done by looking at the 5 least significant bits of the index.

While the code for ‘cons’ is intricate, the idea is reasonably simple as illustrated by the above figure. I will end this post with the actual code. If anyone is interested, I can go into the details of the implementation.

public PersistentVector cons(Object val){
	if(tail.length < 32)
		{
		Object[] newTail = new Object[tail.length + 1];
		System.arraycopy(tail, 0, newTail, 0, tail.length);
		newTail[tail.length] = val;
		return new PersistentVector(meta(), cnt + 1, shift, root, newTail);
		}
	Box expansion = new Box(null);
	Object[] newroot = pushTail(shift - 5, root, tail, expansion);
	int newshift = shift;
	if(expansion.val != null)
		{
		newroot = new Object[]{newroot, expansion.val};
		newshift += 5;
		}
	return new PersistentVector(meta(), cnt + 1, newshift, newroot, new Object[]{val});
}

private Object[] pushTail(int level, Object[] arr, Object[] tailNode, Box expansion){
	Object newchild;
	if(level == 0)
		{
		newchild = tailNode;
		}
	else
		{
		newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
		if(expansion.val == null)
			{
			Object[] ret = arr.clone();
			ret[arr.length - 1] = newchild;
			return ret;
			}
		else
			newchild = expansion.val;
		}
	//expansion
	if(arr.length == 32)
		{
		expansion.val = new Object[]{newchild};
		return arr;
		}
	Object[] ret = new Object[arr.length + 1];
	System.arraycopy(arr, 0, ret, 0, arr.length);
	ret[arr.length] = newchild;
	expansion.val = null;
	return ret;
}

Posted in Clojure | 1 Comment »

Happy New Year!

Can’t remember the last time I laughed so much.

http://www.yankeepotroast.org/archives/2008/09/11_words_that_s.html

Got the Link from Ryan Tomayko’s (great) blog.

Posted in General | No Comments »

IE doesn’t understand HTML or HTTP

The so-called “web”-browser Internet Explorer version 7 (and probably all versions below) doesn’t get HTML or HTTP. In a recent project for a client we’ve been building an advanced, 100% JavaScript client application that had to run in IE7 (as a minimal requirement). The application is rather complex and has to live as a component in every (darn) webpage/webapp on the client’s intranet, including all legacy apps; essentially, the applications include this component by inserting a script tag in their pages. The component’s most basic job is to help the user navigate to the existing multitude of intranet applications, supplying these applications with appropriate input (e.g., navigate to the customer mangagement app with a customer reference as input).

Now these legacy applications are of different ages and have been developed in various technologies, with varying quality and standards-awareness. Now these requirements brings a bunch of problems, and I won’t start complaining too much here. Instead I’ll just focus on one issue: character encodings! One of the aspects of this scenarios is that the applications are using different character-encodings, e.g., ISO-8859-1 and UTF-8. This gives the following requirements.

• Cross page (cross encoding) navigation. For example, our client app often has to navigate from a UTF-8 encoded page to an ISO-8859-1 encoded page, transferring properly encoded parameters from the first page to the second.
• Localization. The client app is available in various languages; together with the requirement that it must exist in UTF-8 and ISO-8859-1 encoded pages, this means that the actual JavaScript being sent on the wire must be available in different languages and encodings, based on the browsers settings.

You’d expect these things to be pretty basic stuff for an HTTP based app; something that would be easy in a version 7 browser.

Cross page (cross encoding) navigation

For various reasons irrelevant here, our client app navigates to an application by dynamically creating a form with method “GET”, and plugging in the URL and the parameters for the receiving application, i.e.,

<form method="GET" action="URL">
<input type="hidden" name="pname" value="pvalue" >
…
</form>

There is an implicit attribute called ‘accept-charset’ which according to HTML 4.01 satisfies:

“This attribute specifies the list of character encodings for input data that is accepted by the server processing this form. The value is a space- and/or comma-delimited list of charset values. The client must interpret this list as an exclusive-or list, i.e., the server is able to accept any single character encoding per entity received. The default value for this attribute is the reserved string “UNKNOWN”. User agents may interpret this value as the character encoding that was used to transmit the document containing this FORM element.”

The problem with IE7 is that it ignores the accept-charset property entirely on forms. In fact, it instead does the default behaviour for “UNKNOWN”, i.e., “the character encoding that was used to transmit the document containing this form element.” Actually, to be precise it doesn’t even do that either: It turns out the IE7 encodes the form according to the current value of document.charset. Fortunately it is possible to set document.charset using JavaScript, this means that it is possible to control the encoding of form input data by setting document.charset just before the form submits. And this works. Problem solved. Kind of …

Unfortunately, this hack turns out to trigger a somewhat strange and nasty bug: After form submission, IE navigates to the desired page and input data is encoded according to document.charset, which is just what we want. However, if you click the ‘back’-button on the next page, IE navigates back to the original page, but the document.charset property somehow persists which means that the page is not interpreted with the correct encoding. OK, so we should clean up after ourselves: One would think that restoring the document.charset to it’s original value after calling form.submit() would work: it doesn’t.

After some experimentation I found that the following works. To submit a form with input data encoded in a particular encoding:

1. on document load, store the original page encoding
2. on form submit change the value of document.charset to the desired encoding, e.g., “ISO-8859-1″
3. on ‘beforeunload’ restore document.charset to it’s original value.

Script character encodings

Our JavaScript client app sometimes lives in a UTF-8 encoded page, sometimes in an ISO-8859-1 encoded page. The client app is loaded by including a <script> tag that points to a servlet that delivers the JavaScript code (customized for the requesting user and his preferred locale). By default when IE loads script, interprets the bytes it receives as characters in the encoding of the current page. However, it doesn’t tell the server which encoding that is. More specifically, our servlet receives a request for the JavaScript client with these HTTP headers:

Accept : */*
Referer : http://localhost:10045/wps/portal/sn
Accept-Language : da
UA-CPU : x86
Accept-Encoding : gzip, deflate
User-Agent : Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322; .NET CLR 2.0.50727; InfoPath.1; MS-RTC LM 8; .NET CLR 3.0.4506.2152; .NET CLR 3.5.30729)
Connection : Keep-Alive
Cache-Control : no-cache

Furthermore, even if we explicitly tell IE which encoding we have chosen, it will still ignore that and use the page encoding. More specifically, even if we return this HTTP:

Content-Type: application/javascript; charset=UTF-8

IE ignores the Content-Type charset. In other words: if we choose as a default (when no Accept-Charset header is present) to deliver the script in UTF-8 encoded, it breaks for ISO-8859-1 pages, and vice versa. So what to do? IE apparently doesn’t speak HTTP.

It turns out that one should use a script tag with a charset property to tell IE how to interpret the script. Ironically this means that on UTF-8 encoded pages one would need to say <script charset=”ISO-8859-1″>. In other words, it is not the HTTP headers describing the resource that describes its encoding. This must be know in advance by all documents that link to the resource by embedding a charset property. Yet another reason that these are tough times to be RESTful…

Posted in General, model view controller | 2 Comments »

More Clojure news and links

Clojure Pipe Clojure blogger and user Bill Clementson has used Yahoo Pipes to create a Clojure mashup feed. This should turn out a good source of Clojure info. Bill’s intro is here, and the pipe is here.

Improved Emacs setup. Bill also posted his Emacs setup. Looking forward to implementing something like that as my setup.

Atoms: uncoordinated and synchronous Rich Hickey added a new reference type with concurrency semantics called atoms. Clojure now has four reference types, each with a unique concurrency semantics: vars (changes isolated within thread), refs (synchronous & coordinated), atoms (synchronous and uncoordinated) and agents (asynchronous & uncoordinated).

Mutual recursion. Using ‘trampolines’, Rich Hickey added support for mutual recursion.

Misc Clojure Podcast w. Stuart Halloway.

Posted in General | No Comments »

Annotated Clojure links - part 1

RESTafarians will tell you that hypermedia is one of the essential ingredients of REST (and the web in particular), and that most people aren’t taking this seriously enough. In my last posting I claimed that

I will write a number of blog postings about my experiences with Clojure. [...] However, to my knowledge, there is less information about how to actually program Clojure.

Well, my knowledge was wrong. Surprise, surprise — I’m not the first person to discover Clojure, be excited and decide to blog about it…

So instead of showing you Clojure fibonacci, (prn “hello world”) and writing imprecisely about functions and macros, I’ll hyper-point to to high-quality information on ‘getting started with Clojure’. If nothing else, my links will increase the PageRank of those blogs So here is my RESTful description of one path to Clojure.

Readers please add your high-quality Clojure links and provide a reasonable description in the blog comments.

Part I - getting started

Clojure theory

Get excited: Clojure for Java Programmers

Get excited by watching the Clojure videos. For the basics, see Clojure for Java Programmers 1 and 2, with accompanying slides. This is great quality information targeted directly at Java programmers. You should have a strong background in Java and be knowledgeable of Java concurrency (I personally recommend Java Concurrency in Practice by Brian Goetz et al.).

Re-iterate your understanding, and go deeper: comparison with other Lisps

If you are ready to dig deeper into this: Clojure for Lisp programmers 1 and 2, with accompanying slides. There is even a transcript of the audience questions for part 1.

The Clojure website

There is a lot of information on the website. To me, this information made the most sense after having seen the videos. I particularly like the essay: Values and Change which explains Clojure’s functional approach to mutability and state. Furthermore, sometimes when watching the videos you’ll want to clarify something. A good way to do this is reading the API docs on the site (which is quite precise) and then open up a REPL (see next step) and try it out.

A Clojure environment

In order to get Clojure up and running you need to setup a working environment containing Java 5 or 6, Clojure and some kind of IDE or text editor. I’ve had success with Aquamacs (which is an Emacs for Mac).

Emacs & Unix: Clojure, Emacs and Slime/Swank on Ubuntu 8.10

Slime/Swank is a development environment for Emacs. Adapting this guide to Mac and Aquamacs was easy. A couple of useful Emacs commands:

• C-x C-e (Ctrl+x then Ctrl+e or “hold Ctrl then press x then e the release”). Send the current expression (to the left of cursor) to Slime.
• C-c C-d C-d. Show docs for the current symbol.
• C-c RET. Macro-expand once.
• M-.. Goto (edit) definition of current symbol; and.
• M-,. return from Goto (edit) definition of current symbol.

Others: Eclipse IDE, Netbeans plugin, Vim anyone?

I only have experience with the Emacs setup - it works fine so far.

If you are annoyed with Aquamacs keeping opening windows on you:
(custom-set-variables
‘(one-buffer-one-frame-mode nil nil (aquamacs-frame-setup)))

Bill Clementson is currently blogging Clojure. He has a setup posting where he is able to run JSwat Java debugger with Clojure. More detailed information about debugging with JSwat here.

I plan to go into depth on various parts of Clojure in the next couple of postings. It will be the same style of annotated links, possibly with discussion if I feel I have anything interesting to say.

Posted in General | Comments Off

The need for Clojure

It is a need usually provoked after experiencing an emotional conclusion to a difficult life event, such as the breakdown of a close interpersonal relationship [or an unreliable concurrent program, editor] or the death of loved one [or an old familiar programming language, editor]… A person with a high need for closure prefers order and predictability and is decisive [...]

[selected, edited parts from Wikipedia on the need for closure ;-)]

Posted in Clojure | 6 Comments »

Jeene update: Performance, features and backlog

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

Performance examples

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

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

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

What can Jeene do right now?

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

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

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

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

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

New in latest svn commit

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

Consider this example:

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

Result: 

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

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

Check back for more later…

Posted in General | 2 Comments »