Embaressignly Parallel : Amstrong, Ch 2

To oversimplify, there are two primary approaches to software concurrency: lock-based and message-based.

Lock-based concurrency is done primarily to separate out listener threads, and to enhance program performance.  Multiple threads can (and generally) do share access to some data, which is protected by locks.  Though this mechanism is mathematically reliable, in practice, implementation can be very tricky, and all sorts of bugs can arise out of it.

Message-based concurrency has a different focus: it utilizes parallelism chiefly for program reliability.  Each thread exists as independent tasks, sharing no memory and communicating only through asynchronous messages.  Though this approach can have performance drawbacks (particularly if much data needs to be passed back and forth), it is a simpler abstraction to work with, and is probably more conducive to generating stable programs, since program errors can be easily encapsulated within a single errant thread.  Importantly, a well-organized, hierarchical ordering of task parallelism can scale far more easily; not only can threads easily run distributed across multiple machines, but a hundred-fold increase in thread count requires no extra concurrency organization, simply more processing power.

Joe Armstrong uses the term "Concurrency-Oriented Programming" to describe the design approach centering around large, message-based programs.  This methodology involves identifying a program's tasks, outlining their interdependence, defining their message exchange, and then coding a direct translation of this task organization.  So, how well does this approach work?

To find these answers, I traveled to 2035, to sneak an interview with AMD Lead Compiler Developer Roto Mitsumi.

Kurt: Mr. Mitsumi, back in 2009, we're still figuring out an idea scheme to parallelize our software.  Can you provide us any insight into approaches we should consider?
Mitsumi: It is with great honor that I am to speak to your time.  I am most humbled to have the opportunity to discuss my experience on behalf of my benevolent employer, AMD.  It is--
Kurt: Mr. Mitsumi.  Please, our time is limited.
Mitsumi: My sincerest apologies.  If only we could parallelize this interview.
Kurt: Yes, ha.  Ha.  Very good.  Please.
Mitsumi: The first thing one must bear in mind is the reason we want to parallelize programs in the first place.  Form must follow function.  A program must be a suitable abstraction of its executing hardware.  So, as chips become parallelized, so must programs.
Kurt: Yes, that's where we are now.
Mitsumi: But if I am recalling correctly, that's not entirely where you are.  Because you have CPUs with multiple identical cores.  This does not last for long.  The average mid-range AMD CPU released now has over 1000 cores, of many varieties.  There are a few dozen dedicated vector cores, a few hundred cellular automata processors, a few hundred x256 cores, and many, many different optimized RISC processors.
Kurt: So, how does this affect design?
Mitsumi: Well, a programmer cannot possibly be aware of the precise system configuration, or even the type of processors available.  He must be able to code in a fashion independent of the underlying instructions.  To do this, the relationships between threads must be very explicitly defined.
Kurt: Are you describing a message-passing system of concurrency?
Mitsumi: Yes and no.  In a traditional message-passing system, the programmer himself must define the communication.  The structure emerges from the messages.  This can become unmaintainable when one begins spinning off a few hundred threads.  Refactoring can be profoundly challenging.  Instead, we take a different approach: one still maintains the independence of threads, but instead works with the data, a much simpler abstraction to refactor around.
Kurt: Isn't that the opposite of a message passing system.  So where do the messages come in?
Mitsumi: It depends on where you are looking.  When the code is compiled, all messages are automatically generated from the data access.  When executing, no data is actually directly shared by the threads: it is still passed by messages, but the messages are automatically generated.  All a developer must do is hierarchically define a data structure, and evaluate the resulting message structure for deficiencies, performance bottlenecks.
Kurt: So, a developer can still think in objects, even while his code executes as messages?
Mitsumi: Your language is technically incorrect, but the idea is right.  Most modern processors try to prioritize interprocessor message passing over shared memory access.  The more cores you have, the less efficient it is to access shared memory, and we're at a point where such a system would be an unfathomable bottleneck.  Because of this, the vast majority of modern computers distribute memory across the motherboard.  Message-passing is how nearly all non-quantum machines will proceed.
Kurt: Interesting.  I'll be curious to see this unfold in the next few decades.

There you have it.  Message passing does come with its own limitations and complexities, but it is scalable, and the advantage of that cannot be underestimated as our hardware evolves.  Any technique that will last in this domain must be able to cope with complexity an order of magnitude higher than most programmers currently address.

GRUMPS Design: Preventing Time Paradoxes with CHESS

An integral part of current GRUMPS design was finding ways to detect and avoid potential time paradoxes.  On my first outing, I attempted to assassinate Hitler, setting off a wild cascade of unpredictable events: I postponed the invention of the transistor, changed the country my grandfather settled in, and popularized disco three decades too early.  Things progressed so wildly until damn-near the whole universe crashed.  Were it not for the last-minute interference of some vastly more experienced time travelers, the end result could have been truly disastrous.

It is of key importance to ensure the operational consistency of a system, particularly in parallel or chaotic domains.  Potential race conditions, deadlocks, and death-of-your-grandfather-prior-to-your-birth scenarios may remain unseen for years after a system is deployed.  Predicting, identifying, and repeating these unstable scenarios is necessary for system-wide stability.

But how does one test for these kinds of conditions?  Optimally, one will explore as many scenarios as possible, emphasizing the ones likely to produce errors.  The "small-scope hypothesis" speculates that the majority of problems can be discovered by simple tests--that problems arise from the breadth of possible scenarios, rather than the depth.  You could theoretically describe any software as a superbly complex state-machine, with state transitions described not only based on user input, but environmental factors like thread interrupts.

If one could construct such an elaborate tree (even for just a few seconds of potential behavior) then the small-scope hypothesis could be objectively tested by performing Djikstra's algorithm on the starting state, and using that to calculate the average number of state transitions before an error occurs.  In all likelihood, most bugs can arise from a simple, but highly-particular thread interweaving.

In the field of Time Travelology, this kind of metric is discussed most frequently in chaos theory: how does a slight perturbation at a moment in time cascade into the future?  Because most errors are small-scope (that is, the instability begins soon after the interruption), I have found it imperative to clean up these unstable branches immediately after creation.

For assistance, I use a highly modified version of the CHESS model checker.  GRUMPS will create a small bubble of unstable space-time, performing a quantum simulation of a vast array of possible short-term futures.  (As a fascinating aside, note that a quantum simulation is, for all practical purposes, an actual progression of reality... quantum simulation is indistinguishable from reality itself).  CHESS' interleaving algorithm is utilized to scope these futures, quickly pinpointing unstable ones.  Once the stablest one is identified, the quantum superposition collapses, the unstable states are thrown into the universe's dustbin, and I leave as if I had never come, my only disturbances insubstantial on a large scale.

Complex systems are inherently chaotic.  We can attempt to control this chaos (say, by stress testing), or we can attempt to manipulate it into its unstablest forms (by controlling thread interleaving).  From experience, I'll have you know that the latter tends to be vastly more reliable, having saved my programs and the very consistency of space-time on a number of occasions.  Otherwise, you might still be a slave to Xuth!a, the bionic emperor-god who rose to power when I once accidentally spilled the beans about 23rd century biotech to a certain Henry Kissinger.

Lewis Carrol: Refactoring for Reentrancy

For years, functional programmers beg the world to see the glory that is reentrant functions: methods that will execute the same every time they are run.  The world ignores them for decades, and only now is finding out that they weren't just crying wolf.

Reentrant programs have a number of advantages: they are easier to test and analyze; automated tools can ensure some types functional correctness, instead of mere syntactic accuracy; but in particular, they are guaranteed not to result in thread conflicts since they only utilize local and passed variables.

Danny Dig's Refactoring for Reentrancy is a program designed to analyze and modify code to bring it back to the functional utopia of reentrance.  By converting static variables into local ones and flagging access to global variables or libraries, programmers can more easily ensure the thread-safety of their programs.

The things the Reentrancer can do are interesting, but the things it can't do I find even more interesting.  Namely, it has no way to assure the reentrant qualities of library calls, and can only infer it by comparing log files.  This reveals an interesting limitation of Java I had not previously considered: you can declare Java methods as static, forcing them to utilize only static variables, but you can't do the opposite; you can't declare Java methods as reentrant, forcing them to utilize only local and passed parameters.  The synchronized keyword can simplify the creation of reentrant methods, but it cannot guarantee it.  It seems that this would be a useful addition to the Java language, particularly help clarifying certain attributes of library calls.

Functional programmers would argue that its almost nonsensical for a function to behave inconsistently, depending upon a global state.  For some insight, I returned to 1890 for a brief conversation with master of logic and nonsense: Lewis Carrol.

Kurt: Mr. Carrol, when do you think it's appropriate for a logical function to return different answers?
Carrol: Well, a close friend of mine once faced this dilemma:

And on mid-summer mornings, she'd slip back in the hole,
To see what the darkness could lend,
But each interaction left her clarity dulled,
Since the liars all claimed they were friends.

And the truth-tellers told her the truth time-to-time,
And at other points offered a joke.
But she never could tell which was which in their rhyme,
Since all of them laughed when they spoke.

Each time they would offer the same foreign names,
And spoke in the same awkward voices.
But it never was clear if their stories were games,
Since each time they would make different choices:

