iGurgitate

It's been news recently that C is more widely used than Java again, and that seems to have caused folks to think more about C than usual. Over, at One Div Zero, James wrote a nice post about some of the ugly details of C related to portability. He pointed out that some patterns commonly used in "portable" C code would not be portable to certain implementations of the language, but those implementations are not in wide use.

Having had experience with C on one of these rare architectures (PDP10) which makes portability much harder than others, I left my 2 cents on the topic.

My perspective has become that it may be that those architectures became less desirable to use because of the fact that porting code (including all that sweet open source goodness) to them was more difficult than other architectures, adding delays to projects which were simply not there on architectures for which C programs were more portable.

I've recently been reading through Knuth's new "Art of Computer Programming" fascicle on bitwise tricks, and thoroughly enjoying myself. Especially in trying to hunt down information on the many side topics which Knuth alludes to in the text. For instance, the fact that really the only bitwise operator that had any historical interest to mathematicians was XOR; also known as the "nim sum", because of it's ability to give a winning solution to the game of nim. Nim is great, and I highly recommend the Wikipedia article about it, but in this post I'm going to talk about something else, related to something Knuth says about our understanding of the power of bitwise operations to generate complexity.

"A famous chain of operations known as 'Gosper's hack,' first published in 1972, opened people's eyes to the fact that a large number of useful nontrivial functions can be computed rapidly."

I've heard of Bill Gosper a few times before, mostly because he is responsible for writing the majority of the short articles that make up the body of work known as HAKMEM. A collection of hacks, tricks, and mathematical curiosities discovered by folks at MIT in late 60s/early 70s. I also have it on pretty good authority that many in that time and place jocularly referred to Gosper as the best 19th century mathematician living today. Most of the examples published in HAKMEM were coded in PDP10 assembly, but I can read a little of that so I set out to find the original source on the subject, Gosper's Display Hack, aka HAKMEM item 145.

Item 145 is one of the shorter items in HAKMEM so I will produce it here in it's entirety. Though the article in the context of other hacks can be found here.

ITEM 145 (Gosper):

0/      TLCA 1,1(1)
1/      see below
2/      ROT 1,9
3/      JRST 0

      CHANGE:         GOOD INITIAL CONTENTS OF 1:
        none            377767,,377767; 757777,,757757; etc.
        TLC 1,2(1)      373777,,0; 300000,,0
        TLC 1,3(1)      -2,,-2; -5,,-1; -6,,-1
        ROT 1,1         7,,7; A0000B,,A0000B
        ROTC 1,11       ;Can't use TLCA over data.
        AOJA 1,0

The Hack Deconstructed

Okay, this is about as simple as you can get. One key thing you need to be aware of is the PDP10 is a 36-bit architecture. That is, registers and words are 36-bits long. So when he's talking about using The rightmost pair of 9-bits as x and y coordinates for display he's talking about quarter words. So, if we attempt to do this on a standard architecture without any emulation it makes sense to use 8-bits of the word to represent our coordinates. This also means that our screen will be 256x256 instead of 512x512 as in the original hack, but this is actually a pretty good size for a little processing app.

With that in mind lets break down what each line does:

0/      TLCA 1,1(1)
1/      see below

 int i = INITIAL_VALUE; // Different values make different pictures
 i = i ^ ((i + 1) << 16);

2/      ROT 1,9
3/      JRST 0

loop:
 int i = INITIAL_VALUE;      // Different values make differnet pictures
 i = i ^ ((i + 1) << 16);
 i = (i<<8) | (i>>>(32-8));  // Sadly this is how we must rotate
 point(i&0xff, (i>>8)&0xff); // We want to plot this on the screen!
 goto loop;

That's it. This is basically the inner loop of our processing app. In reality since the draw() function is polled by the processing environment we dont need the loop explicitely we just put the code in the draw function. You can do a view source on this page to see the whole thing, there's a lot more there but most of it is to allow for the slide bar controls which reset the initial conditions of the loop.

As Gosper originally noted a great deal of complexity is generated from such a simple program. It's very reminiscent of 1-d cellular atomata. Since the PDP10 is a 36-bit machine the recommended initial conditions above don't map directly to the 32-bit case, so experiment with the scrollbars to control the initial values for the left and right half of our initial 32-bit word. The simplest interesting case I've found is 0 0 (Drag both sliders all the way to the left). That one creates some patterns reminiscent of rule 90, and if you let it run long enough it takes on some interesting fractal like properties. A friend of mine, @hallsa also noticed that 7fff 4797 makes some interesting patterns with totally different characteristics. The slider bars may not be as fine grained as one might like, so I may add some keyboard input controls to allow for tweaking of the initial conditions by increments as fine as 1. Have fun!

So I checked out some of the references at the end of Malcom Gladwell's The Tipping Point. Mostly because Gladwell's books always leave me feeling enthusiastic about their ideas, but with the desire to put my hands on something concrete. I became interested in work by Schelling on peoples self segregation. It wasn't so much that the model was surprising from a sociological or mathematical standpoint, but because it represented a pretty simple idea which could be applied to Processing. :-)

So, here it is: more art than science, my processing app which represents a world of households who are just looking for a place to land. They definitely prefer living near each other rather than in isolation. However, if the neighbors are too different from them they will definitely be looking for a better place to live. You can adjust the tolerance of the people that live in the world. See what happens if they become very tolerant quickly vs. slowly, or what the effect of slowly reducing tolerance for a very stable world is. Can you find the tipping point at which order starts to form from chaos?

In the latest version of Dr. Dobbs (January 2006) Guy Steele Jr. has an article named, "Thoughts on Language Design." In summary he seems to be saying, that language design is driven by context more than we realize. That is, for all the ideals that exist in the language design community, the things that are held as most important often are quashed in the face of the facts of the environments in which we program.

In the early paragraphs he gives the example of how the '*' character has come to represent multiply mostly because on the early IBM punchcard machines, lacked standard mathematical symbols other than '+' and '-'. This statement early in the article then set's up the question , "What if a numerical programming language actually looked like the stuff that mathematicians and physicists use on their blackboards?" Yes, what if? Does unicode present a context in which programming can gain productivity? From Steeles own examples I think we can glean the hint of an answer. Until, there is a dramatic shift in the way we enter text into our computers, No. While a special user interface designed for scientists and engineers may provide gains in productivity and expressivness for a few scientists and engineers, how can we overcome the cultural fixed point that is the qwerty keyboard? Unicode alone does not provide the context for the leap to unicode editing of our programming languages.

Some of the more interesting parts of the short article are the personal tidbits that Steele discloses about how his early exposure to the GOTO debate (at age 17!) lead to the first lambda paper ("Lambda the Ultimate Goto"). He even gives us a passage from his public comments at debate whose existence alone is intersting. Also are his comments that he still mostly agrees with his 17 year old self, and his admittance that he now feels the titles of his papers slightly pretentious. Outside of its historical worth, steele uses the ideas of the goto debate and the lambda papers to back up his argument of the importance of context in choosing language features. He argues that his work on turning function calls into branches was important, as was the introduction of structured programming (if-else, do-while) over the use of goto, but architectures have changed and what we have to do now is to find the ideas that are important to add to programming languages now; not just the step of adding multithreading support to a language, but what about a language who does not think in a single threaded way by default, whose structured components are not for loops (which force a single threadedness on us) but something else. Yes, maybe its parallel counterpart can be called the semi-for :-).