Output of a curious mind

"Far out in the uncharted backwaters of the unfashionable end of the western spiral arm of the galaxy lies a small unregarded yellow sun. Orbiting this at a distance of roughly ninety-eight million miles is an utterly insignificant little blue-green planet whose ape-descended life forms are so amazingly primitive that they still think digital watches are a pretty neat idea." - The Hitchhiker's Guide to the Galaxy

It was pleasant to be back in DC for a couple of days even if we ended up staying in one line or another most of the time (we waited more than an hour to eat at busboys and poets). I am glad we were able to stay with Lauren and Jeff in Dupont circle.

The inauguration per se was a massive cluster fuck, at the last minute we exchange our purple tickets for some orange tickets, and after some sneaking in were able to enjoy a really nice view of the main action :



The most impressive was by far the crowd in the back even if I could not only see up to the Washington monument :



We had invitation for two official balls; the youth ball and the staff ball. The youth ball seemed more like the proms I never had. We ended up stuck in the lounge area and never got to see the main stage action.



The staff ball was much better event. It is the last official presidential ball and takes place the next day, does not compete with any other events, and the media are not invited. So we got to see Obama, the VP, and couples of guest in a short amount of time.


The band line up, kept secret until the very last minute, was pretty good : "Arcade Fire" and Jay-Z.

I was excited to read this classic but I ended up hugely disappointed.

Mainly because of my total undifference to the two main themes of the novel: religion and patriocism.
I can try to understand the struggle of someone diverging from such strong cultural artifacts. But my interest for them is comparable to the eternal question of how many angels can dance on the head of pin (zero by the way, angels do not dance. It is not a holly activity).

I feel really let down by this book, maybe another case of over hyping ?

Coming soon to a blog post near you :
- books read in 2008
- white pictures of Chicago
- account of Pierre and Melodie weeding in Manathan

If you have not catch up on the history already go read this decent NYT article first.

The war is not a surprise to anyone and this explain the level of readiness of the Russian.

Do not pay too much attention to the rhetoric on both side. Georgia may be a democracy but more in the Russian sense than what the founding father had in mind when they wrote the US constitution.

The most important element that western media tend to forget is that Gerogia started this round. On August 7 they fired rounds of heavy artillery, large-caliber mortar and Glad multiple launch rockets on Tskhinvali. A clear and brutal act of aggression that begged a response from Russia.

The real question is why?

Ossetia is an impoverished piece of land with no natural resources. The province has been more or less autonomous for a while and short of an ethical cleansing impossible for the Georgian to control.

I try to never underestimate the stupidity of politicians that use patriotic rhetoric but provoking Russia is pure suicide. It is a loosing move for Georgia from the beginning. There must be more to it so lets zoom out a bit.



So where does the move come from?

The players are Europe and the US. Europe has a strong interest in keeping peace around its borders and want to avoid confrontation with Russia at all price. This leave the US as the architect.

I can see two possible reasons for this move.

A play to reinforce NATO. The Russian drew the red line on Georgia and Ukraine. After the war is over the US will have the green light to come protect "the peace". Georgia will become a direct NATO/US protectorate even if they will not become an official member in the short run. What is here for Georgia? Reconstruction money, a lot of it. This will be a god send for the ruling party. Also they will clearly move out of the Russian sphere of influence.

For the US? A big finger at Russia next to their border, but more importantly the control of a chock point. Just look at the map of the region. It will help isolate Russia from the middle east and surround Iran even more. The US will also be able to personally protect the pipelines in the region.

Also this crisis will reinvigorate the importance of NATO in Europe. Europe as lost interest in NATO after the cold war was over. There is no more direct utility for it, therefore no good reason to accept US military dominance inside Europe. But with Russia showing its claws again Europe will probably reinforce their commitment to the alliance.

The second reason might be a side move on Iran. Military actions in Iran, in the form of air strikes or a maritime blockade, are becoming more and more likely as the electoral victory of Obama seem unavoidable.
There is two possibilities here. Just distracting the Russian or creating a bargaining piece. We do not flood Georgia with advanced weapons system like we did in Afghanistan if you let us fuck Iran.

The timing is also critical. The Olympic game makes it easy to push all the action under the radar. More importantly; China, the other potential player in Iran, will have its hands tied for the duration of the games.

