Wednesday, December 16, 2009

Comet is dead long live websockets

I've just had a chance to play with the implementation of websockets
in Googles Chrome browser. This post started me off.

After a small amount of experimentation I was able to make Erlang talk to a web page using pure asynchronous message passing.

I think this means the death of the following technologies:
  • comet
  • long-poll
  • AJAX
  • keep-alive sockets
All the above are merely hacks, inadequate ways of programming round the central problem that web-browsers could not simply open a socket and do asynchronous I/O like any other regular application.

Well now things have changed, web sockets are here

It's not a question of if long-poll etc. will die, it's just a question of when.

Once the handshake is over, web sockets work more or less like regular sockets. The important point to note is that the overhead involved in managing a web socket is minimal. In interactive applications, for example, when providing auto-complete of characters that are typed into a buffer, the current AJAX technology imposes an enormous overhead since virtually all the time in the server is spend parsing HTTP headers.
Pushing data to a client has for years been a total mess. Attempts to circumvent this have involved things like long-poll and comet, or even simply just polling the server on a regular basis. All this is now irrelevant.
So let's see what this means with an Erlang example

Sending messages to a region in a browser from Erlang is extremely easy using websockets.

Add this to your web page:
<div id="tag"></div>
Then do this in Erlang:
Browser ! {send, "tag ! XXX"}
XXX will appear in the div

The server code

start() ->
F = fun interact/2,
spawn(fun() -> start(F, 0) end).

interact(Browser, State) ->
receive
{browser, Browser, Str} ->
Str1 = lists:reverse(Str),
Browser ! {send, "out ! " ++ Str1},
interact(Browser, State);
after 100 ->
Browser ! {send, "clock ! tick " ++
integer_to_list(State)},
interact(Browser, State+1)
end.
To send a message to a tagged region tag in the browser I just say Browser ! {send "tag ! message"} this could hardly be easier.

The details

If you want to try this yourself you'll need a version of chrome that supports web sockets. Then two files local_sever.erl and interact.html

They are listed at the end of this article:

To run things you'll need a local web server and Erlang.

Compile local_server.erl and start by evaluating local_server:start(). Then serve the web page interact.html from your local server.

Enjoy

Listings

-module(local_server).
-compile(export_all).

%% start()
%% This should be in another module for clarity
%% but is included here to make the example self-contained

start() ->
F = fun interact/2,
spawn(fun() -> start(F, 0) end).

interact(Browser, State) ->
receive
{browser, Browser, Str} ->
Str1 = lists:reverse(Str),
Browser ! {send, "out ! " ++ Str1},
interact(Browser, State);
after 100 ->
Browser ! {send, "clock ! tick " ++ integer_to_list(State)},
interact(Browser, State+1)
end.

start(F, State0) ->
{ok, Listen} = gen_tcp:listen(1234, [{packet,0},
{reuseaddr,true},
{active, true}]),
par_connect(Listen, F, State0).

par_connect(Listen, F, State0) ->
{ok, Socket} = gen_tcp:accept(Listen),
spawn(fun() -> par_connect(Listen, F, State0) end),
wait(Socket, F, State0).

wait(Socket, F, State0) ->
receive
{tcp, Socket, Data} ->
Handshake =
[
"HTTP/1.1 101 Web Socket Protocol Handshake\r\n",
"Upgrade: WebSocket\r\n",
"Connection: Upgrade\r\n",
"WebSocket-Origin: http://localhost:2246\r\n",
"WebSocket-Location: ",
" ws://localhost:1234/websession\r\n\r\n"
],
gen_tcp:send(Socket, Handshake),
S = self(),
Pid = spawn_link(fun() -> F(S, State0) end),
loop(zero, Socket, Pid);
Any ->
io:format("Received:~p~n",[Any]),
wait(Socket, F, State0)
end.

