Jonathan Blow's Rants

I recently wrote an entry in the journal for a programming language project, and that entry mid-way turned into a rant about language design and the way it affects the engineering process. So I am linking that from here.

The many-worlds interpretation of quantum mechanics is accurate. Any time something "random" happens, all possibilities happen. For the purposes of simplicity, let's assume forward-flowing time in this view, so that each possible reality branches out in a tree structure to its children (realities that follow that moment in time).

(This is a somewhat goofy way to think about many-worlds, because it ignores the seemingly-illusionary nature of time. At the very least one really ought to think of time as being bidirectional, so that in addition to an infinite number of futures branching out from each "present", there are an infinite number of pasts that converge into each present. Then you eliminate the labels past/present/future and just visualize each reality at a moment in time as a point in some big space -- it's something like an infinitely thick column with a fine structure of local interweavings. But the tree thing is easier to think about).

Consciousness is some thing that originates outside of the world and is the source of "quantum collapse". But because all these realities exist at once, quantum collapse just involves choosing which direction to go along those local weavings as you navigate this big tree structure of reality.

How does a consciousness decide which way to navigate? We'll assume that it doesn't have access to most of the information in the world -- just to a set of values that are near each other in space/time, for example in the brain of a living creature, but potentially in simpler things as well. It looks at the states of those variables (whether they are quantum states or classical states) and just makes some decisions about which way to go in response, over and over again. The decision-making process could be simple and heuristic.

This would have some interesting ramifications regarding computation. To talk about them I first want to bring up an analogy that at first seems mostly unrelated.

At a conscious and subconscious level, people rationalize all the time. They decide on something that they want or believe, then construct arguments about why this thing is good / must be so, and use those arguments to defend the decision. They act like they arrived at the decision through the path of reasoning they're using to defend it, but the truth is that the reasoning was just constructed to support the foregone conclusion. Even people who are supposedly very reasonable / scientific do this all the time. (I know I do.)

In this scenario where a consciousness is navigating this reality-space based on a set of stimuli, there's a sense in which all the brain's operations are more like rationalization than reasoning. Yes, there is some ironclad sequence of neural computations or whatever that caused the brain to instruct the body to do what it did, and all those computations are governed by the laws of the physical universe. But that particular sequence was just enacted because it's the way to get from A to B, or at least to steer in the general direction of some B, which the consciousness chose as its navigation target.

In this picture we have to re-think the purpose of the brain as a computational device. Usually we think of it as a device that needs to compute the right answers or at least useful answers to a wide variety of problems that are thrown at it on a continual basis. Problems like, whose face am I looking at? or Should I try to get a cookie out of that cookie jar way atop the refrigerator? To focus on the face example -- we consider the brain as searching trough some vast set of associations to come up with a unique and unambiguous recognition of the face that's in the field of view.

But if a consciousness is steering a path via quantum collapses, then this is not necessarily the most useful thing for a brain to be. It'd be more useful for the brain to be good at potentially computing a wide variety of answers (many of which are not necessarily useful), and the consciousness navigates through paths that usually contain the useful computations, most of the time. The brain would be performing classical computation, but it would seem a lot like quantum computation -- having the same character of many answers being computed, but only a few being chosen.

This would present a big problem for AI researchers. It's traditional to hold up the example of the human brain as an existence proof that AI is possible. But if the brain is more of an aimless computing device than we suppose, and some kind of extra-world guide mechanism is required to make it function in the way it appears to work to us, then that existence proof would be gone. Which is not to say that AI would be impossible, but the problem would appear much more difficult. We would have no known way of guiding the computation to a useful result (which frankly seems a lot like the problems we have in AI now).

Going back to the dualist model, we can easily modify it so that the consciousness is navigating not a point through the reality space, but a ball of small radius -- in other words, the ball encompasses a number of realities at once (an infinite number, but a small infinity compared to the number of actual realities in the possibility space). The ball moves in order to seek the desired stimuli, but things not pinned down by the stimuli (not observed) are allowed to vary somewhat. Since the brain is a physical system, perhaps some of its internal processes are not observed well enough by the stimuli to be pinned down. In this case there would be many mental processes all arriving at the same conclusion/action/stimuli, and they are all equally valid as descriptions of the way we got from A to B, so "they all happened" in some sense.

As I've described it here, this picture fails to explain some things, e.g. why everyone else besides you appears to be behaving just fine (if the brain were such a lax computing device requiring consciousness to help steer it, and your consciousness went off on some path without other consciousnesses there, everyone else would sort of fall over and start spouting gibberish or something, and why that doesn't happen would require significant explanation).