If this is about Iran things will be moving very fast to keep taking advantage of the game.

My friend Olivier resurrected is musical blog. It is a group project and everyone is invited to participate to some cross continent musical adventures.



Be sure to check it out!

Nothing more distracting than the big boys re-starting the cold war.

This book is a very interesting cultural perspective on agriculture.

The main thesis is a perspective shift: from our illusion of dominance over nature, to co-evolutionary relationship.

The classical example of co-evolution is the interdependence between the bee and flower. By definition co-evolution are mutually beneficial making the question of who is dominating or taking advantage of the other meaningless.

The author explore the reason of our perspective of dominance and distance toward nature using the classical dichotomy between Dionysus and Apollo. Apollo having the upper hand in our culture thanks to Christianity successful battle against Paganism.

This story is narrated around four different desire and an associated plant

Sweetness/The Apple

This story follow the food step of John Chapman aka Johnny Appleseed during Europe colonization of America.
We learn that apples are extremely heterozygous, that is an apple tree will share little resemblance to its parents. Therefore apples are very rarely sweet and fit for consumption. All the apples in a supermarket come from grafts, they are clone of each others.
So if not for their sweetness why were apple tree such a land mark of America colonization? Because it was easy to produce alcohol from them and this often was often a much more sanitary drink than water.

Even if cider was considered cultural acceptable by the puritans it still ended up as a target of the temperance movement with public calls to cut down the trees.

Apple as healthy and delicious fruit is just a relatively recent PR coup of the industry to make the fruit acceptable again.

Beauty/The Tulip
After pages on the aesthetic values of flower (factoid only African culture do not value the beauty of flower, probably because they are too busy trying to find food). The author give an account of the first speculative bubble. The mechanism of which are still very relevant today. Will we ever learn form our mistake?


Intoxication/Marijuana

Explore the motivation for the war on drugs and describe the associated loss of civil liberty.
Also speculate on the cultural and litterer influence of cannabis and other drugs as mutating agents for ideas.


Control/The potato

Examine the strong cultural and political opposition to the introduction of such a wonderful staple food in Europe illustrating again the struggle between Apollo and Dionysus.
Then the author narrate the Irish famine a perfect illustration of a Mathusaliam economic disaster. The principal cause of the famine, the monoculture of potatoes is also the greatest sin of modern agriculture.

This part of the book give account of modern agriculture practices. In particular the clean field method, where the land is regularly dosed with all kind of chemical to make sure that only the desired crop can survive.
After spreading some chemicals called "Monitor" the farmers do not go in the field for four of five days even if the sprinkler system is broken and threaten to ruin the lot. Just to prevent aesthetically unpleasant, but harmless brown spot due to aphids.

The most striking part is the account of the industrial farm, which after disregarding organic agriculture as unable to feed the world, admit that he does not eat his own potatoes and himself prefer to eat organic.


The last part is devoted to genetically modified food, its dangers and unknowns. It explain the principle of "substantial equivalence", that is mixing an approved gene or chemical with an harmless plant does not require any testing or labeling before being commercialized. No research on genetic instability. Thanks lobby, thanks congress.

You will learn this precious pearl. GMO are not considered food and therefore are not under the umbrella of the FDA, they are instead classified as pesticide and as such are regulated by the EPA ! Bonne appetit.

I managed to successfully qualify for the next round. I decided to use Haskell because I was already into it after the icfp contest.



Pb A: Saving the Universe
I started with a backtracking algorithm, simple clean worked well on the test. But on the first input: memory explosion !!!

So I first blamed my Haskell skills and look for memory leak. I also tried more sophisticated optimization with marginal result.

Then it hit me, it was not my implementation or my poor understanding of Haskell, it was simply the wrong approach. Sure I was getting correct results but in O(2^n).
I look at the problem again and there was an obvious and easier dynamic programing approach. All the sudden my problem became O(n).

Pb B: Train Timetable

This one was suspiciously easy. I coded a greedy algorithm in minutes and spend an hour trying to find a fault in my reasoning and implementation. Trying to find degenerated cases and counter argument. It simply seemed to simple.

I guess it was.

Pb C: Fly Swatter

