Archive for July, 2009

« Older Entries

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.

Posted in computer | 2 Comments »

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).

Posted in computer | 1 Comment »

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.

Posted in random | No Comments »

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 zf such that zf2+c = zf. There are two solutions, (1 +/- sqrt(1-4c))/2. Then we can look at what happens when we iterate a nearby point (zf+d)2+c = zf2+c + 2dzf. If |2zf|<1 then the fixed point is stable. It turns out that this only happens for the (1 - sqrt(1-4c))/2 solution, so points in the cardioid are |1 - sqrt(1-4c)| <= 1, 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 |c|2(8|c|2-3) <= 3/32 - Re(c).

For the period-2 circle, we solve (zf2+c)2+c = zf and eliminate the period-1 solutions to get (-1 +/- sqrt(-3-4c))/2. 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.

Posted in fractals | 1 Comment »

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.

Posted in computer | No Comments »

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.

Posted in random | No Comments »

Lost theory

Saturday, July 25th, 2009

This post contains spoilers about Lost if you haven’t caught up to the end of season 5 yet.

The general consensus about the meaning of the season 5 finale of Lost is that Locke did indeed die at Ben’s hand in 2007 and that the person on the island in 2007 that we had been assuming was John Locke resurrected, is in fact Jacob’s nemesis who somehow has the ability to shapeshift and has taken John Locke’s form (and is possibly also the smoke monster).

I have a theory that this is not the case at all. I also don’t think John Locke was resurrected by the island. The apparent resurrection and the presence of two Lockes on the island at once (one dead, the other alive) can be completely explained using just the two forms of time travel we have seen on the show – the physical time-travel that Sawyer et al experienced and the consciousness time-travel that Desmond experienced.

My theory is that when flight 815 broke up, Locke’s body and consciousness were separated. His consciousness woke up on the beach shortly after, but his body took a detour, perhaps to some other part of the island. At some point after watching Jacob die in 2007, Locke’s body (which has by this time regained the ability to walk through slightly less miraculous means) time travels back to 2004 to be reunited with his fresh-from-the-crash consciousness. When Ben kills Locke, the latter’s consciousness travels through space and (a couple of days of) time to his other body on the island (displacing partially the consciousness that was already there). Thus Locke experiences apparently dying and then waking up on the island in 2007 after the Ajira 316 crash. The other Locke (who lived on the island from 2004 to 2007) learnt a lot during that time and joined the cause against Jacob – it is this consciousness that shows through in the plan to kill Jacob.

I also have a suspicion that Locke is not the only character whose timelines are not as simple as we have assumed. Have you ever thought it was strange how Jack woke up in the jungle after the flight 815 crash instead of on the beach with the others? Perhaps Jack’s body took a similar detour. One possibility is that it was zapped from the plane just like it was three years later in the Ajira crash. Another possibility is that Jack actually died in the 815 crash, or at least his body did (which would be an absolutely delicious plot twist) and at some point earlier in his life his body had taken a detour to the island. I love the idea that nothing we’ve seen over the past 5 seasons is quite what it seemed to be.

The idea that if you have two bodies in a particular time period and one of them dies, your consciousness is transferred to the other body is an interesting one, because it provides a partial explanation for Miles’ curious ability. I think Miles will die in 1977 in season 6, and part of his consciousness (including the ability to read the thoughts of the dead) will be transferred to his infant self. Something similar might have happened to Charlotte, except that she died in the distant past so there was no other Charlotte-body for her consciousness to be transferred to.

My theory about the incident at the Swan in 1977 is that Juliet is dead, dead, dead. A plutonium bomb exploded right next to her – there’s no way she could have survived that. However, I also think that whatever happened, happened (anything else would create a paradox) so the rest of the Swan site could not have been destroyed in the blast. While a Hydrogen bomb would have taken out a large chunk of the island, it’s only the Plutonium sparkplug that actually exploded and would not have had a particularly large yield (since it wasn’t designed to be a self-contained bomb).

Most of the Dharma Initiative’s technology is fairly crude and self-explanatory. A notable exception to this rule is the failsafe switch in the Swan. What does it do, and how does it counteract the act of not pushing the button? It must be something fairly significant, since it made the sky turn purple and sent Desmond’s consciousness time-travelling (and his clothes who knows where). There’s no 70s technology that could do that.

I think the Jughead sparkplug exploded at exactly the moment when the pocket of energy under the Swan would have otherwise imploded, taking the entire world with it. The two forces were then in an almost exact balance, with the Jughead explosion essentially frozen in time under the Swan. Radiation from the Jughead was slowly leaking out (hence the concrete wall) as was energy from the pocket that was breached. Radzinsky realized he could prevent an implosion somehow but only by taking some particular action every 108 minutes. This action was eventually semi-automated by entering the numbers and pushing the button, but for some reason this could not be completely automated. The failsafe key triggered another action which caused the energy from the Jughead explosion to be released all at once, destroying the energy pocket and saving the world. Perhaps Juliet was under the Swan all the time as well, frozen in time and dying for 27 years (although only milliseconds would have passed for her) – now there’s a an amazing answer to the “what’s behind the concrete wall?” question! The Swan crater seen at the beginning of season 3 is essentially a plutonium bomb crater (though not too radioactive, possibly for reasons related to the 27 year delay in the explosion).

As for the island itself, I think it’s an alien spaceship that crashed on Earth millions or possibly even billions of years ago. It’s been floating around the world ever since, gradually accumulating debris (at first mud, rocks and sand and then later ships and planes). An ecosystem grew on it. It uses an Alcubierre drive or something similar for faster-than-light propulsion, which involves it containing chambers of negative-energy material, such as the one Radzinsky drilled into. Jacob and the smoke monster are immortal aliens who came to Earth on the ship and have been trapped there ever since, watching what’s going on. Lost will end with the 815ers somehow providing the aliens with something they need to get the ship working again, and we’ll see the island rise slowly out of the sea and into the sky.

Posted in random | No Comments »

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.

Posted in games | No Comments »

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.

Posted in computer | No Comments »

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.

Posted in atheism | No Comments »

« Older Entries