26 March 2005 (revised 27 March 2005)
Abstraction

As a side-project, I am making a programming language. This is not my first language (I made a bunch when I was in college, one of which is even in FOLDOC for some reason). But, it is the first language I have made with anything near my current level of programming skill and maturity -- the last language was 11 years ago, which is a long time if you're a self-improvement kind of person.

As a running test of the language, and as a way of figuring out what to implement next, I am writing significantly-sized software in the language (an Integrated Development Environment and some other things). Usually, writing software involves: (a) thinking up some abstractions that fit your problem, then (b) filling the abstractions in with implementation details. The abstractions don't actually do anything, in the sense that they don't contribute work toward the program's goal. Abstractions are just there to help reduce confusion while you create all the implementation details.

The language I'm making doesn't have all its mechanisms for abstraction designed yet. What that design should be is part of what I am trying to figure out by writing the IDE and other software. So making the software is hazier than usual -- it's a process of (a) Thinking about what the abstraction mechanisms should be; (b) Implementing abstraction mechanisms to some incomplete level of detail; (c) Thinking up some abstractions implemented using these mechanisms; and (d) Creating implementation details. Except the steps don't occur in that order, or in any clear sequence at all. It's like staggering home uphill while drunk, you weave this way and that, making general progress that is not too swift.

This whole process reminds me of how much I do not understand about computer programs. I am a pretty good programmer. But writing software for me is something like a large exercise in faith. Through many years of experience, I know how to imagine abstractions and the way they hook up together and the way information flows between them, and I can do all this fluidly and quickly. Then I go and type things that implement those abstractions, and after a little bit of debugging, it all seems to work.

After the program is done, I mostly understand my abstractions. But the program is not the abstractions -- as I said, abstractions don't do anything but give you a conceptual framework that you can deal with. The program is all the stuff that fills in those abstractions. And whereas I understand all that stuff, looking at it line by line, I just can't step back and visualize how all that stuff makes the program go. I just have to have faith that it will all work.

I have met a lot of smug programmer-type guys who believe they understand computers really well -- and I am dead sure that most of them are wrong. Certainly I am a better programmer than many of them, and I don't seem to understand very much. (By analogy: I have also met a lot of smug sysadmin/IT kinds of guys, and they are basically fools.)

The ability to build something is not the same as understanding the thing that you've built. But a lot of people don't want to acknowledge that, because it would eliminate so much of the ego-stroking on which they depend.

Keeping all this in mind, writing a language compiler/interpreter system is a weird experience. The system I build actually implements implementation details (which causes actual work to be done), but it also spends a great deal of time and effort implementing abstractions (which don't do anything but aid my feeble mind), using its own big abstractions to do so. Inside the system, it's unclear to me where the line is drawn between functionality that implements abstractions and functionality that implements "real work". I know for sure that you could get rid of a lot of the imaginary walls and doors internal to a language system, yielding something a lot leaner and tighter that still does the same job. I just don't understand enough to know how to do that. Perhaps "understanding" is a barrier to achieving that. You can look at biology for an example of how things might go without a requirement for understanding before implementation: evolution does not think about what it is doing, thus you get all kinds of crazy stuff.

Abstractions in the core system, whose main purpose is to represent abstractions in the language system, seem especially hollow.

In summary, when I program now I feel like Zatoichi or Johnny Depp's blind CIA guy at the end of Once Upon a Time in Mexico: I can't see but I can still hit the target. That's one thing I want to achieve, just a little bit, via this new language: the ability to see what's going on.

23 November 2004
Perception and Understanding

The amount of stuff that has to happen in our minds/brains in order for us to understand what we see, or what we hear, is completely crazy. I sort of knew this, because I did some work in computer vision a couple of years ago, but I still didn't have an appropriate appreciation. (And I think most AI people don't).

