khigia

It all started as a loop in bash

2009-10-07T00:00:00+08:00

Once upon a time (and quite a few other times), I needed to start a process and watch it’s status to restart it in case of crash (yeah, this kind of things still happens).

It all start with a simple bash script:

until $CMD
do
  echo "crashed! restart in 1 second"
  sleep 1
done

And then I needed to send alert in case of crash, to stop the process on request and to query the status. At this point, I should have moved away from bash … but I didn’t. Worst than that, I stole idea on the web to add an HTTP API … in bash, yes. Why not monit? not even half the fun!

So now there is this big script, with the wonderfull name of “runloop.sh”, hosted on github.

Following are use examples.

start
Start the command line and monitor the process from another background process. The “myAppID” is a simple identifier of the instance of the running program. This create files to log the pid of the app, of the monitor, and also one file with monitor logs. If myapp crash or stop with exit code different from 0, it is restarted.

shell> ./runloop.sh start myAppID /usr/local/myapp/bin/myapp --be-nice

status
This print a message “running” or not, and exit with code 0 if running.

shell> ./runloop.sh status myAppID

stop
Send the kill signal to process identified by myAppID.

shell> ./runloop.sh stop myAppID

HTTP:
Direct browser to http://localhost:9000/myAppID to get status or to stop myAppID.

shell> ./runloop.sh http

Ubigraph view of pagerank result

2009-06-04T00:00:00+08:00

This post is a sequel to the previous post about visualization of random graph through Ubigraph.

This time, I implemented a very simple pagerank algo (functor Pr) to set the size of the vertices.


./socnet.byte -n 320 -ubi


./socnet.byte -n 520 -ubi

Random graph generation example

2009-05-30T00:00:00+08:00

Have been playing around with the beautiful ocamlgraph library. I also installed xmlrpc-light to draw graph through the free version of the ubigraph server.

I wrote a tool to generate some random graph. The goal is to render graph that have the same connectivity caracteristics as social networks. The generation algorithm is inspired of the forest fire model for graph generation (propagate links to neighboorhood recursively).

The code is online. All is in single file socnet.ml, but I use code from xmlrpc-light library for Ubigraph calls. There is a Builder module to augment the default builder of ocamlgraph with a state; a special UbigraphBuilder to replicate the graph structure for rendering; and finally the algo to generate the graph is in Gen module.

The result is a single binary:


./socnet.byte
  [-n <node-number>]
  [-gv] [-ubi]
  [-fwd <forward-factor>] [-bck <backward-factor>] [-bi <linking-back-factor>]

When creating an edge from a source node to some target node:

forward factor is related to the probability to link source node to successors of a target node
backward factor is related to the probability to link source node to predecessors of a target node
linking back factor is related to probability to create an edge from target node to source node

Following are some screenshots of results, although it is much more interesting to watch the construction steps though Ubigraph renderer.


./socnet.byte -n 12 -bi 0.0 -gv


./socnet.byte -n 12 -gv


./socnet.byte -n 800 -bi 0.0 -ubi


./socnet.byte -n 800 -ubi

Lock-free shared memory: 1 writer, N readers

2009-05-25T00:00:00+08:00

In recent projects I have been involved with, a lock-free shared memory pattern is used quite often. I would like to describe it here, and if anyone can tell me the name for this pattern, I’ll be very much grateful.

This technic I’m going to describe can be used in the case of 1 writter and N readers. It shares some kind of idea from both a spin-lock and an STM (Software Transactional Memory) in the sense that the writer does not take a lock but write some kind of transaction state of the memory, and reader does not lock neither but keep reading in a loop (spin) until the transaction is coherent.

All that will make more sense with some code (refer to note ¹ and ² for warning about this code; messing with memory model is very easy with lock-free stuffs). Suppose you have a shared data containing 2 values x and y; first step is to add some kind of transaction markers:


// beside of the data ...
// 2 transaction markers v1 and v2 are added to the memory
struct element_t {
  volatile uint v1;
  double x, y;
  volatile uint v2;
} elt;

Next step is simple: as long as v1 is equal to v2, the memory is in coherent state; else we don’t know what the writer is doing and nothing should be read. So writer has to maintain those markers as follow:


// writter thread use marker v1 to start a transaction
elt.v1 ++;
// does some data updates
elt.x = 42;
elt.y = elt.x * 12;
// and set marker v2 as end of transaction
elt.v2 ++;

When the reader access the data, it has to make sure that v1 and v2 are equals and do not change during the time reader access the memory. This can be done like following ³:


// reader thread keep reading the memory ...
// until transaction markers are in "correct" state
uint m1,m2;
double x,y;
do {
  m1 = elt.v1;
  x = elt.x;
  y = elt.y;
  m2 = elt.v2;
} while(m1 != m2);
// at this point, x and y have a correct value

That’s it!
So, what the name of this pattern?

By the way, if you like to read about shared memory concurrency, make sure to read the Cilk++ blog , it’s a gem ;).

¹ The marker increment need to be an atomic operation, and you may want to use a memory barrier instruction in some cases.

² This code rely on operations order. In most of programming languages, order is never enforce by the language definition, and some compiler might try to reorder things (to improve cache or whatever). Even in C, the volatile does not protect the code. Only way I know to check this code: compile and test it! different optimization flag can result in different code. Check the generated code on your compiler/platform to make sure.

³ Of course you need to handle manually how to follow pointer in your data.

Adding a timeout to a shell command

2009-04-24T00:00:00+08:00

Quite a few times one or the other of my automation shell scripts got hang while running some external command (e.g. a remote shell command may hang if network is in weird state). For those cases where a stopped automation script could really hurt the system, I ended up writing a script wrapper that add a timeout to any command.
This is kind of heavy weight implementation: instead of running the command directly, this start a first process sleeping for the duration of the timeout, and execute the command in a background process, and finally return the result of the first finishing process! 3 processes: 1 working, 1 sleeping, 1 waiting ... but it helped me few times!
Gisty code

For the lost twitter sheeps

2009-04-10T00:00:00+08:00

Tweet-tweet here, tweet-tweet there, here tweet, there tweet, ... everybody tweet! And you got to choose who to follow or you'll be quickly overwhelmed!
MrTweet can help you there by proposing you some tweets to follow. How can he achieve that? Through this blog post, let's focus on the subject of recommending twitter users to follow to existing user.
Disclamer: I have no accointance what's so ever with MrTweet, and absolutely no knowledge about it, nada; all the following are random thoughts; oh, and I have no accointance with Twitter neither!
Let say you have access to all the tweets of the world [1], and you can know who's following who on twitter. How would you look for new user to follow? Obviously there are quite a few possibilities ... and some of them are probably yet to be invented. Traditionally, mining this kind of info can be done at 2 levels: (1) looking at the content and recommend to user U1 to follow user U2 if there is any correlation between tweets content of users U1 and U2; (2) second level is to look at the graph on connected communities and recommend user U1 to follow user U2 if they share some links in the graph. On top of this there are many refinements in what can be done to mine such information: focusing and differenciating static data and dynamic aspects of user behaviours, mixing approaches of content and meta data, looking for time-series correlation ... this is a vast domain.
Following are some ideas about different way to implement MrTweet.

The UserRank dictature

Using a Pagerank-like algorithm to explore the graph of followers, you can obtain a global UserRank for all the twitter users.
Why Pagerank? Well, this is probably not the best approach of the problem, as it extract a global knowledge of your data, where in this case we should focus on communities. But heck! I like PageRank, it's simple, and it's a good start to think about the problem. PageRank was the first scientific article that I study thoroughly, and it was a ha-ha moment: simple to read, easy to understand, easy to implement ... computer science was possible! No need of linear algebra, matrix and eigenvector to understand it (it helps for the proof though :)). [2]
So how to apply Pagerank to "tweeterers"? Well, following is one way to do it.
For each user consider its followers as mark of interest. The algo define PageRank number Pr of user U as the weighted sum of the Pr of all its followers, where the weight is in inverse proportion of the number of people followed by the follower.
That is, with some notations to make it hopefully clearer:

Let Pr(U) be the PageRank of user U;
Let Fo(U) be the set of all user that U is following, and [Fo(U)] its cardinality;
Let Fi(U) be the set of all user that are following U;
PageRank is: Pr(Ux) = Sum(Pr(Un)/[Fo(Un)]), for all Un in Fi(Ux).

Thus Pr is high if the user is followed by users which have a high Pr and are not following everybody! Easy enough but wait ... how to get the Pr of the followers? this is kind of a recursive definition!
The beauty of the PageRank algo is that it propose an simple iterative solution to solve this problem: asume first that everybody as a Pr=Pr_0 of 1/N (N is the number of users, this give everybody a fair starting value), compute the new Pr_1 of each user using Pr_0 assumption, then compute the Pr_2 of each user given your Pr_1 assumption ... and iterate a few more times until the Pr stabilize, usually after few computations only (this is not magic but math ... which sometimes looks alike). If you like matrix and linear algebra, you can write the whole process as a loop which multiply a the vector of all PageRank by a square matrix of all 'follow-relations'.
Now, all we have is a Pr for each user? then what? Who shall I follow? Well, use your network to discover it!
Take all the people you are following, grab all the people they follow themselves, and remove your own sibling from this big set of people; sort them by Pr and you'll get to follow the most "popular" people linked to your network.
We have a UserRank algo to recommend people to follow to any twitter user! Well, all this rely on assumption that being followed give the user some importance. And I don't know if this works, I haven't tried it! Maybe it can be done with google API and the twitter page of the user ;)
Let explore another algo with another kind of idea.

Following the Slope

In fact, what we're looking for with MrTweet, is the same kind of recommendation as Amazon made popular: "users who like this also like that". Using the same meta-data as previously (the graph of followers), we can rephrase it as "user who follow Ux and Uy are also following Uz".
Algo to solve those problems are usually classified as recommender systems (see the NetFlix for importance of those kind of algo). A big problem of those solution for web application is often scalability and dynamic nature. But let's pick one such recommender system and see what can be done for MrTweet problem.
No surprise, let's look at SlopeOne algorithm. The wikipedia page explain it very simply and I surely can't do better. All we need to do is map the data to our problem. Let say that if user U1 follow user U2, this means user U1 rate user U2 with weight 1. Doing so, we'll have only rating of weight 1. This is ok for SlopeOne to give some result though.
The main difference with previous method of UserRank is that this is not a global analysis of all the users but rely more on the network of the user to which you want to do the recommendation.
Wanna real rating value to feed your SlopeOne algo? well, why not use the UserRank you defined previously as the rating value, and compute the SlopeOne prediction based on that? thus you would get as recommendation not the most popular user linked to your network but the most popular user liked by your network! Not so bad! Maybe yes, maybe not ... need to be tested!

More than a graph?

We've been looking at the graph of followers, which give recommendatons based on "neighborhood". Let's open the problem a bit more ...

instead of using followers, we can look at the graph of replies
why not look at the tweet content? we could check correlation in keyword, or in the URL (even following the URL)?
why not cross data from twitter with data from other network? ... and I'm going to read about this just here: http://33bits.org/2009/03/19/de-anonymizing-social-networks :)

I don't know you, but this kind of problem delight me. But after all this thinking and no action, I'm now going to write some real code to do more than think about algo ;).
[1] With N millions users, 7 tweets a day, 140 bytes a tweet in raw format ... storage is not that huge, even for few years. How many twitter users? where does seven come from? who care! engineers only need order of magnitude and units!
[2] Pagerank is closely related to the hub and authorities: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.3875 [3]
[3] I know, all those ref are "old" :)

TAOCP vs. Code Complete

2009-01-10T00:00:00+08:00

Surprising! as of now, in my experiences of software engineer, I met more people that read/know about TAOCP than people who read Code Complete.
It may be a probability accident (I kind of remember that probabilities and small numbers are not good friends). It may also be influenced by my fields of experiences. But assuming this is real (i.e. programmers know more about TOACP), it's doesn't seems right.
I consider TAOCP as a reference to write efficient code; Code Complete is a reference to write good software (eventually being a product maintained by a team). Both are important, but the first one being used way less often!

Back to roots ... with physics!

2009-01-07T00:00:00+08:00

