Monomorphic

Different technologies have different kinds of aesthetics, and they affect us in various ways, whether we are particularly fascinated with technology or not.

The easiest technologies to understand on an intuitive-emotional basis seem to be those that involve physical processes. Objects rotating, moving, being lifted and displaced, compressed, crushed. Gases and liquids being sent around in conduits, mediating force and energy. In short, the technology that has its foundation in classical mechanics.

If these are easy to get a feel for, it would probably be in part because an understanding of mechanical processes has been of use to us throughout history, and also before the advent of civilisation. An intuitive understanding of things such as momentum, acceleration, gravity has no doubt benefited mankind and its ancestors for a very long time.

It gets trickier when we get to the more recent technologies. Take electricity to be an arbitrary watershed. We have no intuitive idea of what electricity is, apart from the fact we might be afraid of thunder. Electricity has to be taught through the abstract idea of electrons flowing in conduits, a bit like water in pipes (to name one of many images being used).

And then there’s analog and digital electronics, integrated circuits, semiconductors and so on, where intuition has long ago been left behind. We are forced to approach these things in a purely abstract domain.

Yet, when our Mp3 players, game consoles, mobile phones and computers do things for us, we are left with a sense of wonder. Our minds, always looking for stories and explanations, want to associate the impressive effects produced by these devices with some stimuli. With a steam engine, it’s easy to associate the energy with pressure, heat and motion, all of which are well understood on a low level. With a mobile phone, not so much. A lot of very abstract stories have to be used in order to reach anything that resembles an explanation, and still it doesn’t reach the essence of the device, which might be in its interplay between radio transceivers, sound codec chips, a display with a user interface and software to drive it, a central CPU, and so on, together with, of course, the network of physical antennas and their connectivity with other such networks. Is it too much to suppose that the human mind often stops short of the true explanation here? That we associate the effects produced by the device with what we can touch, smell, see and hear?

This is of course the point where many computer geeks worldwide start to feel a certain affection for the materials that make up the machines. Suppose that we are in the 1980′s. Green text on a black terminal background. A particular kind of fixed width font. The clicking of the keyboard. The dull grey plastic used to make the case. All of these things can acquire a lot of meaning that they don’t really have, because the users lack a window (physical and emotional) into the essence of the machine. The ultimate “disconnected machine”, to relate to my field, is software.

This brings up questions such as: how far can we as a species proceed with technology that we cannot understand instinctively, how can we teach such technology meaningfully and include it in democratic debate, and how can we use people’s tendencies to associate sensory stimuli with meaning and effects in a more meaningful way? – for instance, when we design hardware and software interfaces.

I thought I’d write a more personal note for a change.

It’s been just over a year since I started studying for my Ph.D. — formally, I entered the program in April 2009. With at least two years to go, how do things look with some hindsight? What do I think it means to obtain the Ph.D. degree, or, more specifically and usefully, to be a researcher in computer science?

Much of what I’m noticing are things that sound obvious and natural, like everyday truisms, when expressed with words, but the idea I have of it goes a little bit deeper than that. For instance, we all get told over and over throughout our lives, starting in high school, that we have to become good communicators. So it’s not going to be a surprise to anyone when I say that I think the process entails becoming a much better communicator than I’ve ever been before. Maybe what’s different is that I am trying to communicate things that haven’t been communicated before, things that I invented — or things that have hitherto been communicated only by a very small number of people. (Most of the communication I did prior to becoming a Ph.D. student may not have been terribly original.) Basically, reading and understanding a large amount of scientific papers, and understanding them with a particular use in mind, either having or getting a sense of how they fit into your own work. Then, writing your own papers, and communicating, somehow, what you thought, and what you were the first person to think, so that somebody else might read it like you read the works of others, and use it similarly. Then, presenting research, discussing it, and understanding what is being presented and discussed by others — similar challenges in speech instead of in writing.

I can’t speak for other fields, but in computer science ( I work with programming languages and software engineering), I find that a lot of this, for me, has been about building up a certain mental dexterity with formalisms. Understanding the implications of formalisms as you read about them and seek to apply them. Communicating formalisms to others. Some of this is still difficult, in particular the “communicating to others” part, but I think I am achieving things in this regard.

Communication, then, where does it take us? One of my mental images of academic knowledge is a big directed acyclic graph (a tree) where papers reference other papers. A surprisingly big part of writing a paper is ensuring that your work can get assimilated into this graph easily — placing it well, referencing the right things, making sure that you can be referenced easily. Also: defining the boundaries of your work extremely well — here’s where it begins, here’s where it ends. We assume precisely this and arrive at precisely that. It really seems that these things can never be made clear enough.

