Monomorphic

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.

Nomura's Jellyfish. Picture by Kenpei at the Osaka aquarium. GFDL license.

Nomura’s jellyfish, a species frequently encountered in Japan and China, is one of the largest in the world. The body can reach a diameter of 2 m. Since they create big problems for the fishing industry, Japan has now sought China’s help on the issue. It is thought that a recent proliferation of the species, huge swarms appearing every year since 2000, originates at the mouth of the Yangtze river.

Evolution can do fascinating things sometimes. Upon reading about this, a doubtlessly romantic and delusional notion entered my mind. What if the sea ecosystem, or a subset of it, say 10-100 species, perceive the human fishing industry as a threat that needs to be defended against, and in response create an evolutionary niche where a new kind of species can thrive, a species whose only purpose is to obstruct fishing? A romantic notion since it plays off the mythical idea that human beings are at war with nature, or that nature is good and man is evil, something I don’t really believe in. But an interesting one nonetheless. Is such a development possible?

A cold, bright morning in Tokyo’s somewhat fashionable Azabu-Juuban district. I’m looking for a clinic, but I can’t find it. I’ve only visited it once before, more than a year earlier. I look for landmarks that I might remember, bring out the map on my phone, pay attention to every detail in the hope that I will recognize something.

The morning has turned into a game. It’s me against the city layout, me against my memory, me against entropy and the temporal degradation of my cognitive faculties. The ludic dimension has entered my life again. And soon enough, I find the place I was looking for.

When we have a sense of competition, that a victory against something or someone is possible, our awareness of life is heightened in every way. We pay more attention, we notice more, we become more here and now. The endless simmering chatter in our heads, nearly meaningless thoughts that usually refuse to yield anything meaningful, gives way to absolute focus.

It occurs to me that a society where everyday tasks can be carried out like they are games, victories to be won, might be a more moral society, with greater happiness and life awareness for everyone. In such a society, even if you lose a particular game, you win something else.

In his first amendment to Human, All Too Human (1886), entitled Miscellaneous Maxims and Opinions, Friedrich Nietzsche states that

300. HOW FAR EVEN IN THE GOOD THE HALF MAY BE MORE THAN THE WHOLE. — In all things that are constructed to last and demand the service of many hands, much that is less good must be made the rule, although the organiser knows what is better and harder very well.He will calculate that there will never be a lack of persons  who can correspond to the rule, and he knows that the middling good is the rule. — The youth seldom sees this point, and as an innovator thinks how marvelously he is in the right and how strange is the blindness of others. (Helen Zimmern transl.)

Friedrich Nietzsche did not describe software making – I can only assume that he was describing authors and ideologists – but this seems to capture the difficulties of software development only too well. And it seems to give a recipe for how to overcome the communication difficulties (abandon exotic, over-refined solutions and focus on an easily understood middle ground, so that everybody can get together and comprehend the architecture). This was originally published in 1886.

With that, merry christmas!

In the chilly yet sunny winter afternoon, I took a walk past the imperial palace in the centre of Tokyo. I find sunny winter days refreshing.

The palace is interesting to behold. It is fronted by lots of that most precious of Tokyo commodities, open space. Supposedly, during the height of the land bubble, the land on which the palace is built was worth more than the state of California. This is in turn surrounded by some of Tokyo’s most prestigious office buildings in the Marunouchi and Hibiya districts. Tokyo station is just a few minutes away on foot.

The scene is one of juxtapositions. Open space meets tightly packed high rise buildings. Traditional Japanese architecture counters sleek office buildings. Yet this  never feels contradictory, because there is an underlying theme of restraint and control.

As you might expect from a royal residence, the public courtyard is immaculate. The grass is so well cut and even as to resemble a golf course. The trees on the lawn are of uniform height, lushness and distance from each other. The gravel is supremely even.