loop(Buff, Socket, Pid) ->
receive
{tcp, Socket, Data} ->
handle_data(Buff, Data, Socket, Pid);
{tcp_closed, Socket} ->
Pid ! {browser_closed, self()};
{send, Data} ->
gen_tcp:send(Socket, [0,Data,255]),
loop(Buff, Socket, Pid);
Any ->
io:format("Received:~p~n",[Any]),
loop(Buff, Socket, Pid)
end.

handle_data(zero, [0|T], Socket, Pid) ->
handle_data([], T, Socket, Pid);
handle_data(zero, [], Socket, Pid) ->
loop(zero, Socket, Pid);
handle_data(L, [255|T], Socket, Pid) ->
Line = lists:reverse(L),
Pid ! {browser, self(), Line},
handle_data(zero,T, Socket, Pid);
handle_data(L, [H|T], Socket, Pid) ->
handle_data([H|L], T, Socket, Pid);
handle_data([], L, Socket, Pid) ->
loop(L, Socket, Pid).

And the web page interact.html
<script src='/include/jquery-1.3.2.min.js'></script>
<script>
$(document).ready(function(){

var ws;

if ("WebSocket" in window) {
debug("Horray you have web sockets
Trying to connect...");
ws = new WebSocket("ws://localhost:1234/websession");

ws.onopen = function() {
// Web Socket is connected. You can send data by send() method.
debug("connected...");
ws.send("hello from the browser");
ws.send("more from browser");
};

run = function() {
var val=$("#i1").val(); // read the entry
$("#i1").val(""); // and clear it
ws.send(val); // tell erlang
return true; // must do this
};

ws.onmessage = function (evt)
{
var data = evt.data;
var i = data.indexOf("!");
var tag = data.slice(0,i);
var val = data.slice(i+1);
$("#" + tag).html(val);
};

ws.onclose = function()
{
debug(" socket closed");
};
} else {
alert("You have no web sockets");
};

function debug(str){
$("#debug").append("<p>" + str);
};


});




<h1>Interaction experiment</h1>

<h2>Debug</h2>
<div id="debug"></div>

<fieldset>
<legend>Clock</legend>
<div id="clock">I am a clock</div>
</fieldset>

<fieldset>
<legend>out</legend>
<div id="out">Output should appear here</div>
</fieldset>

<p>Enter something in the entry below,
the server will reverse the string and send it to the
out region above</p>

<fieldset>
<legend>entry</legend>
<P>Enter: <input id="i1" onchange="run()" size ="42"></p>
</input>
</fieldset>

</body>

Monday, June 29, 2009

Content Editable

I've been playing with the HTML contentEditable mode in Firefox.

One word awesome.

I quickly managed to put together the basis of a seamless editor. This is described in a seven part article.

The source code is available from http://github.com/joearms/contentEditableDemo/tree/master

Sunday, February 15, 2009

JSON protocols (part 1)

For a long time I have been interested in describing protocols. In 2002 I published a contract system called UBF for defining protocols. This scheme was never widely adopted - perhaps it was just to strange...

I have revised UBF and recast it in a form which I call JSON Protocols - since JSON is widely implemented, this method of described protocols might be more acceptable.

What's the problem?

Client and server interaction should be regulated by some kind of contract that is independent of both the client and server. If the client-server interaction fails, then it should be evident by examining the contract which of the parts in the system has failed. Is the problem in the client or the server?


To simplify our problem we will assume that the client and server interact by exchanging JSON messages and we will add a form of contact that will allow us to check that the sequence of messages is correct.

The File Server Contract

We'll start with a simple example and build a formal description of a file server. I'll use the familiar notion of a finite state machine to describe the operations of the server.

The behaviour of the server is completely specified by a set of
4-tuples of the form:

State x RequestMessage -> ResponseMessage x StateOut

We'll start our specification of the file server somewhere in the middle of a session. We'll assume that users must be authenticated, but we'll show how they are authenticated later.

Let's assume the server is in the state ready - meaning it is ready to accept a request. We can start by defining two state transitions:

ready x getFile -> file x ready;
ready x getFile -> noFile x stop;

This means that if our machine is in the state ready and receives a getFile message it will respond by either sending a file message and transitioning to the ready state or it will respond with a noFile message and transition to the stop state.

Here getFile and file are messages and ready and stop are states.

Attached to the message is some data structure that accompanies the messages.
We can defined these data structures as follows:

data[getFile] = {fileName:string};
data[file] = {fileName:string, fileData:string};

Having defined the data we turn to the wire protocol - what data is actually sent between the client and the server? To answer this we will give a JSON example.

Suppose we want to fetch a file called "index.txt", assume also that the content of the file is "abc" then our contract says that the following JSON terms must be exchanged:

Request =
{msg:"getFile", data:{fileName:"index.txt"}}


Response =
{msg:"file",
data:{fileName:"index.txt", fileData:"abc"},
state:"ready"}
Note that exactly this interchange must take place. If either of the messages is incorrectly typed the contract checker can detect the error and determine whether the client or server has violated the contract.
There is a simple relation between the format of the message that is actually exchanged on the wire and the, algebraic specification of the messages.

[note - I have taken liberty with JSON notation here and omitted the quote marks preceding the tags in the object name, strictly I should have written {"msg":"file" etc., but I have written msg:"file"]

What happens if a file doesn't exist? We had a rule for this:

ready x getFile -> eNoFile x stop;

The reply message eNoFile has no associated data, so no data description is necessary.

As an example, suppose we request the file "badfile" which does not exist. This is what we would see "on the wire".

Request = {msg:"getFile", data:{fileName:"badfile"}}
Response = {msg:"eNoFile", state:"stop"}

Observe that the eNoFile message has no associated data.

Why do we send the state back in the response message?

This is to avoid the situation where the server performs a silent state change that cannot be observed by the client. Suppose we have two rules:

a x s1 -> c x s2
a x s1 -> c x s3

When we send an a message we always receive a c message, but we cannot tell if the server changed to state s2 or s3. To make things clearer we always include the new state in the reply.

Now that we've seen what happens in the middle of a session, we can include details of the login and authentication phase.

login x start -> challenge x wait;
response x wait -> ok x ready;
response x wait -> badpassword x stop;

data[login] = {name:string};
data[challenge] = {salt:string};
data[response] = {md5:string};

Once we are ready we might want to list files:

ready x listFiles -> files x ready;
ready x logout -> stop;

data[files] = [{filename:string}];

This completely (and formally specifies the behaviour of a file sever)

Adding time

We can easily add time to our specification:

read x getFile -> file x read within 2 seconds;

This means that we must respond within 2 seconds.

What else?

We need some meta-information, the version number and name of the protocol, and an introspection mechanism.

Notation

I've been a bit sloppy with notation here and used a notation that I hope is 'self-evident'. The state machine syntax is trivial:

StateIn x MessageIn -> MessageOut x StateOut;

The data notation is less obvious:

data[XXX] = {tag1: type1, tag2: type2 ...}

denotes a JSON message of the form:

{"msg":"XXX", data:{"tag1":Data1, "tag2": Data2, ...}}

Where Data1 is of type type1 and Data2 is of type type2. Observe I have only
used the type "string" in my examples, but this is easily extended to JSON primitive types, enumerations and sequences of types.

I also used the notation [X] (in the definiton data[files] =
[{filename:string}]. [X] means an array (or sequence) of type X.

Contract Checking

Now what we have our state machines and message we can easily write a contract checker.

Given the state of the finite machine and then next message we can easily check if the client and server are correctly responding to protocol messages as required by the specification. Each message has a data type specification can easily be checked.

Comments on this are welcomed.

In Part 2 I will post Erlang bindings for the protocol specification and code for a contract checker.

Other implementers might like to implement bindings and contract checkers for their favorite languages. having done this we could start writing multi-language applications based on formal and checkable contracts.




Wednesday, January 28, 2009

Micro Lightweight Unit Testing

I'm often asked the question "what unit testing framework do you use?" The answer is usually I don't, but I do use a form of micro testing that is built into Erlang.

In Erlang, every assignment of the form Lhs = Rhs where the Lhs is a ground-term and Rhs is a non-ground term can be viewed as an assertion, or unit test, since it can possibly fail.

So when we write:

    {ok, S} = file:open("filename", [read])
We're writing assertion to the effect that opening "filename" for read will succeed.

So how do I write unit tests?

To answer this question, I'll walk you through how I'd write the code for an efficient Fibonacci function.

I'm actually following the three rules of TDD so Uncle Bob and the agile crowd should approve of this method ...

I'll show you the order in which I implement the code. Often we show the final version of some code, but not the order in which the code was written. This time I'm going to show the precise order in which I wrote the code, and show how and when I tested and ran the code.

I'll start by defining a module, with a unit test.

Step 1) First write a micro-unit test:

-module(fib).
-compile(export_all)

test() ->
0 = fib(1),
1 = fib(2),
2 = fib(3),
6765 = fib(20),
ok.
Where did I get these values from? - I checked on the wikipedia - I was unsure if the Fibonacci series starts 0,1,1,2,.. or 1,1,2,3.

This code won't compile correctly, since the fib function is missing.

Step 2) Write the fib function:

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
This version of the Fibonacci function is recursive and very inefficient. But I'll implement it first, because I have high confidence that the code is correct, and because I'll use it later to test the efficient version of the code.


Step 3) I compile and test the module