[Right now I am reading Daniel Dennett's Consciousness Explained which is reminding me of all this. Said book has been on my to-read list for a few years, but when I was visiting Casey in Seattle I saw that he had a copy which bumped it back into short-term memory long enough for me to pick it up].

We are so very, very far from being able to accomplish anything remotely similar to human perception that it's just not funny. We really have no idea how to do it. Our best model is something like this: you have some systems for low-level perception (receiving the photons, detecting edges and texture), some systems for high-level cognition (remembering what a car looks like), some systems in the middle for mediation (maintaining temporary ideas about what things in the image might represent the same object, proposing new associations and culling old ones), and a lot of flow back and forth where the high-level stuff tells the low-level stuff where to look and what to look for, and the low-level stuff tells the high-level stuff what it found there, and eventually consensus emerges.

I think this is the right kind of picture, but at the same time, it doesn't say very much. It gives us the structure of something that can help solve a problem, but not the actual methods used by that structure, which are still dark and mysterious. We don't yet know enough to see all the things we don't understand about that computational framework. It's like a guy from ancient Egypt who knows how a wheel works, so he looks at a modern car and says "Ahh, you push the pedal and the car rolls forward on the wheels, very good", and he knows there is a little bit he doesn't understand about how the pedal makes the wheels roll. But that simple piece of ignorance cloaks a huge amount of stuff about the internals of the automobile. Like, does the Egyptian know how to manufacture plastic for the container that holds the antifreeze?

Usually when we understand so little about a subject, we're unconsciously making a whole bunch of assumptions that are untrue. Lately I've been making a game of repealing as many assumptions as possible. Here's one: Is vision really computable by a Turing machine?

Most programmers would say that it is, and that you're smoking crack if you think it's not. For some reason this goes hand-in-hand with the computationalist view of human cognition (that the human brain doesn't do anything that a computer couldn't do, either). But that's even wrong because there are two separate issues there which are independent (one could be true while the other is false), and the fact that people conflate them shows how unclear the thought tends to be.

We already know of a class of computers that is (probably) more powerful than Turing machines: quantum computers. And we can even build some very simple ones, with more sophisticated versions on the way. Writing an algorithm for a quantum computer is very, very different from a Turing machine. Trying to do a good job of it really makes my head hurt.

So one possibility is, maybe the brain does some subtle quantum things that we don't understand. Then you can have a physicalist viewpoint that contradicts the common assumptions about the computability of vision -- the brain/mind doesn't do anything that a computer couldn't do, as long as that computer is at least as powerful as a quantum computer, i.e. more powerful than a Turing machine. But people don't think about this very much.

I really would not be surprised if the brain is doing a lot of quantum stuff at a very low level. I'll write more about this in a future rant, but for now my thoughts are far too muddled.

Here's a related issue, though. In the previous rant (below), I express my doubt about our current understanding of the mechanisms of evolution. I don't think that our model of genetic computation is sufficient to explain the accomplishments we ascribe to evolution.

When you say things like this, a lot of people will come to the knee-jerk conclusion that you're some kind of religious nut. But there are other possibilities that are wholly within the realm of science, though people don't think about them.

Here's one (and I am not actually suggesting that this is true, just putting it forth as an interesting thought experiment): What if DNA actually did some quantum stuff that allowed it to transcend the arrow of time a little bit, to "see the future" in a very limited, local, hillclimbing sort of way? That would put it in a super-Turing computational class, and suddenly bets are off.

This sounds wacky, but keep in mind that we don't currently understand where the arrow of time comes from, and at a low level, the laws of physics are pretty much the same backwards as forwards. So such transactions occurring at a very low, subtle level would seem at least within the envelope of possibility to someone with an open mind (even though one might ascribe a high degree of improbability to them).

This is not really a new idea -- there's been some science fiction written about related concepts, for example, Greg Egan's book Teranesia. [Which is not exactly a good book, despite the fact that the core idea is interesting. If you want to read a Greg Egan book, try Diaspora or Permutation City or Quarantine].

If quantum arrow-of-time shenanigans really happen, then you could build simulators with Turing machines your whole life and never achieve evolution that's as good as what DNA can do. That's how I have been feeling about perception, lately. It's that far away from what we can do.

I think many proponents of Intelligent Design are nutbags. At the same time, though, I don't discount or ridicule their basic idea. The staunchly pro-Evolution views of the scientific establishment really bug me. According to just about every modern "scientist", if you don't believe that life on Earth is a product of evolution, you're some kind of ignorant crackpot.

I believe in evolution. Hey, it's obvious -- we make evolution happen all the time. For example, we breed dogs (sometimes to make them magnificent and healthy, and other times to create degenerate little lap whelps... but that's a different rant). Almost all plants and animals that we recognize as food have been domesticated. Evidence of evolution is all around us.