The office buildings are similarly controlled: shades of grey and brown, a certain minimalism and homogeneity in design that is easier found here than in Europe, the sense that unnecessary detail has been removed.

There is a sense of power in all this; a will and a shared set of ideas that have been realized to a high degree. The homogenous, flat skyscraper with a grid of windows is the triumph of human, platonic ideas over the organic and the irregular. The palace garden is man’s will taming the uncontrolled vegetation we find in nature. Yet such control is always a question of scale. We can cut and prune the trees, but we cannot control the color of their leaves or the exact angle of every branch. And we can cut and prune the buildings, but generally, we cannot control the shape of the overall skyline in detail. Something organic manifests itself in the multitude, even as some parts are controlled.

Power and rebellion, in constant struggle and symbiosis.

The Scala collections library (in version 2.7.7) has a MultiMap trait for mutable collections, but none for immutable ones. I hacked something up to use while waiting for an official version. I’m finding this to work well, but I don’t have much experience with collections design, so it’s likely to have some flaws. Also, this is a class and not a trait, so you can’t use it with any map you like. And from a concurrency perspective, maybe it’s sometimes better to use backing collections other than the HashSet and the HashMap.

 
import scala.collection.immutable._
 
/**
A multimap for immutable member sets (the Scala libraries 
only have one for mutable sets). 
*/
class MultiMap[A, B](val myMap: Map[A, Set[B]]) {
 
	def this() = this(new HashMap[A, Set[B]])
 
	def +(kv: Tuple2[A, B]): MultiMap[A, B] = {
	  val set = if (myMap.contains(kv._1)) {
		  myMap(kv._1) + kv._2
	  } else {
		  new HashSet() + kv._2	     	   
	  }
 
	  new MultiMap[A, B](myMap + ((kv._1, set)))
	}
 
	def -(kv: Tuple2[A, B]): MultiMap[A, B] = {
	  if (!myMap.contains(kv._1)) {
	    throw new Exception("No such key")
	  }
	  val set = myMap(kv._1) - kv._2
	  if (set.isEmpty) {
	    new MultiMap[A, B](myMap - kv._1)
	  } else {
		  new MultiMap[A, B](myMap + ((kv._1, set)))
	  }
	}
 
	def entryExists(kv: Tuple2[A, B]): Boolean = {
	  if (!myMap.contains(kv._1)) {
	    false
	  } else {
	    myMap(kv._1).contains(kv._2)
	  }
	}
 
    def keys = myMap.keys
 
     def values: Iterator[Set[B]] = myMap.values
 
    def getOrElse(key: A, elval: Collection[B]): Collection[B] = {      
      myMap.getOrElse(key, elval)
    }
 
    def apply(key: A) = myMap(key)
 
 
 
}

Usage:

 
   var theMultiMap = new MultiMap[String, Int]()
 
   theMultiMap += (("george", 1))
   theMultiMap += (("george", 3))
   theMultiMap += (("bob", 2))
   theMultiMap -= (("george", 1))

Here’s something I’ve wanted to see for some time, but probably don’t have time to work on myself.

It would be nice if there was a wikipedia-like web site for code and algorithms. Just the common ones to start with, but perhaps more specialised ones over time. Of course the algorithms should be available in lots of different languages. This would in fact be one of the main points, so that people could compare good style and see how things should be done for different languages. In addition, there should be an in-browser editor, just like on Wikipedia (but perhaps with syntax highlighting) so people can make changes easily.

Furthermore, there should be unit tests for every algorithm, and these should be user-editable in the same way as the main code. In an ideal world, the web site would automatically run the unit tests every time there’s a change to some algorithm and check in a new version of the code to a versioned repository. People could then trust with reasonable confidence that the code is valid and safe. However, if the system were to be as open as Wikipedia is, such a system wouldn’t work, since users could write unit tests with malicious code. So I suspect volunteers would have to download, inspect, and run the unit tests regularly, and perhaps there would be a meta-moderation system of some kind, allowing senior members to promote changes to the official repository. In the meantime, everybody should be allowed to see and edit changes on the wiki immediately, but they would be marked as “untested” or “unsafe”.

