Ravi Mohan's Tech Blog. To read my non technical blog, click here

Saturday, February 21, 2009

Gitting It after all

I finally moved to git (from Subversion). The key to understanding git is to understand how the various "objects" (blobs, trees, commits and tags) form a Directed Acyclic Graph, and then understand the various version control commands in terms of modifications of and traversals on this data structure. Approaching GIT from a "this is another version control system like [your favorite VCS]" is the *wrong* way to go and results in people end up confused because then git will seem to be doing things (annoyingly) differently from what they are used to.

The one minor nitpick I have is that most of the java ide s don't work well with git, but at least to me that is a blessing in disguise. I had planned to do a project with the Java/Eclipse combination but git (and the development workflow it enables) was so compelling that I am using Emacs and Haskell instead.

Which is a definite win. :-)

Update:- Apparently the Intellij IDE has a GIT plugin in the latest version. I greatly admire the product, though I don't use it myself these days.

Friday, February 6, 2009

Exploring Game Engines

A few of us meet on the last Saturday of every month to review our technical progress (or the lack of it). This is somewhat like an iteration meeting in an agile project but focussed on personal achievement. I've written on such "Loser's Club" meetings before.

Recently we added a new wrinkle - each participant of the monthly meeting sends a weekly progress report to the others explaining what he worked on this week.


The following is the (lightly edited) report I sent a few minutes ago.


For the first time in a very long time I worked every day of the week without unnecessary distractions.

As you know, I am working on an AI simulation project. Visualization is a key component and to understand how best to do this, I've been working on understanding the game loop in game engines and what modifications need to be made to use it in simulations. There seems to be a trade off between running the simulation as fast as the hardware allows (needed for effective sims) and slowing the simulation down to (some small multiple of) the screen refresh rate (typically 50-75 Hz) so humans can interact effectively. Networking multiple machines (the simulations needs to, ultimately, run on a cluster) has design implications on implementing the Game Clock (or Sim Clock).

One approach is to completely decouple the sim (which could write the results out into a file, say) and the display (which could work off that file). For some algorithms, ( eg Apprenticeship Learning) , where human intervention and process modeling is part of the learning process, this approach would be problematic, and anyway networking is still an issue, so I need to find a good approach).

I have the beginnings of a really nice game framework (if I do say so myself). I have implemented multiple buffering strategies (pointer flips vs image redraw - The j2se comes with all this bundled up but since the final implementation will not be in Java I am implementing them from scratch to get a good understanding of how it works - only machine for e.g pointer flips give a 50 % boost to the fps), image loading, and a controller that allows either human or algorithm control (most game engines tie the event handling into the guts of the game).





I've attached a (really yucky for now) screenshot. It just shows some sprites moving against a nondescript background, but I am doing some interesting experiments behind the scenes.

In the coming week, I hope to resolve the sim vs game timing issue and also understand (a) tiled backgrounds and (b) how level editors work.

Regards,


The act of writing out what was accomplished every week is very helpful. There's nothing like having to write "Nothing useful accomplished this week" a few times in a row, to alert one to the fact that your life is flowing down the drain!

Last week, I also read "One Jump Ahead:: Challenging Human Supremacy In Checkers", which is an account by Dr.Jonathan Schaeffer of how he built Chinook, a program to beat the Checkers World Champion. This is a very interesting and (to researchers) very inspiring book. Jonathan also explains how he went on to solve Checkers (in the sense that Tic Tac Toe is a completely solved game). All in all, a great account of how research is really done.

Friday, January 30, 2009

Fad Alert

With a subsection of the Ruby Fanboy crowd moving to Clojure, there is a lot of uninformed talk about Software Transactional Memory (STM), mostly regarding how it "solves" concurrency in a multiple core scenario and how it is very "intuitive".

Bryan Cantrill restores sanity to the discussion via his blog post, "Concurrency's Shysters"(Be sure to read the ACM paper he refers to in the post).

Unless you really understand the various concurrency mechanisms, to the point where you can implement some of them and know the theory therof, please please don't code concurrent programs. Thanks in advance.

PS: This is not a knock on Clojure itself. Rich Hickey, its creator, is extremely talented, dedicated and very knowledgeable. Clojure is a great piece of software. This post is a reaction to some uninformed enterprise developers' mumblings on how Clojure is the next bandwagon to jump on.

Monday, January 19, 2009

Book Treks

Working through every single exercise in a good technical book is a fascinating (and educational!) endeavour. Two of my friends are working through some tough technical books in this fashion (and blogging about it).

My friend Manoj wanted to take a break from writing J2EE code and so took a sabbatical to work through SICP. He is blogging his progress here. Another friend, Himanshu, is working through Van Roy and Haridi's "Concepts, Techniques and Models of Computer Programming" and is putting up the answers to the exercises here.

Thursday, December 25, 2008

Two levels of mathematics