Sure, there's the fossil record and all that. It includes a lot of compelling evidence about creatures that evolved from other creatures. But to me that's not quite as immediate and in-your-face as the fact that you can make evolution happen yourself.

Also, you can make evolution happen on a computer, with genetic algorithms and things of that nature. That is pretty neat.

But here's the issue. Everyone who has tried to use genetic algorithms for real problems knows that they are kind of feeble. Sure, they evolve in the way we direct them, sort of. But they sort of hit a wall beyond which they can't evolve things that are interesting or effective enough. Genetic algorithms kind of suck.

This suckiness of genetic algorithms illustrates one thing: if we say that evolution is responsible for the rise of life as we know it, then clearly we don't understand evolution yet. Or to put it a different way, the "evolution" to which we ascribe the development of life is different from the "evolution" that we understand and know how to implement. We get all hand-wavy and vague to cover the difference between these two kinds of evolution. When we implement the thing we understand, we get a system that is not good enough to produce the evidence we see in the real world. Clearly we are missing something.

Some people point out that the Earth is big and as such provides a really good opportunity for parallelism, more than we can achieve on computers right now. They figure that if you could just run a simulation that was big enough and fast enough, our current evolution algorithms would be able to produce life-like complexity. I don't believe this argument. It has always been wrong in the past. For example, the "classical AI" guys in the 1950s through the 1970s all pretty much believed that if you just gave them a fast enough computer, their symbol-processing algorithms would demonstrate intelligence. By the end of the century computers would be smarter than people. Well... that sure hasn't happened. And it's obvious now that there's a huge amount we don't understand about intelligence, and the classical AI approach looks pretty naïve in retrospect. Well it's the same damn situation with evolution.

To me it comes down to one issue: if you understand something, you can implement it. If you understand a car from end-to-end, you can build a car in your back yard. If you understand evolution, you can build a simulation that evolves a bacterium. We don't understand evolution.

If you don't understand something, yet you staunchly believe to the exclusion of all else that that something is responsible for such a huge, varied, and complex thing as life on Earth, then you are not being scientific. You are being religious. In some cases you're engaging in outright zealotry.

To me a reasonable anti-Intelligent-Design viewpoint would be something like this: "Evolution obviously happens, and probably it is responsible for life as we know it. But there are a lot of things about life that we don't understand, and a lot of things about evolution we don't understand, so it's possible that something's going on in there that we really don't expect. Probably there is just some tricky way in which evolution operates to create surprise high-level operations, and when we figure that out, we'll be able to model things better. I am open to the idea that we will never find such a thing, and in that case we'd have to consider other sources of the complexity we find in Life (little green aliens, God, Agent Smith, whatever), but that day is not today."

It seems that we have lots and lots of people with PhDs in scientific disciplines, but very few actual scientists. That makes me, you know, sad and stuff.

I've got some class, and I want to define a data member. According to classic OO doctrine, I am not supposed to let anyone see that data member -- I am supposed to provide accessor functions for getting and setting it. The reason for this is, even though the data member might not actually do very much, and just be minding its own business, I might want to change its name or storage format or side-effects in the future, and the getter/setters shield the rest of the program from those implementation details.

This is extreme bullshit in many ways. The software engineering world is shooting itself right in the face by following these practices. I'll try to cover all the major points regarding why, but there are so many I'm bound to miss a few.

First I'll put forth the alternative to this accessor method, which is just to leave the data member as it is and let the rest of the program access it directly. When you want to change the implementation, you do that and then try to compile the system. You get 375 compile errors and then step through and fix them all, which takes somewhere from a couple of hours to a day.

That's an explicit cost. It's measurable, so you can be scientific about it. You can make some judgment about the cost versus how much benefit you'll get from it, to help decide the overall impact of the change. These are good things.

The cost of using accessors instead, though, is fully implicit. You pay in larger file size (source control operations take longer), and code understandability (there are a lot more tokens in the header files and implementations for a reader to sift through, which inherently makes things more difficult to perceive; also, the caller of an accessor generally doesn't know what's going on behind the scenes when he calls it, which adds to the fog of war). You pay in compile times (more program text), and link times (more symbols to cross-reference). You also pay in that the initial code takes longer to type -- though I don't think that's a very important cost, and C++ already totally sucks at this, but it should be mentioned anyway. You pay in that there's more stuff for your bloated code navigation IDE to sift through, and more ways for it to get confused. There are probably a lot of other costs as well that come up on a case-by-case basis.

