Programs as Cities:

Scenarios for a New Assault on the Complexity Barrier

The Problem

There have been great strides made in recent years in making two classes of large problems easier to solve. One approach has been to increase the amount of computer power available for working with large data sets (weather simulation on a Connection Machine, for instance). The other notable area of progress has been in characterizing certain types of complex phenomenon with a small number of variables (chaos-type mathematics). What remains is the problem of irreducible complexity such as is found in managing large computer programs, real time control systems, large scale simulations (such as C-cubed or medical simulations), and large data bases.

There are two complimentary approaches that can be applied to irreducible complexity. The first is improving the machine representation of such complexity to create better tools for analysis and manipulation. The second approach (visualization) is to improve the user interface so that the user can understand, remember, and manipulate complex structures more easily.

Visualization of even small amounts of complexity has been shown to be useful in programming and system administration (Brown and a thousand other references). A problem with visualization is that all such systems must factor a complex structure in such a way that the part of the structure viewed at any one time is small enough to be gracefully displayed on a computer screen. This re-creates the problem found in text-based displays, where extensive use is made of references to parts of a large structure that are unseen. This approach relies heavily on a programmer's mental recall ability; An interface in which a large structure could be seen at once would reduce such demands.

The biggest barrier to broadening visual user interfaces in the current generation of workstations is the screen. A basic problem is that the screen is two-dimensional. In representations of "box and arrow" diagrams, for instance, it is very difficult to organize a two-dimensional view of a large number of components that doesn't become visually confusing. This is an inherent property of conventional displays due to the limited connectivity possible in two-dimensions. For this reason, unfortunately, increasing the size of the display screen generally does not enable the presentation of more complex visual structures. The HMD approach

A high resolution Head-Mounted Display (HMD) has the potential to effectively display a larger number of visual objects (and a greater complexity of structures made up of those objects) at one time than a fixed screen. The potential for HMDs in programming, and other problems in the display of irreducible complexity, has been limited in the past because of the low resolution of HMDs and the inadequate power of real time 3D graphics, but very high resolution HMDs and adequate 3D rendering speeds are becoming available this year. It is now possible to show enough objects (thousands), including legible text printed upon them, that the amount of printed information visible in a virtual environment at one time will be at least as great as seen on a workstation screen. This level of visual capability also allows for a multi-mode approach: while we emphasize novel Virtual Reality approaches to complexity visualization, text and two-dimensional graphics representations will also be available within the environment.

There are several reasons HMDs hold promise for improved complexity visualization. First, the persistence of objects in all directions creates an effective huge display with more directions in which to look than a fixed display. Second, head position/orientation tracking enables the user to look around objects blocking a point of view, so a dense display is not as challenging to design in order to achieve visual comprehension. Third, and perhaps most important, Virtual Reality allows the user to use two cognitive strategies that are extremely effective: environmental navigation and manual manipulation. Environmental Navigation

Since complexity visualization is for the benefit of people, we should do our best to understand the cognitive powers of people in making design decisions. It is not easy to do this, because cognitive science is a young science, as is computer science. Nonetheless, we believe that there is sufficient reason to make a working assumption that environmental navigation holds promise as a mode of learning and recall of complexity.

Learning keyed to an environment (in this case meaning a spatial environment in which one perceives one's body to be moving, such as a living room or a street) has been shown to be more effective than learning methods requiring abstract associations. In fact, physical environments and smells are the two stimuli that are most effective in aiding recall. Since smells do not have structure, environments would seem to be the most effective cognitive stimuli for aiding in the recall of complexity.

The other domain of extreme complexity in which human beings have a demonstrated ability is language, after which computer control has been approximately modeled. Environmental navigation is more similar than language to problems in large computer systems in that, among other things, it deals more with objects with persistent states and relationships to each other (i.e. the definitions of natural language words are unclear and variable, but a house stays in one place on the same street).

We will make an informal argument comparing large programs and cities. In order to learn how to navigate around a city, one must internalize a structure of immense complexity. While it is only a rough analogy, it would be safe to say that the average programmer has internalized more complexity to learn the city he/she lives in than is found in any program that has yet been created. While people learn cities all the time, it very rare for someone to learn a large program well enough to recall it in detail when maintenance is required after a long period of unrelated work. What is striking about environmental complexity is that it is recalled with remarkable ease when one visits a city after a long absence. It might also be pointed out, anecdotally, that historically, prior to the advent of the printing press, the most common mnemonic devices used involved the memorization of real or imagined physical environments and recall was stimulated by imagining navigations of these environments. Examples include the Memory Palaces that were vital to the development of European culture and the songlines of the Australian aborigines, who have demonstrated perhaps the strongest memory capabilities of any people.

So let us imagine a large program represented as a city. Data flow, control flow, dependency, or other relationships between objects would be streets. Our city will be somewhat flat, but not two dimensional; there will be levels of underpasses. This frees us of the limited connectivity of two-dimensions, but allows us to go up in a helicopter and get a bird's eye view (a overview that looks two-dimensional will be more comprehensible than a jungle-like three dimensional overview). We can see the whole program at once. Each part of our city has been ornamented with decorations that persist even though they have no semantic relevance. (The topology of neighborhoods would have consistent semantics, the appearance would not.) The decorations are vital to assisting recall of a large number of neighborhoods. Manual Manipulation

Just as environmental navigation is promising as a method of learning and recalling complexity, manual manipulation is promising as a method of testing and changing complex structures. Hand/eye coordination is one of the central tasks of the human nervous system and one of the areas in which human beings undeniably attain the highest degrees of cognitive ability.

When it comes time to change the structure of our city, it is made small. We pick up streets and re-connect them.

We make extensive use of continuous feedback in this aspect of our interface design (as opposed to the event-loop notion of interface in which the computer-user dialog is represented as discreet, independently meaningful events). For instance, you might put a fist into a node (street intersection) in the shrunken city. Upon straightening the index finger, all the streets connected to the node light up. Upon straightening the second finger, all the streets connected to those streets light up. By opening the fingers one by one you can browse for paths that lead outward from the node in a continuous, interactive fashion and understand a great deal more about the local structure of a graph in a short period of time than would be possible with discreet queries.

Another example would be a critical path diagram. Each path would be represented as a telescoping tube (that would also be a tunnel for travel when the city was big) that could be pulled to a maximum length, representing the maximum time a sub-task would require, or pushed to a minimum length, representing the minimum length of time. The experience of browsing such a model by continuous manual manipulation would be like playing with a puzzle, and would likely be more informative that screen-based displays of similar information.

The comparison of versions and the viewing of modification histories of complex structures will also be facilitated in an interface in which the entire structure can be seen at once in an overview.

While the ornamentation of the city is arbitrary, the topology is meaningful and is formally described. A semantic assistant agent watches while the city is manipulated and prevents meaningless or contradictory changes to its design during the manipulation process. Conclusion

Interfaces using HMDs for the visualization of irreducible complexity hold great promise and should be attempted.

The group productivity potential of this type of interface should also be noted. Multiple programmers can be present in the same city, seeing each other at work and engaging in group projects. This might very well facilitate social modes of memory creation and recall more easily than abstract cooperations do.

It should also be noted that in applications related to simulation, a single virtual environment could contain the simulation experience and the code running the simulation, facilitating a quick development cycle.

Go back to Jaron's home page.