Was it blue he preferred?  No, this time it was red,
Though Alice had asked the same question.
She never was sure why the Cheshire said
"You must make your discourse reentrant."

Frank Lloyd Wright: Rereading the Classics

Kurt: Hey, Frank Lloyd Wright?
Wright: Oh no.  Not you again.
Kurt: No, no, this is just a courtesy call.
Wright: What kind of courtesy?
Kurt: I'm just letting you know that more people are complaining about Fallingwater.
Wright: What!?  How is that courteous?
Kurt: I'm just saying, maybe you should have taken a more modular approach.
Wright: What does that even mean?  If I ever live long enough to find you--
Kurt: Oh.  You won't.

Man, I love time traveling.

Three, largely unrelated points brought to mind by a recent paper Rereading the Classics, by  Panagiotis Louridas:

Why do people consider weak typing an advantage?
Yes, it will save you the laborious effort of declaring a variable type, yes, it will save you  the effort of having to declare classes or interfaces for polymorphism.  But neither of these  are particularly time-consuming or challenging processes.  The effort you save by not generating  an interface is far overshadowed by the challenge you will have later trying to decipher your  code.

What is a function taking?  Can I get a list of types I can pass in?  With strong typing, you  can.  With duck typing, you're in trouble.  Java got this one right.  Interfaces are  lightweight, flexible tools to address polymorphism.  If you disagree, then I suspect that you  don't know how to use interfaces properly.

Why is there a distinction between "classic" languages and "pragmatic" ones?
An interesting distinction is brought up between those uncompromising, yet broadly influencial  languages that never take off in industry (Lisp, Smalltalk), and those more-compromising  languages that eventually do (Java).

It casts a spotlight on the question: when is compromise acceptable in a language (or  architecture)?  Consistency and simplicity are generally optimal: they give a developer a  clearer understanding of how to work within the environment.

One of my favorite features in Smalltalk is the way in which it sidestepped the performance  penalties of a strictly object-oriented framework: even though all operations are defined as  smalltalk code, functions may also defer to optimized assembly commands, substantially speeding  up things like arithmetic.  However, if a developer wished to modify any of these functions, he  can still modify the Smalltalk code, ignoring the assembly optimization.  This was one of the  few structural compromises in the language, and it was a very powerful one.

What made Java more widely adopted than Smalltalk in industry?  There's a host of non-technical  reasons (the backing of Sun, good timing), and many technical ones (simplified deployment over  the web through [much-derided] applets, in-order arithmetic expressions, the ability to  implement many interfaces in a single class, support of C-style primitives).  The more tools you  give developers to work with, the more people will willingly adopt the language.  The added  flexibility doen't necessarily make a language superior, but it does make it more accessible,  and a large development community is the single most powerful attribute a language can have:  someone, somewhere will find a way to do what you want to do, and make their suggestion public.

Biocomputers and quantum computers the two most substantial paradigm shifts in 21st computing)  will most likely follow a similar pattern.  A powerful, inflexible language will be created and  be met by all sorts of worship by the academic community, but the technology will only take off  once a more familiar language is released incorporating aspects that made the uncompromising  language so powerful.

Does form in always follow function in a programming language?
The article gives much focus to the statement that "form always follows function" in nature, and  so should it in technology.  What does this mean exactly?

Well, one good example is that most languages are structured in a sequential manner, mirroring  the capabilities of the underlying hardware paradigm.  Single-core execution predominated for  decades, and our languages were built with that in mind.

There is a good chance that the increasing adoption of multi-core systems will eventually result  in a new style of programming.  Not merely synchronization control, or fork/joins, but an  altogether new style.  If form follows function, perhaps our code will eventually be split into  parallel tracks, visually organized as a side-by-side list of streams of code.  If the code is  executing on multiple cores, it should probably *look* to a developer like it is executing on  multiple cores.




Viewing the evolution of programming languages can provide a sense of how the field progresses,  and, to some degree, can assist one in anticipating future changes.  But perhaps more  significantly, it can give one a better understanding of why things are as they are now.  You  never really understand your own country until you've visited another.  You never fully  understand your language unless you see the ideas that created it.

Functional vs. Object-Oriented Design

Supporters of functional programming are often deeply convinced of their methodology's superiority: its mathematical purity, flexibility, and conciseness.  Object-oriented designers frequently consider this approach obtuse, and difficult to organize.

For all the vitriol and dogma surrounding these two approaches to programming, there are only three core  I consider genuinely important:

• Should one allow functions to modify state information, or merely return a value?
• Should one allow functions to access information not directly passed to them?
• Should functions be explicitly tied to classes, or can they stand alone as occupants in a system?

These are frequently made out to be arguments over programming languages--yet, as Bertrand Meyer points out in Software Architecture: Object-Oriented vs. Functional, both types of languages can assume the same effective organization.  This isn't a question of languages, but of architecture.

Should one allow functions to modify state information, or merely return a value?
At the heart of this question is the concept of consistency.  Should functions be permitted side effects?  Arguably, this is the source of most instability in programs: the program enters an unexpected state as a result of functional side-effects and can no longer operate properly.

From a performance perspective, there's a lot of good reason to permit inter-function state modifications: it prevents the creation of an abundance of temporary values that need to be held in memory.  From a mathematical perspective, it's just allowing noise into the system.  Ultimately, these side-effects are a relic of modern hardware: The Von Neumann bottleneck makes frequent creation of temporary variables incredibly expensive.  This is a by-product of the fact the modern architectures separate programs from data.  This will change as our approaches to computing change: a well-designed quantum system will require no side-effects, since these intermediary calculations can be processed synchronously and in a highly-optimized fashion (multiple calculations on the same machinery at the same time, something currently impossible); a well-designed biocomputational system will contain densely-linked side effects, such that every function affects all others.


Should one allow functions to access information not directly passed to them?
This is largely a question of syntax, really.  Effectively, every function in a standard class has the explicitly-declared parameters sent to it, as well as every member variable.  This can reduce verbosity (no need to explicitly pass in the majority of data being used) but can also obfuscate the data being functionally used.


Sophisticated IDEs will eliminate this problem--they can present all the data a function is actually using concisely, and use that information in compilation.

Should functions be explicitly tied to classes, or can they stand alone as occupants in a system?
Strategy pattern.  It works.  If you don't accept this, you probably work in a terminal and refuse to accept that better development tools exist.




Both of these approaches are Turing-complete.  Both can organize in most any way a developer wishes, as long as they can think in the right abstractions.  Object-oriented programming is a highly-pragmatic approach to modern programming that trades mathematical purity for organizational clarity.

These paradigms evolve with hardware, however.  We will see a return to something more similar to functional programming as our hardware begins to evolve, but that does not necessitate the abolition of useful organizational patterns--it simply requires densely reflective languages, powerful optimizing compilers, and hardware that isn't burdened by the replication of data.

We won't always be using Von Neumann computers.  Even Von Neumann knew this.

Publishing Research in Academia (ReLooper)

Like any institution, universities struggle to establish a meritocracy, to offer staff recognition correspondent to their academic success.  This challenge takes two forms: how do you reward success, and how do you recognize it?  While the former is an interesting institutional question, the latter I am far more concerned with.  The criteria they establish for determining staff's contributions became a key focus for the staff itself.

The method you use to evaluate professors determines what they will do.  When a university prioritizes the number of publications made, then researchers will adjust their approach to publish a maximum amount of papers.  When a university prioritizes impactful contributions, researchers will try to maximize impact.

Each discipline faces its own challenges of publication and reward, but few are as damaging and avoidable as those in computer science.  The accusation?  Disposable projects.  Effort that could easily become something, but don't.  Great ideas that go nowhere, because there is no incentive to make them go anywhere.  Computer science is still struggling to adapt to its own power, and many inefficient institutional constructs have yet to be replaced by better ones.

In order to help shepherd along this progress, I've decided to bring some ideas back from the not-so-distant future, interviewing Alice Feldman, Public Relations and Research Promotion (PRRP) Officer for the University of Illinois department of Computer Sciences in the late 2010s.