A geometric problem: after gathering the needed formula I was figuring out all the corner cases and I thought there were just to many of then (4 to be exact ...). I wondered if there might be a simpler approach. Let see, integrating weird shapes ... Monte Carlo !!!

Haskell is used in a lot of trading firm, they must do stochastic simulation with it. So I should be able too.


After figuring the in and out of random generation in Haskell, I have a very elegant solution. That converge sloooowlyyy. Again I blame my understanding of Haskell. Decide against parallelizing the code since a twice as fast version of something that is very slow is still slow. Try Python not faster.

Back to solution one, but sadly I was out of time ..

The ICFP Programming Contest is one of my favorite contest. Sadly in the past few years I was not able to compete live. But this year the old team was back ! With Pierre in New York and motivated, we were able to have kick some martians' butts.

ICFP was always for us a reason to learn a new programming language. The first time was OCaml, two weeks before we choose the language and do our homework, but nothing beat getting your hand dirty with a short deadline to learn.

This years we decided to use Haskell (our team was named LazyMonkeys).
I am already pretty decent at it but it was a first for Pierre. Who by the way did a pretty good job. It was funny to see him use OCaml idioms like let in instead of the favored where, but I was never found of where too since it remove the ability to read the code top to bottom.

The contest was very interesting with unusually clear and short instructions, I did not even print them. You can read all about how you had to help a poor rover find his way home on Mars while avoiding the Martians here. It also had a nice range of possible progress from a simple steering solution to a more complex strategy.

At first we kind of doubted of our choice since we had to do real time analysis of a telemetry feed and I seriously consider switching to Erlang. But there is good threading support in Haskell so we stayed with it.

Our solution :

We have a very simple one based on fuzzy steering. With a thread managing the network, one for the motion planning and a last one for visualization.

We lost a lot of time on the network part. The task recommended to disable Nagle’s algorithm which was only possible with the more advanced Network.Socket. The issue that gave me a lot of grief was that on the OS X 10.5 when doing a gethost on localhost the first answer is a IPv6 address. Network.Socket does not seem to be able to manage IPv6 so it was difficult to debug the issue.

We used OpenGL for displaying our robot activities :

It was very helpful in detecting logical errors.

Summary, what we did wrong:

• Did not have a comprehensive test bed to be able to measure our progress. Would have been very useful at the end when we try to tune our parameters.
• Did not create a trigonometric/geometric module early enough
• Discover that Aquamacs new version is way cooler that Emacs.app and spending 2 hours updating my .emacs

What we did right:

• Create a SVN in advance
• Build the OpenGL display, the one offered by the server was good enough for the first day but when we added more complex comportment we need more visual info.
• Choose a robust solution
• Made good use of Haskell laziness

I am a big crypto nerd. I read David Kahn's "The Codebreakers" when I was young. After opening Cryptonomicon my classes attendance dropped for a few day. It used to be a dream of me to be cryptanalist. I even had a little moment of glory when I broke an algorithm that one of my graduate teacher presented as a possible thesis project in just one night.

It was very exciting to be able to see and PLAY with an Enigma.


My over excitement may have freak out K a bit but there was so many interesting machine to see !!!
Like the famous Bombe :



I was also able to add some very good picture to my collection of "Me and Super Computer".

K got a job for the Obama presidential campaign. So we packed all our belongings in oversized truck and left DC.



The road trip was pretty mellow. We were looking for more weird museum and adventure parks. Sadly we only crossed a few at a late hour.

We made good use of K's ipod. We listen to Randy Pausch's Last Lecture and tear up a bit. We also had a large stack of podcast and we were able to catch up on some This American Life (K even agreed to listen to Stack Overflow).

WALL-E is an instant classic. In part because it is cleverly overflowing with references, from the obvious 2001 to the classics Pixar. Finding all of them will probably fill endless discussions with friends and many pages of student's papers.

One in particular really touch me.

!!! Spoiler Alert !!!



Back on earth after EVE fix WALL-E the adorable little machine loose is personality. This immediately reminded me of Robert Heinlein's "The Moon Is a Harsh Mistress". I read it probably when I was 10 or 12 during the period of time where I devoured all of Asimov's books and other SF classics.
It contained a lot of new and interesting ideas for me at the time: the sentient AI, the organization of the underground rebels, the libertarians ideas and more is coming back to me as I am writing this.