Because these costs are implicit, they are very hard to measure. Yes, they are small -- but most of them are cumulative (consider the compile/link costs). If you pay an extra 10 seconds per programmer every time they hit F7, and on average a programmer hits F7 30 times per day, that's 25 minutes per week wasted. Treat this as an extremely conservative lower bound -- I think the cost is a lot worse (due to understandability issues, which dwarf things like build time issues, but build issues are more measurable). But I am just trying to make the point that even if you think the cost is low, it is not zero. And it's a tricky situation because no-one can say exactly how far above zero it is.

Most of these software engineering paradigms/sets of best practices/etc are just a bunch of big farces. And one reason for this is that they never consider the cost of the solutions they propose. They say "Hey there is this problem, it can be solved with X". But how much does X cost? They sweep it under the rug, they assume the cost of X is zero. Well sorry, but it's not. It never is. So for these people to deserve being taken seriously as engineers, they had better start measuring the costs of their techniques and doing some actual cost/benefit analyses. I am reminded of the Adbusters "Economists Must Learn to Subtract" campaign.

I mean, these OO best practices people are telling me I should buy this paradigm, but they can't tell me how much it costs (in fact they're not even aware that it costs anything), and they can't tell me in concrete terms how much benefit I will get from it. If I'm a smart buyer, am I going to buy it or not? Hmmmm.

So getting back to this whole accessor function thing. Aside from the cost being implicit, it is also invoked much more frequently. By this I mean, you're paying the implicit cost for all data members in your system, regardless of whether you change them or not. Well here's a news flash: most of those implementations are not going to change, almost ever. We have a hard enough time getting software done in the first place these days. So you're paying for something that most of the time you won't need.

Furthermore, this accessor function thing only solves easy problems, not hard problems. It can only shield the implementation change from the rest of your program when the new implementation is emulatable by the old implementation's accessors. Hey, guess what, that is only going to be true for relatively simple changes. For any more substantive changes, you have to change the accessors and then go through the code fixing all 375 compile errors. And in that case, you paid the implicit accessor cost all along yet now change-time comes and you get to pay the explicit interface-change cost anyway, in addition. In that case, it sure sucks to be you. Wouldn't it have been better to pay only the explicit cost?

Given that the programmer has bought into this paradigm where he is not supposed to have to change the interface, he is going to try as hard as he can to cram the new functionality into the old interface and avoid those 375 compile errors, even though the best thing for the health of the program is to change the interface and do the clean-up work. So he makes the interface function do some Byzantine conversion, raising the software complexity and lowering its quality. So this engineering paradigm actually encourages code rot, explicitly.

Extreme Programming has some aspects about it that I think are very sound. A major one is the prototype-based development, where you start programming a simple system, make it testable, and then expand it to envelop the functionality that you need step-by-step. This kind of "necessity-based design" is very sensible, and when fully bought-into, I think it says you shouldn't use accessor functions. Because accessors are about accomodating situations that aren't happening right now and probably won't happen, which is the anathema of necessity-driven design. (On the other hand, there are lots of things about XP that I think are goofy and lame, like Pair Programming -- yecch.)

The "just change the implementation" approach that I am advocating here is very safe now, because languages like C++ have link-type type checking (and if you are making a change that involves something remaining a compatible type, just re-name the variable). Back in the pre-ansi C days, you could get screwed by making big sweeping changes like this, because you'd miss some things and the compiler would link incompatible stuff together and you'd get a runtime crash. But that's not a problem in C++ and other modern languages. When you change an implementation, the compiler tells you exactly what you need to do to bring the program back into line. We should stop pretending that that isn't the case.

