ICFPC 2006: Epilogue

The results of the ICFP contest for 2006 are now available. "Team Smartass" came first, followed by "kuma-" and "You Can't Spell Awesome Without ASM" in the second and third places respectively. Amazingly, the lone hacker "Witrala" was able to take the fifth place. Congratulations!

There is also a a video of the presentation by the contest's organisers at ICFP 2006. It is quite shaky, there are audio and video synchronisation problems and there is a guy sitting near the camera who gets tickled by almost everything into laughing out loud, but it is still worth a watch, especially for those who participated in the contest or those who want to know just how the organisers created the task.

This year's contest has proved to be so popular that the organisers have created a separate site called boundvariable.org dedicated to the "Cult of the Bound Variable".

An interesting bit about this year's contest was that the teams in the first and the third places were both from Google. Another interesting bit is that the individual members of these teams are also ranked very high on TopCoder and have been toppers in various contests organised by TopCoder. "Team Smartass" comprised Christopher Hendrie (ChristopherH), Derek Kisman (SnapDragon), Ambrose Feinstein (ambrose) and Daniel Wright (dmwright). "You Can't Spell Awesome Without ASM" comprised John Dethridge (John Dethridge), Ralph Furmaniak (RalphFurmaniak), Tomasz Czajka (tomek) and Reid Barton (reid).

Update (2006-10-22): Yumpee has pointed me to the ICFP 2006 paper (PDF) written by the organisers.

Fullmetal Alchemist

I generally like animé, but I am not into it the way VikGup is, for example. About the only series I used to watch regularly was Dragon Ball Z (DBZ), before Cartoon Network India abruptly and very irritatingly pulled it off the air just as it was near the final few episodes. I liked the overall story in DBZ, but I felt the episodes and the fights were unnecessarily long and dragged-out, really testing one's patience (it reminded me of Ramanand Sagar's TV series "Ramayana"). I also liked Animatrix a lot. I have watched parts of other animé series, but I have never felt compelled to watch an entire series from the beginning to the end.

I am not a fan of the way most serious animé suddenly switches to "silly mode" in the middle of a scene, with characters swinging their limbs about wildly and screaming for no good reason, the drawing degrading in quality with quivering outlines - it just ruins the whole experience for me. I also find a bit odd the technique of showing an essentially still frame and then moving the camera about - I realise that the animators want to save effort and that it is a commonly-used technique elsewhere, but it seems to be used a lot more often in animé and I wish they didn't do it. Finally, the English dubbing is almost always terrible and I wish I could just see them in the original Japanese with English subtitles (I believe the DVD releases allow you to do that). All this aside, I must admit that many of the more popular animé series are beautifully drawn and have an overall story that is so fantastically different from anything else that one generally gets to see.

When I read Stevey Yegge's blog post on animé, I felt an urge to check out some of the animé series that he recommends. As luck would have it, Animax India has been showing some of the animé series that he highly recommends and on a whim I decided to check out Fullmetal Alchemist.

I am not disappointed at all - this is a wonderful series. It does switch to "silly mode" some times, but the rest of it is so good that I can live with that. The art is awesome, the story is intriguing, the music is nice and the story actually moves forward in each episode. No wonder many people have rated it one of the best animé of all time.

By the way, by the time I started watching the series, the episodes being shown were from the last one-third of the series so I didn't quite follow some of the things. Fortunately, Animax started showing the whole series from the beginning on weekends in a "catch-up marathon", with eight episodes shown back-to-back on every day of the weekend. In the evening on weekends they also show five episodes back-to-back to allow you to catch-up with the regular episodes that were shown during the week. It is a bit exhausting and my wife and sister think that I have gone crazy.

I am really looking forward to watching the concluding episodes that will be shown during this week and the next. I am also looking forward to watching the movie.

"The Vietnam of Computer Science"

Via reddit.com, "The Vietnam of Computer Science":

"Although it may seem trite to say it, Object/Relational Mapping is the Vietnam of Computer Science. It represents a quagmire which starts well, gets more complicated as time passes, and before long entraps its users in a commitment that has no clear demarcation point, no clear win conditions, and no clear exit strategy."

A nice albeit verbose article on why using Object/Relational Mapping to store objects in relational database systems sounds like a good idea at first but then becomes a quagmire once you start trying to resolve more and more of the inherent differences between the two approaches.

Terminal Sickness

I have a simple requirement: I want my programme to be able to spawn another programme on the same machine and talk to it using the simplest possible means of communication, that is, via the spawned programme's standard input and output streams.

The driving programme is written in C and the spawned programme could have been written in any programming language (hence the need for using as simple a form of communication as possible). The messages exchanged between the programmes are terminated by newline characters.

This should have been a relatively simple task with code somewhat like the following (error-handling has been omitted for clarity):

  /* File descriptors for pipes connecting driver and inferior
     processes. */
  int drv2inf[2], inf2drv[2];
  
  /* Create communication pipes. */
  pipe (drv2inf); pipe (inf2drv);

  if (fork () == 0) {
    /* In child process - close "other" ends of pipes first. */
    close (drv2inf[1]); close (inf2drv[0]);

    /* Redirect stdin and stdout. */
    close (0); dup (drv2inf[0]); close (drv2inf[0]);
    close (1); dup (inf2drv[1]); close (inf2drv[1]);

    /* Spawn inferior process - should never return. */
    char *args[] = { prog, NULL};
    execv (prog, args);
  } else {
    /* In parent process - close "other" ends of pipes first. */
    close (drv2inf[0]); close (inf2drv[1]);
  }

However, running this with a test programme (written in C) revealed a problem: messages sent by the spawned programme were not reaching the driving programme!

The reason is that stdout is normally "line-buffered" - i.e. output is buffered till either the buffer becomes full or till a newline character is encountered. When stdout is not connected to a terminal however (for example, when output is redirected to a file), it becomes "block-buffered" - i.e. output is buffered till the buffer becomes full. Of course, you can force the output buffer to be flushed out using fflush() at any time. This behaviour of the C runtime is a reasonable tradeoff that seeks to optimise throughput and response under different conditions. In my case the C runtime determined that stdout was not connected to a terminal and therefore should be block-buffered. The messages sent by the spawned process were therefore still sitting in its output buffer while the driving process waited to hear from it.

My knee-jerk reaction was to insert a call to setvbuf() with a mode of _IOLBF just before the call to execv() in order to force a line-buffered mode for the spawned process. Of course, this does not work for the simple reason that the C runtime is re-initialised after the call to execv().

A possible solution is to mandate that the spawned programme force a line-buffered mode for stdout using something like setvbuf(). Another solution is to mandate that the spawned programme always use the equivalent of fflush() to flush its output buffers after every message. However, these just work around the problem rather than solving it. I also do not want to place unnecessary restrictions on spawned programmes.

So it seems the only solution left is to use a pseudo terminal to fool the spawned programme's runtime into thinking that it is attached to a terminal. A glance through the sample code given in my copy of Stevens's "Advanced Programming in the UNIX Environment" reveals that some ugly code is needed to make it work properly. It also makes my programme even less portable than it currently is. I am therefore a bit loath to take this approach.

Does anyone know of a better solution to this problem?

Update (2006-09-16): Thanks to all who responded. Using a pseudo terminal solved my problem. The forkpty() function from libutil provided by the GNU C Library (thank you Scott) conveniently wraps everything I need into a single function. The only problem is that it also redirects stderr to the newly-created pseudo terminal and this robs the spawned programme of a simple method of debugging. To work around this issue, I had to save the stderr stream using a dup() before calling forkpty() and then restore it using a dup2() in the child process.

One of the problems with using a pseudo terminal that initially stumped me was the fact that the spawned programme seemed to send the driver programme all the messages it was sent by the latter in addition to sending messages of its own. It took me a while to realise that this was because of terminal echo. Switching terminal echo off resolved this problem.

Update (2007-10-18): Here is the relevant portion of the programme that finally worked for me:

#include <stdio.h>
#include <stdlib.h>

#include <errno.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <termios.h>
#include <pty.h>

/* Spawns a process with redirected standard input and output
   streams. ARGV is the set of arguments for the process,
   terminated by a NULL element. The first element of ARGV
   should be the command to invoke the process.
   Returns a file descriptor that can be used to communicate
   with the process. */