The end really affected me because, unlike WALL-E, Mike does not recover is sentience.

I was so sad that I rewrote the end.

"Don't reinvent the wheel, just realign it."
Anthony J. D'Angelo

It is difficult in programming not to reinvent the wheel and I can see two reason for that:

First, because you can! (and it is more fun!)
It is surely desirable as a learning exercise since algorithms should never be magic black boxes, but in real life this is an extremely bad idea.
Even implementing a seemingly simple algorithm is full of little corners and non obvious degenerate cases. For example, a careful inspection of the algorithms in any textbook never fails to reveal a lot of mistakes (computer algebra humhum).
We all think that we are exceptional programmers but this is simply hubris. People unsure of their abilities do probably a better job because they are going to be very suspicious of their own work. Every piece of code should be considered guilty, even with good unit tests. If the code was automatically derived from a formal specification you should be extra suspicious of the specification.

The second reason: you do not know about similar problems that have been solved (or at least extensively investigated). Or you fail to find an interpretation of your problem in terms of a well known one. (Your best shot is usually to try to map it to a graph problem.)

Sadly, this book does not teach you humility but it is a very good resource for the second problem. It is composed of two major parts.

The first half goes over some general principles like linear programming and backtracking. The techniques are illustrated by engaging little war stories. Big-O notation and NP completeness proofs are also reviewed.

The second is a catalog of data structures and algorithms divided into relevant categories. No actual algorithm is given but instead a reference to possible algorithms with their respective trade offs. Each section has an illustration that makes browsing through the book in search of inspiration very convenient.
Reading the catalog I could not stop thinking that a wiki would be a perfect home for such materials.

The book does a very good job at exposing a large quantity of techniques and how to combine and adapt them to solve your problems.

If you have never been exposed to those ideas before it is probably a bad place to start, but if you need to refresh your memory and fill some gaps the materials are very appropriate.

The negatives :

- a lot of errors for a second edition, but there is an errata on the author's web page.
- references to existing implementation is dated and by consequence useless.

This text book would be an excellent read after a first course on algorithms and a valuable addition to every programmer's book shelf.

"Head First Design Patterns" by Kathy Sierra, Bert Bates, Elisabeth Freeman, Eric Freeman

It is always very hard to find appropriate learning materials. Writing a didactic text is very difficult and often confused by the writer, as much as by the reader, with writing reference materials.
Finding a pedagogic book of quality is not enough, it has to be appropriate for you. It needs to fit your general background. The issue for me is that I have a higher mathematical sophistication than the average programmer and even computer scientist (I know I am so great).
More importantly, it needs to match your previous knowledge on the subject. The key is that the material has to be challenging enough so you learn something new but not be completely out of your grasp or just demanding more time and effort than your motivation provides.

Sadly the perfect match never exists.

Back to "Head First," I wanted to refresh my memory on design patterns. My first introduction to the subject was the Gang of Four book and was probably a bit premature. The value of a solution to a problem you never had yet is not great.

So I wanted to get a different perspective and this book had some good reviews.

The style is very visual :
I was not very convinced at first but after the little introduction on why it is important to keep you engaged with the material I decided that I should give it a try.

Conclusion : not for me. It was a big error on my part to read an introduction book on a subject I am already familiar with. I needed a reference book to refresh my memory and learn more advanced patterns.

Also, it is not dense enough for my taste. I am used to reading difficult graduate texts and I need to be challenged by the materials.

I really like the annotations on the diagrams but the little story was not motivating for me at all. There is a lot of wasted space with gratuitous pictures. I enjoy some entertainment like the side notes in Concrete Mathematics but this is too much.

I think the book has huge value for a first time learner and someone that does not have a lot of academic dedication.

I am back to reading the GoF book and I really appreciate it this time.

I rarely lay my eyes on mediocre content anymore. Collaborative filtering has become very good but too much content come out. The filter is not deficient or the threshold too low. No, there is simply too much good content that deserve to be read, a blessing and a curse.

We need tool to help us manage this stream of good data. First locally with local queue offering ease of ordering and organizing (tagging). Then harvest the collective intellect to help us.

We need to combine the collective filtering (reddit and digg) and the collective ranking (google).