Kurt: It's great to be speaking with you, Alice.
Feldman: It's always great to have an opportunity to be heard.
Kurt: So can you briefly discuss the scope of your position?
Feldman: Certainly.  I'm in charge of the PRRP office at the university's CS department.  Basically, I help get the work done here at the university out in the open.  I keep businesses up-to-date on our research, find collaborators, research online communities, just try to be sure that our efforts propagate as thoroughly and widely as possible.
Kurt: So how old is this position, and when did it come into being?
Feldman: Our office has been open now for 5 years, me being the second officer.  The University recognized that Computer Science simply had many opportunities not found in other disciplines, and was being held back by traditional publishing.  In science, you spend your hours gathering data, and though others may try to verify your experiment, very rarely does the data itself see a second functional life.  But the work our professors do here--their effort, their research, effectively is completely reusable.
Kurt: Your referring to programs, proofs-of-concept?
Feldman: Exactly.  So much of the effort done in this discipline can be immediately applied, and built off of.  We found that too often, we'd have some fascinating research papers or dissertations that would simply be thrown out once it was finished.   Not only were we limiting our ability to impact the discipline, but we were limiting our opportunities to get the University's name out.
Kurt: Any examples?
Feldman: Well, any time someone thinks "Java concurrency" now, they immediately think University of Illinois.  Prof. Danny Dig has done some fascinating work in this area.  For years, that work was severely impaired in its impact... some ideas made their way into the language or its tools, but most simply faded away, made irrelevant as soon as the platform took a step forward.  So we make sure that his work is incorporated into well-known public libraries, and make sure to commit the manpower to maintain that work.  We make sure all our faculty's research is as accessible as possible, and consequently, people use it.  Professors get their names out, the University gets its name out, the field advances.
Kurt: Computer science has been around for many, many decades now.  Why do you think your type of work took so long to take off?
Feldman: Part of that is tradition--it takes time to change the way people think.  But, more importantly, it strongly correlated with the growth of the open source community.  Researchers needed a platform into which to integrate their work, users to use it, developers to improve upon it, and projects with enough respect to give the effort significance, pride.  At this point, there are enough users of this kind of software to make contributing worth the time, to give the University numbers worth bragging about.
Kurt: Numbers?
Feldman: We have hundreds of thousands of developers using hundreds of contributions from our professors, running collectively on billions of dollars of equipment.  There's no reason to wait for someone else to implement your idea any more, when its so easy to let them improve it instead.
Kurt: Interesting stuff.  We're about out of time, but thank you for taking the time to talk to me.
Feldman: It's my job.  And it's technically your job, too, you know?

KDE: When the Bazaar Sets of to Build Cathedrals

First, a piece of dated Linux humor... one man's depiction of the KDE and Gnome development processes, circa 2002:

KDE

A big room somewhere in Europe with lots of chrome and glass and a great big whiteboard in the front with lots of tiny, neat writing on it. There are about 50 desks, each with headphones and pristine workstations, also with a lot of chrome and glass. The faint sound of classical music permeates the room, accompanying the clicky-click of 50 programmers typing or quietly talking in one of the appropriately assigned meeting areas. (Which of course consist of elegant contemporary white pine coffee tables surrounded by contemporary white pine and fine leather meeting chairs.) Coffee, tea, mineral water and fruit juices are available in the break area.
At the end of the day, everyone checks in their code and the project leader does a "make" just to make sure it all compiles cleanly, but it's mostly only done from tradition anymore since it always compiles cleanly and works flawlessly. When all milestones have been met, and everything has been QA'd, (usually within a day or two of the roadmap that was written up 18 months previous) a new KDE release is packaged up and released to the mirror sites with the appropriate 24-hour delay for distribution before being announced.
KDE developers are generally between the ages of 16 and 25, like art made of lines and squares and the colors white and black. When/if they finally stop taking government subsidies and get around to getting "real jobs," most of their salary will be taken in taxes so the socialist government can subsidize the care and feeding of the next generation of KDE developers, just like it did for them. A high percentage of KDE developers, during their mandatory 5 years of government military service, crack from their years of cultural dullness and flee Europe to become terrorists for the sheer joy to be found in killing random strangers for no discernible reason.

GNOME

An abandoned warehouse in San Francisco, kitted up as for a rave, electronica playing at 15db louder than "my ears are bleeding and I'm developing an aneurism" volumes and the windows all painted over black so that the strobe and spotlights and lasers can be seen better. Computers, mainly made of whatever stuff has been exchanged for crack or scavenged from dumpsters behind dot-bombs, are scattered around on whatever furniture is available, which also consists of whatever stuff has been exchanged for crack or scavenged from dumpsters behind dot-bombs. There's no break area, but you may be able to bum a beer (or more likely something harder) off of one of the developers hanging around, and they will probably be too jacked up on X, coke, acid, heroin, ether or all of the above to notice that you've taken anything.
Development strategies are generally determined by whatever light show happens to be going on at the moment, when one of the developers will leap up and scream "I WANT IT TO LOOK JUST LIKE THAT" and then straight-arm his laptop against the wall in an hallucinogenic frenzy before vomiting copiously, passing out and falling face-down in the middle of the dance floor. There's no whiteboard, so developers diagram things out in the puddles of spilt beer, urine and vomit on the floor.
At the end of the day - whenever that is since an equal number of programmers will be passed out at any given time - or really whenever someone happens to think of it (which is rarely), someone might type "make" on some machine somewhere, with mixed results. Generally nothing happens, so he/she shrugs his/her shoulders and wanders off to look for someone who might have more pink/black-striped pills. Once in a great while, generally in the unpleasant time between the come-down from the last thing they took and before whatever it was they took just now comes on fully, someone will tar up a bunch of random files and post it on a website someplace it as the next GNOME release, usually with a reference to some kind of monkey.
GNOME developers rarely live past 25 and prefer "alternative" art - generally stuff made of feces that's "too edgy" for most people to "understand" or "like." Core GNOME developers are heavy Ketamine users. The bodies of GNOME developers can often be found in dumpsters or floating face-down in any sufficiently large body of water.

In many ways, the joke illuminates how far these two environments have come, reflecting the growth of the open source community itself over the past decade.  At this point, both Gnome and KDE are sophisticated, fully-featured desktop environments with large, well-organized development communities.  Even though the open source movement has been around since the late 80s, it continues to grow, learning (as a whole) to address increasingly complex products in an increasingly coordinated fashion.

The joke was written in the early KDE days, when it could be sustained by just a few dozen developers, and truly was a well-coordinated product.  As the complexity of the system increased, its cohesiveness began falling.  Throughout the mid-2000s, the system suffered from a glut of features and lack of focus.  With time, they've regained their composure, now boasting over 400 active developers:

Source

This is a project currently on par with many enterprise systems in terms of size.  As Till Adam and Mirko Boehm discuss in When the Bazaar Sets Out to Build Cathedrals, the primary factor determining the growth an open source system is their ability to bring in active developers; in turn, this ability is proportional to the maintainability of code, encouraging a cleanliness of design rarely found in corporate environments.  Entire sections of code can be scrapped to meet the community's needs.  Furthermore, extensive effort is consistently made to have the software interact well with other systems (KDE's data access is designedto be accessed by other environments, such as Gnome).  Though these decisions are challenging for any development group to make, open projects have more incentive and fewer structural roadblocks.

As software becomes ever more complicated, this development model becomes increasingly important.  Incredibly large projects require a coordination and developer community outside the scope of all but a few organizations.  For example, though Red Hat only employs a few hundred developers, they can release an operating system containing approximately 60,000 man-years of effort, the equivalent of a $10.8 billion project.  Simply put, open source can scale very, very well.

The history of the KDE project reflects a slow, but steady sea change in the way software is developed and organized.

Refactoring Sequential Java Code for Concurrency

As programmers, we have an innate understanding of the power of computation.  I would estimate that more effort has been made on developer's tools and libraries than any other singular domain.  We make programs to help us program.  It's a challenge we understand.

From a strictly technical standpoint, any job that a programmer can do, a program can do, given sufficient understanding of the problem.  Highly-technical problems in particular lend themselves to automation.  The Concurrencer prototype is a recent example of this: an Eclipse-based refactoring tool to automatically multi-thread recursive Java functions.

It seems to do a reasonably good job of performing some code translations, and can catch many issues that a developer might miss.  Theoretically, these tools can be very useful going forward.

But I have two major objections with this tool, neither of which are technical in nature:

1. If you want your tool to be used, host it somewhere visible: First off, this is an Eclipse plug-in, and should have an update site.  Eclipse provies some simple tools to enable this.  It's an easy way to get more people to use your program.  Also, there have to be better places to host a project than a personal university web page--those are prone to disappearing with IT upgrades.
   
2. If you want your tool to improve, make the source public: I understand this is a research paper, and the authors may want to keep the code private until they publish a paper on it.  But once the paper is published, there's no good reason to keep the code private.  I can download the .jar and decompile the bytecode anyway, so why add hurdles?  Host it on SourceForge.  It'll attrack more interest in your work.  Hey, it's not even so hard to host an Eclispe update site on SourceForge.  The paper discusses an assortment of potential enhancements to the tool that I suspect the authors will not have time to implement themselves.  Why not make it easy for others to build off your work?
   

It is the responsibility of academics not merely to discover, but to share their knowledge.  There's no reason I should have to wait until the 2020s before universities begin to disperse their research in an open way.

If researchers are hesitant to take these measures because they are time-consuming, there's no reason not to off-load that work to grad students.  Whatever measure, the usefulness of a tool is generally proportional to its community.  Why not build a community around your ideas?

Fork/Join Parallelism

Early programming was highly dependent upon the underlying hardware.  Programmers would manipulate data on what was effectively a register-by-register basis, executing [relatively] simple assembly commands to alter the information.  With increasing computational power has come higher levels of abstraction, slowly freeing developers from the complexities of hardware, allowing effort to be focused on higher-level concerns.

Working with a modern, managed, programming language, one no longer needs to worry about assembly, about memory allocation or destruction, about paging or class loading, or a host of problems stemming from the operation of lower abstraction layers.  This seems an inevitable, and generally beneficial trend.  Developers can focus more on the busines problem and less on the technical.

In many ways then, modern parallel programming seems like a step back.  Developers are being asked to consider aspects of the hardware they were previously able to ignore (the number of CPUs) and aspects of the data they were previously able to ignore (the relationship betweeen data members necessary for synchronization).  Currently, many of our development models are heavy-handed: thread creation and signaling is a comprehensive, though highly error-prone coding style.  The predominant abstraction--threading--often entails substantial computational overhead.

