Archive for July, 2009

Complexity metric for identifiers

Friday, July 31st, 2009

As far as I know, every code complexity metric ever divised treats all identifiers equally. After all, they're all just opaque strings to the computer, right?

But complexity metrics are not designed for the benefit of computers - they're designed for people, to try to make the code less complex and easier for people to understand (otherwise we could just measure the length of the generated binary code).

And there is certainly something less complex about a variable called "cost" than a variable called "amountPaidPerItemInDollars" for example - a program using the second should surely be considered more complex than an otherwise identical program using the first, right?

On the other hand, one doesn't necessarily want to count all the letters in an identifier to measure its complexity - that would just lead to very cryptic or meaningless 1 and 2 letter variable names.

I think the answer is to divide identifiers up into words (in case sensitive languages by starting each word with a capital letter, and in non-case-sensitive languages by separating words with underscores). Each word counts for one point and should be a real word in the English language, or defined elsewhere in the program as a sequence of other words (perhaps with a special comment that the compexlity measurer can understand). So, for example, instead of having a lot of variables containing the characters hyperTextMarkupLanguage, one would have a glossary section in one's program saying "html == hyper text markup language" and then treat "html" itself as a word.

Making up terminology is an important part of programming, and one that I think is often overlooked. Giving a decent (appropriate, one word) name to each of the important concepts in your program from the get-go, and giving each of these terms a precise meaning (even if some details of those meanings change as the program evolves) causes one to be able to think about these concepts more clearly. It also leads to easier and more consistent naming of variables and types.

Manifesto for a new demoscene

Thursday, July 30th, 2009

Since computers become powerful to decode compressed audio and video in real-time, and storage capacities and bandwidths have increased to make storage and transmission of such streams practical, the demoscene has become even more niche than it used to be.

Nowadays, most demos are more about art than cutting edge technology. The exceptions tend to be demos that are constrained in one way or another, for example by being written for old hardware, or limited in size.

I'd like to propose a new kind of constrained demo - one that isn't limited to a particular size, but which is completely procedurally generated. Such techniques have always been used in demos (particularly constrained ones) but generally combined with other techniques. It would be interesting to see what is possible in demos that have no data that is temporally or spatially indexed or was generated by transforming temporally or spatially indexed data. That means no waveforms (all sounds must be synthesized), bitmaps, JPEGs, MP3s or video streams. Vector graphics are allowed, but only if they are hand-drawn (so you can't generate a vector image by automatically stenciling a bitmap image of the Mona Lisa, for example). If you want the Mona Lisa in your demo you have to draw the vectors yourself. Bitmap art could be done in the same way - rather than by storing the finished bitmap in the demo binary, one would have to store the sequence of commands the artist used to draw the image in whatever graphics program (which could then be rendered to a bitmap at startup time).

Alien rights

Wednesday, July 29th, 2009

It occurred to me recently that no country on Earth currently has a law against killing any sentient alien life forms that might come to visit us.

Now, call me overcautious but I wouldn't want to visit a place where it would be perfectly legal for anyone to kill me.

Perhaps the reason that we have not been visited by extra-terrestrials is simply that they think Earth would be a dangerous place for them.

Perhaps all we need to do to join the interstellar community is to pass a law affording the same rights that humans have to any aliens that might visit us.

Algorithm for Mandelbrot cardioid

Tuesday, July 28th, 2009

A good way to speed up a Mandelbrot set plotter is to eliminate the main cardioid and the largest circle. It turns out that there are simple equations for these, which can be found if you know that the cardioid consists of all the points which converge to a single point and the largest circle consists of all the points which converge to a cycle of period 2.

First the main cardioid. For each c, we can find the fixed point of iteration z_f such that z_f^2+c = z_f. There are two solutions, \displaystyle \frac{1}{2}(1 \pm \sqrt{1-4c}). Then we can look at what happens when we iterate a nearby point (z_f+d)^2+c = z_f^2+c + 2dz_f. If |2z_f|<1[/latex] then the fixed point is stable. It turns out that this only happens for the [latex]\displaystyle \frac{1}{2}(1 - \sqrt{1-4c})[/latex] solution, so points in the cardioid are [latex]|1 - \sqrt{1-4c}| <= 1[/latex], with equality for the boundary. Having to compute a complex square root is a bit ugly, though - can we do better? It turns out that we can. It's a fiddly calculation but if you multiply out all the square roots and simplify, you can get the formula [latex]|c|^2(8|c|^2-3) <= 3/32 - Re(c)[/latex]. For the period-2 circle, we solve [latex](z_f^2+c)^2+c = z_f[/latex] and eliminate the period-1 solutions to get [latex]\displaystyle \frac{1}{2}(-1 \pm \sqrt{-3-4c})[/latex]. In this case, both solutions are equally valid, since the cycle consists of both. Picking one and doing the same derivative analysis (this time applying two iterations) gives us the circle with center at -1 and radius 1/4.

Code complexity editor feedback

Monday, July 27th, 2009

It would be nice to have a text editor that shows (along with information like the line and column number the cursor is on) a metric for how complex the code in the buffer is. Then refactoring would give immediate feedback - a change (hopefully a decrease) in this number.

Climate change is irrelevant for alternative energy

Sunday, July 26th, 2009

I've read a number of things lately (particularly on Motl's blog) suggesting that maybe anthro-centric climate change doesn't exist, or that if it does the effects are small in comparison with natural variations caused by things like natural disasters and long-term solar cycles. This is certainly not a mainstream point of view amongst climate scientists, but Motl does make some interesting points that I have yet to see refuted.