I use the example of books because it seem a simple example (away from too many technical terms) and also the time cost of reading a book is order of magnitude higher than for an article.
You may not have wasted your time with a good book but you could have made better use of it reading a better book for you in that point in time.


The problem: My Amazon wish list is exploding. I want the list to go
from helping me remembering what I want to read to selecting which book
I should pick next.

In formal terms: I want to go from an unsorted set to a priority
list. The problem becomes what ordering function I should use ?

A solution: Using social networks and other web 2.0 ideas could be
very helpful.

My fundamental misfortune is that I am extremely curious and reading
books is the principal way (closely rivaled by web articles) by which I
satisfy that need. Also a large part of my pure entertainment comes
from reading fiction.

Those desires compound themselves faster than my ability to read, the net effect is an always increasing reading list. How
bad is it? You cago
see yourself 384 books over 16 pages. Plus a dozen books on my
book shelves :



The solution is not to find more time for reading, I read all day and
watch almost no TV. I could even say that the issue is related to
the best use of the short time I have on this earth. A fundamental
dilemma that could sure use some help.

I used to browse through the list from time to time and select what book I
wanted to read next. But now it is almost too overwhelming.
My solution as a geek is to look for a better tool (not to clean up
the list).

Amazon focuses on helping you add items to your list. This probably makes
perfect sense for them because they are helping their customers and the
pathologically curious are, perhaps, not a big market for them. But I would
love to see the data, to be sure. Notably, the distribution of wish list size and how size correlates to sales.

Netflix does not really have a better approach; your wish list is
ordered for logistical reasons but by the customer and the end result is
not much better once your queue size explodes.

There is a very similar problem that is currently being worked on: reading web articles with a user rated aggregate. And I think a
similar technique could apply.

First some very simple additions to Amazon's wish list:
(a) TAGS
obvious
(b) Search box
idem

The principal difference is that the problem is orders of magnitude
smaller and less time critical. So we have more processing power at
our disposal.

So here are my suggestions for the ranking function:


(1) Multiple hits by one's self
What mostly ends up determining which book I buy is how many positive references I see. I might read a review positively recommending it and, since I am interested in the subject, I add it. But the buying decisions will mostly come if I get multiple references.
Every time you see a positive reference you can click on a reddit-like up arrow (or down for negatives). Will also happen when you try
to add the same book twice.


The system should make it as easy as possible for you to add this
input. Not only when you are connected but even more importantly off
line.

(c) Easy on/off line addition
Being able to use your cell phone, text message and even recognition of bar codes
from pictures.


For the other criteria we need external information and the most
natural source is peoples' ratings of books they've read. It also makes sense that
the to-read and already-read list be integrated.

(2) The crowd at large
How popular is a book? Harder than it
seems. The book needs to be compared to other similar books (a
hard pb in itself) but also take into account the general popularity.
There is also the difficulty of determining the difference between bad and controversial/not for everybody.

(3) Friend and friend of friend
But actually not really. Your friends are usually not a perfect match of your taste and interests (not a bad thing at all). There is sure to be some overlap.

(4) Recommendation
Your friends may not exactly share your taste but they know
you. They should be able to recommend books specifically for
you.
An example, you did not really like that book but you think that K will love it. Or, this
is a very good introduction, the materials were way too easy for you and you
wasted your time but P was looking for an introductory book.

(5) Semantic graphs
Other people that may share your interests but
are not your real-life friends. They are probably a better predictor of your
taste. Of course it is a hard problem to identify the relevant subgroups.

Bonus : Time clue
My interests go through cycles, it would be great if the list could take advantage of it.


I am sure that everybody who tried to have an annotated and rated
mirror version of their library online discovered that it is tedious, even
with great tools like Delicious' iSight scanner abilities.

So the wish list needs to be useful even without the social part
and have enough value to make it worth it by itself. Hopefully items a, b and
c would do the trick. It could nicely bug you about books you
purchased after a while (bonus: figure out how long it will take you
to read it).

This service would have to be integrated into a lot of other services. It would
have to be a Facebook app, use Amazon web services etc...

How to monetize the service? Ads, percentage of sale from books, paid for
suggestions?