There is one argument against what I am advocating here that I think is a little bit valid. Which is that, in addition to shielding against changes to program text, accessors also shield against having to know whether something changed or not, which means that changes you make are lower-cost. (Because programmers on the team don't have to realize that they need to do something in a different way now, they just plod on as before). That is a benefit of accessors, but at the same time I don't think that it comes close to recouping the cost. If a programmer is used to doing something one way, and it changes, the compiler will give him an error message, and he figures out how to do it the new way, and there he goes. This would be a problem if it happened to a lot of things all the time, but it doesn't. It happens to a minority of the system a minority of the time.

I didn't mean to focus just on accessor functions here; I think many software engineering paradigms suffer from very similar problems. Accessor functions are an easy example though, and most people know about them, and at the end of the day this rant is already long enough so I won't drag anything else into it.

I'm currently reading On the Sensations of Tone, by Hermann Helmholtz, translated by Alexander J. Ellis. Helmholtz wrote the book in 1862, and here is a quote:

Indeed it is seldom possible to survey a large surface of water from a high point of sight, without perceiving a great multitude of different systems of waves, mutually overtopping and crossing each other. This is best seen on the surface of the sea, viewed from a lofty cliff, when there is a lull after a stiff breeze. We first see the great waves, advancing in far-stretching ranks from the blue distance, here and there more clearly marked out by their foaming crests, and following one another at regular intervals towards the shore. From the shore they rebound, in different directions according to its sinuosities, and cut obliquely across the advancing waves. A passing steamboat forms its own wedge-shaped wake of waves, or a bird, darting on a fish, excites a small circular system. The eye of the spectator is easily able to pursue each one of these different trains of waves, great and small, wide and narrow, straight and curved, and observe how each passes over the surface, as undisturbedly as if the water over which it flits were not agitated at the same time by other motions and other forces. I must own that whenever I attentively observe this spectacle it awakens in me a peculiar kind of intellectual pleasure, because it bares to the bodily eye, what the mind's eye grasps only by the help of a long series of complicated conclusions for the waves of the atmospheric ocean.

The book is amazing for its readability and accessibility. (Helmholtz doesn't assume that you've ever seen the graph of a function before, and proceeds to explain it from first principles.)

When I read this, I'm in the presence of a man who's operating from a vantage point higher than most. It's incredibly refreshing, compared to the avalanche of papers written by Lamer Q. Postdoc and cohorts, that we usually find ourselves slogging through. So much "work" today is so terrible. Experience would lead me to expect that things were just as bad back in 1862, except that most of the bad stuff hasn't survived. Maybe that's so, but it just seems unlikely to me, because there certainly was less volume of publication, and yet so many great discoveries were made during that time. Perhaps it was balanced in quality rather than quantity -- they had lots of pseudoscientific wack-jobs publishing ridiculous stuff. That could be.

Anyway, I think there is a scientific literature quality problem, and it's self-perpetuating. Each field has coalesced on its own standard format for research papers, which new students must follow to be taken seriously, and into which they quickly become indoctrinated. But in many fields the form is more or less crap, and this encourages the production of crap, with very few examples of non-crap to light the way (and worse, no clear method for students to discern what is crap and what is good). I'm thinking most specifically of areas like computer graphics, or "Computer Science" in general, but my grievance applies to other fields too.

I figure that if I can be as smart and upright as Helmholtz, then I'm doing okay.

Fans of 100 Bullets (see below) should head over to Casey's web site for his preview of Aquaman: Ground Assault and other exciting blockbusters-to-be.

At E3 today, and I'm reading this little preview magazine called "rumbled" that's an insert to MCV. (The magazine doesn't say so, but it's not hard to see that it's a paid insert by the publisher Acclaim; all the previews are for Acclaim games and the 1 or 2 ads are also by Acclaim. Though they dishonestly try to make it look like somewhat like a real publication).

Acclaim is publishing a game called 100 Bullets, and there's a preview for it. It's a licensed IP, based on a comic book of the same name. The preview article begins:

"If a stranger gave you an attaché case containing a gun, 100 untraceable bullets, proof that someone had done you an irreparable wrong along with immunity to exact revenge on that person, would you pull the trigger? That's the intriguing premise behind 100 Bullets...."

Now hold it right there. Obviously the premise is not "Would you pull the trigger?", because that would make it some kind of deep and interesting moral dilemma game, the likes of which we don't understand. The premise is more like, "When you pull the trigger, are you going to hit the guys?"

"Obviously it'd be a very short game if Burns politely declined Graves' offer, and an impossibly tough game if he was actually limited to 100 rounds. Instead you're thrown straight into the firing line with plenty of bullets to spare and plenty of enemies to kill too."

What kind of lobotomized asshead makes these decisions? "Yeah, this whole point of this comic is that people are given 100 bullets and a gun. But let's not restrict you to 100 bullets, because if we did that, we couldn't make this a generic boring shooter like all the others. So you get tons of bullets! Maybe you can beat up hookers to get more bullets. People really responded to that hooker stuff in Grand Theft Auto."

Like, holy shit people, the gaming press and fan sites would love to talk about a game that's perhaps 12 hours long, where you only get 100 shots and you have to make them count. That gets you the kind of press you just cannot buy. And hey, you might even manage to make an interesting game. You might give game players a reason to tell each other about this game, igniting some good word-of-mouth publicity. You just might catch potential buyers' interests when they're browsing through the store.

Movies and TV shows are built around this kind of gimmick all the time, quite successfully. But the game business is so lame we can't even do gimmicks any more because they're unsafe?

Why even bother to license an IP if you're going to disrespect it like this? It's not exactly a huge-value license, like the Terminator or something.

This is about as ridiculous as when Gathering of Developers published "KISS Psycho Circus" but there was no KISS in the game. Or my favorite game-in-development, Fight Club. Ahh, Fight Club.

22 April 2004
Program Verification, Computer "Science" and the Holographic Principle

I've been thinking a lot lately about how we make sure that programs work. In the game business (as well as any others where concrete results are required), the answer is that you just test the hell out of your software and you fix all the problems that arise, and you keep testing until the behavior is acceptable. For some level of software complexity, you will never reach zero bugs through this kind of behavior, because that would require too many man-hours. Essentially we're just doing an iterative function-solve, wherein we take as many steps as we have the resources to take, and when we're done we just hope that is good enough (or else the project has failed). [There are some other pertinent points to this analogy -- most game developers are familiar with the phenomenon of getting stuck in a local maximum and then having to just iterate there because they need to ship].

Now, a lot of people at universities who call themselves professors of "Computer Science" would consider this to be a scruffy, undignified approach. The more dignified approach would be to sit down and think really hard and do a bunch of analysis to prove that your program is correct; that way you know it *really* works. It's a nice idea; in the "test a whole lot" model of software correctness, you can of course fail to catch some bugs because your testing just didn't touch on that part of the input space (and the input space is so huge you just can't touch it all). When engaging in such brute-force software testing, we can take a cue from the "prove it correct" guys and try to understand where the important wrinkles are in the input space (places where the program behaves discontinuously), test a lot in those areas, and test less in the in-between areas because those are expected to be smooth. Except of course this analysis is really hard to do, so hard that we almost never do it successfully except for the most obvious cases.

In academia, folks have been working on theorem provers that try to prove program correctness. I have always looked upon this as an essentially hopeless task, because real programs are just incredibly complex and theorem-proving approaches only seem to work in stark, simple environments (this is not just true for program correctness, but in other areas where theorem proving was tried as well, like AI planning / deduction / knowledge-representation systems). I'm not totally down on the idea of theorem proving, because maybe sometime in the future we will develop the paradigm enough that we can give it a small nugget of a real program and get back some reassurance that the nugget is correct. That would be somewhat useful (though we are a long way from even that).

Lately, it occurred to me that the very idea behind proving program correctness seems odd, and is probably incorrect. Is "computer science" really a science? If so, then it is about making predictions about what that will happen with physical computations, where those predictions are falsifiable. An example from the science of physics: you have Newton's theories of motion, which seem to explain moving bodies pretty well, except at small scales or at really high velocities, where the theories are falsified and we needed guys like Lorentz and Einstein to come up with more-encompassing theories.

With computers, we have theories like: if you put this particular set of gates together, and represent numbers in binary form and pump them through the gates, the output is greater than or equal to the input; or, such-and-such sorting algorithm (built out of many of those gates) takes O(n logn) steps to run. If computer science is a science, then we expect these theories to potentially be falsified in the future. If on the other hand it's mathematics, then instead of theories, they're rules that don't necessarily correspond to anything in the physical world, and we just extrapolate them forward and see what comes out of it.

Computer science is ostensibly a science in that it deals with real machines that produce real and testable outputs. However, almost everyone treats it like mathematics, in that they assume these laws of computer behavior are invariant and can never be broken (unless the computer is somehow malfunctioning).

In that sense, the "test a lot" model of software correctness is the truly scientific one; it doesn't make any assumptions about the relationship between the algorithm and the real-world behavior. It just empirically tests the real-world behavior and then tells you if it was right or wrong (and *how* wrong it was). On the other hand, the "proving program correctness" approach makes a lot of assumptions, most basically that the computer will do exactly what mathematics says the algorithm would do, for some extremely long and complicated series of manipulations with tons of dependencies.

From this point of view, the "test a lot" model is actually more solid and in some sense more dignified than the "make predictions" model, unless you believe that our model of computation, and the predictions it makes, are unshakeable. Well, so far everybody has a whole lot of faith that those predictions are right, so it's not an issue. But what if they weren't? In other words, what if the computations that a computer performs, must necessarily differ in some subtle way from the idealistic versions of those computations that we think about?

This sounds absurd, because it seems so easy to extend computational behavior by induction. I have this logic gate, which behaves a certain way, so if I string a whole bunch of them together, by induction, it behaves in this more complicated way. Voila. But we have to remember that "proof by induction" is clearly math and doesn't necessarily correspond to the physical situation we're applying it to.

More concretely, my suggestion is this: what if physical computers only behave ideally while we stay within some envelope of low computation speeds, large physical units performing the computations, etc -- in much the same way that Newton's laws are valid only for a mid-range of phenomena?

Maybe I am starting to sound nutty. But there's reason to believe that our unshakeable laws get shaken. Let's look at the Holographic Principle, stated by Gerard 't Hooft in 1993; though it's not yet proven in any palpable sense, a whole lot of physicists believe in it. It basically says that the complexity of what goes on in a certain region of space is limited not by the volume of that space, but by the surface area of its boundary. (A web search for "Holographic Principle" will turn up lots of interesting information; there is a straightforward and readable explanation in Lee Smolin's recent book Three Roads to Quantum Gravity, as well).

One tends to measure this boundary surface in Planck areas, where 4 Planck areas are required to hold one bit of information. When we relate this to computers, the following fact boils out: Take a boundary around some region of space, count the number of Planck areas, divide by 4, and that is the most computer memory that you could pack into that space (or else the most complicated algorithm you could fit there).

This is really shocking. Currently, computer engineers' model of computer memory is that you have some little piece of matter that holds a 1 or a 0, and you can cram a bunch of them together, to hold a whole bunch of bits, until you fill up some volume. So, if 'x' is your unit of length, then the amount of memory you can hold is O(x**3). But the Holographic Principle says the limit is really O(x**2). As computer scientists know, there is a whopping big difference between n**3 and n**2, so there is some explaining to do here.

If the Holographic Principle is really true, then physical computers cannot really be what we think they are, in the limit. We might best visualize the computations being performed by a 2D entity, some kind of projection of the 3D thing we currently consider to be the computer.

This means that right now, we ought to be vigilant in looking for the place where the ideal behavior (math-like) diverges from the actual behavior (science-like). But everyone is very busy writing web-database interfaces with JavaBeans, so they don't care.

We would not currently see this difference between n**3 and n**2 because Planck units are very small, so there are huge ginormous numbers of them in the area around any sized space that we currently build computers in. So we don't come anywhere near bumping up against the limit. And even if we do get near the limit someday, maybe we will understand how to engineer within the framework of the Holographic Principle, and build things at small+numerous scales that still behave like ideal computers.

Then again, nobody said this Holographic Principle thing is the *only* way in which physical computers differ from ideal computers -- it's just an obvious one that is staring us in the face right this second. There could be an innumerable number of differences. Nobody knows, and until we start questioning, nobody will even be on the road toward knowing.

Given this background, the theorem proving approach to software correctness, as we understand it currently, seems to be based on a long string of very questionable assumptions. Maybe the theorem-proving approach is woefully, dramatically wrong, and if so we wouldn't even understand how to begin fixing it. On the other hand, the "test a lot" approach would probably still work, though it would be harder to steer if we didn't understand the relationship between changes we make in the source code, and changes in the resulting behavior. (Though come to think of it, that already seems to be true for most programmers working in the field, even for computers at the current scales).

Who's to say that there isn't some more-abstract, less-overtly-physical limit on information processing in this universe? Maybe if you string together a long series of computations (in space, or time, or in some mysterious other metric), the answer wouldn't come out how you expected, not because of any size or volume constraints, but because such a thing just doesn't happen here?

Currently, many of our real physical computers are of somewhat poor quality. Certainly they fail pretty often due to normal implementation-detail-like things. (For example, some bit of ram not actually getting set because the electrons accidentally decided not to go there within the allotted time). This kind of event is unlikely, but if you test for it frequently enough (as we do with a huge number of computers performing huge numbers of memory operations all the time), then it will happen now and again. And these events are more likely than they might otherwise be, because we build so close to physical tolerances, in order to make the computers as fast as we can.

If we were already seeing sporadic symptoms of computers not behaving the way they "should" in some science-vs-math sense, we probably wouldn't recognize them. They'd be lost in the noise of all these routine failures.