However, even if Motl is right that still doesn't exuse us from having to invest in alternative energy sources, because fossil fuels are still running out. They've been getting more and more expensive for years and it's not because of the price of the dollar or the greed of oil companies - it's simply that we've already used up the oil that is cheap to extract, and what remains is more labour-intensive and therefore more expensive. This trend will continue until it becomes more cost-effective to use renewable energy sources.

It's in the interests of everyone (except the oil companies) that this happens sooner rather than later. The reason for this is that fossil fuel energy becomes more expensive the more money you spend on it (like diamonds, and for exactly the same reasons), and renewable energy gets cheaper the more money you spend on it (like computers, and for exactly the same reasons). Once all the money we're currently spending on oil goes into research into renewable energy sources rather than research into oil extraction methods, energy will get much cheaper very very quickly, and our transportation, heating and electricity costs will all go way down. Also, we will stop pouring so much money into the pockets of unpleasant middle-eastern regimes.

There are also environmental problems caused by fossil fuels that are not disputed at all, such as the damage caused by oil spills or the pollution caused by coal mining operations. However, we don't yet know what similar environmental problems will be caused by the renewable replacements (perhaps our solar panels will require elements for manufacturing that are also messy to mine, or poisonous chemicals). But given the amount of energy that will be generated by a solar panel (say) over its entire lifetime, it seems unlikely that the environmental problems of using renewable energy will be worse.

Game browser

Friday, July 24th, 2009

I was thinking some more about convergence of game engines recently, and started wondering what a cross between a web browser and a game engine would look like.

I think the real value in this would be lowering the barrier to entry for 3D game creation, much as the appearance of HTML and web browsers made it easy for anyone to create rich documents and publish them to the world.

The first thing we need is a very high level way of specifying simple 3D environments. I think the best interface for such a task ever conceived is that of the holodeck in Star Trek: The Next Generation. Captain Picard walks into the holodeck, which initially is an empty room. he says "Computer, create me a table" and a generic table appears. Next he says "make it pine, 2 inches taller, rotate it 45 degrees clockwise and move it 6 feet to the left". Iterating in this way, he converges on the design he had in mind. Seeing the intermediate results immediately allows him to determine what's "most wrong" and therefore needs fixing first, and may also provide inspiration in the event that he doesn't really know what he wants just yet.

The difficult thing about this interface is that one needs to have a big database of objects to start with - tables, trees, bees, books and so on. Once also needs a big database of textures, a big database of transformations and so on. In fact, there are all sorts of databases which would come in handy - animations, AI routines, material properties, object behaviours. The obvious "Web 2.0" way to populate these databases is to encourage people to publish the things they create for their own games in such a form that they can be used by other people for their games. I don't think the software should necessarily go out of its way to forbid people from making content that can only be used in their own game, but making the default be "this is free to use" would probably help a lot.

If you're creating a website today you can easily find lots of free backgrounds, buttons, menus, applets and so that have been created by the community. With the right encouragement, a similar community could form around creating game things. Put a search engine on top of this community's effort so that when you search for "chair" you get a gallery of models to choose from and you're well on your way to the holodeck interface.

To create compelling games, one needs more than just a decorated 3D space to wonder around in - there need to be challenges, there needs to be something at stake. The web model breaks down a bit here - since you can get from anywhere to anywhere else just by typing in the appropriate URL, what's to stop players from just transporting themselves to the holy grail room?