Which leads to another mental image of research: the paper/unit of work as a building block. The more solid it is, and the harder and sharper its surfaces and edges are, the better structures can be built from it (though I think there are other kinds of valuable works too). That’s one direction I think I need to be aiming for as an aspiring researcher.

Many software developers, while making a tool to solve a specific problem, heed the siren call of generality. By making a few specific changes, they can turn the tool into a general framework for solving a larger class of problems. And then, with a few more changes, an even larger class of problems, and so on. This often turns into a trap, and there is a risk that the end of the line is an over-generalised tool that isn’t very good at solving any problem, because the specificity that was present in the first place was part of why it was powerful. In this way, constraints can equal freedom.

Sometimes, though, the generalizers get it right. These are often moments of exceptional and lasting innovation. One example of such a system is the fabulously influential (but today, not that widely used) programming language Smalltalk. Invented by the former jazz guitarist and subsequent Turing award winner Alan Kay, Smalltalk was released as one of the first true object-oriented programming languages in 1980. It is probably still ahead of its time. It runs on a virtual machine, it has reflection, everything is an object, and the separation between applications is blurred in favour of a big object box. On running Squeak, a popular Smalltalk implementation, with its default system image today, users discover that all the objects on the screen, including the IDE to develop and debug objects, appear to follow the same rules. No objects seem to have special privileges.

Another such system is an application that used to be shipped on Mac computers in the distant past, Hypercard. Hypercard enabled ordinary users to create highly customized software using the idea of filing cards in a drawer as the underlying model, blurring the line between end users and developers through its accessibility. I haven’t had the privilege to use it myself, but it seems like this was as powerful as it was because it served up a homogenous and familiar model, where everything was a card, and yet the cards had considerable scope for modification and special features. Even though, in some ways, this system appears to be a database, the cards didn’t need to have the same format, for instance. (Are we seeing this particular idea being recycled in a more enterprisey form in CouchDB?)

There are more examples of successful highly general design: the Unix file system, TCP/IP sockets and so on. They all have in common that they are easy to think about as a mental model, since a universal set of rules apply to all objects, they scale well in different directions when used for different purposes, and they give the user a satisfying sense of empowerment, blurring the line between work and play to draw on the user’s natural creativity. Successful general systems are the ones that can be easily applied in quite varied situations without tearing in the seams.

While not widely used by industrial programmers today, Smalltalk was incredibly influential. In 1981 Objective-C was created by Brad Cox and Tom Love, directly inspired by what the Smalltalk designers had done. Objective-C was subsequently used as the language of choice for NeXTStep, and later for Apple’s MacOS X when Apple bought NeXT. Today it’s seeing a big surge in popularity thanks to devices like the iPhone, on which it is also used. In 1995 Java was introduced, owing a great deal of its design to Objective-C, but also introducing features such as a universal virtual machine and garbage collection, which Objective-C didn’t have at the time. In some sense, both Objective-C and Java are blends of the C-family languages and Smalltalk. Tongue in cheek, we might say that it seems evolution in industrial programming these days consists of finding blends that contain less of the C model and more of smalltalk or functional programming.

The project I’ve been working on for some time (the last year or so) is starting to acquire a more definite form, and hopefully more information about it will be released in the coming months. Its official name is now Poplar, and the current official overview is available here. Basically it revolves around protocol based component composition for Java.

There is now an opportunity to do a paid internship for 2-6 months at Japan’s National Institute of Informatics in this project. If you are a masters or Ph.D. student who is interested in programming languages and software engineering, and you think the project sounds interesting, please do consider applying. Unfortunately the internship is only open to students of institutions who have signed MOU agreements with NII. The list of such universities, which includes many institutions from around the world, as well as more formal information, is available here. If you know or want to learn Scala, all the better!

In research and academia, one of the fundamental activities is the invention and subsequent examination of new concepts. For concepts, we need names.

One way of making a name is stringing words together until the meaning is sufficiently specific. E.g. “morphism averse co-dependent functor substitutions in virtual machine transmigration systems”. Thus the abstruse academic research paper title is born.

Sciences sometimes give new meanings to existing words. This could be called overloading, following the example of object-oriented programming. E.g. a “group” in mathematics is something different from the everyday use of the term. A “buffer” in chemistry is something different from a software or hardware buffer, even though a fragment of similarity is there. And so on. This overloading of words gives newcomers to the field a handle on what is meant, but full understanding is still impossible without understanding the actual definitions being employed.