The module now looks like this:

-module(fib).
-compile(export_all).

test() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
6765 = fib(20),
ok.

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

I compile and test it:

1> c(fib).
{ok,fib}
2> fib:test().
ok
So now I have something that works.

step 4) Add unit tests for fastfib

test/0 looks like this:

test() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
6765 = fib(20),
0 = fastfib(0),
1 = fastfib(1),
1 = fastfib(2),
2 = fastfib(3),
K = fib(25),
K = fastfib(25),
ok.
Here I check that fastfib returns the same value as fib with the lines
  K = fib(25),
K = fastfib(25).
Step 5) Write the fastfib function.

The entire module looks like this:

-module(fib).
-compile(export_all).

test() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
6765 = fib(20),
0 = fastfib(0),
1 = fastfib(1),
1 = fastfib(2),
K = fib(25),
K = fastfib(25),
ok.

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

fastfib(0) -> 0;
fastfib(N) -> fastfib(N, 1, 0).

fastfib(1, A, _) -> A;
fastfib(N, A, B) -> fastfib(N-1, A+B, A).

Step 6) Compile and test.

I compile and test the module, as in Step 3)

Step 7) I change the exports of the module and change

-compile(export_all). to -export([test/0, fib/1]).

I rename fastfib to fib and fib to slowfib.

Done

Step 8) Quickcheck

I don't have John Hughes Quickcheck on my machine, but If I did, I could write a test case that said "forall integer N >= 0, fib(N) and fastfib(N) compute the same value" - quickcheck would then generate zillions of tests that test this property.

Finally

I have used the convention of exporting a function test/0 in several modules. I also have a simple program which checks a large number of modules. It checks if the module exports the function test/0, and if so evaluates (catch Mod:test()) if this returns ok, then the module has passed its test. If not I print an appropriate error.

Note how when I wrote the module I wrote a test case, then implemented the function it was testing, then wrote another test case, then more code etc. This way I'm interleaving writing test cases with implementing the test case. This way I write the code in a number of small steps, and if something goes wrong I can just reverse the last step.

When I'm finished with the code all the test cases are ready - so I don't write the code then the test cases, I interleave the two.



This is my micro-lightweight unit test framework

This is what I use for my hobby-hacks. For paid work I use the OTP test server.