Monthly Archives: February 2007

Why designing a language and designing a command line are different

If you’re not familiar with them, take a moment to check out some of Damian Conway’s modules. Good examples of what I’ll be referencing in this post are Perl6::Form and Text::Balanced.

Damian’s modules are the ultimate in user-friendliness, or to put it another way, DWIMminess (Do-What-I-Meaniness). He has relatively few functions, each of which is very full featured. Each takes a variety of kinds of arguments, and interprets what you probably wanted to do with that kind of data. They’re very “smart”, in a sense. And you could imagine that this would enable a very easy programming style, because the module is interpreting what you want to do along the way.

Another example of DWIMminess is the entire Perl 6 language. Well, it’s DWIM factor has been decreasing recently, but usually features are introduced as though they were in a Damian module and then slowly simmered into something a little stupider (describing the behavior of the functions, not the decision to make them behave that way). Why do we do that to Perl 6? Why might Damianesque interfaces not be as nice for programmers as it would seem?

First, let me make a case for “smart” interfaces. I want my command line to Do What I Mean as much as possible. I use this nice little program on “my taskbar called Deskbar, in which I can type a variety of things and it uses heuristics to determine what I wanted. For example, if I type “mplayer ~/movie.avi”, it will open mplayer and play that movie. If I type “gmail.com”, it will open my web browser to Google mail. If I type “dict persephone”, it will open a terminal with the definition of “persephone”. And it is wonderful; I don’t think it has ever done the wrong thing.

My case is that that is not a good thing to do when programming larger applications. Many folks would agree with me, but that doesn’t matter. I’ll bet they don’t know why they agree with me.

It’s about the information available to the programmer. When we’re writing code, usually we want to be as general as possible—to make as few assumptions as possible—when we’re programming part of a large application. We want to be able to work on as many forms of data as possible, and be agnostic to it if we can. For example, an object which maps strings to Foos doesn’t need to know anything about Foos to do that, so you could reuse that implementation for an object which maps strings to anythings.

On the other hand, when we’re on the command line, we know everything. We know what command we’re running, which arguments we’re passing, what error message it told us when we tried the same thing thirty seconds ago, whether the files we’re passing exist, whether the arguments we’re passing have spaces in them, etc. etc. We can quickly detect a failure, and we can also verify that it looks right pretty quicky. If you type “open -f http://google.com”, you don’t expect it to delete your hard drive. This opens something somehow, and it’s going to operate primarily on http://google.com. Who knows what -f means… it doesn’t really matter, since you can probably see what it means pretty quickly. But if you typed “$cmd -f $arg”, you can’t see what -f means pretty quickly, because it means something different for each value of $cmd. So even after you think your code is sturdy, some $cmd may come along someday and cause something totally unexpected to happen.

My stance is that DWIMminess is good in principle. More programming languages should do it. But you have to be very careful when you are dealing with complex programming problems. Essentially, the “I” in “DWIM” is what you need to worry about. “I” is the person who wrote the code: whatever it looks like to them, that’s what it should do. And that explains my all-too-common position in Perl 6 arguments of “DWIM ONLY AT COMPILE TIME!”. At compile time, the decision about what to do is made based only on information the programmer has, so if it’s a good DWIMmer, it will make the same decision the programmer would have made. Don’t choose behavior based on what the runtime values are, since that can cause two different interpretations of what IM in the same lexical position, i.e. your DWIM thinks that the programmer meant two different things by the same line of code. While that is an interesting literary device, I don’t think I’ll face much resistance convincing you that that’s a bad thing in programming.

Keep in mind, this is neither a case against polymorphism nor is polymorphism (including multimethods) a case against this. I am a big fan of strongly-typed polymorphism, like C++’s and Java’s1. If you write a->add(b), you don’t have to know what exactly a is, but you do have to know whether it’s a number or whether it’s a set. The word “add” means pretty different things on numbers and sets, and the programmer should know which one he’s talking about. Thus, in order to call add, a must be declared as something that has an add method, say “Set”. Then when something derives from “Set” and defines its own “add”, it knows that it is talking about adding an object to a collection, not adding a number to another, so the programmer’s original intent by a->add(b) is preserved.