Sometimes new terms can be created using inventors’ names and everyday words. E.g. a “Lie group” or the “Maxwell equations”, or “Curry-Howard correspondence”. This is potentially useful, but perhaps not something you can do freely with your own research without seeming like you’re trying to inflate your ego excessively. (Even though researchers love inflating their egos, nobody wants to admit it.)

There’s a similar problem in software development. When we invent names of functions, classes and variables, the lack of words becomes very clear. Intuitively, what is an “adapter registry”? An “observer list”? Or an “observer list mediation adapter?” My feeling is that we often end up compounding abstract words because we have no better choice. And here lies a clue to some of the apparent impermeability of difficult source code. We need better ways of making names. We’re inventing ideas faster than our language can stretch.

The Gregorian calendar has been in use since 1582. Among its features is a moderately complicated rule for leap years: if n mod 4 is 0, then n is a leap year. However, if n mod 100 is 0, then n is not a leap year, unless n is a multiple of 400.

In addition, we live in a world with timezones and regional differences in when countries go on and off daylight savings time, if they have such a system. As yet another example of Japanese rationality, Japan does not have a DST system.

Implementing date and time computations correctly can be very hard for computer programmers and is invariably a source of many hidden bugs that may take a long time to discover. Yesterday, a large amount of Sony’s Playstation 3 game consoles stopped working normally.  This was later fixed. There was speculation the error was due to incorrect leap year handling. It wouldn’t be the first time this occurred if this was indeed the reason.

In a software company where I used to work, there would usually be massive troubles every time some country went on or off daylight savings time, or any other time calculation hit a sensitive spot. I’m fairly sure that the world’s software systems, including government, finance, insurance, health care, suffer untold billions of damage every year due to the complexity of the system. Maybe we should simplify it.

I suggest having “years” with 365 x 4 + 1 = 1461 days instead of the usual year for starters. This would move the leap year problem ahead until year 2100, when the next special rule comes in. By that time, software engineering technology should have improved enough that this should no longer be an issue, I hope. If not, we can invent another system by then. Let’s also scrap all daylight savings time everywhere. It’s easy to do and the savings would be huge.

Academics and practitioners, having rather different goals in life, tend to approach software development in quite different ways. No doubt there are many things each side of the fence can learn from the other, but I think academics in particular could often benefit quite a lot by adopting some of the practices used in industrial development. And not just computer science academics!

A common misconception is that these techniques only are useful with large projects and large teams. I find, though, that they can help reduce much of the growth pains even in small projects, helping them reach maturity much faster.

Use version control. Classical, but invalid, counter arguments include “it’s a hassle and too much work to set up”, or “there’s only one person working on this project anyway”. Even if it’s only you, you will benefit massively from being able to undo your changes far back in time. It will let you experiment safely. Plus, setup is no longer an issue with free and easy-to-use services like github and bitbucket. My tool of choice is now Mercurial, and I used to use SVN. And there are many other good choices.

Use a debugger. If there is a debugger available for your language, and there most certainly is, then you should use it to find nontrivial errors, rather than extensive printf style testing.

Don’t optimise prematurely, but when you need to, use a profiler. Profilers tell you where a program’s performance bottlenecks are. You can profile things like heap usage (what classes use most space in Java, for instance) and CPU usage (which functions use the most CPU time). For Java, I’ve discovered that the NetBeans IDE has a very good built in profiler. Eclipse also has one, but it didn’t work on Mac last time I checked. For C/C++, GProf used to be good and probably still is.

Use unit testing wisely. All of the above apply even to very small projects, but I think some projects are too small to need unit tests, at least initially. You be the judge. I find that unit tests can have a lot of benefit when applied to the fragile, complicated parts of a system, where many different things interlock. If you are ambitious you can also write tests first and code later — test driven development.

Use a good IDE if you can. For a language like Java, where you have to type a lot of code to get something done and spread out your code across lots of files, a good IDE that can generate boilerplate code and navigate quickly can really speed up your work. It’s beneficial for other languages too. But I have no problem with people who use pure vim or emacs, after all these are practically IDEs.

I believe that honing your software development skills as an academic can pay off. Also see: Daniel Lemire on why you should open source your projects. (I will get around to doing this eventually, I promise )

Scala is a little wonderland sprinkled with useful things you can mix and match as you like to improve your coding experience while staying on the Java platform. The Option classes, the structural case matching, the compact declarations, lazy evaluation… the list goes on. But at the heart of it is the decision to mix freely the functional and imperative programming styles.

How does this work in practice?