This blog is not completely abandoned ... I'm just buzy lazy those days.
Just to relate my brief come back to roots: doing physics simulation in 3D ;).
I've been playing with Irrlicht as 3D framework. It's good, not to complex. But the API is not always easy (you're forced to use the irrlicht not-automatic counting ref). I haven't found doc about coordinate systems (orientation and angle's units) but it's using common practices in game engine. It's pretty fast, and the simple included demos help a lot to get started (Ogre3D don't come with simple examples).
For the physics engine, I've used Bullet, and it's really pleasant to use! and result are great! I only quickly went through some part of the code, and it's great code, I think I will learn quite a few tricks of this code (e.g. how to avoid conditional branch ('if') to select between 2 unsigned integers ... and it even can be usefull for efficiency on some processor like Cell (maybe related to parallelism and pipelining?). No really, this is beautiful code, and if you just want to play a little bit with physics, using Bullet directly is more fun than PAL (Physic Abstraction Layer).
I'll post the code when/if my Domino Rally simu is done :) ... but without sound it's not good.

Terminology: radix, Patricia, TRIE and tree

2008-11-30T00:00:00+08:00

I took some time to get the terminology: radix tree/trie, patricia tree/trie ... it's all the same, really:

A trie is a multi-way tree;
I guess radix term replaced the Patricia appellation because it sounds more generic (not specific to information retrieval);
And in the case of radix trie, if you use the binary representation of the key, you have an alphabet of 2 and the trie become a 2-ways tree, thus radix tree :P

String specific data-structure: set and map

2008-08-09T00:00:00+08:00

Lately I've been playing a bit ... well, that's a programmer kind of game: I wrote yet other implementations (with yet other bugs I assume) of some classic data-structures, in Ocaml.
Those are all about string set or string map, and are purely functional (thus persistent).
The code is in the project ocaml-stringset (http://github.com/khigia/ocaml-stringset/tree/master). There is a TST (ternary search tree), a Collapsed TST, a Trie (bootstrap version of Chris Okasaki) and maybe other will be added. Most of the code is in file/module StringSet so it is easy to embed in a project. There is one example file for each datastructure (as well as some unit test ... and the unit tests of TST iss pretty bad as it test the internal structure, not the API).
Haven't been as far as doing stress tests though it would be nice to compare the different behaviours.
Update: those algo are implemented for string, but we could certainly provide a generic implementation for any datatype that is iterable collection and whose items are comparable. I may try to make some generic version later on.
Update: most of those tree algo implementation are NOT tail recursive; this would probably need continuations ... I'll add this if/when needed (in production environment, it should probably be done anyway except if the use case is restricted and ensure a limit in recursion depth).

Generate all pair permutations in (not really) random order (and space efficiently)

2008-08-07T00:00:00+08:00

(that time I learnt the lesson: never promise what the next post will be about coz I often not deliver)
Optimization algo need to explore the space of solutions, and this exploration is a major part of the algo! Let's focus on one simple case: exploring in random order two finite dimensions. For example, let two integer variables, V1 taking value in interval [1, 100] and V2 taking value in interval [1, 20]: how to explore all the possible pairs (v1,v2) in random order?
A simple (almost-)solution is given by the following python code:


[(e1,e2) for e1 in shuffle(range([1,100)), for e2 in shuffle(range(1,20))]

which is in fact the cartesian product of the shuffles of V1 and V2 intervals ... but this is ordered by values of the first shuffle and thus not random.
OK, now is the bad news: I have no solution completely space efficient to propose. My best effort is a solution which compute at least two shuffles, one on each dimension (kind of O(n + m) for space) and is even not random ... just random enough for most of the cases :P
So how? the solution is describe in this post http://weblog.raganwald.com/2007/02/haskell-ruby-and-infinity.html and especialy the section about the tabular view of the cartesian product. Did you read it? so the proposed solution is to navigate the cross-product table along its diagonal instead of row by row ... simply smart isn't it? It give "impression" of randomness :P
Ocaml code for this algo is here: http://github.com/khigia/ocaml-anneal/tree/master/walks.ml (function pair_permutation_random_seq); It uses extensively an ad-hoc stream implementation (Seq module) to perform the walk lazyly. It was a good example to test the stream implementation!

Simulated annealing in OCaml

2008-06-11T00:00:00+08:00

I've been using this python implementation of simulated annealing to deduce Singapore bus service from a database of bus stops (see previous posts about Google Map API).
I wanted to play a little bit more with this algo and decided to port it to OCaml: you can find the code on GitHub.
As a first try, I wrote a direct code translation. Only few points differ:

The OCaml code use a stream implementation (lazy list) ... (mostly equivalent to my previous Erlang implementation).
The OCaml code uses array structure where Python uses list.
The OCaml implementation of function reversed_section do only one array reverse in all cases.

Result is quite ok. Without any optimization on the algo, the OCaml native code performed quite faster (around 10 times faster), meaning that solving the TSP problem for SG bus services took 40 minutes for OCaml version where the Python code ran for hours (of course we could improve this version too).
The algo itself can be improve (I guestimate the time for SG map problem can be reduce by one more order of magnitude with the same simulated annealing approach).
But in coming post (code is there, need time to clean it), I'll be looking at other interesting problems I found inside this one, especially on how to walk in solutions space in quasi-random order.

SG bus routes ... following

2008-05-28T00:00:00+08:00

This post is a following to the previous post about drawing SG bus route with google map API.

Status of the system

This is for now only a toy demo, all in a single javascript document that draw the map when loaded (the javascript file is generated from a KML file by a python program that also computes the bus service routes).

Toward drawing all the bus services ...

Drawing all the bus services on the same map not only is *very heavy* for the browser (at least for firefox, and its SVG renderer) but also give very little information (it is too much data at one time).
See by yourself:

Even zooming (on Dhoby Ghaut station):

What could be done ...

To solve the problem of too many services displayed at same time, definitively a good UI could improve usability. What I have in mind is a kind of UI which enable to select which services to display ... but maybe something better can be done like auto-selection of services to display depending of zoom factor or user itinary?
The previous point could also help to not send all the data to the client (in order to save bandwith).
Automatic route simplification: on one route, when adjacent stops are "too close" to each other, we could remove one of them on the drawing (which would make it lighter, and also remove some artifact like tiny wigzag caused by stop on the opposite side of the road).
Adding some constraints manually (editing few distance between some stops) to correct some wrong path.

More?

As in the previous post conclusions, I think a mashup of existing itinery service to display the itinery on a map could be quite interesting.

SG bus services map

2008-05-24T00:00:00+08:00

Playing with the DB of SG bus stop locations and google map API.
My goal is to try to draw the route of the bus services ... but the DB has no info about the order of the stops per service (there is info of which services stop for each bus stop). Following are some experiments, with display about bus service 124.
First try was kind of funny (not unexpected!) as I draw the bus route "as stops are found in DB" ... which apparently is from left to right:

So, to get a better idea of the bus route, I'm trying to draw the shortest path ... better and even quite enough:

But of course this is inexact map as:

this shortest route uses all bus stops without taking care of which ones are on the way to go or the way to go back (this data is not in my DB);
the length of the path does not depend of the road ... those are only straight lines!

But anyway, this give a better view of the bus service than nothing or a guide book of bus stop names ...

screenshot-sgbus-124_inner

2008-05-24T00:00:00+08:00

screenshot-sgbus-124-shortest_inner

2008-05-24T00:00:00+08:00

erlocaml wc map-reduce example

2008-05-20T00:00:00+08:00

New example in ocamerl lib of erlocaml project: a tiny map-reduce-like (1) word-count program (word-count is the simple example often used to illustrate map-reduce principle).
First part of this example is an ocaml distributed erlang node [l52]. It is composed of one permanent registered ('wc') mbox [l40] which upon request create other mboxes implementing the mappers [l19] (on request, a mapper read a text file [l8] and send it word by word to reducer [l29]).
Second part of this map-reduce example is an erlang module implementing two functionalities. One of them is the reduce part implementation [l34] done by a process which accept messages from mappers and update a dictionary accordingly. Second responsibility of this module is orchestration of the map-reduce flow [l90], consisting of running all mappers [l66], waiting end of all those executions [l79], and collecting result of all reducers [l95].
Assuming EPMD is running, this script run an ocaml node and an erlang node, and run a simple map-reduce to count words in two test files.
As usual, not sure it's a useful example, but it was sure fun to write :)
(1) this is not a map-reduce lib ... there is no failure case taken care of, processes pipe is mostly done through messages over network (while map-reduce is mainly meant to use an efficient filesystem based communication), etc!

Ocamerl - Erlang ... echo-ing in shells

2008-05-13T00:00:00+08:00

Little intro step-by-step to the ocaml-erlang message exchange mechanism offered by ocamerl (a lib of erlocaml).
Subject of the following code is a wonderfull application ... named "echo server"!

In the interpretor shell of ocaml, we create a hidden erlang node and an activity to echo all received message (both on console as well as in respond to the caller).
In the erlang interpretor shell, we send few message and compare them to the received ones.

The following assumes code is running on machine "comp1".
Ocaml shell:


(* getting Ocamerl available in toplevel *)
ocaml> #use "topfind";; (* ocamerl used findlib for install *)
ocaml> #thread;; (* ocamerl is multithreaded app *)
ocaml> #require "ocamerl";;
(* creating/declaring a node, assuming epmd is running *)
ocaml> let o1 = Ocamerl.Enode.run "o1" ~cookie:"cookie";;
val o1 : Ocamerl.Enode.t = 
(* creating/declaring a mbox, equivalent of erlang process *)
ocaml> let m = Ocamerl.Enode.create_mbox o1;;
val m : Ocamerl.Enode.Mbox.t = 
ocaml> Ocamerl.Enode.register_mbox o1 m "echoer";; (* give it a name *)
- : unit = ()
ocaml> Ocamerl.Enode.Mbox.create_activity m (fun msg -> match msg with
    | Ocamerl.Eterm.ET_tuple [|pid; any;|] ->
        Printf.eprintf "MSG:%s\n%!" (Ocamerl.Eterm.to_string msg);
        Ocamerl.Enode.send o1 pid any
    | _ ->
        () (* drop unexpected msg *)
);;
- : unit = ()

Erlang shell:


# starting erlang node with same cookie
erl -sname e1 -setcookie cookie
% check connection
erl> pong = net_adm:ping(o1@comp1).
pong
% utility to print whatever is in message queue
erl> F = fun() -> receive W -> io:format("got back: ~w~n", [W]) after 1 -> error end end.
#Fun
% some tests ... send data, received it back
erl> {echo1, o1@comp1} ! {self(), {1,2,"test"}}.
{<0.37.0>,{1,2,"test"}}
erl> F().
got back: {1,2,[116,101,115,116]}
ok
% in the mean time, ocaml shell also display the data

That's it! A wonderfull echo server :)
Amongst things on the to-do list:

Should not have to create a mbox and set its activity separately (need some wrapper)
Could have an onode ocaml toplevel which run one node by default and offer direct interface (e.g. "send").

Erlang to call an Ocaml seam carving lib

2008-05-10T00:00:00+08:00

Yet another useless example for erlocaml, but this time it is not completely silly ... it does something :)
In fact the project eocarve uses:

the ocamerl library (which got a makefile install rule for the occasion);
the seamcarving library provided by mce (thanks!) (it's LGPL so the full code can be found in eocarve).

Idea is simple: an ocaml node run and provide a API for Erlang node to call the seamcarving library. See eocarve wiki for details/example.
Aim of this project was mainly to demonstrate use of ocamerl lib ... however it may be usefull for an Erlang web app which would need seamcarving (heavy weight for CPU!). Had fun to integrate those lib in same app.

Tiny progress on erlocaml

2008-05-06T00:00:00+08:00

Minor updates for erlocaml (more exactly on ocamerl) ... mostly code cleaning and minor refactoring!
Only one new feature: ability for Erlang processes to send message to unregistered ocaml processes. An example of that is "ex_node_mult" which generalize "ex_node_double" by dynamically creating ocaml process to perform a multiplication ... yep I know, not very useful


% erlang code using the ocaml node
{byn, OcamlNode} ! {self(), 2},
By2 = receive M -> M after 1 -> error,
{byn, OcamlNode} ! {self(), 3},
By3 = receive M -> M after 1 -> error,
P1 = make_ref(),
P2 = make_ref(),
By2 ! {self(), P1, 21},
By3 ! {self(), P1, 21},
ok = receive {P1, 42} -> ok after 1 -> error end,
ok = receive {P2, 63} -> ok after 1 -> error end

With this feature, ocamerl begin to be usable ... and that's exactly what I will be doing next: experiment with more useful (at least less silly) examples! Some ideas are:

tiny mapreduce example with ocaml workers (erlang doing the network part);
using the ocaml image processing lib from erlang (not best example as lot of data need to be exchange ... this is task to be solved for future erlocaml development);
others???

me me Euler Pb1: looking at the data (and fun with python)

2008-04-25T00:00:00+08:00

Google for it, Euler problem #1 has got a lot of solution implementations. Most of them use similar algo: produce the list of all numbers in the range [0-1000], filter only number divisible by 3 or 5, and compute the sum. This is perfectly fine, and it's wonderfull to code when your language allow some kind of lazy list (default in Haskell, or often called stream library in other language).
But can we construct the sequence of "number divisible by 3 and 5" directly?
Let's have a look at what this sequence looks like:


m = 42
l = sorted(list(set(range(0, m, 3) + range(0, m, 5))))
l
[0, 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36, 39, 40]

Well ... cannot see a pattern ... let's look at the sequence of difference between 2 consecutive numbers:


map(lambda (x,y): y-x, zip(l, l[1:]))
[3, 2, 1, 3, 1, 2, 3, 3, 2, 1, 3, 1, 2, 3, 3, 2, 1, 3, 1]

Here we go ... I have no idea why, but seems that we can construct the sequence using the list of increment 3,2,1,3,1,2,3 (same with m=300).
And then, here come a different python solution:


from itertools import cycle, takewhile
def succ(b, inc):
  while True:
    b += inc.next()
    yield b
sum(takewhile(lambda x: x < 1000, succ(0, cycle([3,2,1,3,1,2,3]))))

By the way, there must be a mathematical solution to this first problem, some kind of magic formula ... any pointer?

ocaml vs. F# for big integer ... surprising performance test!

2008-03-30T00:00:00+08:00

Was inspired by Rober Pickering post about a post about Euler problem 14 ...
Without changing the algorithm, I ran a simple test to compare F#, ocaml byte code and ocaml native code ... and the result is quite surprising, for me at least!
The program do a lot of computation on integer (even 64 bits); I remember (no ref) that ocaml is more efficient for floating point operation that for integer. But anyway, just wanted an idea of how to port this code to Ocaml.
Following is the code in F# as seen on cited post:


#light
let rec seq_length x n =
    match x with
    | x when x = 0L -> (n + 1)
    | x when x = 1L -> seq_length 0L (n + 1)
    | x when x%2L=0L ->seq_length (x/2L) (n + 1)
    | _ -> seq_length (3L*x + 1L) (n + 1)
let rec loop i imax n =
  let n' = seq_length i 0
  let imax, n = if n' > n then i, n' else imax, n
  if i < 1000000L then loop (i + 1L) imax n else imax
print_any (loop 1L 0L 0)

And here is an Ocaml version:


let ( ** ) = Int64.mul
let ( // ) = Int64.div
let ( %% ) = Int64.rem 

let rec seq_length x n =
    match x with
    | 0L -> (n + 1)
    | 1L -> seq_length 0L (n + 1)
    | x when x %% 2L = 0L -> seq_length (x // 2L) (n + 1)
    | _ -> seq_length (Int64.succ (3L ** x)) (n + 1)

let rec loop i imax n =
  let n' = seq_length i 0 in
  let imax, n = if n' > n then (i, n') else (imax, n) in
  if i < 1000000L then loop (Int64.succ i) imax n else imax
let _ = print_string (Int64.to_string (loop 1L 0L 0))

Surprisingly (for me!), the compiled F# code is much faster:

time mono eul14.exe: 12.979s
time ./eul14.byte: 58.145s
time ./eul14.native: 30.234s

I'm not sure why Ocaml seems to be slower for this test. Can it be a GC issue?

ocaml native code

2008-03-25T00:00:00+08:00

I was playing with this mini raytracer and modify it to use glcaml instead of glut.
I was delighted to see how the native code is faster than the byte compiled one ... of course this is expected but after playing for some time with the byte code I was surprise how fast the result came after the first native compilation :)
(below is google graph; time unit is second)

ocamerl ... no update :(

2008-03-13T00:00:00+08:00

Quick news about ocamerl:

I changed the build system to ocamlbuild (need ocaml 3.10).
... and that's all! can't find time to clean all the mess.

So anyway, here is the current state of ocamerl:

ocaml can register a hidden erlang node (epmd).
ocaml node can respond to ping and keep connection up with erlang node (net_kernel process)
erlang can send (some) terms to named ocaml process
ocaml can send (some) terms to erlang process if it received the pid in a previous message

That's all for now! Argh!
Amongst things I'd like to change:

simplify terms manipulation in ocaml
add features (most important initial message from ocaml to erlang)
complete redesign of concurrency (using events or JoCaml maybe!)
add a minimum of documentation

I need motivation! In fact I have no project which would need ocaml + erlang ... for now.

For who is this blog?

2008-03-13T00:00:00+08:00

I've been writing here some ideas or development status.
But looks like my readers are more oriented towards code examples or solutions ... so I'll try to be more pragmatic in future.
Anyway my code is better than my English (at least I hope so!) so that should improve quality of this blog ;)

Control by fuzzy logic

2008-03-13T00:00:00+08:00

As exercise of Ocaml, I wrote a very very simple library for inference using fuzzy logic.
There is only the bare minimum ... but it's often enough anyway ;). If someone is interested I can:

write a small doc
write a example
complete some parts

This is my first project on GitHub.

Could Erlang and ICE be friends?

2008-02-19T00:00:00+08:00

How could an Erlang process communicate with an ICE-based application? The mix seems a bit strange (why would you need ICE when you already have Erlang ;) ) but without entering in details of why we would like to do so, let's consider how can we plug an Erlang sub-system in a ICE application.
One way to go would be to write a slice2erl compiler! That's presumably lot of work. This kind of work is being done for OCaml in the Hydro project ... and is on my list of next things to play with.
Another way to get Erlang talk to ICE application would be via a custom intermediate translator between the Erlang app and the ICE system (using some intermediate language having a complete interface with both Erlang and ICE, like C, Java, or Python); yes, this surely add complexity and slow down the full system, but efficiency of distributed application is more often bound by design than by runtime ;).
Btw, as far as ease-of-development is concern, I have the same kind of feeling when comparing C++ to Python or ICE to Erlang :)