int
spawn (char *argv[]) {
  int ret_fd = -1;

  /* Find out if the intended programme really exists and
     is accessible. */
  struct stat stat_buf;
  if (stat (argv[0], &stat_buf) != 0) {
    perror ("ERROR accessing programme");
    return -1;
  }

  /* Save the standard error stream. */
  int saved_stderr = dup (STDERR_FILENO);
  if (saved_stderr < 0) {
    perror ("ERROR saving old STDERR");
    return -1;
  }

  /* Create a pseudo terminal and fork a process attached
     to it. */
  pid_t pid = forkpty (&ret_fd, NULL, NULL, NULL);
  if (pid == 0) {
    /* Inside the child process. */

    /* Ensure that terminal echo is switched off so that we
       do not get back from the spawned process the same
       messages that we have sent it. */
    struct termios orig_termios;
    if (tcgetattr (STDIN_FILENO, &orig_termios) < 0) {
      perror ("ERROR getting current terminal's attributes");
      return -1;
    }

    orig_termios.c_lflag &= ~(ECHO | ECHOE | ECHOK | ECHONL);
    orig_termios.c_oflag &= ~(ONLCR);

    if (tcsetattr (STDIN_FILENO, TCSANOW, &orig_termios) < 0) {
      perror ("ERROR setting current terminal's attributes");
      return -1;
    }


    /* Restore stderr. */
    if (dup2 (saved_stderr, STDERR_FILENO) < 0) {
      perror ("ERROR restoring STDERR");
      return -1;
    }

    /* Now spawn the intended programme. */
    if (execv (argv[0], argv)) {
      /* execv() should not return. */
      perror ("ERROR spawning programme");
      return -1;
    }
  } else if (pid < 0) {
    perror ("ERROR spawning programme");
    return -1;
  } else {
    close (saved_stderr);
  }

  return ret_fd;
}

Crikey

Germaine Greer in The Guardian on Steve Irwin:

"The only creatures he couldn't dominate were parrots. A parrot once did its best to rip his nose off his face. Parrots are a lot smarter than crocodiles."

[...]

"What Irwin never seemed to understand was that animals need space. The one lesson any conservationist must labour to drive home is that habitat loss is the principal cause of species loss. There was no habitat, no matter how fragile or finely balanced, that Irwin hesitated to barge into, trumpeting his wonder and amazement to the skies. There was not an animal he was not prepared to manhandle. Every creature he brandished at the camera was in distress."

This was the seemingly sole voice of reason among the glowing obituaries all over the place hailing the "Crocodile Hunter" as a hero and a conservationist of wild life.

Exercise

I'm not a fitness freak but I do believe in the old adage that a healthy body houses a healthy mind. Consequently, I had decided early on in my life to try to remain as fit as is reasonably possible. Unfortunately for me, I have not consistently implemented this resolution over the years with the natural result that I had become lethargic, easily tired and had gained unseemly tyres of fat on my person. I have been trying to rectify matters over the last few months and it seems to be paying off, slowly but surely.

Back in college there was a time when I used to jog in the mornings, swim in the afternoons and play football in the evenings, though I took on the latter two activities more for fun than for improving fitness as such. After leaving college and taking up a job, I tried to jog regularly in the mornings but gave up after a couple of months or so. Without jogging partners from my college days like Pranjal and Subra to goad me, it required too much will power and discipline to refuse the warm embrace of sleep and brave the cold morning air every day. As a wit once remarked, the toughest distance you have to cover while jogging is the stretch between your bed and the floor. To keep myself from putting on excess weight, I tried to regulate my diet a bit. However, that can only help so much when your entire day is spent sitting on a chair at your workplace and your entire night is spent either sitting on a sofa or lying on a bed. Before I realised it, ten years had passed and I had become an embarrassingly unfit image of my former self, advancement of age notwithstanding.

So I have been forcing myself over the last few months to go to bed relatively early (10 PM) and get up and go for a jog, or even a brisk walk, early in the morning. It was difficult at first and I was very irregular but it has now become easier - I wake up by 6 AM without the need for an alarm and am able to convince myself to get out of bed.

I prefer running through the streets of the city in a single long loop and getting a varied view rather than doing monotonous laps in a park or a stadium or staying at one place on a treadmill. Unfortunately for me, it turns out that there are an alarming number of vehicles on the streets even at 6 AM in the morning and spewing noxious fumes and that there are a large number of stray dogs which sometimes bark at you, sometimes run after you and sometimes leave their poop behind for you to watch out. The footpaths are not continuous or even and the roads have oddly parked vehicles or idiots driving the wrong way. The parks nearby are a bit too crowded for me to have any hope for a decent pace of jogging. The playgrounds in the neighbourhood are either too muddy or filled with children, not to mention stray dogs.

I had therefore switched over rather reluctantly to running on a treadmill. Fortunately for me, I live in an apartment complex that has a fairly decent gymnasium. I found out that running on a treadmill is not as bad as I had feared and is in fact much better in several ways. For one, the surface is not as hard as that of a road or a footpath so it feels much better to run on. More importantly, it allows me to properly warm up, maintain a steady jogging speed for a while and then properly cool down. I can easily control the effort expended by varying the speed, the slope and the duration. I can vary the programme to accommodate any constraints of time I might have. The other equipments available in the gymnasium also allow me to exercise other parts of my body. There are also some other benefits of working out in a gymnasium that cannot be described publicly without putting one's marital life into jeopardy. ;-)