• Statements can have side effects, like in Java
• The final statement evaluated in a function is its return value by default
• Every statement evaluates to a value, even control flow statements like if… else, unlike in Java

The bottom line is that some problems call for a functional programming style, and others for an imperative one. Scala doesn’t force you into a mold, it just gives you what you need to express what you’d like to express. This can lead to very compact code. Here’s a function that recursively finds all files ending in .java starting in a given directory. The File class here is the standard Java java.io.File!

Remember, the last expression evaluated is the return value.

 def findJavaFiles(dir: File): List[File] = {
    val files = dir.listFiles()
    val javaFiles = files.filter({_.getName.endsWith(".java")})
    val dirs = files.filter({_.isDirectory})
    javaFiles.toList ++ dirs.flatMap{findJavaFiles(_)}
  }

But we can write it even more compactly at the expense of some clarity:

 def findJavaFiles(dir: File) = {
    val files = dir.listFiles()
    files.filter(_.getName.endsWith(".java")).toList ++
 files.filter(_.isDirectory).flatMap{findJavaFiles(_)}
  }

Now write this function in Java and see how many lines you end up with.

I just got a new laptop, courtesy of the lab. Naturally, it’s of the fruity kind. One of the first steps: install essential software.

I thought I’d make a list of software I consider absolutely essential on any new computer, and it became longer than I thought.

General use:

NetNewsWire for news reading

DropBox for file syncing

OmniFocus as a task organizer (the GTD methodology actually works — it has liberated me from reciting a long list of things to do in my head all day long)

CircusPonies Notebook for note taking

iStat Pro for system monitoring

If I want to develop software:

Eclipse

Fink and MacPorts so I can get various unix tools (I can’t settle for one or the other, since some tools are in one of them only, but normally Fink is nicer since the packages are precompiled)

Apple’s developer tools

If I want to read and write papers:

TeXShop

Mendeley Desktop

So these are the “absolute essentials”. Of course web apps like gmail count too, but they require no installation. Anything I’ve missed?

One thing I do not install, but perhaps should, is Apple’s MobileMe. Considering how fruity my environment is, there ought to be some benefit. But between Dropbox, my own DAV server for calendars, and built-in syncing of apps like OmniFocus, I can make things stay in sync anyway, so MobileMe is probably not worth the cost… I think.

Flood-it, a color filling game. This version was made by Lab Pixies for the iPhone, but many others exist.

There’s a veritable torrent of little games constantly being released for the iPhone. One of the more likable ones is Flood-It, which I’ve been playing recently. The premise is extremely simple: you start off with a grid divided into squares of different, randomized colors. You are given a tool that works a bit like the bucket fill in a picture editor. At each turn, the player chooses a color to fill the grid with, starting from the upper left corner. The monochromatic area slowly grows, and the aim is to fill the entire grid with a single color within a limited number of turns.

A recent analysis showed that finding an optimal solution to games like Flood-It is a NP-hard problem. In addition, deciding whether the game can be solved in n steps for some n is NP-complete. The analysis relies on a reduction of Flood-It to an instance of the SCS problem (shortest common superstring). (It’s important to note that what is NP-complete is deciding whether a particular board can be solved in a certain number of steps, not solving the game with a bounded number of steps. This can be done in polynomial time.) For those who need a summary, ACM Communications had an excellent review of the state of the P/NP problem in September last year.

For a NP-hard problem H, there exists a polynomial time reduction of any problem in NP to H, meaning that if we can solve H in P-time, we can solve any problem in NP in P-time. Many optimization problems in society rely on approximate solutions to difficult problems: routing traffic, assembling DNA sequences from partial subsequences, mathematical theorem proving… On the hypothesis that evolution has turned people into efficient solvers of hard problems (i.e. we have good heuristics in our brains from birth and from experience), we ought to pay people to play these games on their phones, but map real problems into game instances, so that people effectively work while they’re playing. We ought to design games that act as front-ends for real combinatorial problems.

A computer game, as we understand it, can be defined as a very smooth learning curve, and if we only “play” very tricky instances of combinatorial problems, the game would probably present too much of a barrier to new players. So maybe the best way of executing this kind of scheme would be that a majority of all game instances do not represent real problems, but mere training or verification of already solved problems — but every once in a while, a real problem pops up. The player should still get paid though.

A double benefit would be blurring the line between work time and  play time, what is useful and what is useless — I think this line is often artificially constructed. Has technology ever before given us the possibility to literally turn work into play?

Acknowledgements. I am indebted to Christian Sommer for showing me the complexity analysis of Flood-it.

The Flood-It game, easy difficulty setting, with the player having made some progress.