1C++ and Java were not examples of languages that got DWIM right, they were just the most common example of strongly typed polymorphism. C++ and Java both lack another very important feature of abstraction: the ability to ignore what isn’t important. Haskell, which I didn’t want to mention for fear of sounding like a zealot, has strongly typed polymorphism and the ability to ignore what isn’t important (called parametric polymorphism): it puts “What I Mean” in the naming of the methods; i.e. you can’t have add both mean adding numbers and adding to collections, their types would be incompatible. So you’d have to have add and addToCollection or something, which is why the programmer can leave out the types and still be perfectly clear about what he means. Dynamically typed languages like Perl and Python have the ability to ignore what isn’t important, but give up the ability to say exactly what you mean all the time. Some runtime data may come into your function one day and break it, by trying to add numbers when you meant add to a collection. The method case doesn’t break much, because good method naming and a little bit of argument arity checking will quickly find your problem for you when you run your test suite. Operators are a different story, though: if you overload operators too heavily (which is done at runtime in those languages), it can do the wrong thing and you won’t catch it until 1,000 lines later. That’s because operators have a fixed arity, and many object types will overload them, so where is it going to die?

Perforce Sucks

Okay, I’ve used CVS, I’ve used Subversion (command line, tortoise, svk), and I’ve just been introduced to Perforce here at NetDevil. And man, I have to say, perforce blows.

My coworker and I were trying to work on the same segment of code, separate from the trunk. So I did a little research and merged his branch into mine. Perforce died, saying I have to enable some option to do that. So I enabled the option and tried again. Perforce was obedient, and finished about 8 minutes later.

Then I looked at the changes it merged in, and they didn’t make any damn sense! It added the files that were new in his revision, but it didn’t change some of the files, and it changed some files that he didn’t change. I submitted the change before I realized this. So I set out to discover how to roll back a submitted changelist. A half hour of experimentation turned up nothing. And it’s no surprise: here are the instructions from perforce.com on how to do it:

  1. Sync to the revision before the one you are rolling back
  2. Mark the changed files in your changelist for editing
  3. Add empty files for each file you deleted in your changelist
  4. Sync to the revision that you are rolling back
  5. Resolve all files in the new changelist, choosing “accept yours”
  6. Sync to HEAD
  7. Auto-resolve all files in the new changelist
  8. Delete all files you added in the changelist you are rolling back
  9. Submit the new changelist

Are you kidding?. Okay, I have to say, the svn merge syntax for doing the same thing in subversion is a little strange and hard to remember, but holy crap! At least in subversion you don’t have to manually mark/add/delete each file you changed; it does all that for you.

Oh, I suppose I should mention that the procedure given above doesn’t work.

Another issue: I have been working here for less than a week, and I think I’ve lost about three hours of development time because perforce is so slow. I think it’s probably a little faster than subversion on checkout (that is, sync). But it’s way slower for everything else. Each operation takes at least 30 seconds, and several fairly common operations (creating a new branch) can take as long as 20 minutes.

Sword Gestures

It has been two weeks since I have done the slightest amount of work on the sword game. Kudos to Ben for keeping it moving along. Anyway, it’s time for some brainstorming.

Our current idea (as of last week) for a control scheme for the sword game is (1) to have it in slow motion for strategic, rather than strictly action, play, and (2) to control the sword based on gestures, of sorts. Not pre-programmed gestures like (ugh) Black and White; more like drawings of what you want the sword to do. Draw a Z and you’ll get a Zorro motion. I like this idea a lot, and I think it has a lot of potential. So, I have to tackle the problem of, given a gesture, how do you figure out what to do with the sword.

Well, we want it to be sort of vague and interpretive. We also want it to be natural, the way a human would interpret when given that gesture. These two things point me straight toward setting up descriptive equations, filling in known information, and solving for the rest of the details. But what kind of information does the gesture specify?

We know it starts about where the sword currently is when you draw the gesture, and it ends in the same direction as the end of the gesture. We can intuit velocities, but I think it’s better to let the equations figure those out. We also know a few points on the curve (as many as we need, really). We’re trying to solve for the force to exert at every step. Oh, and we know we have a maximum force we are allowed to exert, which should play a role in the solving process (so the solution doesn’t try to do anything impossible).