The perfect rating function could also be an excellent complement to
present /., reddit, dig and co. because there is an over abundance of
good articles I want to read. It is reaching beyond my quick
browsing abilities; I need a way to prioritize the.

I have some papers around on Virtual Machine optimization that I wanted to try in practice so I decided to see how much improvement to the VM used for the 2006 icfp contest was possible.

I started with Pierre's implementation in C because after spending a good part of the night debugging it I was much more intimate with it than my rushed (the contest last only 3 days) and long forgotten one.

So I started by giving the code a good cleaning and taking care of a few low hanging fruits.

First step : profiling.

But before I had to find a good benchmark, the one provided take 20 minutes to execute not very convenient. So I fetched the UM compiler and after some easy modification cut it to a 2 min test, much more manageable.

Sadly gprof is not being very useful in the situation since there is not much function calls going on.
I did not got much better information with dtrace, I was very tempted to try harder and dig deeper with it, but I do not think that it is a good project to learn more about dtrace functionalities.

What I found was that memory allocation and de allocation represent less than 2% percent of my execution time which made all my ideas about better memory management completely irrelevant.

The next step was probably to use an instruction level profiler but I do not really have a good tool under the hand so I went for some simpler instrumentation to the code. Not knowing what part take the most time to execute I could at least easily figure out which one was used the most and start my optimization there.

Again I was disappointed by my finding since there is not much I can do to improve ALU operations.

Then I started looking at the assembly code but I am more of PPC, MISP fan when it come to asm and so far I went to extreme length to avoid x86. I am curious about x86-64 but the VM is very 32-bits oriented I would have to pay a significant cost in complexity to port it to 64-bits.

And I realized that the heart of my problem is that the VM language is by design very simple and therefore is not going to be a good artifact to hack around. I guess those optimization papers are going to have to wait for another opportunity.

But before moving on to something else I am still going to make the code direct-threaded using gcc labels as values feature, just as an exercises. I will let you know of any impact on performances.

The first book of the trilogy "The golden Compass" mostly set the
background for the following books by exciting our curiosity with the
mysterious "dust" and introducing most of the characters. But the story in
itself is barely interesting enough to keep reading. I would have
probably put the book down if not for the warning of my friends that
the other books are much better.
I have to admit that my principal interest ended up being to "find the
10 differences" with the movie.

"The Subtle Knife" is in my opinion the stronger of the books by
pushing the story in new and interesting directions. The book opens a
few new subplots and deepens the mystery surrounding "dust."

"The Amber Spyglass" is in comparison very weak and honestly
disappointing. The narrative completely breaks down in the last third of
the book. Too many subplots are opened and they fail to nicely
converge. It seem that the author crushed the story to make it fit in
one book. Spoiler: The reenactment of the biblical scene of the
original sin was a very promising idea that failed at delivery. And
the moral tale instead of coming out of the blue at the end could
surely have been better integrated in the story.

I wish the author would have decide to properly exploit all the themes
he opened by better balancing the material between the books or having
one more volume.

I am probably being a bit too critical because a few of my friends
over-hyped the last book to me.


The controversial anti-religious theme did not resonate very much with
me mostly because I come from a very secular culture.


The author's main reproach against organized religion is their active
persecution against scientific knowledge that has the potential to weaken their
authority by invalidating their dogmas. The times of Galileo seem long past in Europe but I have to recognize that in the US even in the
absence on this continent of the once all powerful Roman Catholic Church there is still a strong push against science, most notably in the very
successful anti Darwinism movement but also against steam cell
research.



I am not going to talk about the state of affair of secularism in this
country but I do not think that Pullman pushing children "to have to be all those difficult things like
cheerful and kind and curious and patient ... to study and think and
work hard" and encourage them to build a better world for everybody
will destroy their moral value.

Also, sadly, even if at first the book focus on a very dynamic and empowered Lyra, the introduction in the second book of the very strong boy
character that ends up dominating the girl by his mental strength is
very disappointing because if someone has suffered greatly and is still
suffering of the oppression of the church well above science it is
without doubt women.

On a side note, it would be interesting to see if a movie adaptation of
the trilogy will be completed. Even if it was possible to avoid the religious theme in the
first book, it will be impossible for the next one without
completely altering the story and leaving only cute talking animals
fighting against pseudo-nazi fascists