An alternate abstraction is a task-based view, often utilized in a fork/join framework.  Under this methodology, a developer constructs independent tasks that can be sent to a queue to be processed by a worker thread.  The threads themselves represent interfaces to processors and can operate independently of the developer's code.

This has one main advantage and one main disadvantage: on the upside, this method can spawn an optimum number of worker threads for a given system, whereas a traditional thread model entails however many functional threads a developer can identify.  Furthermore, since the threads are permanent, there isn't substantial overhead in their creation and destruction.  For many concurrent problems, this is an ideal approach, abstracting away the hardware again and simplifying the logical interdependency.

This simplification also reveals its weakness--or perhaps more appropriately, its limitation.  For this model to work, each task or work unit must be completely functionally independent.  On one hand, this limitation still meets the needs of many (perhaps most) problems requiring heavy parallelism.  And unless the computational demands of a program are particularly high, then parallelism shouldn't necessarily be a chief concern.  But as I stated, this is a limitation, and there are some types of thread behavior that this prohibits, particularly if multiple threads are dynamically modifying the same data.

Originally, I'd set out to interview Henry Ford, who is in many ways the godfather of modern parallelism: he is the man who optimized the execution of tasks by best mapping it to the available hardware (in this case, manpower).  Unfortunately, I only was able to reach his secretary who informed me that "Mr. Ford isn't taking calls from the future.  He considers the future too bombastic."  Very well.  I'd probably spend most of the time whining about Detroit anyway.

The Future of Emacs

A confession: I have always been a VI man.
A further confession: I have never been a very good one.

The very thing that alienated me from Emacs is perhaps its greatest strength: its boundless flexibility.  Emacs is designed in such a way that a feature can be added without a substantial architectural learning curve.  Despite the sheer breadth of functionality the program has grown to encompass, at base, it is a relatively simple program: it is a text-editor with plug-in support.

So why VI over Emacs?  And will either of these programs be around in 50 years?

When I was originally learning VI, I recognized it as a dated technology.  It's a fantastic tool for working in a terminal, but is outshined by a host of editors in a modern, windowed environment.  I chose VI over Emacs because I wanted to be able to work in terminals, not because I wanted to learn a sophisticated IDE; simply put, VI is basically the same on any *nix machine, Emacs isn't.  VI is a skill that doesn't vary machine-to-machine.  Emacs keywords and features vary by release.

VI is useful but losing purpose with time.  In the long run, will Emacs' flexibility save it from irrelevancy?  To answer these questions, I shot off to 2059, explored the Emacs dev-sphere and had a quick holo-con with 70-year-old project maintainer Jerry "Wildebeest" Gorman.

Kurt: I have to say, it's stunning to see how long the Emacs project has lasted.  Could you describe some of the changes to the system in the last 50 years?
Gorman: Oh, it's been incredibly active.  We've optimized our algorithms for quantum architecture, we've integrated ASCII-video translation features so video streams can be rendered as stacked layers of colored ASCII text, we've worked on enhanced session concurrency, so a hundred users can share thousands of frames efficiently, we've--
Kurt: Are any of these developments unique to Emacs though?
Gorman: What do you mean?
Kurt: I mean, can Emacs do anything that other IDEs aren't doing right now?
Gorman: Well, it's written in Lisp, which is--
Kurt: So?
Gorman: And it's free as in speech.
Kurt: Plenty of other things are as well.
Gorman: And it has a small memory footprint.
Kurt: Don't you have petabyte QRAM chips now?
Gorman: And it--
Kurt: Can't you just admit that this is all nostalgia and outdated skills?
Gorman: No, it's totally about--
Kurt: What!?  Do you still check your e-mail with Pine too?
Gorman: Yeah, what about it?
Kurt: Gah!

To all readers curious as to the future of Emacs, I apologize for hosting such an embarrassing interview.  I just often feel like developers deny the real reasons for their habits.  Anyway, Emacs does offer some valuable lessons to modern developers, even if the platform itself is old:

1. Keeping the system open and easily flexible can grant it a long, rich life: A program need not be open-source to maintain an active development community, but should grant developers access to anything they could want to change.  Winamp is an outstanding example of a closed-source program that maintained a very active development community.  It gave users the ability to modify its appearance, its inputs, outputs, and to create new windows and features.  The end result was a product that was heavily used for years.  Though Winamp offers a cautionary lesson: by remaining closed source, you increase the chances of a product dying a slow death, since its longevity (and legal ownership) depend on the whims of someone other than the developer--in Winamp's case, AOL.
2. Simple interfaces can encourage complex development: Keeping the bar to entry low can keep people interested.  Emacs was easy to add-on to, and so many people learned to add to it.  This can either be done by defining well-structured, simple interfaces, or (more dangerously) by keeping most of the program's data flatly structured.  Firefox takes something of a hybrid approach, defining interfaces for various layout information, but keeping the data itself (including settings and page trees) "flat" and global.
3. Maintain a good way to publicize user's contributions: In the case of Emacs, maintained packages are kept in the program itself.  Because these features are most often accessible by keystroke combinations, they don't cloud up screen space and because Emacs is a terminal program, they're not very large.  Many modern projects maintain web pages dedicated to their add-ons.  Winamp and the Mozilla projects are particularly good about this.  Eclipse offers a well-centralized update utility, but lacks a good central resource.  Consequently, fewer minor changes get published, which potentially are slowing down the growth of the platform.  There are many outstanding, large contributions, but minor 3rd party enhancements are rare in the Eclipse ecosystem.

Emacs is something of a legend, and it can sometimes be hard to separate the program from GNU philosophy from Stallman's ego.  And in truth, maybe they shouldn't be completely separated: each has arguably benefited from the other.  Emacs may technically live forever, but I consider the program increasingly irrelevant.  Its lessons, however, can still be applied.  And I have yet to see another development tool grow  in such a broadly communal fashion.

Immanuel Kant: Mattson's Pattern Language

Most any attempt at taxonomy is inherently flawed, or at least incomplete.  There is no objectively clean way in which a complexly interwoven system can be described both completely and succinctly.  You can see this in biological taxonomy, which struggles to incorporate genetic history into a timeless label (birds share the same superclass as dinosaurs and mammals, incorrectly suggesting their common ancestor).  You can see this in medical taxonomy, which struggles to describe the symptoms, causes, and circumstances around the disease in a single label (resulting in dozens of competing standards used by different groups in the industry to describe similar things).  Yet biological taxonomy is immensely useful.  Medical taxonomy is immensely useful.  Neither is perfect, but both highly functional.

Entire fields of philosophy are devoted to exploring the ways in which we are shaped by the organization we impose upon something.  This is a particularly interesting question in computer science for two reasons:

1. We have the ability to organize information into any conceivable way: a pattern language isn't merely a labeling of natural phenomenon, it is a fundamental way of conceiving the organization of information itself.
2. We use and build upon our taxonomy more than almost any discipline: a program consists of millions of inter-related components existing at dozens of levels of abstraction.  Each new contribution is defining something new, and is likely to be the foundation of something else.  Thus how we think about it affects how we actually do other things that haven't yet come up.

Curious as to the epistemological significance of such qualification, I fired up the GRUMPS and had a quick cup of coffee with Immanuel Kant.


Kurt: Immanuel, in trying to organize a new system of knowledge, what is it that I'm seeking?
Kant: Experience without theory is blind, but theory without experience is mere intellectual play.
Kurt: So in constructing a language, I'm primarily seeking to guide and organize my thoughts?
Kant: All the interests of my reason, speculative as well as practical, combine in the three following questions: 1. What can I know? 2. What ought I to do? 3. What may I hope?
Kurt: So it should be comprehensive, practical, and illuminating?
Kant: Intuition and concepts constitute the elements of all our knowledge, so that neither concepts without an intuition in some way corresponding to them, nor intuition without concepts, can yield knowledge.
Kurt: Then it should be accurate, and intuitive as well, I see.  Thank you muchly for your time and words.



Though a taxonomy is inherently imperfect, they can still be good.  So how would Kant's questions apply to a pattern language?

1. It should help a developer be more productive: a good taxonomy of patterns will help a developer think in a way that clarifies their understanding of their system at as many layers as is pertinent.  It should given them a practical layering of concepts, and provide relevant ideas at each layer.
   
2. It should be easily expandable: no taxonomy is permanent, least of all in the world of programming.  A new pattern should have an obvious place in the language, and pertinent, identifiable relationship to other ideas based upon its placement.
3. It should be as simple as is practical: the more effort is required to understand it, the less people will use it.

So how does Tim Mattson's concurrency pattern language stack up?

1.  Would it help a developer be more productive?  It's hard to answer this without actually referring to it during the creation of a program, but I like how he cleanly distinguishes between the various roles of software engineers, and organizes his language accordingly.  That said, I don't know the chances that a developer would benefit from looking up a list of patterns so broadly categorized.
   
2. Is it easily expandable?  This structure doesn't draw much of a relationship between categories, and can be a bit questionable in the consistency of its abstraction layers.  Is a pipeline an algorithm strategy or an architectural pattern?  He puts it in both categories without explicitly explaining the difference in their use.
   