Language typing: no strong preference yet!

2008-01-17T00:00:00+08:00

Having used different kinds of language (C++, python, ruby, ocaml, erlang), I still can't choose what kind of typing I prefer as far as static vs dynamic typing is concerned (I will not discuss the strong vs duck typing).
I'm not convince that a static type system is a useful "bug avoidance system" (for my kind of development habits at least!). Not that it cannot prevent some bugs, but those are probably the "easy bugs" that would have show-up in unit-tests ... and this is exactly the point: unit-tests are anyway necessary to test the functional aspect, so type kind of bug will be found in either kind of development environment.
Having written lot of code in python and C++, I sure better love python: I will not repeat here why language like python or ruby are more easy to read, more concise and so on ...
However in team environment, a type is a first documentation feature! In a clear API, the type information is nearly enough to use the API (most python API documentation define all types of the parameters ...).
Also with my last experiences with ocaml, I discover that having to define the type oblige to think more about what is the data. When thinking of the type of a data, you end-up asking you question like: what is it that I want to manipulate? if it should have this and that method, is it an application object? is it a subcomponent of my current object? is it a facet/interface of my object? can I abstract this "thing"? ... all that is a good point in favor of strongly typed language at compile time as it help to concentrate on defining data!

Pythonize your vim

2008-01-17T00:00:00+08:00

Tip I enjoyed today: python in vim, how cool is that!?
For those who like vim but not the vim script language, try :help python.
Example: :py import vim :py [vim.current.buffer.append(str(e)) for e in xrange(10)]

Coming soon: an interesting post about ocamerl

2008-01-08T00:00:00+08:00

Managed to have some time to play with ocamerl: ocaml node is now able to receive data from erlang node, and also send data to pid on connected nodes.
I begin to understand what I'm doing, so that I will be able to clean the code and refactor some parts very soon.
As example, an ocaml process which multiply integer by 2! wow! What' an interesting example!


bash> cd trunk/lib/ocamerl
bash> ./ex/node_double >/dev/null 2>&1 &
bash> erl -setcookie cookie  -sname erl
erl@devhost 1> net_adm:ping(ocaml@devhost).
pong
erl@devhost 2> {bytwo, ocaml@devhost} ! {self(), 8}.
{<0.37.0>,8}
erl@devhost 3>  receive I -> io:format("Got: ~w~n", [I]) after 0 -> ko end.
Got: 16
ok

Note: the ping was optional and the answer seems correct: 8 * 2 = 16!

Simple game

2008-01-02T00:00:00+08:00

It's kind of surprising how people can like such a simple game as pong. Isn't it even more odd to find programmer which enjoy their program to play?
All that to say: ocaml node (using the ocamerl lib of erlocaml) can now reply pong to a ping request from erlang node ;) ... and that's all it can do!
Next step: receive data :)

ocamerl update: handshake

2007-12-28T00:00:00+08:00

Code in ocamerl (part of erlocaml) pass the node handshake. Hopefully nobody will read this code before I clean it up a bit ... because right now it is a furious mess!!!
I spent some time (arg, that's a lot in fact) on a stupid (as the bug's author) bug. The (simplified) handshake is a follow:

the 2 nodes exchange a challenge which is 4 random bytes interpreted as a Int32;
each node computes the MD5 of (their own cookie + challenge);
each node compares its result with the digest of the other node.

My bug was to concatenate the cookie (string) with the raw 4 bytes of the challenge ... where I had to concatenate the cookie with the string representation of the 32 bits long unsigned integer!
(in fact the handshake is done with 2 challenges: each node send a challenge to the other)
Anyway, the handshake pass correctly now, and ocaml node can receive the ping control message ... but do not reply yet! after it reply, sure I clean the code!!!

Concurrent behaviours

2007-12-22T00:00:00+08:00

As spotted in this blog post using Erlang in robotics seems a pretty good idea to implement robust systems and concurrent behaviours.
However I do not consider the subsumption architecture (Brooks, 1986) as the best example of action selection architecture for concurrent behaviours. As far as I remember, the subsumption architecture assumes predefined priorities on behaviours (hierarchy), and has a fix set of rules on how some behaviours can subsume others.
As far as reactive architectures are concerned, IMHO Erlang style of concurrency could be more effectively used on architecture using activation networks (Maes, 1989), or a voting mechanism a la DAMN (Rosenblatt, 1995), or a pertinence-based selection like Creature (Blumberg, 1997), or whatever architecture which enable a distribution of control.
But yes, Erlang seems quite a good match to implement autonomous entities (robots or software agents (MAS)).

ocamerl

2007-12-16T00:00:00+08:00

Christmas is coming, and I found a new toy to play with: ocamerl. This is a very simple solution to exchange data between erlang and ocaml. In fact, this is mainly an ocaml implementation of the erlang external binary format (based on this discussion/code). I just added few tools to make a TCP connection to exchange those data.
On erlang side, I use 2 processes: the receiver process listen on a TCP port,read data and send it back to any erlang process meant to handle incoming data; the second process is busy transfering all data in its message queue to some TCP server (the ocaml part). On ocaml side, there are a couple a function to transform erlang forms in ocaml entities and vice versa.
I only wrote a very very simple exemple: an ocaml echo server, which multiply by 2 all integers sent in message (deep search in tuple).
Erlang side init:


1>Receiver = spawn(oe, print_mailbox, []).
2>Sender = oe:messenger(12345, 54321, Receiver).

Ocaml side init:


./ex/double -recv 12345 -send 54321

Then, any term sent to from erlang is sent back by ocaml.


3> Sender ! {true, 12, {1,2}}.
{true,12,{1,2}}
Sending data: <<131,104,3,100,0,4,116,114,117,101,97,12,104,2,97,1,97,2>>
Received binary: <<131,104,3,100,0,4,116,114,117,101,97,24,104,2,97,2,97,4>>
Converted to term: {true,24,{2,4}}
Received: {true,24,{2,4}}

Funny, isn't it ? :) This is an early stage of course. Code is part of erlocaml project (in lib/ocamerl). My goal is to write a hidden erlang node in ocaml. Not sure it is useful, but quite certain it is interesting ;)

Hylomorphism and Euler problem 2

2007-11-19T00:00:00+08:00

In my recent posts I've played with Euler problem 2 and hylomorphism: here I use the hylomorphism concept to solve the Euler problem 2 using Ocaml :)