User interface would be very important since this kind of site needs to be fun and easy to use regularly.

Has this kind of project already been carried out by someone? I can find some things by googling. The Code Wiki appears to once have been a wikipedia of code, but it seems defunct, C# only, and now they’re selling a book with the contents of the site! Algorithm Wiki has many algorithms in different languages, but the user interface is awkward and littered with obstructive advertising, the code is hard to browse, and it doesn’t make for a usable quick reference. They seem to have gotten off to a good start though. Any others?

Edit: Rosetta Code seems to be the most mature and useful such site out there today.

Today, Java is one of the most popular programming languages. Introduced in 1995, it rests on a tripod of the language itself, its libraries, and the JVM. In the TIOBE programming language league charts, it has been at the top for as long as the measurements have been made (since 2002), overtaken by C only for a brief period due to measurement irregularities.

Yet not all is Sun-shine in Java world. Sun Microsystems is about to be taken over by Oracle, pending EU approval. (EU is really dragging its feet in this matter but it seems unlikely they would really reject the merger). Larry Ellison has voiced strong support for Java and for Sun’s way of developing software, so maybe this is really not a threat by itself. But how far can the language itself go?

The Java language was carefully designed to be relatively easy to understand and work with. James Gosling, its creator, has called it a blue collar language, meaning it was designed for industrial, real world use. In a world where C++ was the de facto standard for OO programming, Java was a big step forward in terms of ease of development, with its lack of pointers and strong type system – to say nothing of its garbage collection. Many classes of common programming errors were removed altogether. However, in the interests of simplicity and clarity, some tradeoffs were made. The language’s detractors today point to problems such as excessive verbosity, the lack of closures, the limited generics, and the checked exceptions.

For some time there has been a lot of exciting alternative languages available on the JVM. Clojure is a Lisp dialect. Scala, the only non-Java JVM language I have used extensively, mixes the functional and object oriented paradigms. Languages like JPython and JRuby basically exist to allow scripting and interoperability with popular scripting languages on the JVM.

Today it seems as if the JVM and the standardized libraries will be Java’s most prominent legacy. The language itself will not go away for a long time either – considering that many companies still maintain or develop in languages like Cobol and Fortran, we will probably be maintaining Java code 30 years from now (what a sad thought!), but newer and more modern JVM languages will probably take turns being number one. The JVM and the libraries guarantee that we will be able to mix them relatively easily anyway, unless they stray too far from the standard with their custom features.

So in hindsight, developing this intermediate layer, this virtual machine – and disseminating it so widely –  was a stroke of genius. Will it be that in future programming models we have even more standardized middle layers, and not just one?

Meanwhile, there’s a lot of debate about the process being used to shape and define Java. For a long time, Sun employed something called the Java Community Process, JCP, which was supposed to ensure openness. Some people proclaim that the openness has ended. To take one example, very recently, Sun announced that there will be support for closures in Java 7, after first announcing that there would be no support for closures in Java 7. The process by which this decision has been managed has been described as not being a community effort. Some aspects of Java are definitely up in the air these days.

For a long time, the level of comfort allowed us by technology has risen persistently. This trend shows no signs of slowing down. One of two things would have to happen: either we reach some point where a fundamental barrier prevents us from extracting or converting certain natural resources beyond a certain rate, and this becomes a hard constraint on humanity for all time, or physical matter ends up being under our complete control. In this latter scenario, which I don’t view as unlikely, we’d be able to convert trash into useful things at our whim, for instance.

This scenario is sometimes referred to as an age of abundance. It may have a large intersection with the singularity, an idea first championed in 1993 by Vernor Vinge, or it may be a consequence or a necessary prerequisite of it. For now, let us focus on the economic aspect of abundance only.