3. Is it as simple as is practical?  It's certainly simple, and easily understood.  There is a chance it's too simple, providing too little guidance as to the niche of various algorithms and approaches.

Maybe "pattern language" is a bit of an overstatement in describing the system.  It's more like a group of lists for developers of varying focus.  This isn't a bad thing--it could be a handy reference for a developer looking for ideas to address a specific concurrency problem.  The title is deceptive, however.

GRUMPS Design: Metacircular Virtual Machines

On only one occasion have I taken self-reference to its logical extreme:  the GRUMPS Superluminal Computation Optimizer.  In an attempt to dramatically enhance the speed of GRUMPS' computations, I designed a system to send instructions back in time so that the results would be available sooner.  The system was profoundly metacircular; not only was the system self-referential, but individual function calls would often be literally self-referential, creating themselves in John Conner-like fashion.

In developing this system, I noticed a paradoxical advantage: it was in some ways far less stable.  A simple bug would cascade rapidly, bringing down the whole system.  The net result was that I'd detect bad code much sooner than normal.  Furthermore, optimizations would often have a substantial affect on the system, shortening recursive invocations and affecting wide swaths of code.

For the most part, I am a high-level developer.  I am grateful for the abstractions granted to me.  I don't always want sweeping power over my system, and metacircularity grants one an extremely intricate power over the informational structure of a system.

This power is further complicated when it is attempting to recreate another system, rather than exist independently.  The Jikes RVM project is a Java-based Java VM, giving the developer far more power than an standard app developer needs, but exactly as much power as a performance theorist needs.  In evaluating such a project, it can be difficult to separate its meta-circular qualities from it's Java qualities.  What value does it derive from being densely recursive, and what value from being Java in particular?

Metacircular VMs (virtual machines written primarily in the same language they execute) are easier to port--only the the boot image, loader, and some memory behavior need to be translated for each operating system.  Most of the environment's behavior is self-referential, meaning it can execute on any environment support the lowest-level operations it specifies.  For a Java VM, metacircularity doesn't offer much to most application developers, since most programmers' applications will be running on a standard JVM anyway.  However, for support tools (like debuggers) and highly-specific performance-dependent niche applications, the ability to optimize the VM and code in the same context could help developers improve application performance, and identify the true bottlenecks in their system.

As a Java application, JikesRVM has some notable advantages and issues.  It gains all the structural benefits of Java--the ease of organization, the simplified modularity, the portability of code.  However, it also gains some of the problems--in particular, the hindered performance.  There is a reason JikesRVM is primarily a research project: it is much slower than the Sun JVM.

It's an excellent playground for testing out optimizations.  Its structure makes it easy for a researcher to get a comprehensive picture of how their work in interacting with the rest of the system.  Furthermore, it is probably the easiest way for a Java developer to understand the inner-workings of a Java VM.  But realistically, most of this theory achieves its fullest impact when done in a language closer to the processor.  Jikes has a long life ahead of it, but that life won't be on your laptop or cell phone.

Design and Project Management: JPC (Java-based x86 emulation)

The first think you may notice upon visiting JPC's web page is the banner loudly proclaiming "JPC is the fast pure Java™ x86 PC emulator".  The second thing you might notice is its absurd URL: www-jpc.physics.ox.ac.uk.  This project is hosted on Oxford's Physics Department's server.  Or maybe it's the fact that all the images on the main page are stretched to fit the designated rectangles, implying a stunning degree of apathy regarding presentation.

This is a project that makes a profoundly impressive claim, but exists somewhere in the abyss of near-forgotten software.  Reading the project's architecture, I was both deeply impressed with some of their technical accomplishments and know-how, and perplexed as to the niche the program was supposed to be filling.  You can get a good impression of project's nature by observing the status and users pages: it is currently an idle project, incapable of booting most x86-based operating systems, used primarily to play DOS games in a browser.

Clearly, this is a project that has a lot to teach.  Much from its successes, and much from its failures.  First, my complaints:

1. Java's portability is meaningless when you're emulating hardware.  This is a very oddly placed abstraction layer.  For you to run an x86 application, you now need to have booted into an operating system and loaded a JVM.  JPC is effectively relying on the JVM to ensure its portability.  In a sense, it's using Java for what a compiler should be used for.
   
   Any application that can be compiled with gcc can be compiled to run on any hardware gcc supports.  If they had written their code in C++ (or even combined Java down to binary, rather than bytecode), they would get the some functionality, but without the performance penalties inherent to the extra abstraction layer.
   
   The only novel deployment area for Java is applets, and those... well, we won't get into applets.
   