(* Given a hylomorphism implementation ...*)
let rec hylo_impl step till col inj v s =
    if till s
    then v
    else
        let ns = step s in
        let nv = inj (col s) v in
        hylo_impl step till col inj nv ns
;;
(* ... solving Euler problem 2 is quite easy! *)
let eul2 n =
    hylo_impl
        (fun (n0, n1) -> (n1, n0 + n1))
        (fun (n0, n1) -> n0 > n)
        (fun (n0, n1) -> if n0 mod 2 == 0 then n0 else 0)
        (fun x a -> x + a)
        0
        (1, 1)
;;

This time I tried to add default value with labels notation of Ocaml. But I have a problem with type inference: if the given default function has a type, all function I pass as parameter must have the same type as the default one ... still have to learn a bit more about polymorphism in ocaml I presume ;). The following code may work in some case, but it forces the type of the functions, which is really bad! Any advice to solve this problem?


let hylo
        ?(step = fun x -> x + 1)
        ?(till = fun x -> true)
        ?(col = fun x -> x)
        ?(inj = ((fun x a -> x :: a), []))
        s
    =
    let (injf, injv) = inj in
    hylo_impl step till col injf injv s
;;

Euler problem 2

2007-11-14T00:00:00+08:00

This blogpost present a good F# solution to Euler problem 2. The code make use of infinite sequence. I've written other solutions to this same problem. The first one is a code specialized to solve this problem: it computes the fibonacci sequence while checking the problem conditions and computing the problem answer.


#light
let rec fib_filter_fold (n0,n1) filter folder acc m =
    if n0 <= m
    then fib_filter_fold (n1, n0 + n1) filter folder (if filter n0 then (folder acc n0) else acc) m
    else acc
let pb2 m = fib_filter_fold (1,1) (fun x -> x % 2 = 0) (fun acc x -> acc + x) 0 m
printf "euler problem 2 (1000000): %a\n" output_any (pb2 1000000)

I then wrote a second version, trying to make use of Seq functions. Idea is to start with the fibonacci sequence and apply some modification on it to solve the problem. I'm not so happy with the result!


let fibs =
    Seq.unfold
        (fun (n0, n1) -> Some(n0, (n1, n0 + n1)))
        (1, 1)
let reach_index s m =
    s
    |> Seq.mapi (fun i x -> (i, x))
    |> Seq.find_index (fun x -> x > m)
let pb2seq n =
    Seq.truncate (reach_index fibs n) fibs
    |> Seq.filter (fun x -> x % 2 = 0)
    |> Seq.fold (fun acc x -> acc + x) 0
printf "euler problem with seq (1000000): %a\n" output_any (pb2seq 1000000)

Why don't I like this? because I have to manipulate the sequence twice, first to find the index of the last element to take into account, and second to compute the problem answer.I would have like a method 'take_while' in Seq to write something in the line of:


let pb2_not_compilable n =
    fibs
    |> Seq.take_while (fun x -> x < n)
    |> Seq.filter (fun x -> x % 2 = 0)
    |> Seq.fold (fun acc x -> acc + x) 0

... am I missing something?Btw, how to implement this "take_while" function? I've try, but Seq has a 'hd' function but no 'tail' ... what am I missing here? I'm sure this is possible to implement ...

Hylo again

2007-11-11T00:00:00+08:00

The previous blogpost implements a hylomorphism in Erlang.
Following is again the same in F#: but this is part of my exercices to learn F#, and I just begin to learn ... so the code is ... ergh, whatever.
And I have no idea how to implement default values. Any advice?


#light
open Microsoft.FSharp.Collections.List;
let rec hylo step till col inj v s =
    if till s
    then
        v
    else
        let ns = step s in
        let nv = inj v (col s) in
        hylo step till col inj nv ns;
let fact =
    let step = fun x -> x - 1 in
    let till = fun x -> x <= 1 in
    let col = fun x -> x in
    let inj = fun a x -> a * x in
    hylo step till col inj 1;
let evens n =
    let step = fun x -> x + 2 in
    let till = fun x -> x >= n in
    let col = fun x -> x in
    let inj = fun a x -> x :: a in
    rev (hylo step till col inj [] 0);
let to_bin n =
    let step = fun x -> x / 2 in
    let till = fun x -> x <= 0 in
    let col = fun x -> x % 2 in
    let inj = fun a x -> x :: a in
    hylo step till col inj [] n;
let expand l =
    let rec duplicate c n a =
        if n > 0
        then duplicate c (n - 1) (c::a)
        else a
        in
    let step = fun li -> tl li in
    let till = fun li -> match li with |[] -> true |_ -> false in
    let col = fun li -> match hd(li) with |(c,n) -> duplicate c n [] in
    let inj = fun a x -> (x :: a) in
    rev (hylo step till col inj [] l);
do printf "fact(5)=%a\n" output_any (fact 5);
do printf "evens(10)=%a\n" output_any (evens 10);
do printf "to_bin(10)=%a\n" output_any (to_bin 10);
do printf "expand([(1,2); (4,7)])=%a\n" output_any (expand [(1, 2); (4,7)]);

Morphing ruby to erlang just for fun

2007-11-11T00:00:00+08:00

Read some introductions to theory of categories (a very good introduction to the theory, or this one more programmer oriented). As I also stumble upon this thread, I discover a new concept: "hylomorphism is a composite of an anamorphism (unfold) and an catamorphism (fold/inject) [1], [2]", along with a ruby code to implement it in some way (this the googlegroup thread above).

Just for fun (and be sure to understand it), I translated the code in Erlang. I've used the property list module to implement some kind of default value, but it's not really elegant. Anyway, code is here.