I've written about the connection between programming and mathematics before. My latest discovery is that there are two "levels" (for lack of a better word) Mathematics - one inhabited by engineers and one by mathematicians. This divide seems to carry over into books as well - thus, taking Calculus as an example, Gilbert Strang's book is an Engineer's guide and Spivak's book is for mathematicians.I am working through the latter, and while it is very clearly written, it is a whole different level from any book on Calculus I've worked with before.

Friday, October 3, 2008

An Unsatisfactory Proof

To be proved

"If the symmetric difference of sets A and B is a subset of A, prove that B is a subset of A"



symmetric difference of A and B = A U B \ A ^ B (using U for union , ^ for intersection and \ for difference).

What I've come up with


The Proof


Let x be an arbitrary element of B.

Then x is also an element of A (case 1) or it is not (case 2).

case 1.

If an arbitrary element of B is an element of A then B is a subset of A .

case 2.

x is an element of B but is not an element of A. In which case, it is an element of (A U B) \ ( A ^ B), ie it is an element of the symmetric difference of the sets A and B. Since it is given that the symmetric difference of A and B is a subset of A, x is an element of A.

Since x is an element of A in both cases and since x is an arbitrary element of B, we conclude that B is a subset of A.

Q.E.D

I keep getting the feeling there is a more elegant way to prove this. If anyone wants to write to me (or comment here) I'd appreciate it much.

PS: - the proposition is obviously true (draw a Venn diagram to see why). I am asking for help on the (structure of the) proof itself.

Friday, September 5, 2008

The key to understanding proofs

is to realize that the exposition of a proof is distinct from its derivation. The (published) exposition is a very condensed description of the what and why. The (usually unpublished) derivation is about the how (the proof was derived). Reading carefully between the lines of the exposition one can often discern a faint outline of the creator's thought process but that's about it.

A (weak) analogy is having the binary code of a program that does something wonderful.Without the source code(the step by step derivation of the proof), one has to use disassemblers (digging into the exposition)to figure out how it works. Having the source code would be better in some contexts, but most proofs are "binary only".

Having said that, nothing stops me from starting from the givens and trying to prove the conclusion myself, which is a worthwhile exercise in itself. ("worthwhile" as in "what does not kill me makes me stronger" ;-) )

Saturday, July 12, 2008

The JVM and Tail Recursion

In an attempt to investigate the performance of a trampolined interpreter on the JVM, I discovered something interesting.

First, some background. In essence, trampolining is a strategy used to avoid stack overflow on platforms (like the JVM) that save to the stack even when not necessary , e,g while doing a tail recursive function call. So after doing a CPS transform and then trampolining it by returning a lambda wrapped "thunk", my interpreter *should have* handled an infinite tail recursive call *without* a stack overflow exception. But it failed anyway!

After Dan Friedman pointed out (by email) that "If you use exceptions in Java, you will regain tail recursion. I think that is the only way to get around Java. ", I did some digging and found something even more interesting.

Tail recursive (java) functions are properly handled by some java JVMs (specifically the JITs) and not others! See this article for a good explanation.

Try running Listings 4 and 5 (from the referenced article) on your JVM :-D . I suspect that C# code equivalent to the two listings in the article (numbered 4 and 5) would both run perfectly. Can someone with a Windows machine and dotNet installed let me know if it works? (post a comment here or send me email! Thanks in advance!)

Footnote: the conversion of the tail recursive function (in the article) into the while loop form is one example of how a trampolining interpreter could "break stack build up".

Wednesday, July 2, 2008

Directions

This is the first post on my brand new blog. The essential difference between this blog and the old one is a change of "voice" and focus.

Unlike the "catch all" nature of the old blog, this one will have a sharper focus, specifically on things technical (mostly code/mathematics/algorithms etc - but "technical" is used very broadly - I could very well end up dissecting the Black Scholes Equation for pricing derivatives, for example.). I will create a separate blog for non technical ruminations (TBD).

So what's happening on my end? Life is insanely busy (as usual) and I am meeting great people (as usual) and situations (as usual) and the great difficulty (as always) is choosing among the zillion challenges to tackle next. "So little done, so much to do", to quote Cecil Rhodes, but hey it beats a boring, "normal" life any day.

On the technical/programming front, I am investigating the impact of various (language) interpreter designs on execution time. Over the coming weekend, for example, I am trying to get some sense of how much overhead trampolining adds to interpretation time (vs a normal recursive descent parser).

So that is what I'll write about in the next few entries. And then there is the reinforcement learning library I wrote for the good folks in the DRDO (Defence Research Development Organization for non Indian readers). I could probably spin that off into an open source project once I (find some time to) tidy it up a bit.

Then there's the derivation of concurrent algorithms, the relational-algebra to SQL query generator thingy I've been fiddling with off and on for a while now, and thoughts on programming with typed channels and machine learnng algorithms as programming primitives. Lots of interesting things to write about.

Stay tuned.

Hello Word! It is good to be back.