2. Follow your own rules: Newman and Dennis (the code's authors) explicitly warn against premature optimization.  "Make it work, make it right, make it fast", right?
   
   Again, looking at the "status" page reveals the only successful emulation behavior to be in DOS.  Now maybe "work" in this context can mean "work quickly"--the program is near useless without it.  They still seem to contradict "Before building each part of each stage, be clear what aspect is being developed and why" by repeatedly insisting that this is supposed to be a full x86 emulator.
3. Be honest about numbers: The project is regularly described as being "fast".  All sorts of benchmarks are given for a prototype using a simplified instruction set.  But the actual x86 emulation?  No mention in the paper.  After searching around, I found a presentation on JPC from which numbers can be derived; it's mentioned that using Java HotSpot, one can get approximately 20 x86 instructions per actual x86.  This translates to around 5%.  Simply put, that level of efficiency is far too slow to compete with most modern virtualization solutions.
4. If you're going to have open code, invite people: They're GPL'd but don't have a CVS or SVN server set-up.  No instructions as to how to contribute.  It might seem like they don't care because I suspect they don't.

That all I said, I'm still damn well impressed.  They were approaching a profoundly difficult problem, and sought a number of avenues to conquer it (at one point looking into the JVM code to find out how classes are managed in memory).  From their work, I learned quite a bit about Java's memory management and techniques for performance optimization.  There are some outstanding ideas in there: unfortunately most of those ideas are either centered around Java optimization or in advantages of virtualization--I remain unconvinced of the synergy between the two.

Curious as to the fate of this project, I fired up the GRUMPs and went off to the distant future: September 2009.  What I found shocked me: the project hasn't budged.

Biocomputers: Fault Tolerant Systems

An underappreciated distinction between software engineering, and all other fields of engineering: in software, the blueprints are the final product.

If I build a car, a scanner, a hard drive, anything that has a physical manifestation, then I run the risk of a manufacturing defect.  Most devices go bad after a time.  However, the blueprints do not.  In most ways, this is an advantage for software: it is limited in the ways it can decay.  Software defects are limited to their blueprints (code) and their operating environment.

In one way way, however, this gives hardware an advantage: fault-tolerance through duplication.  If you have two of any given device, chances are that one of them will behave as planned.  And if you can identify when hardware behaves unexpectedly, then you can replace it before it affects the system.  RAID works with disks.  It does not with software.

By conventional design, software is not fault tolerant.  You can spawn a hundred copies of your thread, but if your logic is incorrect, chances are that all hundred will fail.  Attempts have been made to build fault-tolerant software before.  The Guardian Tandem/16 would keep backup processes to run if primary processes fail, restoring a checkpoint and running from there.  While this mechanism could work for some types of faults, in reality, this is transaction management, not a full-functional backup.  Again, a logic error in one thread would simply be repeated in the backup.

So what would true software backup systems look-like?

One could take the military approach, in which three teams must independently reimplement the same functionality, with the end action being a consensus of three unrelated code bases. This substantially increases the reliability of code, but it also requires three times the effort.  A similar strategy is frequently employed by developers: test-driven development, in which the accuracy of the executing code is verified by another set of test code.  But, though this drastically helps code reliability, it isn't exactly fault tolerance.  Additionally, use of try/catch blocks in code can help identify, prevent, and sometimes fix problems, but it lacks the kind of hot-swap easy fix capability of well-designed fault-tolerant hardware.

Can complete fault tolerance exist in software without a doubling of design effort?  It depends upon the kind of faults one is looking for.  Many distributed algorithms can prevent problems that arise by thread crashes or competition over resources.  In order to support complete software fault-tolerance, a completely different approach to computing is required.  It is a field barely blossoming in 2009, but by the 2060s becomes critical to many high-end, computationally complex systems: biocomputation.

The human brain is a type of computer with heavy levels of fault tolerance.  It frequently makes processing mistakes (think of stubbed toes, misspoken words, phantom cell phone rings), but generally recovers from these.  How does it do this?  To explore this question, today we interview Dr. Larry Gernsback, head of the Neurocomputing Design Division in Qx Machinations (founded by two former Intel engineers and an MIT neuroscientist in the 2040s).

Kurt: Dr. Gernsback, you're involved in a field that would be foreign to most of our readers in 2009.  How does a neurocomputer differ from a standard digital computer?
Gernsback: Well, neurocomputers and biocomputers operate quite differently from classical digital and quantum computers.  The most familiar technology might be something along the lines of a highly-networked analog control system.
Kurt: I'm not sure I understand, please clarify?
Gernsback: In a traditional computer program, an operation is specified, it is compiled, and it runs exactly as it was told to do, in any given environment.  A loop will behave the same no matter where in the code it is placed.  In a biocomputer, there are two primary differences: first, no code can operate independently of its execution environment.  All functions must be fed with extensive data regarding the state of the area of the system it well be placed in.  Second, the code isn't compiled into machine instructions, but rather into probabilistic control mechanisms.  In effect, the code becomes the summation of a set of highly-conditional input-output matching.  Its effectively like performing a Fourier transform on discrete data.  Rather than being a signal defined by a single function, it becomes defined by a large series of additive, simpler functions.  So when you write a method, it is compiled into a number of regulating methods, each listening to different system state information, and modifying different system state information.  The cumulative effect is the desired functionality.
Kurt: So what benefit does this have?
Gernsback: Well, the primary consequence is that everything in the system affects everything else.  Now, this might sound inherently unstable, but if designed properly, it is quite the opposite.  A function will behave predictably when placed into a predictable environment; when anomalies occur in the system, they modify the global variables that all sorts of functions are listening for.  These functions in turn regulate those variables, returning them to normalcy.  Everything acts as a controller for everything else, meaning that parts with only some functional overlap will actually mutually enhance each others' reliability.
Kurt: Most fascinating.  So besides reliability, what does one gain from such functionality?
Gernsback: Well, it fundamentally changes the way in which one designs the system.  The "program" itself will seek out order, self-organize around the data feed into it.  This makes some classes of data analysis, security, even user interaction entirely different.  Rather than programming the internals of a feature, you mathematically define the desired outputs, and then feed the system extensive sets of simulated data.  New regulating functions will emerge to adapt to this data, modifying the program in such a way that it produces the desired output.
Kurt: So, the software is evolved, almost literally?
Gernsback: Precisely.  And with that design paradigm, one gets all sorts of other gains.  The program can evolve in multiple different directions in virtual environments, and even "mate" with each other.  It enables you to run the genetic algorithm on programs themselves, enabling you to rapidly produce a variety of possibilities, and select the desired one.  It costs almost the same to produce 100 unique programs that meet your requirements as it is to produce 1, fundamentally changing the way one approaches the system.  A good developer knows how to guide the evolution of a product, more like a botanist than a traditional engineer.  We have a joke around the office that software that doesn't behave as desired only needs to be "domesticated".  I think its an apt term, in some respects.
Kurt: I'll admit, a lot of this discussion went over my head, but the structure of it I find extremely fascinating.  And I'll have you know, Dr. Gernsback, that your work is only the beginning.

Okay.  At this point in time, we have C++ and some basic calculators implemented in DNA.  We don't have extensively self-modifying programs.  What we have is redundancy and transaction management.  This is powerful, and this will be the dominant paradigm for some time to come.  But true, complete, software-level fault tolerance is currently profoundly laborious to implement.  And until a program can dynamically modify itself, the most effective duplication is a duplication of effort.

Terry Goldberg: Big Ball of Mud

This weekend I received notice that a certain nameless interviewee has filed a Defamation of Character lawsuit for a recent blog post.  Frustration aside, this legal circumstance got me thinking; I am technically bound by all the rules of law—federal, state, and local.  Yet there is no conceivable way I could know all these laws.  I am fundamentally bound by more law than I could know in a lifetime.  Even if I limited myself to a particular sub-field of law, and even if I limited myself to recent law, there is more tax law produced annually than I could conceivably read in a year.

The legal framework of the United States begun simply.  The constitution provided general guiding principles, but most particulars had not been fleshed out.  Verdicts were at the discretion of the moral compass of juries, who often deferred to English Common Law until America’s legal framework became comprehensiveness enough to stand on its own.  Over the years, decades, new laws continually got built upon old laws.  Extensive [over]reactionary laws (fixes) altered the system in response to questionable verdicts in trials (bugs).  Entirely new fields of law emerge (features) as the culture and economy of the country grew.  The system becomes progressively more complicated, with no conceivable force to simplify it.  An obtuse, interwoven set of legislation and judicial precedent define the behavior of the system, often failing to maintain an intelligible high-level structure.

In the world of software, we call this situation a Big Ball of Mud.  When a lawyer can spend days attempting to find a law or judicial ruling pertinent to his case, then you have a system too complicated for its own good.  It may be fully featured, but it is difficult to maintain, and expensive to understand.

So how does one address a system of exponentially increasing chaos?  While meeting with my lawyer, Terry Goldberg, this weekend, I took a minute to interview him on his opinions of the process:

Kurt: In the world of software, a product that is grown ad-hoc over many years can often become unnecessarily expensive to maintain.   Do you see analogous behavior in law?
Goldberg: Without question.  There are more lawyers now than at any point in our nation’s history.  We constitute a larger percentage of the working force, yet can charge more than at any point in the past.  And I think a lot of this has to do with the fact that there is more law now than there was at any point in the past: congress has passed more bills since 1976 than were passed in the preceding 200 years.
Kurt: Do you believe this is how the system should operate?
Goldberg: It depends on what you seek from it, but as a system of regulation and common utility, I think it has become too obtuse, and continually worsens.  I got into law because of a belief in justice.  But indecipherable law colludes a sense of what is just.  I would love to defend my clients based upon the ethics of their actions, but that is simply not how cases are decided.  In many cases, there is an obvious right or wrong party, but it is endlessly difficult to find the text that proves their legality.
Kurt: In essence, you don’t know where the relevant code is.
Goldberg: It depends on how specialized you are and on the nature of the case, but quite a lot of my job entails searching for precedent.
Kurt: Is there any way to change this?  To simplify the beast?
Goldberg: Many countries go through legal resets.  Switzerland re-wrote its constitution as recently as 1999 to prevent the need for an endless series of legal patches.  But once a system has grown beyond a certain size, these kinds of reboots are impossible.  Too much of the country becomes shaped around the law.  If you reset the law, you reset these institutions, which can be dangerous and incredibly expensive.
Kurt: So what happens then?
Goldberg: It will grow more and more complex until it reaches a breaking point.  When the demand for lawyers is so high such that the effective productivity of the institutions they guide is hindered, then there might be a demand for a simplification.  Until such time, it will only get worse.

As my readers know, I’m fond of overstretching metaphor, but I see many similarities in programming and law.  Each theoretically produces a codified framework whereby inputs (events in law) produce predictable outputs (rulings).  Much like law, early maintenance is critical to keeping projects sensible.  Once they grow past a certain size, it becomes impossible to simplify them down—there is simply too much dependency.  Many businesses will simply keep patching a system until it collapses beneath its own weight—until fixes and improvements are so convoluted and time-consuming that there is no conceivable way to match the pace of market demands.

At that point, they will scrap the software and start over.  They will write a new constitution.

Once a Big Ball of Mud is created, there is rarely hope to recover it.  One can attempt to isolate parts of it, but if the system were easily made modular, it wouldn’t be a Big Ball of Mud.  Early and frequent refactoring is essential if a system’s goal is longevity.  But as much as programmers may wish for that goal, it very rarely is a business priority in an industry that redefines itself every few years.

As long as hardware is improving at a rapid pace, software will be rapidly evolving, and thus taking the time to refactor to ease long-term maintenance is not always worth it.  Any project should attempt realistic expectations for their timeline, and effort should always be made to grow them in a sustainable way.    But each business has a different set of priorities, and it is often more financially beneficial to release now.

But the advantage of software is competition: if your product lags because of its design, someone else will eventually replace you.  One has incentive to code quality, or market share will decline.  That is a flexibility law does not offer.

Thomas Jefferson: Layered Architectures / Xen

Layered architectures come up again and again in software design, being a natural byproduct of the recursive nature of computing.  Any function call that never references its parent is effectively a new layer.
Of course, we don't always call these things layers: to do so would be to cheapen the term.  In software architecture, a layer generally consists of a swappable set of functions that maintain the integrity of the overall layer stack.  The traditional network layers are an excellent example of this.  UDP could transmit HTTP data, even though TCP is generally used for this.  Different devices use different physical links, and a countless set of application-layer protocols without imposing any required changes to the layers beneath.

The network stack also reveals something about the dynamic nature of architectural layers: as long as your interfaces are stably defined, new layers can be inserted, removed, or combined as necessary.  The original OSI model for network stacks established 7 layers for digital communication, including a "data-link" layer (separate from the physical layer), and a "presentation" layer (separate from the application layer).  Functionally, these are important layers.  Practically, their implementation wound up combined with other layers in the stack such that they are now rarely discussed independently.  The "session" layer, responsible for maintaining a dialog between remote application is now functionally part of the transport and application layers: TCP will guarantee message delivery, and HTTP will manage a client/server session.  SSH can easily be used as the application layer, wrapping any other application layer within it.  Because the interfaces are well-designated, these layers can be added without affecting the system as a whole.

Another example of the evolution of layers due to well-designed interfaces is in virtualization.  Any program that executes on a computer goes through a number of translations, often being translated from managed code into assembly code, assembly into bits traversing a system.  Memory access is converted from virtual to physical addresses, physical to block/offset locations.  Anywhere a conversion takes place, a new layer can be inserted, as long as its external interfaces communicate consistently.  This notion has enabled computers to run multiple simultaneous operating systems.  New layers are added, translating kernel's system instructions into lower-privilege commands, and translating the operating system's "physical memory" addresses into the real physical memory addresses.  The end points can communicate just as they had previously, however.

Granted, the addition of new layers will always reduce performance.  So developers have turned to concepts such as paravirtualization, effectively combining separate layers into a single one, maintaining consistent behavior at the end-interfaces, but internally operating differently than if the layers were distinct.  For example, a paravirtualized operating system may delegate memory paging to the hypervisor, rather than handling it by itself to improve performance.  Thus, one step in the memory translation is saved.  Similar approaches are taken for devices: rather than have a layer to deal with driver translation, hypervisor-level drivers can be accessed by the hosted operating systems.

A rough analogy of this set-up can be found in law.  Layered architecture is like federalist government: the responsibilities of each layer of government (federal, state, local) are determined by the functionality of the layer above it.  These layers operate by consistent interfaces (law and funds) but internally have theoretical freedom in their implementation.  Realistically, this is often not the case: governments can often micromanage state spending by strongly incentivizing certain actions ("sure, you don't have to drop your local speed limit to 55, but then you unfortunately wouldn't qualify for highway funds").  In this respect, government is more like a "relaxed" layered system... higher-level layers can interfere with lower level ones.

So, would government an ideal government be able to defy this desperation of layers?  Does good software expose the internals to lower layers?  Is it even remotely fair to treat the answers to these questions as related?  Of course not.  Thus, in celebrated ignorance of this conclusion, I present to you: an abbreviated interview with Thomas Jefferson, political theorist on federalism.

Kurt: Mr. Jefferson, it is with great privilege that I needlessly interrupt your studies.  I have but a simple question for you:
Jefferson: What, man?  Who the hell are you?  I've never seen cloths so fu--ed up before.  Holy sh--.  Georgie boy bought me the good stuff this time.  I cannabalieve it.  Heh, heh.  Get it?
Kurt: Mr. Jefferson, are you...?
Jefferson: Yeah, man, what?
Kurt: I'm embaressed to even be asking this question... are you... well... in a condition to speak?
Jefferson: Sh-- man, I do all my writing fu--ed up.  It's the best fu--ing way, man.  Best fu--ing way.
Kurt: Ah... well.  I guess I'll just... just, how do believe that governments should be arranged?  What amount of authority should a federal body have over smaller ones?
Jefferson: God damn, field me the easy ones, freaky alien dude.  The several states composing the United States of America are not united on the principle of unlimited submission to their general government; but by a compact under the style and title of a Constitution for the United States, and of amendments thereto, they constituted a general government for special purposes and delegated to that government certain definite powers and whensoever the general government assumes undelegated powers, its acts are unauthoritative, void, and of no force. To this compact each state acceded as a state, and is an integral party, its co-states forming, as to itself, the other party. The government created by this compact was not made the exclusive or final judge of the extent of the powers delegated to itself, since that would have made its discretion, and not the Constitution the measure of its powers.
Kurt: So... maintain a strict separation then?
Jefferson: God I am fu--ed up.

I... I really don't know if I feel comfortable applying that advice to my programs.  But I'm not sure if I'm comfortable applying it to government any more either.  Damn.

Augustus Ceasar: Data Grows Up

As the web grows more densely interconnected, challenges begin to arise.  How does one balance the demand for data interoperability with the demand for privacy?  How does one maintain consistency within a technological framework fundamentally designed to be flexible?  How can you avoid the labor and challenge of crafting redundant data, requiring a user to supply information that’s already a part of the cloud?
The Facebook project has done an outstanding job engineering around these challenges, building what is currently one of the leading social networking sites.  Millions of people use it for hundreds of different reasons, leveraging an ever-increasing volume of user information to build new services in a controlled matter.  With the proper design, the site has become the center of a small universe of activity based around the notion of digital community—the sharing of notes, photos, the organization of political movements and Scrabble games.

To do all this, Facebook has had to figure out how to compromise with developers: how to involve third parties while controlling data access and application behavior.  They’ve literally re-implemented a wide assortment of web technologies to make this happen: FBML to allow developers to code near-HTML web pages capable of invoking Facebook services; FBJS to allow developers to code dynamic web page behavior while forbidding access to undesired operations and out-of-scope Facebook components; FQL to give developers access to Facebook data in a predictable, controlled, and optimized way, requiring the necessary authentication and abstracting away data that could compromise the security of the site.

In many ways, these approaches are brand new: they’re creating new implementations of already-modern languages.  But the fundamental paradigm Facebook is using is rather old: they’re providing a controlled environment for developers to practice much the same thing they’ve been doing before, abstracting away the complex translation necessary to make their code operate cleanly.  It is giving developers a new environment to practice old behaviors.

So characteristics abstraction enable it to be so effective?  With the recently fixed and more-stable-than-ever GRUMPs, we’ll be probing these questions by interviewing legendary Roman emperor Octavianus Augustus Caesar.

Much like modern developers, Augustus Caesar rose to power amidst an environment in profound flux, and great organizational instability.  Yet he thrived in such a chaotic environment, and rebuilt the Roman Empire in a way that lasted centuries after his death.  Creators of application frameworks could learn much from his political acumen.  Without further ado:

Kurt: Augustus Caesar, it is a great honor to have you here.  You’re a figure of rare notoriety and influence.
Augustus: The honor is mine.  I have long thought about how I could address the future… the wisdom I could impart to my successors’ successors.
Kurt: So Caesar, how is it that you found a way to organize a state rapidly tending toward decay?
Augustus: You must first understand the cause of that decay; all people want two things: freedom and power.  These are the forces most actively working against any attempt at order, for two reasons: freedom threatens, since every man chooses a different route with his liberty; power threatens because it is scarce—it only comes at the expense of others.  Fundamentally, you will realize that freedom and power are the same thing: power is simply the point at which your freedom overrides another’s.
Kurt: So do you seek to eliminate freedom and power from your developer’s—er, I mean, citizens?
Augustus: No, no.  It is far more subtle than that.  If you eliminate freedom, others will not follow you.  You can never remove a man’s desire for freedom, and where a man has unmet aspiration, he is dangerous.  Too with power; you cannot rob all men of power for they will fight to win it back.  Rather, you must give to each man the smallest freedom and power they require to be content.  You must give to each city enough independence to thrive gratefully, but never so much that they feel capable of conquering their limitations.
Kurt: So one must carefully craft architectures to allow programmers to modify what they need without affecting the systems that you yourself are defining?
Augustus: You speak with the confidence and obscurity of the sibyls.
Kurt: I mean, you give power to others only where it doesn’t intrude upon your own?
Augustus: All granting of power intrudes upon your own.  Rather, you must only sacrifice as much power as is required to make others feel powerful.  A man governs best when he believes something is his.
Kurt: Then give a developer the tools to make an application feel and behave how they wish, but maintain control over the data.  I mean… keep local customs alive?
Augustus: You recruit soldiers from around the world.  They will remain loyal to you if you feed them and permit them to practice their own religion.  They must respect your rules, but you must maintain rules men can respect.
Kurt: Right, so no Javascript pop-ups.
Augustus: Moreover, you exercise power only where necessary, and in those places, exercise ruthlessly.  In other areas, simply give them rules they must follow to maintain their power, and they will do so.  Let your borders be protected by the client states, not by your own legions.
Kurt: So, don’t try to control the kinds of applications that flourish, merely provide them an incentive an opportunity to flourish, and they will empower your architecture...
Augustus: The people will celebrate Rome if they believe their city to be both Roman and theirs.
Kurt: Augustus Caesar, your wisdom inspires.  We are almost out of time, but do you have any closing thoughts?
Augustus: A principate is all-powerful, but never lets himself be perceived as such.  Freedom is the most powerful political illusion, more pure and celebrated than a vote.
Kurt: So, one must emphasize the power you grant third party developers--let them use your information, but not change it.  There’s so much more to learned, but I'm afraid our time is up.  Thank you, Caesar, for coming.

Perhaps it’s a stretch to compare Facebook to great historical rulers.  But in many ways, the challenges and solutions are the sames.  Facebook is manipulative in an almost political sense with its users and developers:  It offers rich functionality and hides the costs (to privacy and such) by providing users the impression that they fully control their data, and developers the impression that they fully control their application.

If Facebook had simply provided a high-level API to build applications, it would require developers to approach on bended knee.  A simple API doesn't give a developer a feeling of power over data, a sense of independence and excitement so necessary to maintaining a user-driven application.  If Facebook were upfront about the ways in which they use user data in advertisements, people would feel violated.  But give a user a chance to deny an application access to their data, and they feel free.  Give a developer a chance to program in a familiar language, and they feel powerful.  They feel like Facebook's application is theirs.

Facebook has consistently impressed me with its design.  A look beneath the hood has only reinforced my respect.  But maybe that’s just what they want me to think.

GRUMPS Design: Pipes and Filters

In one sense, pipes and filters are the computational paradigm most reminiscent of classical signal processing.  In circumstances where one input is modified in many ways to produce one output, piping is often the most sensible and flexible solution.  Piping stdout and stderr programs in *nix allows the users to easily execute complicated operations without requiring them to create new programs.  Instead, they can simply string together transformations, finding, manipulating, and redirecting text.  This is similar to audio production, in which a limited number of filters can be used to make a great variety of modifications to an acoustic signal; applying reverb and then noise will sounds substantially different from applying noise first, and then reverb.

Thus, in pipe/filter processing, each permutation of the available filters constitutes operates like a new filter in itself, meaning that every new contribution enriches the entire processing ecosystem.

That said, there are dangers in overstretching this analogy.  Computer pipes and filters encounter issue that direct signal processing does not.  Circuits do not have to deal with error conditions: they will treat all inputs the same.  They do not have to worry about time spent switching between processes: the transition is instantaneous.  They rarely need to navigate a complex push/pull pipeline: each push/pull would be a separate component in itself.

When I was originally designing GRUMPs, I gave consideration to designing some of the components as a pipe/filter set-up.  Because of the flexibility such a system would offer, I assumed that it would enable me to prototype many different kinds of physical set-ups until I came across one that stably opened a worm hole through time.  Some of my initial prototypes processed time flux data in exactly this matter, but I soon came across some issues that prevented me from continuing to work in that paradigm.

The most substantial among these was the increasingly evident need to maintain a global state.  A pipe/filter setup treats each component as structurally independent from one another.  So what do I do when my flux capacitance monitor begun measuring anomalous gravitational waves, forcing me to alter the rate of boson production?  A pipe/filter system can’t handle this condition easily.  Technically, you can design a pipe to take multiple inputs, but that begins to breakdown the purity of the design, complicating the system’s structure in the long run.  Simply put, too many components needed to talk to too many other components in GRUMPS simultaneously. 

Another problem came from the need to dynamically redirect the flow of information.  Technically, one can operate a conditional filter pipeline, but again this breaks the purity of design.  Depending on the nature of information streaming through the black hole, I might need to enable or disable various filters and amplifiers, frequently reconfiguring the data flow multiple times per second.  Ultimately, this began to look more like a fuzzy state diagram, and less like a pipe/filter setup.  My assumptions that I could simply reconfigure and rerun proved consistently wrong, as the setup had to adapt to running conditions.  Filters failed because a large, carefully calibrated system cannot dynamically respond to circumstances when it is designed to process information linearly.

Pipes and filters are a fascinating and profoundly useful paradigm.  But despite their flexibility, it is still a solutions to a very limited subset of problems.  I keep it in my back pocket, but I am less inclined to assume it the best methodology than I used to.

Being "In the Web"

While I'm busy with repairs to the GRUMPS, perhaps we should have a high-level discussion about the evolution of software's treatment data over the last 30 years.

Once upon a time, as recently as the dark ages that we call the 1980's, information was commonly recorded onto long lengths of magnetic tape.  To retrieve the pertinent information within your network, a "robot" would have to move throughout the machine, pick a tape, move it to the tape reader, the tape would be wound and your data read.  That is, if you were located within the facility.

Transferring large volumes of data was often prohibitively expensive for most IT groups, so tapes were often mailed (as in physically delivered... by a person) between facilities.  Highways simply had a higher data throughput than most networks.

A computer was envisioned as a one-application-at-a-time interface, so developers were given full discretion to use the system's resources as they saw fit.  By the 90's, most software was inconsistent, and profoundly insular.  There just wasn't enough network bandwidth to consider data available in "the cloud" (at the time, not more than a diffuse altocumulus cloud).

And then the internet happened.  Everyone was in everyone else's data.  Programs were talking to central servers, grabbing information from a variety of places, and putting it together.  A hundred data access standards were created and destroyed.

Right now, the shape of software is changing.  Far more programs are highly networked, and far more programs co-exist on a single system.  And we've gotten to the point where the system is increasingly dependent upon the broadcast and receival of networked information.

XML has been among the most successful ways to define an data type comfortably interoperable between programs.  Web services (SOAP) in particular define standard to allow data to be queryable.  And increasingly, applications are providing developers a way to broadcast their own data.  A crucial component of the Android operating system is the ability of programs to inform the whole system what data and functionality they have available, such that it can be easily invoked by other applications.

In order to achieve this kind of deeply inter-connected software, restrictions are imposed on developers.  Don't present information anyway, present it in a limited way, and declare the type of data you're using upfront or there'll be hell to pay.  Or you at least won't be able to access your desired information.

This exhibits a fascinating paradox in programming: limitations are profoundly helpful.  Limited vocabularies of interaction can enable richer interaction, by ensuring that various software truly speak the same, simple language.  Essentially, they enforce the data-centric nature of these applications; in REST architecture, one is limited to simple reads and modifications of data.  When you define your operation around the data (rather than UI or rules of operation, say), one allows an application to participate in the cloud.  A program isn't limited by the functionality created by the developers, but can become part of a rich ecosystem of interaction.  An alerts module can be invoked by a hundred other modules.  User data can be combined with a hundred other kinds of data, as long as it is made available.

I knew a developer who declared that any operation in a program should be executable by command-line, enforcing a vocabulary of interaction to better define the behavior of the system, and to allow it to better integrate into the ecosystem of the operating system.  The fact is, most modern software can only benefit from putting its public interaction upfront, and that action is most cleanly defined by data.

Lao-Tzu: A Timeless Way of Building (Christopher Alexander)

I often try to break down computing into its core form and function; the act helps one maintain perspective on the full scope of power of the technology.  At base, what is a computer?  A device to manipulate information.  That is, a machine that assists you in reducing something to an abstract representation (information), and can then modify or examine that abstraction quickly.  Fundamentally, the work done by any computer is simple, or can at least be reduced to simple steps--assembly commands are essentially a form of arithmetic.  There is nothing a machine can do that you or I can't... a computer can simply do these simple things orders of magnitude faster.  They can do complicated things quicker, and that speed enables them to realistically manipulate information in ways the unassisted human mind cannot.

So what is ultimately the force driving the analysis or manipulation of information?  Programs.  A computer, being an all-powerful tinkerer of data, can manipulate information in any possible way.  Any way data can be changed, a computer can do.  And the expressive language for that is programs.  A programming language can be called "turing-complete" if it exhibits this characteristic, if it is capable of all forms of information processing.

A programming language is fundamentally a description of a pattern... it describes some relationship between kinds of data, and how to act on them.  A larger program is made up of many simpler patterns--methods, subroutines.

When you recognize that programs are an arbitrary data container for any and all patterns, something interesting is revealed about software engineering: any architectural style, design pattern, or coding technique can be explicitly defined as code.  If your style cannot be, then it is either an inconsistent pattern (and thus not really a pattern), or your description of the pattern is incomplete.  Programming languages are literally a pattern-description language, and a complete one at that.

So why don't textbooks describe design patterns as code, and instead portray them as "ideas"?  Ultimately, this is due to the presence of a human mediator; the human machine has evolved to process information by a completely different descriptive languages, and very different algorithms.  What is effective for a computer, is not necessarily effective for a person, and at this point in history, it is the person that is writing programs.  That said, most patterns do have explicit definitions in many languages.  The observer pattern is built into Smalltalk.  The object-oriented paradigm (itself a design pattern) is fundamental to a number of programming languages.  Well-designed interfaces can effectively permit any pattern to be expressed within the language.

If I may be permitted to take an aside... if programs are simply a representation of patterns (a translation of "concepts" into "information" such that a computer may work with them), then where does the mind fall into this structure?  By some definitions, a "mind" is simply any system that processes and responds dynamically to information.  Could a "mind" itself simply be a program, a layering of patterns?

Enticed by the prospect that this blog entry lay on the cusp of enlightenment, I decided to open up a dialog with legendary Chinese philosopher, the Great Master Lao-Tzu.  Certainly, he can show me the way.

Kurt: We live in a universe exhibiting an astounding variety of patterns.  How do you make sense of such incredible complexity?
Lao-Tzu: All difficult things have their origin in that which is easy, and great things in that which is small.
Kurt: Exactly!  An endless layering of simple patterns can give rise to the deepest of functions.  Can this include the human mind?
Lao-Tzu: Nature is not human hearted.
Kurt: No, but is the human nature-hearted?  Are we merely a specialization of universal operation, an instance of self-organization and programmatic expression?  Are we not a vast compendium of nature's rules? 
Lao-Tzu: To see things in the seed, that is genius. 
Kurt: So you agree!  By Jove you agree!  Then the act of finding patterns is the act of returning to the root of organization?  And the act of documenting the sub-programs of the mind, the more rules that are discovered, the more easily those patterns can be discovered? 
Lao-Tzu: The more laws and order are made prominent, the more thieves and robbers there will be. 
Kurt: Wait, do you imply that one most look then from the ground up, rather than from the top down?  Is there deceit in comprehensiveness? 
Lao-Tzu: He who knows, does not speak. He who speaks, does not know. 
Kurt: Are you calling me verbose?  And also, wait... you just said that... doesn't that contradict-- 
Lao-Tzu: The words of truth are always paradoxical.  
Kurt: But every paradox has a resolution.  What is the resolution to the statement you just posited? 
Lao-Tzu: I have just three things to teach: simplicity, patience, compassion.

There was a great tremor and the black hole collapsed in a most extraordinary fashion, light sputtering from the abyss, great and rapid shifts in the temperature of the room.  GRUMPs stood still, smoke emanating, both exhausted and tranquil.

Okay, screw revelation.  I have time-machine fixing to do.