-module(hylo).
-export([
    % hylomorphism API
    new/1,
    % examples/toys
    evens/1,
    fact/1,
    to_bin/1,
    expand/1
]).
% internal declarations
-record(hylo, {
    do,
    till,
    collecting,
    injecting
}).
% API
new(PL) when is_list(PL) ->
    H = #hylo{
        do = proplists:get_value(
            do,
            PL,
            fun(X) -> X + 1 end
        ),
        till = proplists:get_value(
            till,
            PL,
            fun(X) -> X =:= undefined end
        ),
        collecting = proplists:get_value(
            collecting,
            PL,
            fun(X) -> X end
        ),
        injecting = proplists:get_value(
            injecting,
            PL,
            {   [],
                fun(A,E) -> [E|A] end,
                fun lists:reverse/1
            }
        )
    },
    fun(S) -> eval(H, S, element(1,H#hylo.injecting)) end.
% internal implementation
eval(H, S1, R) ->
    {_, InjF, InjR} = H#hylo.injecting,
    case (H#hylo.till)(S1) of
        false ->
            V = (H#hylo.collecting)(S1),
            S2 = (H#hylo.do)(S1),
            eval(H, S2, InjF(R, V));
        _ ->
            InjR(R)
    end.
% examples
evens(N) ->
    H = new([
        {do, fun(X) -> X + 2 end},
        {till, fun(X) -> X >= N end}
    ]),
    H(0).
fact(N) when N > 0 ->
    H = new([
        {do, fun(X) -> X - 1 end},
        {till, fun(X) -> X =< 1 end},
        {injecting, {1, fun(A,E) -> A * E end, fun(A) -> A end}}
    ]),
    H(N).
to_bin(N) when N > 0 ->
    H = new([
        {do, fun(X) -> X div 2 end},
        {till, fun(X) -> X =< 0 end},
        {collecting, fun(X) -> (X rem 2) end},
        {injecting, {[], fun(A,E) -> [E|A] end, fun(A) -> A end}}
    ]),
    H(N).
expand(L) ->
    H = new([
        {do, fun ([_|T]) -> T; ([]) -> [] end},
        {till, fun ([]) -> true; (_) -> false end},
        {collecting, fun([{C,N}|_]) -> lists:duplicate(N, C) end}
    ]),
    H(L).
-ifdef(EUNIT).
-include_lib("eunit/include/eunit.hrl").
evens_test() ->
    ?assert(evens(10) =:= [0,2,4,6,8]).
fact_test() ->
    ?assert(fact(5) =:= 120).
to_bin_test() ->
    ?assert(to_bin(10) =:= [1,0,1,0]).
expand_test() ->
    ?assert(expand([{$a,2},{$b,3},{$c,4}]) =:= ["aa", "bbb", "cccc"]).
-endif.

xkcd draw the time...

2007-11-05T00:00:00+08:00

Mobile phone keyboard

2007-10-26T00:00:00+08:00

Was "playing" with keyboard map and layout recently in my Ubuntu 7.10 and realized that mobile phone dedicated to SMS or email have a keyboard's layout following the PC QWERTY keyboard (e.g. Nokia E61i).
Is there any phone with a Dvorak layout? Shall we assume that phone user already know the PC keyboard and do not want to learn another one?
But could we assume that the size change imply a new learning of the keyboard usage, and this is good time to change the layout for a more appropriate one?
Is this all nonsense?

Erlang walk in AVI file

2007-10-09T00:00:00+08:00

Warning: long post ahead ... but mostly code :)
This post contains absolutely no idea nor thought: it is just a recap of my attempt to read an AVI file format (or RIFF file format, as I do not parse AVI data but only document structure). Let's go directly in code with this simple module header!


-module(avir).
-compile([export_all]).
-include_lib("kernel/include/file.hrl").

dbg(Level, Template, Args) ->
    Indent = lists:flatten(lists:duplicate(Level, "  ")),
    io:format(Indent ++ Template, Args).

go() ->
    go("test.avi").

go(Filename) ->
    {ok, #file_info{size=Size}} = file:read_file_info(Filename),
    {ok, IODev} = file:open(Filename, [read, binary]),
    {ok, Parts} = walk_data(0, [], IODev, 0, Size).

So, dbg is a crap function to print debug message ... yeah, the old fashion way, it's so simple for just a post! go is the main entry point and call the 'real' code: the approach is to call the walk_data function which will build and return a list of AVI structures (first parameter will be level of nesting, used for printing comment with a meaningful indentation, and second one is an accumulator for recursion to come).
I mainly use this short document: AVI is a (nested) sequence of two kind of structure, either LIST or CHUNK. More precisely, first come a mandatory RIFF-AVI LIST then multiple (and optional) RIFF-AVIX kind of LIST. Let's walk those structures:


walk_data(Level, Parts, File, From, To) when From < To ->
    case chunk_or_list(File, From) of
        avichunk ->
            {ok, Part, NextPos} = walk_chunk(Level, File, From, To),
            walk_data(Level, [Part|Parts], File, NextPos, To);
        avilist ->
            {ok, Part, NextPos} = walk_list(Level, File, From, To),
            walk_data(Level, [Part|Parts], File, NextPos, To);
        Error ->
            {error, "maybe unexpected EOF", Error}
    end;
walk_data(_Level, Parts, _File, _From, _To) ->
    {ok, lists:reverse(Parts)}.

chunk_or_list(File, Pos) ->
    case file:pread(File, Pos, 4) of
        {ok, <<"RIFF">>} ->
            avilist;
        {ok, <<"LIST">>} ->
            avilist;
        {ok, _FourCC} ->
            avichunk;
        eof ->
            eof
    end.

Walk is straightforward, from position From to To, accumulating result in reverse order (I love this [head|tail] list notation ... was Prolog the first to use it?). chunk_or_list read few bytes (the FourCC header) to guess the kind of the next structure (CHUNK or LIST) in file; this structure is loaded, and walk continue.


walk_list(Level, File, From, To) ->
    case read_list_header(File, From) of
        {ok, AviList={avilist, List, FourCC, DataPos, DataSize}, NextPos} ->
            dbg(Level, "read list header (pos=~p, next=~p): List=~p FourCC=~p~n", [From, NextPos, List, FourCC]),
            {ok, SubPart} = case FourCC of
                <<"movi">> ->
                    dbg(Level, "... skipping list FourCC=~p...~n", [FourCC]),
                    {ok, []};
                _ ->
                    walk_data(Level + 1, [], File, DataPos, DataPos + DataSize)
            end,
            {ok, {AviList, SubPart}, NextPos};
        eof ->
            dbg(Level, "end of file~n", []),
            eof
    end.

read_list_header(File, Pos) ->
    case file:pread(File, [{Pos, 4}, {Pos + 4, 4}, {Pos + 8, 4}]) of
        {ok, [List, <<Size:4/little-unsigned-integer-unit:8>>, FourCC]} ->
            {ok, {avilist, List, FourCC, Pos + 12, Size - 4}, Pos + 8 + Size};
        {ok, [eof, eof, eof]} ->
            eof;
        _ ->
            {error, "no list header to read, but not empty data~n"}
    end.

To walk a LIST, read the header (remember that the FourCC field length is part of the data size ...), read the nested data (this re-use the walk_data), and return the LIST representation: a 2-tuple with first the header (could be a record) and then a list of sub parts. There is a useless test to not walk the real data because my test file is kind of big. Walking the CHUNK is quite the same.


walk_chunk(Level, File, From, To) ->
    case read_chunk_header(File, From) of
        {ok, AviChunk={avichunk, FourCC, DataPos, DataSize}, NextPos} ->
            %FourCC = <<_StreamNumber:2/binary, _DataType:2/binary>>},
            dbg(Level,  "read chunk header (pos=~p, next=~p): FourCC=~p DataSize=~p~n", [From, NextPos, FourCC, DataSize]),
            chunk_spy(FourCC, File, DataPos, DataSize),
            {ok, AviChunk, NextPos};
        eof ->
            dbg(Level, "end of file~n", []),
            eof
    end.

read_chunk_header(File, Pos) ->
    case file:pread(File, [{Pos, 4}, {Pos + 4, 4}]) of
        {ok, [FourCC, <<Size:4/little-unsigned-integer-unit:8>>]} ->
            NextPos = Pos + 8 + Size,
            PaddedNextPos = NextPos + (NextPos rem 2),
            {ok, {avichunk, FourCC, Pos + 8, Size}, PaddedNextPos};
        {ok, [eof, eof]} ->
            eof;
        _ ->
            {error, "no chunk header to read, but not empty data~n"}
    end.

Similar to LIST, without nested data. Also, this went wrong at the first attempt: I found in this page that CHUNK data is padded to word boundary (grr).
But that's all it take to read a well formated RIFF file. And for those wondering about the chunk_spy function, continue to read this blog :).

Erlang/OTP installation from sources

2007-09-26T00:00:00+08:00

I'm probably missing something in Erlang/OTP installation from sources ... my goal is to install multiple version of OTP in user space.
Here is one way to do it:

remove any symlink if needed rm /home/khigia/local/lib/erlang
apply the "normal" quick install steps for the new OTP version, let say otp-R11B5 cd /home/khigia/apps/otp-src-R11B5; ./configure --prefix=/home/khigia/local ; make; make install
modify the install to be version specific mv /home/khigia/local/lib/erlang /home/khigia/local/lib/otp-R11B5 ln -s /home/khigia/local/lib/otp-R11B5 /home/khigia/local/lib/erlang

Changing the symlink enable to switch Erlang/OTP version. There must be an easiest way ... how?

Different DBMS

2007-09-07T00:00:00+08:00

It's common knowledge that DBMS is a very important part of a fast scalable distributed systems as far as performance is concerned. But I often tend to forget it and blindly rely on well known relational DBMS. Recently I stumble upon the following other DBMS/discussions and the last one really opened my eyes:

The Erlang/OTP come with mnesia allowing transaction on distributed DB. However it has been argue (note: this need some reference...) that distributed mnesia cannot scale (it needs some agreement between all nodes for transaction). For huge distributed system (or nodes on low network) the application has to maintain data consistency without relying on transaction. Berkeley DB seems to be the preferred way to go for this, but as I understand it, it is not a DBMS which manage distribution but a tool to help you to do so.

CouchDB is one DBMS trying to handle the distribution of DB.

Also I just discover the terminology column-oriented DBMS through this (too?) simple wikipedia article. Being used to R statistics system helped me to (try to) understand what it really is. At least I better understand why Google developed BigTable and I have to read or listen more about it ...

Recommending popular items

2007-09-06T00:00:00+08:00

The prediction module using Slope-One algorithm can compute popular items.
In this implementation, popular items are not only the most frequent items. Each user's ratings defines some kind of relative order of a subset of items. The prediction module compute some kind of global order for all items by merging all "user subset's orders". This is actually using Slope-One algorithm for a user which would rate all items with same score.
Popular items recommendation is useful for new user!

Screenshot: adviserl services

2007-08-31T00:00:00+08:00

Screenshot: adviserl

2007-08-31T00:00:00+08:00

One more service for adviserl: an HTTP API

2007-08-31T00:00:00+08:00

Did I say adviserl need doc and testing ... well ... I did implemented something else: a (too) simple HTTP API based on inets. It enable rating of items and retrieving recommendations. Hopefully it will also display few info about state of adviserl application. If set in config file, adviserl will start inets at startup.

mnesia enter in the playground

2007-08-23T00:00:00+08:00

adviserl is now version 0.2 thanks to its new default backend: Mnesia.
Mnesia
All 4 data services (sources, items, ratings and predictions) can now store everything into Mnesia tables, which help to (let's hope ...) ensure consistency. Using Mnesia will also ease to distribute the application later.
The main difficulty was the backup of adviserl data because all services are independent. So adviserl only provides tools (adv_mnesia:backup/0, adv_util:save_files/0) and the user of adviserl need to know want he want to backup and when (no logic is implemented to backup or restore data). There is no function to restore a backup when adviserl is running, but for a shortcoming, it is easy to stop and restart adviserl.
For now, adviserl start mnesia if needed, but cannot stop mnesia when adviserl stop. Still wondering if mnesia could/should be an included application (using mnesia_sup module).
API changes
The main interface has change a little bit to facilitate the use of ID or key to identify items and sources. By default, 'keys' are used to identify sources and items (adviserl:rate/3,4). New functions enable to directly use ID (adviserl:rate_id/3,4).
Also new functions enable to add rating asynchronously (adviserl:async_rate/3,4 and adviserl:async_rate_id/3,4), meaning that recommendation will not use those ratings until specified (adv_predictions:init/0): this enable to quickly add a lot of ratings (without expensive update of recommendation data), then purposely trigger a re-initialization of recommendation data.
Conclusion
That's all for now.
I hope I can work on using multiple prediction algorithms, but it may be better to first implement some regression tests and write a minimal documentation ;)
I'm looking forward to play with recommender algorithms :)

advance backward?

2007-08-03T00:00:00+08:00

I added a "welcoming bug" feature in adviserl: a simple save_files/0 function to backup the recommender data in a persistent manner.
That was quick to write, and I really need it now that I begin to look at a lot of data. But it's the wrong way to do it: I need to synchronize the multiple servers before to make or restore the backup. Still wondering if I should have done that in a branch ...
Anyway, it's here, and it works: if the application anvironment define few files where to save data, those files will be read and written when application start or stop respectively (you can use load_files/0 or save_files/0 whenever you want, but be careful that servers should not process anything else at the same time to avoid inconsistent state).
Mnesia backend is becoming urgent now ... it's the next point on the roadmap :)

Sieve again

2007-07-27T00:00:00+08:00

I didn't known this was a so popular problem when I coded a sieve of Eratosthene using stream design from SICP.
In fact, I saw this video about NewSqueak which present an example of a concurrent algorithm of the sieve, and in this related discussion on plan9 group I also found an Haskell implementation (more related to the stream design than to the concurrent design IMHO). I also had a look at libtask which offer a C version of the concurrent sieve.
That's already a lot, so one more shouldn't be useful ... but I like this example, and thus here is my Erlang implementation using a spawn for each prime in the sieve.

delicious adviserl

2007-07-21T00:00:00+08:00

I (began to) wrote a delicious API to implement a toy example for adviserl (thus the code is here). More about the toy example in next blog post.
Haven't found anywhere a delicious API library for Erlang ... but haven't really look for it because I wanted to avoid dependency. So I wrote one, organised in 2 parts.

The first part (deli_api) is able to:
- connect to the delicious server and retrieve data (posts) using inets http client;
- convert those data (posts) in Erlang terms using xmerl (discard XML as different delicious API (rss, api, ...) have different format of the same data);
The second part is a gen_server (deli_posts) which accept those requests:
- {login, User, Password}, return ok
- logout, return ok
- {get_posts, User, [Option]} with Option=no_update, return {ok, [Post], archive|uptodate}

The server will maintain a local cache (a DETS file) and download from delicious server only if needed and requested. The login is only used to retrieve data from delicious server: data put in cache can always be accessed without password.
I may like to use this API in order to write a plugin for SharedCopy: any shared URL could be automatically posted in delicious (seems easy with Yaws but I need a web hosting for that).

Storing data into adviserl

2007-07-21T00:00:00+08:00

The recommender system adviserl manage all data (item and user, or source) through identifiers.
Keeping those identifiers opaque for the whole system is possible, but as many prediction algorithms use integer identifiers (for matrix operations), adviserl provides an API in input of the system to generate integer ID if needed. Thus all identifiers in adviserl are integers, with an automatic conversion if needed.

erl> rate(5, 1, {3,no_data}). # user 5 rate item 1 with score 3 (no rating data)
erl> rate("bill", "microsoft", {5, no_data}). # user "bill" rate item "microsoft" ...
erl> adv_items:id_from_key("microsoft").
2 # item "microsoft" got ID 2
erl> adv_source:id_from_key("bill").
1 # source "bill" got ID 1

The API is also usefull to keep data about items or sources, which open the possibility to content-based recommendation algorithms. For this, it's enough to call the item/source API before to set related ratings. Any item/source has an integer ID, a external key (any Erlang term), and a data term (a property list in the following example).

erl> adv_items:insert_new("linux", [{tags, ["oss", "os"]}]).
{true,3} # bool if inserted or existing, integer is ID
erl> adv_items:object_from_id(3).
{3,"linux",[{tags,["oss","os"]}]} # {ID, Key, Data}
erl> adviserl:rate("linus", "linux", {6,no_data}).

Advises on delicious tags

2007-07-21T00:00:00+08:00

Because CF need data to learn, small examples to illustrate adviserl are not easy to find. And thus the first "real" example is already a mis-use of adviserl: it uses the CF algorithm as an IR tool!
Anyway, here we go, I created a tag recommender with my delicious bookmarks (this is not new, delicious already display related tags, but this is just an application example toy).
This is done by considering each bookmark as a source (a user) and each tag as an item: each time a tag is associated with a bookmark, this is translated as "the bookmark rate the tag with a score of 1". The complete code is this: application:start(adviserl), {ok, DeliciousPID} = deli_posts:start_link(), gen_server:call(DeliciousPID, {login, User, Password}), {ok, Posts, _Status} = gen_server:call(DeliciousPID, {get_posts, User, Options}, infinity), io:format("Loading posts", []), lists:foreach( fun(#delipost{href=HRef,tags=Tags}) -> io:format(".", []), lists:foreach( fun(Tag) -> adviserl:rate(HRef,Tag,{1,no_data}) end, Tags ) end, Posts ), io:format("~n", []). Getting a recommendation for few keywords is then:

Keywords = ["erlang", "concurrency"],
KeywordIDs = lists:map(fun(K) -> adv_items:id_from_key(K) end, Keywords),
Ratings = lists:map(fun(ID) -> {ID, 1} end, IDs),
Rec0 = adviserl:recommend_all(Ratings),
lists:map(fun({ID,_}) -> {ok,K} = adv_items:key_from_id(ID), K end, Rec0).

(lot of this code is about format and conversion, hopefully it will be done in next API release).
This delicious example toy can be run by keywords.sh in delicious example folder.
Yeah, I know, we can do the same more easily with few statistics (and R) and no CF ... but (1) I needed a small example and (2) this could be extended to use different user accounts.
Hey! I should try to use citeUlike instead of delicious for the next example!

adviserl got a gen_server API

2007-07-18T00:00:00+08:00

Until now, to access a remote node running adviserl, you could use the native Erlang RPC: erlang> rpc:call(adviserl_node@localhost, adviserl, rate, [1, 2, {3,nodata}]).
I added a gen_server API to do exactly the same thing: erlang> gen_server:call({adv_api, adviserl_node@localhost}, {rate, 1, 2, {3,nodata}}).
This is not simpler, but not more complicated either, and hopefully this will be more flexible when coming to distribution (the API may then become a global process).
I also added a bunch of shell script to start, stop, rate, or run prediction from command line. The start-stop script (adv.sh) is quite usefull, while the others are convenient when debugging. Those scripts have yet to be documented :( but are more or less straightforward and have a minimum help message when bad options or bad arguments are given.

shell> ./bin/adv.sh start
shell> ./bin/adv-rate.sh 1 2 2 # user 1 rate item 2 with score 2
shell> ./bin/adv-rate.sh 1 3 3 # ...
shell> ./bin/adv-rate.sh 2 3 3
shell> ./bin/adv-rate.sh 2 4 4
shell> ./bin/adv-rate.sh 3 3 3
shell> ./bin/adv-getratings.sh 1
3 3
2 2
shell> ./bin/adv-recommendall-source.sh 3 # prediction for user 3
4 4.00000
2 2.00000

I think my next post on adviserl will show a more useful example! :)

object AND functional

2007-07-11T00:00:00+08:00

From a programmer perspective, how easy (difficult) is it to mix OO and functional programming?
Earlier this year, I've been reading SICP and Programming pearls at the same time; Last month, I've been writing both OO Python code and functional Erlang code. Those experiences are probably the best feeling of programming I had since a while: I'm not writing code, I am coding abstractions.
But I'm still wondering about mixing both styles/paradigms in the same project or same code file. My intuition is that it may be nice to work with different styles for different parts of a program, but I would really be afraid to introduce such kind of mix in a project maintained by multiple programmers. Any experience to share on this subject?
Perhaps I should give Nemerle a try. Any other?

Googling to learn collaborative filtering

2007-07-10T00:00:00+08:00

I have no idea what is a good way to discover and learn new things. Surely "science of learning" has some models and advices that may have been useful, but I choose to follow the lazy way. To learn about collaborative filtering, I googled.
The first source of information reported by the search engine is (of course?) wikipedia: collaborative filtering .Then I passed 2 links in Google results (general information) to direct myself toward specialized articles through this great personal page. I navigate a bit in it and with the help of few more Google searches I got lost ... on my way to be lost, at least I figure out some articles that seems fundamental: Reporting and evaluating choices in a virtual community of use, GroupLens: an open architecture for collaborative filtering of netnews, Social information filtering: algorithms for automating 'word of mouth'. My machine learning background is appreciated at this stage.
But Wow! That's a lot of information: do I really understood what I read? This was time to got dirty hands so I choose one system looking relatively simple and faced it at implementation level: Slope-One algorithm.
Then I found a recent article about Google news personalization recommender system: I still don't feel comfortable to compare the different algorithms, but at least this great article put things in real context (taking into account the big scalability problem). And also this point me toward a wonderful survey: Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions.
I have enough (too much) information for now, so I guess that (1) it is why I feel a bit confused and (2) it is the good time to write down all that stuffs to try to organized it: field description and algorithms classifications, evaluation of recommender systems (see for example here and here) and at last but not least the scalability problem. And I will try to use citeUlike and its recommendations :)
Hopefully, after that, I can go further "Incorporating contextual information in recommender systems using a multidimensional approach" (available here), but before I still have to find a survey of available recommender systems. Any recommendation? ;)
Did I miss something important?

Adviserl goes live

2007-07-06T00:00:00+08:00

Long time ago I wrote a very simple Slope-One implementation (collaborative filtering algorithm): this was easy and fulfilled all my needs ... which was then to learn CF and Erlang ;).
Then I realized that it could be more than fun and could even become useful as a simple recommender system. So I wrote it as an OTP application and it is published under GPLv3 license. Lots (lots!) of things still have to be done but the basic are like that:

% start application: by default use Slope-One data/algorithm
application:start(sasl),
application:start(adviserl),

% add some rating in the system
adviserl:rate(1, 2,  {3, no_rating_data}), % user 1 rate item 2 with value 3 (no data)
adviserl:rate(1, 4,  {5, no_rating_data}), % ...
adviserl:rate(2, 2,  {1, no_rating_data}),
adviserl:rate(2, 5,  {8, "damn good!"}), % any data term can be associated to rating value
adviserl:rate(3, 4,  {3, no_rating_data}),
adviserl:rate(3, 5,  {2, no_rating_data}),
adviserl:rate(3, 12, {2, no_rating_data}),

% some debug output to "see" the data
adv_ratings:print_debug(), % display the ratings per user
adv_items:print_debug(), % display a covisitation matrix

% try some predictions
adviserl:recommend_all(1), % prediction for user 1
adviserl:recommend_all(2), % ... for user 2
adviserl:recommend_all(3),
adviserl:recommend_all(4),
adviserl:recommend_all([]), % for any user without rating!
adviserl:recommend_all([{2,5}]), % for any user having those ratings
adviserl:recommend_all([{4,5}]), % idem
adviserl:recommend_all([{2,5},{4,5}]), % idem with multiple ratings
adviserl:recommend_all([{3,5}]), % ... even if item is unknown

% update on the fly
IncreaseRating = fun({R, Data}) -> {R + 1, Data} end,
DefaultRating = {1, no_data},
adviserl:rate(1, 2, {7, now()}), % user 1 change rating of item 2 from 3 to 7, adding data
adviserl:rate(1, 2, IncreaseRating, DefaultRating), % update from 7 to 8 with function
adviserl:rate(1, 42, IncreaseRating, DefaultRating), % rate item 42 at 1 (default)

ok_lah.

Among the main points on the pseudo roadmap:

API to call adviserl functions through process messages
data persistence
data distribution
algorithm distribution

Simple stream implementation in Erlang

2007-05-07T00:00:00+08:00

My projects are all suspended ... I have been busy playing with stream examples of chapter 3 of SICP :).
I wrote in Erlang a simple implementation of stream as cons-list. It is not meant to be efficient but easy to understand (and debug):

a stream is here a tuple {stream, Head, DelayedTail}, where DelayedTail is a 0-arity's function which return the next stream element tuple;
a macro implements the delay function used to construct a stream tail: -define(DELAY(Any), fun() -> Any end).

Note: the head is not delayed, and if we need a delayed head this probably means that we need a lazy-evaluation model, to which I'll come later. Using abstract functions, head/1 to access current value and tail/1 to force evaluation of next stream state, will enables to hook a memoization process if needed.

Anyway, the stream concatenation and the delay's macro are enough to build all stream manipulations. Here are some examples:

% map: application of a procedure to all elements of a stream
map(Proc, Stream={stream, undefined, undefined}) ->
    % empty stream: do nothing
    Stream;
map(Proc, Stream) ->
    % apply Proc to current, and delay apply to all tail elements
    {stream, Proc(head(Stream)), ?DELAY(map(Proc, tail(Stream)))}

% filter elements of stream with respect to some predicate
filter(Pred, Stream={stream, undefined, undefined}) ->
    % empty stream: do nothing
    Stream;
filter(Pred, Stream={stream, _Head, _Tail}) ->
    Current = head(Stream),
    case Pred(Current) of
        true ->
            {stream, Current, ?DELAY(filter(Pred, tail(Stream)))};
        _False ->
            filter(Pred, tail(Stream))
    end.

% generalized map: apply proc to multiple streams (traverse streams "in parallel")
gmap(Proc, Streams=[First={stream, undefined,undefined}|_Others]) ->
    % assume all stream have the same length
    % found one stream empty: end of process
    First;
gmap(Proc, Streams=[First|_Others]) ->
    % create a list of heads
    Heads = lists:map(fun(S) -> stream:head(S) end, Streams),
    % create a generator of the list of tails
    FTails = fun() -> lists:map(fun(S) -> stream:tail(S) end, Streams) end,
    % result is the application to heads and delayed mapping to tails
    {stream, Proc(Heads), ?DELAY(gmap(Proc, FTails()))}.

And now, we have enough to use the streams:

% explicit definition of infinite sequence of integers
explicit_integers_from(N) ->
    {stream, N, ?DELAY(explicit_integers_from(N+1))}.

% add values of 2 streams
add(S1, S2) ->
    gmap(fun([X,Y]) -> X + Y end, [S1, S2]).

% infinite sequence of Fibonacci numbers
fibs() ->
    {stream, 0, ?DELAY({stream, 1, ?DELAY(add(fibs(), tail(fibs())))}) }.

A bit more usefull: 2 infinite sequences of prime numbers. First one uses the sieve of Eratosthene; second one uses basic definition of prime: number not divisible by any previous primes.

% Sieve of Eratosthene:

sieve(Stream) ->
    Current = head(Stream),
    {stream, Current, ?DELAY(sieve(filter(
        fun(N) -> N rem Current /= 0 end,
        tail(Stream)
    )))}.

sieve_primes() ->
    sieve(explicit_integers_from(2)).

% prime numbers using the factors decomposition property

primes() ->
    {stream, 2, ?DELAY(filter(fun is_prime/1, explicit_integers_from(3)))}.

is_prime(N) ->
    iter_is_prime(N, primes()).

iter_is_prime(N, Primes) ->
    FirstPrime = head(Primes),
    if
        FirstPrime * FirstPrime > N ->
            true;
        N rem FirstPrime == 0 ->
            false;
        true ->
            iter_is_prime(N, tail(Primes))
    end.

And of course there are lot of stream examples in SICP chapter, like the impressive Euler transformation to accelerate convergence of sequence.
In this thread http://erlang.mirror.su.se/ml-archive/erlang-questions/200010/msg00165.html you can find a real stream implementation by Richard Carlsson, as well as interesting discussions about stream and lazy evaluation. Also check this other thread http://www.erlang.org/ml-archive/erlang-questions/200602/msg00003.html if you're interested by memoization in Erlang. I may test it later to learn the magic of Erlang parse_transform ;), but I think an easy possible way to implement memoization for my stream is to model a stream as a tuple of 4 elements, adding a dictionary of memoized values as last element (my current implementation uses the process dictionary to store memoized values).
Actually I'm not sure if this post is too short to be a tutorial or too long to be a interesting post! Anyway, it exists now ;) ... mostly because a friend gave me motivation to do so, thanks!

Programmers everywhere!

2007-04-28T00:00:00+08:00

In last point of one of this previous post I was remembering (to me!) the need to know the roots of computer science. Since then, I read (began to...) some interesting articles on wikipedia: history of CS, the pioners, the list of Turing award winners ... wikipedia is really time consuming!
Curiously, it's more difficult to find a good list of modern computer scientists (or programmers, as they prefer). I like the post Beautiful Code: Leading Programmers Explain How They Think. Any other recommendation?

SICP, concurrency and time

2007-04-28T00:00:00+08:00

This was too simple, so why wasn't I aware of that? concurrency and time is the same thing ... or at least you cannot have one without the other, logic! I'm currently in a "back to basic" phase ... but I don't have enough time: how can I manage to implement stream, while reading the meta-circular evaluator chapter, and also having a "normal" life? time and concurrency ...

8-queens ... me too!

2007-04-10T00:00:00+08:00

Even it the 8-queens puzzle is often used to illustrate the recursivity principle, I never tried to solve it myself. I only wrote my N-queens solution recently (using Erlang), and was pretty happy to see that list-comprehension is quite good for the principle of generate-and-filter. Oh! and I tried the ESDL library to display the result :) ... I was just as excited as the day I did my first openGL tutorial in C.

Positive integer and recursion

2007-04-05T00:00:00+08:00

I remember my first steps of Prolog, I was following an exercise to define positive integer as a recursion of the same function ... I did not really known why I did that, but it was fun to define the integers (the funniest Prolog exercise is still to write a Prolog interpretor in Prolog). Today I'm reading SICP and I just found in Ex2.6 that the recursive integer definition is the basic of lambda calculus: Church' numerals! Definitively, I have to learn this lambda calculus. At least I have now a better understanding of it (thanks also to this post) and I wrote the addition and multiplication operators in Erlang.

grinderl is sinan-ized

2007-04-05T00:00:00+08:00

Forgot to mention: grinderl now use sinan as build system (makefiles are still around but should disappear as soon as the tests will be handle by sinan). Hopefully sinan will help to deals with dependencies and release handling.
Btw I continue to follow the development of the CEAN repository ...

Some articles and why they surprised me

2007-03-31T00:00:00+08:00

Softskills blog post on Thinking Parallel : I try my best to be open-minded ... but I would have never read this book before to read this post: I just don't like the title "How to win friends & influence people". But after the blog post, I realized it's a nice book I can read to learn about "how to behave as a good developer in a good team". Why am I so not understanding and stopped at the title!? stupid me!
Tags efficienty at Amazon vs. LibraryThing : before to read this article, I almost forgot that users of a system don't care to give input to this system! We, as users, only have one objective to target, and system should be transparent. UX Design rules.
Regular expression can be simple and fast :What!? This time I almost forgot that from all the good software applications around the world, there is probably very few which come from a long scientific study of the subject, with design comparisons and efficiency implementation tests! Most of them come from an idea, quickly throw one day as a piece of code, and evolving as the project mature. I should never forget again: enough is enough! (still, regular expressions with automata is a basic of computer science: don't forget the basics!)

grinderl: less tsung, more capistrano

2007-03-31T00:00:00+08:00

I decided to change the roadmap of the grinderl project.
It first application was to be a tiny load-test framework (at least a testing framework as I'm not sure it is efficient enough to create heavy load on a well design server). And I still have to finish the part of creating useful statistics from all the results.
But now I think that I could implement a better node management API, and then grinderl can become one way to call code on remote host (not exactly as RPC since command are asynchronous and supervised by remote host). One application could be to install an external application on all remote host, or manage deployment like does capistrano (but with the full Erlang environment available!).
So the new (of course, it's the first!) roadmap:

Stabilize the current version:
- move test to become command
- better handling of results sent by remote hosts
Develop concurrently the remote node API and a UI:
- API to manage remote hosts
  - use slave module
  - have a look at this how-to
  - can we install a minimal Erlang node on a remote machine through ssh ... using CEAN or erlware maybe?
- UI: network tools seems to require a network-able UI (probably using yaws) to be able to:
  - see/manage nodes/hosts
  - send command to all/any hosts, monitor results (looks like each command will need a specialize UI)

Conclusion:

Sad note: nothing new in grinderl (this project don't seems to appeal my creativity)
Good note: simple project to learn Erlang distributed programming

List of Erlang data structures

2007-02-24T00:00:00+08:00

How would you implement a huge-but-sparse 2D matrix in Erlang?

First solution who came to my mind was to google for some linear algebra library ... that failed!
The second one, implement a dict-of-dict structure.

That was quite easy, but as I was wondering on efficiency I needed to understand differences between dict, orddict etc. On my way I came up with this (ongoing) list of Erlang data structures.

Simple problem ... looking for simple solution

2007-02-24T00:00:00+08:00

I use Vim in a Gnome Terminal in a Ubuntu/Gnome desktop, with the terminal fullscreen mode option ... and thus can't see the popups of Gaim/Skype (I don't want to use the sound alert to not disturb my colleagues)! I would love to see the small message near tray icon that I normally got in "not-terminal-fullscreen mode". Maybe I should switch back to XFCE ...

GMailReader

2007-02-15T00:00:00+08:00

I used GReader since few months now, it works pretty well ... it's maybe too good: now I would like to read my email in GMail with the same presentation as GReader! (i.e. don't hide the other emails when I click on one, but only expand the text of the selected email).
I know about some tools to do the opposite (send email from feeds) like the excellent RSSFwd. So after the question "what's the difference betweens a forum and a blog?", here comes "what's the differences between a feed and a (thread of) emails?". Can I say that every email is a feed (with one post), to which I can participate (the thread of emails becoming a feed with more than one post).
Some days I really have stupid blog post, and I'm happy to not have to read my blog :)

clap clap clap

2007-02-12T00:00:00+08:00

Warning: this is a bad post!

Applauding's time during meeting ... clap clap clap ... today (again) made me think to the sound of the steps of the "stupid mule" following the man who gives it the heavy duty! worst, the mule often carry the rewarding food it will got!
That's not that I don't ike to applaud: I do think dedicate work and recognize good work is really better than the work itself! But please, don't ask me to applaud ... I will do it by myself!
Yeah, I'm a bit sad/angry ... and I like to write in this mood ... and I LOVE/NEED blues music, my liberty universe!
Note: I'm sorry for those strong animals (mules), they're good!, I just needed a metaphor to express myself.

Teamwork

2007-02-12T00:00:00+08:00

Have you ever row in a quadruple scull's? in a 20 paddlers dragon boat? Efficiency is not a matter of individual strength, it's mostly a matter of synchronization! And for that, team have to be organized ... why? to follow a common objective! that's the definition of a team. That's why hierarchical organization had been so successful: it obliged a single base! But it's maybe not optimal ... Look at open source projects, really, look at that (CK, thanks for the link)!

[priv] TaDa - readings

2007-02-12T00:00:00+08:00

See also this list from Darius Bacon
Technical/Science document

Comprendre le cerveau : naissance d'une science de l'apprentissage
Amazon CS book wish-list
Producing Open Source Software (by subversion creator, see in this video about poisonous people)
Introduce aphordance in UX design.
- The Design of Everyday Things, 1988, Donald Norman

General

THE Reference I never read :)
- The Society of Mind, Marvin Minsky
CRAP-ify your graphics design
- The non designer's design book: Design and Typographic Principles for the Visual Novice, Robin William
Wanna know about how to tell story?
- Understanding Comics: The Invisible Art, Scott McCloud
Keep symphony in mind
- Dialogue:the art of thinking together, William Isaacs
- Beethoven's Anvil: Music in Mind and culture, William Benzon
Meaning of life, positive psychology
- Man's search for meaning, Viktor Frankl
- Authentic happiness, Martin E. P. Seligman
Right-handed brain ;)
- Right hand, left hand:the origins of asymmetry in brains, bodie, atoms and cultures, Dr McManus
  - (author won an Ig Nobel)

Finance

Interesting (?) blog post about ETF (?) http://rlove.org/log/2007070601
One Up On Wall Street : How To Use What You Already Know To Make Money In The Market, Peter Lynch and John Rothchild (amazon link)
The Little Book That Beats the Market, Joel Greenblatt (amazon link)

grinderl: early stage

2007-02-10T00:00:00+08:00

I did it! I have try to code my first OTP applications following most of the recommendation of the documentation (and the French book Erlang programmation was a great help).
One of those applications became an opensource project: grinderl. I did blog a bit about it in this blog post, and now it has evolved from the all-in-one-module code to a small ongoing project (hosted by googlecode). To do that I used:

application/supervisor/server/fsm/event ... all the generic modules: not complicated
eunit: simple enough, and tests should be compatible with the test_server application
dialyzer: wow! it can save a lot of time, especially because Erlang has no type system: a MUST.
appmon: great and easy to see your supervision tree
debugger: I still prefer to write message in the console ... please don't tell that to anybody!
edoc: I learned how to use it, but sadly it didn't teach me to write good documentation...

I may like to have a look at cover and profiling tools, I may want to learn about Erlang port, but I guess the two main points I missed are:

mnesia: looks so great!
release handling: this is a tricky part of OTP application distribution I think!

And for the last one, I hope the sinan built system can help me (Eric Merritt promised us a high level user documentation soon).
My only regret is that I haven't found a complete tutorial to go through all the steps of transformation of an Erlang program in an OTP application release. And that's too sad that I don't feel able to write one!

STM drive me to the Anarchy

2007-01-23T00:00:00+08:00

STM stand for Software Transactional Memory. How does it drive me to anarchy? because I get lost again following all the web links!
In fact I was wondering where to get some information about this mechanism used in some concurrency models. For those like me who like concrete explanation, I recommend to read this blog post from Joe Armstrong then beautiful concurrency for more details.
And if you are still wondering why I wrote the term "anarchy", it's just because I read about the work of Audrey Tang who integrated STM in Pugs (an Haskell implementation of Perl) ... and she also appears to be a proponent of the Individualist Anarchism.

Erlang: the good, the bad and the chubby

2007-01-23T00:00:00+08:00

(hoping my favorite guitarist don't mind that I borrow one of his title)
Some (mostly subjective) comments after few days playing around Erlang:

The good: I have never before implemented a server (relatively efficient TCP proxy) so quickly. Asynchronous call are as easy as synchronous ones and network is invisible! that's good! physician can wrote as many differential equation as they need, synchronous model are a strong hypothesis of the world!
The bad: syntax! I was used to Prolog notation, but Erlang introduce too many meaning for punctuation while newline or indentation has no meaning at all! Anybody interested in Pyerlang (a syntax translator python-inspired)?
The chubby: my next blog will be about transformation of a simple Erlang server to a (nearly) complete OTP application. Yes, OTP is a good framework, but learning it is far to be as easy as learning Erlang!

Music comes from here!?!!

2007-01-23T00:00:00+08:00

This evening my pandora radios navigate from Tab Benoit to Popa Chubby by Melvin Taylor, and from Buddy Guy to Robert Lowery ... even better than a random selection on my hard-drive since my collection is quite limited!
But the evening's question is not about blues nor guitar, it is a question about physic: isn't my brain afraid of my headset? if my brain has a pure stereophonic analysis model to locate the sound source, it should conclude that it come from the center of my head, isn't it? ... I listen again, and yes, sound comes from there. Good brain, not as afraid as I am.

UX* Design

2007-01-16T00:00:00+08:00

I assisted to my first presentation about User Experience Design (as I discovered, UX Design is not only UX). Here is a quick summary of what I still remember.
From what I understood UX Design is defined by:

aesthetic
functionality
innovation
enterprise impact
human factor (~ergonomics)

A product specification can then be described by a list of features, where each feature is defined by:

description (what is/does it?)
functional test (how to test the functionality?)
intend or goal (what's the objective of the feature, for e.g. "make user happy")
how to test/measure the feature (particularly its goal)

Relative reading (added in my reading queue):

The Design of Everyday Things [Donald Norman, 1988]

D. Norman introduced the term affordance about user interaction, and emphasize on the design of product: "make the task dominate, make the tool invisible".

Thread, Event, and concurrency model

2007-01-16T00:00:00+08:00

I recently jumped into the Erlang world, mostly seduced by the message-passing concurrency model (as opposed to the shared-state concurrency model) [1]. This was a choice a priori without real objective (I mean without project, just as learning experience).
Now we have (project in my company) to implement an "efficient" and scalable server: fast, robust and highly-available (as any servers, of course). Coming from a really bad Python threaded-server experience, I'd rather read some hints before to go to any platform or framework (Stackless Python, Twisted, Erlang/OTP, Java, C/C++ ...). Here are some available documents related to high performance network servers:

Wow! that's tough to decide anything! Where I'm a bit surprised is that concurrency model choice is often viewed as Thread vs. Event, and each side argue about throughput , switching context cost, and latency. As I understand, message-passing and event is not the same: most of the event model I've seen do not enable pre-emption without relying on threads to manage some event loops. And I naively assume that pre-emption is a good choice to implement robust and available server.
To conclude, if I have to choose something today, I would still choose Erlang! Because it implements efficient lightweight process: easy as threads, message passing model, and pre-emption able [2]. Furthermore Erlang proposes through OTP a whole framework for robust application, and I see a (good) framework as an invaluable experienced-user knowledge (thank you OTP folks!).
Notes: [1] Indeed Erlang feature an efficient implementation of so-called processes (also known as lightweight-thread, micro-thread, greenlet or tasklet ... but the term process emphasize on the absence of shared-state common to many thread implementation). Erlang made also the choice of functional programming style as a programming guide to context independent code (unique affectation of variable, reduced side-effects).
[2] Having a lot of Python code, I had to compared Erlang vs. Stackless Python. In fact they share a lot of characteristics but Stackless has not the whole OTP framework and more importantly Stackless message sending block if there is no receptor of the message (more in this discussion about Stackless vs. Erlang).

meta-musico-post

2006-12-11T00:00:00+08:00

What should contain my blog-posts? (sorry, I'm quite new in blogging world...)
Anyway, question is: should I post from time to time on the music I like or should I make a web page to gather all? Ok, nobody care ... but if you have time, have a look at musicovery, it's beautiful and fit well in my graph-oriented brain (I have a dream project called orgraphizer, but it's still more a dream than a project).

To do or not to do?

2006-11-27T00:00:00+08:00

I did mistakes (I mean I discover some new ones).
I implemented programming tools, some of them far too quickly to provide them a good architecture. At this time, I only needed few functionalities, but as requests came I implemented some quick-fix/quick-adds. And now, even if we don't planned to use those tools any further, I have to maintain those becomed-crappy-tools!
Too conclusions, choose one depending of your mood:

Don't do anything before to be requested to do so; don't provide tools, keep it secret.
Never implement software without specifications and stay humble: never never never do quick design before to be a expert/guru/grand-master/programming-giant/computer-god!

Baby steps in the Erlang world!

2006-11-25T00:00:00+08:00

It took a long time to decide to learn Erlang instead of Haskell or OCaml/F#. What I really want to learn for now are the OTP principles of distributed application. So I wrote my first Erlang script (not yet an application) and it confirmed my point of view: Erlang make easy the development of distributed program! really!!!
At my work we needed to test performance of a TCP server (and we'll used Grinder because most of our API is Python). I've decided to use Erlang to do the same thing as an exercise: grind.erl (of course it will never become neither as huge as Grinder neither as efficient as Tsung; I even do not hope it can be usefull). But with few lines of code, I was able to reproduce the same behavior as Grinder: launch on multiple machine multiple tester agents executing some test function and gather the results of all the tests.
Ok, I did not told all the truth: that's not a very small number of lines: arround 260 (with tests and all). But all the code is for running multiple time a test function and gathering some statistics on its result (run_task). Distributed this behaviour among multiple Erlang node is only a map call (distribute_task)!
Here is a code extract:

distribute_task(NodeLst, Task) ->
    NodeLstLen = length(NodeLst),
    StatListener = spawn(grind, statistic_gathering, [now(), NodeLstLen]),
    io:format(
        "~w create statistic gathering process ~w on node ~w~n",
        [self(), StatListener, node()]
    ),
    TaskRunnerCreator = fun(Node) -> spawn(
        Node,
        grind,
        run_task,
        [StatListener, Task]
    ) end,
    Runners = lists:map(TaskRunnerCreator, NodeLst),
    io:format(
        "~w create a list of task runners: ~w~n",
        [self(), Runners]
    ),
    Runners.

And here is a usage example:

grind:init([node(), grinderl@node.net]).
grind:distribute_task(
        [node(), grinderl@node.net], % use 2 nodes
        {
            % on each node run the test function in 50 concurrent process
            {concurrent, 50},
            % two statistics to gather
            [{mean, writetime}, % a real value (mean, std. dev., min, max, med will be retrieved
             {count, writer_val} % a occurence counter
            ],
            % foo function to test: must return a tuple {ok|error, Pid, ValLst}
            fun(Writer, WritenValue) ->
                FWrite = fun() -> io:format("~s got ~w~n", [Writer, WritenValue]) end,
                {WriteTime, _Res} = timeit(FWrite),
                {ok, self(), [WriteTime, {Writer, WritenValue}]}
            end,
            % arguments to used for each call of the test function
            [{rr, ["bea", "pouf"]}, % first is taken in the list with a round-robin style
             {choice, [0, 1, 12, 42, 77]} % second argument is randomly choosen from the list
            ]
        }
    )

This first steps was to become more familiar with Erlang language. My next steps will be:

use edoc ...
use logger/trace services instead of printing every function call
use generic services (gen_event, gen_server)
create an OTP application (application, supervisor)
use Mnesia to gather statistics
what about OTP release
embed everything in distribution package (automake/autoconf ?)

Becoming nerd...

2006-11-15T00:00:00+08:00

Oh no! I will become a real nerd if I continue to laugh at those stupid (and so gr8) jokes!
http://xkcd.com/c184.html
Only one excuse: I used to work in 3D computer graphics field ...

To Zune or not to Zune

2006-11-14T00:00:00+08:00

Zune: an iPod-like with Wi-Fi!
... but I don't like all the marketing stategy behind those products :(
Any iTux project?

Home Multimedia System

2006-11-10T00:00:00+08:00

Since I read this post from Joel Spolsky about Sonos, I cannot wait anymore to get such a cool wireless distributed system everywhere in my house ... but I will try to wait a bit more for two reasons: first my house is too small :), second I would like the same kind of system but also including video.

Pacstatistics

2006-11-04T00:00:00+08:00

(from the humor archives)

My next programming language

2006-11-02T00:00:00+08:00

... This is a personal message address to me in future ...
What is my next programming language?
Scala , F# , Haskell , OCaml or Erlang?
Yes, my next language will be functional, and I will focus on improving my skills in concurrent programming and distributed applications. And here come the reasons for the choice of the above shortlisted languages:

I just experimented the threading system of Python ... that really not fair guys, so I quit Python!
Scala use the Java threading model, that's good as far as I know (and Scala looks fine!);
F# enable to use all .NET library so I could experimented Tao on Mono (.NET threading is also good, IronPython rocks);
Haskell is pure ... I'm curious to understand those mysterious monads;
OCaml mixes functional and imperative ... really efficient and yet simple;
Erlang embed asynchronous model inside the language ... concurrent and yet simple.

Why concurrent programming? Why distributed?
Nowadays computers aim to solve complex systems: large amount of data to process, large number of interactions, or naturally distributed systems. Parrallelism and distribution seems to be in the pipeline with multi-core processors and clusters supported onto a network more and more efficient (optic-fiber at home by example). Without looking at language theory (see Future of software design?), my next language has to enable a software design with those intrinsic features: parallelism (data or computing) and distribution.
And why functional?
I don't really know ... for the fun??? I read a lot about Haskell recently; I just want to change my mind with another programming paradigm, and I secretly hope that my functional code will be better optimized on multicore machine. If you want real justification you may have a look at Functional Programming For The Rest of Us or Everything Your Professor Failed to Tell You About Functional Programming.
Final choice of my future language
Still have to choose one in the shortlisted choices, but with which criteria? Type inference is a must (coz above all, any good programmer has a special quality: he's lazy). But I don't see a strong typing as a must-have: it sure solves problem, but not all, and in the end you still rely on unittesting.
Let's do a first cut in the shortlist based on personal assumption: .NET is a better platform than Java (wow!). So:

remove Scala: F# offer same kind of possibilities using .NET;
remove OCaml: shares a common ML-like syntax with F# but F# offer .NET platform access where OCaml offer efficiency.

Haskell is pure but I prefer easy development aiming at concurrent and distributed programming, which is not part of the Haskell language itself. Then I have to choose between Erlang or F#: let's go for Erlang, let's concentrate on distributed development embedded in Erlang language. If later I really need/want .NET platform, it will still be good time to review all those choices adding new languages progress!

Mirror neurons and understanding by imitation

2006-11-01T00:00:00+08:00

Thanks to Hanna Wallach for pointed to some articles about autism and mirror neurons .

In the field of agent simulation in a VR world, some AI method give to an agent a representation model of its world where it can simulate approximate behaviors of other agents before to take a decision of its action in its real (virtual) world: simulation of a virtual world inside a virtual world...

But the first time I discovered this idea of "interpreting a model of other" was with Hercule Poirot who try to imitate the person he want to understand, and even some small movements (like the position of hands or the smile...) can help him to "take the place of other".

Blogging is not easy!

2006-10-31T00:00:00+08:00

my English is so clumsy! (is "clumsy" the good adjective to express how bad it is?)
my posts are too long to express any clear idea
there is still no code!!!

@home

2006-10-31T00:00:00+08:00

I recently discovered Africa@Home.
From of software engineer point of view, "@home" projects are very interesting. And when they are used for humanitarian purpose, that's even better, isn't it?

From how to what

2006-10-31T00:00:00+08:00

Some of my good friends liked to kid me this way: they show me a program they just wrote/discover and secretly bid if I will ask my favorite question: "do you really need this?" [1]. Before they told me this fact, I didn't realized that I often ask that question. The bad thing is that it could sounds like "what useless is your work!" ... I'm so sorry if some people understood that of me. The good thing is that now I take care not to say it again ... but I keep remind the real meaning: what is the point which is really important in that? In fact the real question is not about the word "need", but is about the word "this".
To my mind, the real importance of this question is about distinguish "how" and "what" [2]: this point is useful for me in any area but let illustrate it with programming language.
When I learned to program I often thought in a problem-solving approach: I searched how to solve the problem. Perhaps because of the language I used: C. This is a perfect example of language to express not what you want to do but to express what you have to do to get this result: this is exactly how to do (and you can even set the register of the microprocessor because you know exactly how to do to obtain your result ... and how the processor work, wow!). This is really efficient on nowadays machine ... but with new processor instruction sets and hopefully new processor architectures (x86 is not really the best one!), with also concurrency in its way to be widespread everywhere, the compilation of C code may result in less efficient running code that compilation of high level language. OK OK, some times a cast in void** is easier and more efficient than anything else, but I'm really curious of what Haskell compiler developers will be able to do.
Another approach of problem is to concentrate on definition of what we try to solve (problem-defining approach?). The idea is that if you know exactly the prototype of the C function to write and its documentation, 80% of the work is done. The best example I can think of is a logical programming language: prolog. Those kind of programming give you an reasoning engine to which you just have to give facts and rules: he will search for you the result you want. You have to define what you know and what you want, he knows how to do, really! It's so convenient to express complex reasoning system of AI.
More surprisingly (to me at least) another language which guides you to think about what you want is SQL. That's only after having written some fairly complex queries (like mathematical integration of probability distributions) that I realized that I was completely focus on the data I have and on the data I want, and no way I can define how to proceed in SQL! Those languages can be seen as declarative languages: express your knowledge of what you want, let the engine do it for you.
Another kind of language can help to problem-defining approach: the functional languages. Because the way to write functional code is to think about what is entry of function and what is the output: the "how to do" is replaced by "what is this function" (for example you don't write how to loop, you call the function which solve the next problem after the first step (often recursion)). Main difference between logical and functional languages is the internal engine of logical system (backtracking) which enable in logical language to not make difference between the parameters of function and the return value: functional language let you define what is the result and what is the process (here the developer is happy) where you have to use (and tricks) the logical language process with languages like prolog.
All that to say that in most of the case a language focusing on defining data and their process should be more convenient to design robust solution to well defined problem. And so my next blog post will probably be on what is my next language (matz said it's good to learn one language every year!).
[1] PAF used to call it the "coquellienne question" [2] Lot of those ideas come from my studies/past experience at ENIB/CERV

Re-discovering my music

2006-10-22T00:00:00+08:00

I changed the sound system of my computer from the cheapest one to a new Sony branded but yet very simple one. After 7 months using the old stuff, I just re-discover my music. That's too good, and Popa Chubby guitar's sounds better than ever!

CS in learning, learning of CS

2006-10-22T00:00:00+08:00

About education of CS and CS in education.
In the President's letter of Communications of the ACM [March 2006, Volume 49, Number 3] David A. Patterson explained how to "re-invigorate computer science curriculum", and request for evolution of computer science education. Briefly, improving CV is achieved by two general ideas. The first is "Technological update": student should study and use tools (ex. Eclipse) as well as library (ex. JUnit) for homework, and also a focus should be given on study of parallelism. The second way to improve CV is to make "Course I would love to take": for example he cites the construction of own supercomputer through FPGA, but also participation to an open-source project.
The point of view is mainly oriented toward programmers. And I agree that programmer students must be confronted to industry's reality: they should have used during home-works a version-control system, followed any methodology ... which imply that teachers use those tools too: this is not always the case as they are often researchers and don't have the same needs as industrial do.
The education problem is not so simple if we think that today programmer can be tomorrow solution architect. Where the programmer will be interested in the better version-control system, the architect will like to know more about deployment tools. The problem arises: taking time constraint into account, what are the best things to teach to please future programmer but also future manager? IMHO "what" we learn at school is not so important as "how" we learn it (curiously, when I am programming I always focus on "what" I do instead of "how" I do it ... could be the next blog post). How we learn is of course the way we learn it but also the context or environment in which we learn it. If I would easily link the way to learn to pedagogical problem (see also an interesting blog on Non linear learning, the non linear internet), "how" we learn is certainly always oriented towards the learner: what is his motivation? And I guess that the only common interest for all students but also teachers is the CS culture: tools, languages, methodologies, communities, blogs, research ... Students look only for help/guide/mentor/model to develop their computational thinking; if the teacher is aware to be an entry-point to CS culture, students will learn the needed knowledge from any source: lecturer, books, internet or themselves! Motivation is good enough (see Scientists call for government to help fund video game research), students will learn what they need. Ok, this is the optimistic point of view of education.
Lots of random thoughts ... I hoped that bloging would help me to organize that confused brain of me, but instead it help to put in it some more random thoughts! All those ideas come to me when I thought to the recruitment problem: how to evaluate knowledge and knowledge use of a candidate? how to define the need of a position? ... still have so few ideas about it.
So I conclude with the only thought that is clear to me:

Education

2006-10-22T00:00:00+08:00

MacMillan English Dictionary

2006-10-21T00:00:00+08:00

This is my first blog: hopefully I will make progress in writing after a while ... please be patient ;)
This is also my first English writing: I mean first text willingly written in English just for fun. We'll see if the spell checker is good. Making this blog will certainly encourage me to use my new MacMillan dictionary for English learners: easy to search, easy to read with highlight of very common words (the "must know"), and easy to understand with very simple definitions. Particularity of this dictionary is that all the definitions are given using only a very small subset of English words, which is called the base vocabulary. I purchase the book version and got in same time free access to the on line version, which is really good and have the wonderful advantage of giving pronunciation by sound media.