One of the pleasantly surprising facts of working out is that it actually leaves me energetic and enthusiastic, rather than tired and achy, for the rest of the day. I feel much better than before and I hope I am able to maintain this regimen.

Good Bye Advogato!

Advogato is going offline.

I feel a bit sad about it even though I had stopped updating my Advogato diary and have been using Blogger for blogging for the last three months. After all, Advogato is where I started blogging regularly.

mibus provides a nice tip: You can access all your Advogato diary entries in a convenient XML format by appending "diary.xml" to your normal diary URL. For example:

http://www.advogato.org/person/rmathew/diary.xml

There is a "Planet (Former) Advogato" for aggregating the blogs of all those who used to blog on Advogato but have moved elsewhere for one reason or the other.

Expensive Conferences

I like to pretend that I am interested in compiler construction techniques. I was therefore quite interested in attending the New Horizons in Compilers (mirror) workshop that will be held as a part of HiPC 2006 right here in IISc Bangalore. Unfortunately, it turns out that you have to register for the entire conference to be able to attend this workshop. The really awful part is that I would have to part with 22,500 rupees ($500) to be able to do that. There is no way that I am ever going to shell out that kind of money for something like this.

Apparently this is supposed to be the "reduced rate" for Indian participants who are not from academia, government organisations or three-four letter organisations. Even for ACM/IEEE/IFIP members, it is still 16,900 rupees ($375) and that is still a lot of money in this part of the world for this kind of an event. It is as if they are making an active attempt to keep everyone else out. I did ask the "registration chair" and the workshop organisers for a better option but apparently there is none.

What a shame!

Where is The Purple Dragon Book?

The "second" edition of the Dragon Book (a.k.a. "Compilers: Principles, Techniques and Tools" by Alfred Aho and others) has already been delayed a lot, considering that the previous edition was published twenty years ago in 1986 and the new edition was supposed to be published "soon" years ago. The final publishing date was supposed to be 31^st August 2006 and the corresponding Amazon.com page and the Addison-Wesley page continue to stick to the same date as of this writing and yet proclaim the title to be unavailable. Jeffrey Ullman says that the book is finally done and that they handed it over to the publisher at the end of June 2006, so I wonder what is causing all these delays and whether the wait would be worth it. Note that an online preview of some of the revised as well as newly-added chapters is still available, though the site uses an awful amount of Flash, JavaScript and pop-ups for some weird reason.

I put "second" in quotes since the publisher says that this is the second edition, though coming after the Green Dragon Book and the Red Dragon Book, I think this should be called the third edition of the book. However, I do realise that there was a change in the title of the book and it was thoroughly revised when it was published as the Red Dragon Book, so this is just nitpicking on my part. It has already been nicknamed the Purple Dragon Book based on its cover, continuing the convention for giving nicknames to its predecessors.

I read parts of the Red Dragon Book when I took the Compilers course in my college about twelve years ago. It was a bit boring (as are almost all textbooks I have ever read), but it was the only book I could lay my hands on that covered bits of everything about compiler construction. Even to this day, 20 years after it was published, it still seems to be a recommended book if you want to know about the basics of compiler construction. However, it is acknowledged to be terribly out-of-date with the current techniques, so a major revision was long overdue.

I have been meaning to brush up on the fundamentals of compiler construction techniques for several years now, especially since the time I was introduced to the development of GCC, but my excuse was that I wanted to postpone it till the time the new edition of the Dragon Book becomes available (which was always marked to be released "any time now"). Now that the Purple Dragon Book would become available "soon", my excuse is that I would at least wait for the second printing so that all the readily-apparent errors are corrected and I don't have to read the book with a thick errata in hand. I would also wait for the low-priced Indian edition to become available since the international editions are atrociously priced in my opinion.

Yes, I do make up really silly excuses for what is ultimately procrastination driven by plain old sloth.

Update (2006-06-07): As luck would have it, just a day after I write about the unavailability of this book, both Amazon.com and Addison-Wesley now show it as in-stock and ready for shipping.

"If You Come Today"

"If you come today, it's too early. If you come tomorrow, it's too late. You pick the time."

Sriram pointed out a video of the (English) song "If You Come Today" sung by and featuring Rajkumar. The lyrics of the song are rather confounding, but my favourite parts are the "Tick, Tick, Tick, Tick..." and the "DOHLING!".