If these things come to pass, one of the fundamental assumptions of classical economics – scarcity – would be contradicted. I would suggest that we are culturally unprepared for this kind of world.

As countries’ economic productivity increases, we are faced with the choice of whether to work less and enjoy the same standard of living, or work as much and enjoy a higher standard of living. My understanding is that people have always chosen the latter.

In The Protestant Ethic and the Spirit of Capitalism, Max Weber puts forth the view that the development of capitalism in Europe was largely influenced by protestant values, particularly Calvinist ones. Even though many European peoples today consider themselves to be secular, it is clear that a Christian legacy has left a big mark on contemporary European culture. Simply put, many people only feel proud when they work and feel that they serve a useful purpose to their country. This is why they cannot choose to work less.

In an era of abundance, people would not be needed for the carrying out of most tasks. If they insisted on carrying out the tasks anyway, they would have to know that they were being costly and useless, thereby depriving them of enjoyment – unless we deluded them!

I see a few ways out of this situation.

• Craftsmanship is considered a uniquely human and artistic activity, and people who turn to art and crafts can continue to feel that they are important.
• Some work is fundamentally centered on human interaction and human meetings, for instance care, psychotherapy, hairdressing and leadership. These roles are unlikely to grow useless even as technology advances (purely materially).
• Culture would have to change, allowing people to rest and feel valuable even without contributing to their society’s affluence. If this is possible or not is an open question.

I should point out that the contribution-as-pride mindset is a feature not just of European protestant cultures, but also seems to be one of Japan – though for different reasons. And probably one of many other countries as well.

Recently I watched a friend give a presentation on a research topic he’s been working on for years. I found the presentation to be fascinating, and the clearest explanation of his work that I have seen to date. But I felt compelled to criticise him on one point.

In order to lighten up the speech a bit, he had chosen to include characters from a popular science fiction movie on every other slide, using them to explain the results he had attained in theoretical computer science. The link between the characters and the results was nearly non-existent; the pictures were clearly only there to lighten the presentation up a bit. I had been irritated by people’s tendency to do these things for some time, so I decided to point it out. One extreme example of this tendency gone too far occurred recently in a presentation about the database CouchDB – readers can Google for the slides to see the full controversy, though they are somewhat NSFW. (I don’t want to make moral judgments in this context, but I think the academic/professional domain can be kept free of these controversies. Save those battles for where they belong!)

So there’s a tendency for people to sugarcoat their presentation topic sometimes. The arguments in favor of doing this are that it can lighten an intrinsically heavy subject a lot, and save people from nearly falling asleep from compounded boredom (such as a conference where 30+ presentations about results in theoretical computer science are given). Essentially it mixes in some sugar with the sour stuff, yielding what might be called a sweet and sour talk. The medicine becomes easier to swallow.

But isn’t there something essentially contradictory about mixing contemporary pop culture so freely with results that, in this case, were about essentially pure mathematical theory? For one thing it takes the essentially perennial and debases it, linking it up with images that are hopelessly stuck in a short timeframe. For another, it can be seen a vote of non-confidence in your own ideas. It can be seen as saying “I know this is boring and useless to you, so please bear with me, and look at these amusing pictures until it’s over.” I’m not a good presenter, but in order to become one, I think I need to have sufficient confidence in my ideas to present them unsweetened unless the circumstances are extreme. I need to make my audience see the value in my ideas. Also, it’s quite different if the sugar coating is of the kind that helps people get into your idea, or if it’s the kind that just distracts (this case).

My view is therefore that one should use one’s lumps of sugar with restraint. Maybe a situation where this is called for is when the audience necessarily contains some people who are on the level that you need to be talking to, and many other people who are not on that level, and cannot possibly be brought up to it. In this situation, the sugar might be used to keep the second group somewhat alive and alert. And this is in fact the kind of situation my friend wrote the presentation for originally. So, no scorn on him, just a word of warning to the general public!