I think that any non-trivial game would generally involve writing some code (possibly in an ECMAScript-ish sort of language). That code would need to have certain powers over the player, including associating information with them (like "has the player been through this obstacle yet?") and the ability to move the player (which could be done by moving a portal through the space that the player's avatar is occupying) to send them back to the beginning if they haven't completed a required obstacle or if they are "killed" by the minotaur. In computer games, death is of course never permanent, so can be effectively emulated by teleportation.

Another web principle that I think this software should embody is decentralization. Someone who wants to create a website has many options for hosting it (depending on their needs), one of which is to run their own web server. A major problem with a system like Second Life is that there is a central server, which is a single point of failure and a monopoly of sorts over the game universe. Virtual "land" is not not free in second life, it leased from the central authority. And if that central authority decides to raise their prices, censor content they find objectionable or has a server failure, there is nothing that the users can do about it. I suspect that this is a limiting factor in SL's growth.

If no-one "owns" this universe, who decides how it "fits together" (more concretely, what's to stop everyone saying "our site is directly north of Yahoo!"). I think in this scheme one has to give up having a single Hausdorff space and instead have many worlds connected by portals. The owner of a space decides what portals go in it, how large those portals are, what their positions and orientations are, how they move and where you end up when you go through them. Portals are not necessarily bi-directional - on going through one, one cannot necessarily get back to where one was just by retracing one's steps. They are more like links on a website than the portals in Portal. Mutual portals could be constructed though, if two gamemasters cooperate with each other to do so.

Ideally a portal should be rendered in such a way that you see what's on the other side - this just means that that "world" would also be loaded by the client software and rendered from the correct perspective (though should not be able to affect the player).

I think it would be great fun to wander around and explore different game worlds this way. It might be confusing sometimes, but if a place is too confusing people probably won't create many portals to it, so the system would be self-governing to some extent.

The system I've described could run with a standard HTTP server to implement a wide variety of single-player games. But where the internet really comes into its own is real-time interaction with other people - (massively) multiplayer games. Here, things become more complicated because the movements and actions of each player need to be sent to all the other players, and conflicts need to be resolved (who actually got to that loot first?) These problems have all been solved in real-life multiplayer games - one just needs a server which does some of this "real time" stuff as well as serving the content.

While games would be probably be the initial "killer application" for this, I'm sure all sorts of other interest applications would emerge.

Shortly after I originally wrote this, Google announced their O3D API which seems like it has at least some of the same aims, though at the moment I think it's really just an in-browser 3D API rather than a 3D version of the web. However, it'll be interesting to see what it evolves into.

Vista without Aero

Thursday, July 23rd, 2009

A while ago, I switched my Vista laptop from using Aero glass (which it is capable of) to the classic Windows 98 theme that I've been using (with few modifications) for over a decade. That one simple change made the machine quite significantly faster - that much faster that I decided to keep glass off despite it being that much prettier. I think part of the reason is that I tend to keep a lot of windows open at once, many of them maximized. Because the Desktop Window Manager keeps the bitmap for each open window, this uses up quite a lot of memory.

Unfortunately disabling DWM still doesn't give me back the ability to use full-screen DOS applications, which is something I occasionally miss. Still, I can use DOSBox for those tasks now.

Next time I replace my laptop, I'll have to try this experiment again and see if the performance difference has become negligable.

Disproof of God

Wednesday, July 22nd, 2009

It's pretty easy to prove that God didn't create the universe, given just a couple of very uncontroversial postulates and the definitions of the words "universe" and "God" as most people understand them.

  • Define the causal closure of a point in space-time X to be X plus the causal closure of any points that could influence X or be influenced by it.
    Define the universe (which we'll also call the "L-universe") as the causal closure of planet Earth as it is today. (If you dislike the use of "planet Earth" or "as it is today" in this proof, you can substitute it for some other subset of the universe that is alleged to be created by God.)
  • Postulate that if A created B then A influenced B. This is a pretty trivial postulate - creation of something is obviously a kind of influence over that thing.
  • Postulate that creators cannot create themselves. This is also pretty trivial - the concept of creation of an X implies that there is a time before the X exists and a time after which X exists. The creator of X must exist in both of these times, but the creation can only exist in the latter.

Suppose that the universe was created by God.

  • This implies that planet Earth was created by God (planet Earth is part of the universe).
  • This implies that God influenced planet Earth (creation is a sort of influence).
  • This implies that God is in the causal closure of planet Earth (definition of causal closure).
  • This implies that God is part of the universe (definition of universe).
  • This implies that God could not have created the universe (creators are not part of their creations).
  • Which is a contradiction. Therefore, the universe did not have a creator.

This is a formalization of the common "If God created the universe, who created God?" argument but sidesteps the possibility of a creatorless God or a God created by another God by including all such Gods in the larger L-universe.

This suggests that to believe in God, one must have a different definition of "universe" (call it "S-universe") which is a subset of the "L-universe". This brings us to the real value of this proof - any argument for the existence of God that doesn't distinguish between the L-universe and the S-universe must be invalid, because to be true it would have to apply to the S-universe (for which there can be a God) but not to the L-universe (for which we have already seen that there isn't). Some examples of such arguments:

  • We don't know how the universe was created, so let's just define God to be whatever created the universe.
  • The universe seems well suited to our needs.
  • Anything of sufficient complexity must have had an intelligent creator.

Photos January-July 2009

Tuesday, July 21st, 2009

This brings a whole new meaning to the words "embedded circuitry":

This picture was taken by Alex:

Home-grown strawberries: