The future of user interfaces

Smashingmagazine offers a good summary of future user interfaces.

Blog-o-pictures

I found this blog thanks to this entry about Russian retro-futuristic art.

But truth be told, I prefer some older posts even better.



Also, one about Buran, the ill-fated russian space shuttle...

Funny science quote of the day

I found this piece funny, in particular:

[Funding a particle accelerator is] not a trivial sum of money for a lot of people, but it's a drop in the bucket compared to the $1,500 per head price tag of the Iraq war to date. And building a particle accelerator doesn't require waterboarding anybody.

(Well, strictly speaking, neither does the Iraq war, and I can't say with certainty what might happen if Alberto Gonzales were put in charge of ILC construction...)

and

this kind of ultra-hot, ultra-dense stupidity can only be achieved by colliding at least two forms of idiocy at speeds approaching that of light

Concept Programming Redux

Based on feedback from many people (most notably Daveed Vandevoorde and Lionel Schaffhauser), I posted a new presentation about Concept Programming. This should make the ideas much easier to grasp.

During the discussion, Daveed Vandevoorde pointed me to a very interesting paper about memory transactional models, which he used as an argument in favor of functional programming. Recommended reading, even if I don't think that this is a point for functional programming at all myself (what is really being used is the very strong type system of Haskell).

Lionel Schaffhauser pointed out a number of presentation-related issues, which prompted me to change the order of the slides and add a whole section about the "Maximum" example.

As a reminder, there is also an older presentation about XL itself.

See announcement on the XL web site

Airbus construction

You may recently have heard that an Airbus A340 was recently damaged during ground testing. Well, it's surprising this does not happen more often. Below is a video showing just how complex the construction of an A340 is:

E8 theory...

Garett Lisi recently posted An Exceptionally Simple Theory of Everything on ArXiv. Don't expect the article to really be "exceptionally simple", the title is really a pun on the fact that E8 is the largest exceptional simple Lie group. There's nothing really simple about all this, except that it's a beautiful form of symmetry.

This work was quickly picked up all over the place, for example at Backreaction, where a good discussion followed. It even made it to Slashdot, where whatever discussion was typical Slashdot ("it's funny, laugh!" :-). Not useful, but entertaining.

Unfortunately, it also made it to less reputable science outlets. My favorite blogger made predictable comments about it being stupidly wrong, rejoicing in an arXiv demotion from hep-th ("professional") to gen-ph ("laymen's fantasies"):

Update I: the preprint was re-classified from the professional hep-th archive to gen-ph, general physics, an archive mostly dedicated to laymen's fantasies. Thanks God. Comment for general readers: this preprint is of course not peer-reviewed and probably won't get published anywhere.

That demotion may very well be Motl's own fantasy, as the preprint still appears as hep-th for me. In any case, you can compare Lubos' "professional" piece of work to, say, John Baez's reaction to the exact same event. True, Baez also shows some skepticisim, which I will share for the moment, but he remains healthily neutral, whereas Motl "exploded in laughter" at the first equation in the paper. More importantly, Baez, unlike Motl, starts looking at similar work, like earlier attempts at unifying forces using SU(5). That's the right way to go. Even if the paper is totally bogus (which I don't think it is, more likely to be subtly bogus), you still have to prove it, which Lubos Motl spectacularly failed to do as usual.

So... Why be skeptical? Simply because that's not the first time folks look at E8, and even if Garrett Lisi's approach is innovative, it may still very well be entirely wrong, until experiments show the predicted additional particles. But at least, Garrett is ready to take that risk, and that's worth a lot in my book. And, if nothing else, he provided us with a very beautiful video:

So at this time, what I find a source of concern is not Garrett's article itself, it's all the publicity around it. Early publicity for something as "grandiose" as a "theory of everything" can prove fatal to the researcher if he turns out to be wrong, or to not make as much progress as expected. That's in no small part what happened to Laurent Nottale. And just like for Nottale, that would be a shame if Garrett Lisi ended up doing nothing more than surfing in Hawaii...

And I also believe that Garrett Lisi's work is absolutely not in conflict with my own ideas, nor any step in that direction. In other words, the paper I submitted still shows, in my opinion, just how far Garrett's work is from a "theory of everything".

The other side

Funny that I should, twice in the same day, read a story about what the other side has to say about one of Richard Stallman's many gripes:

• The first one is Rob Pike's recollection of a protest against one of his software patents.
• The other is Dan Weinreb's rebuttal of Stallman's story on Symbolics and LMI.

Selling: From complex to simple

An interesting thought from a friend of mine over lunch a couple of days ago (that's my rewrite, so errors are mine).

Hi-tech companies start with the complex, high value add, because it means high differentiation. That's where engineers shine. But as their market expands, marketing becomes more and more important. And marketing hates complexity, because it's hard to sell. So as the company grows, it natually swings towards commodity markets, not because they bring more money, but because they are simpler to sell.

Simple. Right, or wrong?

Growing a language

I recently re-discovered an excellent paper I had not read in a long time, Growing a languag by Guy Steele. Highly recommended.

Concept Programming presentation posted

I finally posted a slideset about concept programming that had been rotting on my hard disk for way too long... (also posted here.) This gave me an opportunity to re-read older articles on these topics, one I had written for Dr Dobb's Journal, and another one written by Martin Heller (Mr. Computer Language Person) for Byte. They are still pretty accurate.

What is concept programming?

Concept programming is a new programming paradigm which is intended to reduce the gap between the concepts in your brain and their representation in computer code. The method is detailed in the slides, so I won't repeat it here. There is also a very simplistic overview at Wikipedia.

These techniques apply to many programming languages. I used them personally for assembly language in HP Integrity VM. But just like you can do object-oriented programming more easily in C++ than in C, it's easier to use a language designed specifically for it. The slides also give a few examples of how the concept programming philosophy impacted the XL language design.

Making Things Happen - Getting Help

Concept programming has a pretty long history. I'm not sure when I invented the term exactly, but I'd say before 2003 (I'm pretty sure it was explicit on the "new" XL web site). But this is too valuable to be left dormant like this. I would so much like to spend more time on it, but... too... many... things... at once.

This is the reason I am trying to get some help getting this stuff done. It actually proves difficult. You would think this is easy: the ideas are pretty clear and easily explained, a lot of code is already available. So what's the problem? The problem is getting people to listen at all, just like in that story of that world-class musician posing as a street musician. If you don't remember the results: practically nobody listened to him.

Well, just like that musician, concept programming and XL will require more than talent and technique. They are now in need of some kind of advertising, evangelism, call it what you want. If you think that you can help promoting these simple ideas about programming, let me know...

The dawn of 3D games...

I was recently drawn to look back at my first paid programming job, Alpha Waves, which apparently may also have been the first 3D platform game.

Others writing about this game after more than 15 years helped me realize that my recollection of that time might be an interesting bit of computer history worth sharing (If you don't care about such old geezer's stuff, skip that article!) Some of it is documented elsewhere. Some of it may well never have been written before.

Anyway, this is the kind of story that might interest my kids, if only them...

Update: One of my kids, reading the article, asked me why I had been calling Alpha Waves "the first real 3D game", since Starglider 2 had been released more than one year earlier. And it's true that the static screen snapshots below don't do justice to the difference between the state of the art at the time and what Alpha Waves brought to the gaming experience. It's only watching a video of Starglider 2 that my son realized how bad 3D was back then. Videos convey the point much better than words or static pictures:

Starglider 2

Alpha Waves

By the way, Google video really rocks!

Inspiration: Starglider 2

One thing I remember is my inspiration for writing Alpha Waves. It all started with a game called Starglider 2, which for the first time on Atari ST and Amiga (and in microcomputer history, for all I know¹), featured somewhat realistic 3D graphics. What made them realistic was that for the first time, this game showed animated flat-shaded graphics. Earlier games like the original Starglider only drew lines. Hiding the lines for back-facing polygons was considered highly advanced stuff. So flat-shaded polygons? That was almost surreal.

My first reaction when seeing Starglider 2 was: "Wow!" My second reaction was: "How do they do that?". Finally, this would turn into: "Can I beat that?". As you can see on the picture, Starglider 2 displayed 3D graphics in a small region of the screen, and only a small number of objects were visible at once. So the next steps, obviously, were to see how large of a screen region you could use for 3D graphics, and how many objects you could draw at the same time.

Today's 3D graphics are generated by hardware capable of filling petagazillions of pixels per second, so young readers may not realize that the memory bandwidth at the time made the simple task of filling the screen with polygons more than a few times per second a challenge in itself. Starglider 2 was smooth!... which, at the time, did not mean 60fps like today, more like 10-15 when the screen got crowded. Remember, this was the time where the boink demo was considered extremely cool.

In summary, doing better than Starglider meant something like filling two thirds of the screen, having 15 objects on screen instead of 4, and remaining above 10 frames per second. Ultimately, Alpha Waves would far exceed this initial objective: full screen, not a single bitmap sprite on screen (even the player was drawn in 3D), and sometimes as many as 50 objects on screen. The Atari ST even ended up with a dual-player mode where two players would compete on screen simultaneously (a feature that never made it to the PC version).

Elaborating 3D algorithms

Obviously, to best Starglider, I had to first understand how one would draw 3D graphics on screen. I quickly rediscovered the mathematical formulas, but they were only the beginning. The real question was how to do it fast. Again, to understand the problem, you have to remember that we are talking about a time where the Motorola 68000 used in the Atari ST and Amiga was considered a relatively fast processor. This processor not only had no built-in floating point capability, it was actually very expensive to do a multiplication! So I ended up reformulating the problem as: "How can I draw 3D using mostly additions?."

The solution would seem extraordinarily obsolete today. The code pre-computed displacement along the X, Y or Z axis, so that it could rotate these vectors only once, and then describe all objects using an encoding that looked like: "go one step right, then two steps up, then one step back". Each individual step was recorded in a temporary array, and then the final 3D object was created by connecting some of these recorded points. Again, this may seem like a very silly algorithm when, today, 3D routinely uses things like quaternions to compute coordinate transforms. But boy! was it fast!

Of course, there were a few other tricks along the way. For example, without floating-point capabilities there was obviously no way to compute a cosine. This was easily solved by storing a pre-computed sine/cosine tables returning integer amplitudes (-32767..32767). That made it possible to use another micro-optimization. On the 68000, the multiplication operation took two 16-bit arguments and returned a 32-bit value. Multiply a 16-bit signed coordinate by a 16-bit signed amplitude gave me a 32-bit signed coordinate. Anybody today would shift that down to obtain a 16-bit value, but the 68000 had no barrel shifter, which meant that shifting down would have been expensive. On the other hand, it had a swap instruction exchanging the high and low 16-bit parts of a 32-bit register. So after applying swap to the result of the multiplication, I was getting a 14-bit coordinate.

Drawing polygons

The problem of coordinate transforms being solved, the next most difficult problem was drawing polygons quickly on screen. This involved a number of steps: clipping, decomposing the result in a number of triangles and trapezoids, and drawing each piece. The details of the kind of techniques used are now well known, and illustrated here (see figure 9.6 in that article).

My original polygon drawing algorithm was already relatively fast, but the Infogrames folks later insisted that I use their in-house routines to facilitate the porting to Amiga (where they had these routines already available). They had at least a couple of people dedicated to the in-house library of graphics routines on a variety of machines, and they were slowly switching to C for the high-level game architecture, using C a little bit like we use scripting languages today, for the slow stuff. And honestly, the Atari ST version of their polygon routine was a little bit faster than mine, using self-modifying code to optimize the inner loop as it ran.

Well, that optimization made it incompatible with the new and amazing 68020-based Atari TT (because you needed to tell the instruction-side of the processor to re-fetch the data you had just written on the data side, which that code did not do). Being pretty annoyed at the 2% difference between their code and mine, I created a best-of-breed combined routine using an assembler variant of Duff's device, which if my memory is correct, bested their code quite handily, and also ran on the Atari TT. But that all happened much later, when we were in the final phase of the game development.

From polygons to worlds

Earlier stages of the development of Alpha Waves were much more modest. I was only starting to be able to draw and rotate simple 3D objects. It began with a big cube showing the limits of the 16-bit coordinate space, the limits of my "world". Then, inside that cube, I placed another one, and one more to test how objects were hiding one another, and so on.

Soon, I had something like a dozen cubes floating in space. And more, and more. And that's when it slowly became clear that I was close to achieving my original dream. This was definitely faster than Starglider. Even with all these objects drawn on screen, on the entire screen no less, this was still smooth. I was thrilled, I was proud! This may seem ridiculous when today anybody can run Second Life and access some 24 terabytes of stored world information, but at the time, this was world-class 3D graphics.

But all things considered, rotating cubes on a screen gets pretty boring pretty fast. So to test my graphic routines, I started exploring ways to move inside my little 3D worlds. The first one was the most obvious possible: some kind of flight simulator that would let you fly through the world. You'd turn left and right or up and down with the joystick, and move forward by firing the joystick. That allowed me to test all possible rotation angles. To avoid the bugs when coordinates exceeded the 16-bit space, I added code that would keep me inside the coordinates cube. It was as if you bounced on the walls, on the ceiling or on the floor.

Believe it or not, I thought it was fun to bounce against the walls, and started testing all kinds of funny dynamics. The next obvious step was to bounce against the cubes inside the world instead of flying right through them as was then the de-facto industry standard... The cubes acted like big repellers, and so bouncing off one would allow you to quickly accelerate, for instance to climb to the top of the world. Add a little gravity, some platforms on the floor to start bouncing when you fell, and Alpha Waves was born!

In my mind, I was sort of recreating the experience of being a smurf, which in the comics bounce from the floor to reach a table, and so on. And I was starting to think that I might build some kind of smurf-based adventure game around that graphics technology. To that end, I started creating a little mechanism to switch from one "room" of the game to the next, through "doors" located on the walls. The trick was to reach the door, and you would switch to the next room. This way, I could explore an even larger world.

I was certainly starting to see some game potential in my code, but I was still not considering that little toy demo as a game, more like the foundation for what might one day be a real great adventure game in 3D. Sure, I had a lot of fun bouncing around, but who else would find this funny?

I couldn't have been more wrong!

Alpha Waves, meet Infogrames

I understood that when I presented this code to Infogrames. At the time, this was still a pretty small company occupying a single floor of a building in Villeurbanne. I don't know how large it was, but I would guess about 20-30 people. Still, this new building was already a giant step up compared to the office I had visited one year earlier, during my first interaction with them. And I need to explain that the first interaction was the reason I was getting back to Infogrames.

The first time, I had been looking for a student job, and they were looking for someone to translate some book about expert systems. Don't ask me why. I think that Bruno Bonnell thought at the time it was a good idea to diversify the company into "serious stuff" like artificial intelligence and some kind of expert system software for mom and pop. No kidding! These were wild times...

In any case, I did the required job, but when came time to be paid... they had already figured out that expert systems were a totally crazy idea and changed their mind. So they did not need my work any more, and in that case, why pay for it? Guess what, when you are aged less than 20, you are pretty naive, you tend to trust folks. In short, there was no written contract, just a gentlemen's agreement that they all too happily broke. I did not get a dime.

So one year or so later, when I returned to them, it was primarily with the intent to make up for that loss by working as an intern for one month, doing little and learning a lot from them. Why did I think this was a good idea? I don't know. I just wanted them to pay me something I guess.

Hey! This is a game!

Anyway, to convince them to hire me during the summer months, I had prepared a sort of career portfolio with various tiny programs. These were a number of half-baked experiments with various technologies like 2D scrolling, sound, text display, and so on. Not a single of these programs was a real game, but my point was more to show that I could write code.

The piece of code I thought would impress them the most was some sort of small clone of Time Bandit, with a few additional features like proportional text being displayed on screen, that was looking so much nicer than the typical fixed font of the time... There was not much of a plot, only a few worlds, but I thought this demonstrated I knew enough about game coding for a summer intern job. Well, when I showed that code, Infograme's technical director essentially yawned. I was seeing the chance of getting my money back escape...

Disappointed, I took the last floppy in my pile. This was the one containing the "Cube" demo. But if my marvelous Time Bandit clone had failed to impress them, this would would definitely be a total flop as well. Anyway, I started it up, gave the joystick to the technical director... and one hour later, he was still holding it, bouncing left and right like crazy! In my memory, he looked every bit like the guy on the picture, fascinated by this new and strange kind of game...

When he finally left the room, the technical director quickly came back with a contract that essentially read: Christophe de Dinechin will be paid 5000F (less than $1000) for a two months intern job working on Infograme's "Project Cube". Well, fool me once, shame on you, fool me twice... My answer was quick: no way, that game is not an Infograme project, it's almost finished (something I had realized only minutes earlier), if you want it, this will be a royalties-based contract. He replied, "This is a standard contract, just sign it, we will adjust it later." Fortunately, I had previous experience with this kind of "contract", so I steadfastly refused to sign anything.

Frederick Raynal

After that, things moved relatively fast. Negotiating royalties was a real pain for me, and according to him, a pleasure for Bruno Bonnell. He commented something along the lines of "all these guys tell me that they don't need much... Well, that's what they get!". I fought for a royalties rate that I thought was decent. In the end, I was very disappointed when I left the room with, if my memory serves me right, something like 17%. I shared my disappointment with the engineers around. I remember a silence. And then, I was told that this was actually the best rate Infogrames had ever conceded to an independent author.

I do not recall how Frederick Raynal got involved exactly, but what I do recall is that he looked at the code, and told his management he felt this code could be ported to the PC. This was against Infogrames' policy at the time, which was to never port an assembly language game to a different CPU. Frederick argued that my code contained comments all over the place that made it very clear what was happening. And so he ported it to the PC. He actually did more than port it. The PC version included, for example, a very nice tutorial showing how to use the game which did not exist in my original version. The only thing he failed to do is accounting for different CPU speeds, and so Alpha Waves is practically unplayable on today's machines without slowing it down quite a bit. Update: I had him read this blog, since I'm talking about him, and he commented that it was the last time he made this mistake :-)

More than anything, Frederick is a really nice guy, and we still exchange email every other year. As history would record, he would go on creating Alone in the Dark, a game that was extraordinarily successful, and then many other very successful games. Alone in the Dark used 3D graphics for characters, a first in the industry. Frederick has said that this use of 3D was a consequence of his earlier work on Alpha Waves.

Aftermath

The rest of the story is, unfortunately, consistent with Infogrames earlier behavior regarding payments. I had every trouble in the world getting them to pay the royalties as scheduled in the contract. For a short while, I considered reusing my game engine for the Smurf-style adventure game. But after several late payment notices, I got fed up of Infogrames and gave up gaming for good. Apparently, Frederick Raynal had similar issues after the success of Alone in the Dark.

This is my personal experience of the early days of the gaming industry, and the very beginning of 3D in videogames. It was wild, it was fun!. Thanks to Alpha Waves and my urge to beat Starglider, I got to meet a few people who are living legends today, and to see the early days of the company that later bough american icon Atari.

If you have any stories about this period, I'd love to hear them. Please leave them in the comments area.

---

¹Update: Well, it turns out I did not know much. Actually, the MS-DOS port of Elite also had flat-shaded graphics, unlike the hidden-line graphics of earlier versions. Like Starglider 2, however, the 3D experience was lacking.

Update: I also discovered that the id Software web site claims that Hovertank was the first 3D game on the PC. Obviously, they are wrong: Alpha Waves predates it by one year, and it offered a better 3D experience.

Je suis jeune, il est vrai ; mais aux âmes bien nées
La valeur n'attend point le nombre des années.
Pierre Corneille, Le Cid

Group Dynamics

As usual, each time I venture around Backreaction, I find something interesting to read. This time, it's Bee's musing about group dynamics. She states that in every group, there is a soul, a brain, a heart and an asshole. They are not necessarily separate people, sometimes one person may combine two or more functions.

As usual with any classification, you often find the limits. I believe that Bee is mostly referring to groups in movies or books, to the kind of dynamics that makes a plot interesting. But even then, you often find other parallel classifications, for instance hero + heart + comic relief, or good + bad + ugly, and so on...

Application to programming teams

In programming teams, I think that the same kind of classification applies. It is not necessarily exactly the same pattern, however. In most programming teams, for instance, you don't care much about having a heart. You do care about having a soul and a brain. And generally, you also need a "benevolent dictator", or maybe a "general", i.e. someone who thinks about the organization of the project. I don't want to call this person a "manager", because in my experience, it is very rarely a manager doing that job.

The relevant observation Bee makes is that, in general, you don't need more than these few people. A plot with 20 all-equal people is not generally much worse than a plot with 4 main characters. Similarly, programming teams are most efficient when they are small and focused. As soon as the team grows, you need a clear hierarchical organization, so that each subteam remains around 5 people. Equalitarian programming teams rarely work efficiently. In general, the hierarchy establishes itself based on historical and productivity precedence, as illustrated by many open-source teams, most notably the Linux kernel team.

It seems to be a pretty general rule. If you look at the large companies, they were usually created by a very small group of complementary people (I made random guesses for the role attribution):

• Steve Jobs (soul), Steve Wozniak (brain), Mike Markkula (general) for Apple
• Bill Gates (soul), Paul Allen (brain), Steve Ballmer (general) for Microsoft
• Scott McNealy (soul), Bill Joy (brain), Vinod Koshla (general) for Sun Microsystems

Self-evidently ludicrous ways to teach programming...

As usual, Geekstorming nails it right on the head:

This introductory comp sci course teaches Java. Java, as you probably know, is a language in which the canonical "Hello, world!" program takes seven lines of code and requires you to invoke the following concepts:

• Classes
• Static methods
• Command-line arguments
• Visibility

None of which, you may notice, have anything to do with writing "Hello, world!" on the screen.

Yes, this is self-evidently ludicrous! That kind of problem is one of the very reasons behind concept programming. The way we teach programming today relies on a serious cognitive dissonance between the concepts that would be natural to use and the one you actually have to use. Hopefully, XL is a step in the right direction.

But really, it seems like we always find a way to teach things in a complicated way.