A Bezier-like spline might suffice. We are given a curve, i.e. a bunch of points, and we’re trying to find a smooth interpolant. Let’s look at what information we have at each point:

  • A 2D position at each point.
  • A 3D position and velocity at the first point.
  • (perhaps) A time at the last point.

y much information. And the information we need:

  • A 3D force for the handle at each point.
  • A 3D force for the tip at each point.

I’m making the assumption that we linearly interpolate the forces between each point, so the force half-way between two points is the average of the forces at each of the two points. So we have 6 unknowns. We need 6 equations (for each point).

How do we interpret the 2D data? I’m going to say for simplicity’s sake that we put a plane in front of the fighter and require that the sword pass through the corresponding point. This may be the weakest assumption of the algorithm. And there’s another problem with this approach: in order to compute that, we need the position and orientation of the sword at each point, another five unknowns in exchange for only two equations!

Hmm, as I hash this approach out, it seems to be breaking down. Maybe I should scrap and come from a different angle.

Busy Beaver Function

When we’re talking about game design, Namaste usually comes from the perspective that you can make a computer do anything. I’m usually of the perspective that there’s a lot of stuff that isn’t practical or isn’t possible to make a computer do (I’m usually too liberal in handing out this “impossibility” trait, though). There is a pragmatic reason for this difference of perspective: when I set out to solve a problem, I want the problem solved; that is, my algorithm will work in all cases and will always finish. But in game design, a lot of the time you don’t need to completely solve a problem for it to work. For example, in Minesweeper Infinity, when we were discussing how to approach the solver, Namaste kept coming up with the idea for a pattern recognition engine. Like, when you see 1,2,1 along a wall, you always know that there are mines under the two 1s, and not under the 2. The idea was that you could solve most boards by building up a collection of such patterns. But an algorithm that uses that approach has two output values: either “it’s solvable”, or “it might not be solvable”; but I was looking for an algorithm that would say either “it’s solvable” or “it’s not solvable”. I did eventually come up with my algorithm, but it degenerated into the “it might not be solvable” case again when we put a “bailout” parameter on it in order to make it run faster.

But I digress. What I really want to share with you today is the concept of the busy beaver function. This is a function which is perfectly well-defined as far as its semantics, but is impossible to write in a computer. We begin with the concept of a Turing machine, a concept with which most computer scientists are familiar. A quick refresher: a two-symbol turing machine has an infinitely long tape of bits on which it works. It has a set of states, and for each state it has an action for each symbol. That is, if it’s in state 4 and it is currently looking at a 1, it has instructions about what to do next. These instructions are simply which symbol to write on top of the 1 (could be a 0, or it could be a 1 again), then which direction to move the tape (one to the left or one to the right), then which state to go to next. If a turing machine ever goes into, say, state 0, then it stops running and says “I’m done”. The Church-Turing thesis states that this small amount of machinery is enough to compute anything that is possible to compute, and has yet to be disproven (all modern computers are equivalent to a finite turing machine).

The busy beaver function Σ(n) looks through all turing machines with n states (there are finitely many of them) and, of the ones that eventually stop running, picks the one with the largest number of 1s written on its tape. Σ(n) is the number of 1s. That’s pretty easy, right? I mean, once you played with a few turing machines, it seems like you would be able to “compute” the value of this function. In fact, we know some values of this function, namely Σ(2) = 4, Σ(3) = 6, Σ(4) = 13.

But you will never write a computer program that says “What value of Σ would you like to compute? “, then you enter a number, then it runs for some time (could be billions and billions of years) and says “here is the value you were looking for”. Even with unbounded time and memory, you cannot write such a program. (A complex proof is given on the Wikipedia page, followed by a very simple one in the last paragraph of the proof section; see the very simple one :-).

Even more interestingly, this function grows more quickly than any function you can compute. So not only can you not write a program which computes the function, you can’t even write one to compute an upper bound. For example, there is some n for which Σ(n) > n A(g64, g64) (do read some wikipedia aricles and try to grok the size of that exponent!).

Oh, I forgot to mention: nobody knows Σ(5) yet, but we know it is at least 4,098. Also, nobody knows Σ(6), but it is at least 10865 (now you see what I mean about it growing quickly?).