How computers will be used will be determined in part by technology trends, and in part by trends in the needs of people for computation, and by changes in living and activities. These changes are parts of feedback loops: for example, changes in needs cause changes in investments which cause changes in technology which enable changes in lifestyle. Beyond a few years the scene is no more predictable in shape than any other chaotic system. I nonetheless propose some strong attractors based on what seem to be stable regions extrapolated from the present.

No abstract available.

For thirty years, most interface design, and most computer design, has been headed down the path of the “dramatic” machine. Its highest ideal is to make a computer so exciting, so wonderful so interesting, that we never want to be without it. A less-traveled path I call the “invisible”; its highest ideal is to make a computer so imbedded, so fitting, so natural, that we use it without even thinking about it. (I have also called this notion “Ubiquitous Computing.”) I believe that in the next twenty years the second path will come to dominate. But this will not be easy; very little of our current systems infrastructure will survive. We have been building versions of the infrastructure-to-come at PARC for the past four years, in the form of inch-, foot-, and yard-sized computers we call Tabs, Pads, and Boards. In this talk I will describe the humanistic origins of the “invisible” ideal in post-modernist thought. I will then describe some of our prototypes, how they succeed and fail to be invisible, and what we have learned. I will illustrate new systems issues that user interface designers will face when creating invisibility. And I will indicate some new directions we are now exploring, including the famous “dangling string” display.

We describe the results of examining two large research and commercial systems for the ways that they use threads. We used three methods: analysis of macroscopic thread statistics, analysis the microsecond spacing between thread events, and reading the implementation code. We identify ten different paradigms of thread usage: defer work, general pumps, slack processes, sleepers, one-shots, deadlock avoidance, rejuvenation, serializers, encapsulated fork and exploiting parallelism. While some, like defer work, are well known, others have not been previously described. Most of the paradigms cause few problems for programmers and help keep the resulting system implementation understandable. The slack process paradigm is both particularly effective in improving system performance and particularly difficult to make work well. We observe that thread priorities are difficult to use and may interfere in unanticipated ways with other thread primitives and paradigms. Finally, we glean from the practices in this code several possible future research topics in the area of thread abstractions.

Two key ideas in garbage collection are generational collection and conservative pointer-finding. Generational collection and conservative pointer-finding are hard to use together, because generational collection is usually expressed in terms of copying objects, while conservative pointer-finding precludes copying. We present a new framework for defining garbage collectors. When applied to generational collection, it generalizes the notion of younger/older to a partial order. It can describe traditional generational and conservative techniques, and lends itself to combining different techniques in novel ways. We study in particular two new garbage collectors inspired by this framework. Both these collectors use conservative pointer-finding. The first one is based on a rewrite of an existing trace-and-sweep collector to use one level of generation. The second one has a single parameter, which controls how objects are partitioned into generations: the value of this parameter can be changed dynamically with no overhead. We have implemented both collectors and present measurements of their performance in practice.

Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. Our strategy was, first, to use machine-dependent C code as an intermediate language, second, to create a language-independent layer known as the Portable Common Runtime, and third, to write a relatively large amount of Cedar-specific runtime code in a subset of Cedar itself. By treating C as an intermediate code we are able to achieve reasonably fast compilation, very good eventual machine code, and all with relatively small programmer effort. Because Cedar is a much richer language than C, there were numerous issues to resolve in performing an efficient translation and in providing reasonable debugging. These strategies will be of use to many other porters of high-level languages who may wish to use C as an assembler language without giving up either ease of debugging or high performance. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix* operating system, and some measures of the performance of our “Portable Cedar”.

Operating system abstractions do not always reach high enough for direct use by a language or applications designer. The gap is filled by language-specific runtime environments, which become more complex for richer languages (CommonLisp needs more than C+ +, which needs more than C). But language-specific environments inhibit integrated multi-lingual programming, and also make porting hard (for instance, because of operating system dependencies). To help solve these problems, we have built the Portable Common Runtime (PCR), a language-independent and operating-system-independent base for modern languages. PCR offers four interrelated facilities: storage management (including universal garbage collection), symbol binding (including static and dynamic linking and loading), threads (lightweight processes), and low-level I/O (including network sockets). PCR is “common” because these facilities simultaneously support programs in several languages. PCR supports C. Cedar, Scheme, and CommonLisp intercalling and runs pre-existing C and CommonLisp (Kyoto) binaries. PCR is “portable” because it uses only a small set of operating system features. The PCR source code is available for use by other researchers and developers.

Menus are largely formatted in a linear fashion listing items from the top to bottom of the screen or window. Pull down menus are a common example of this format. Bitmapped computer displays, however, allow greater freedom in the placement, font, and general presentation of menus. A pie menu is a format where the items are placed along the circumference of a circle at equal radial distances from the center. Pie menus gain over traditional linear menus by reducing target seek time, lowering error rates by fixing the distance factor and increasing the target size in Fitts's Law, minimizing the drift distance after target selection, and are, in general, subjectively equivalent to the linear style.

The use of feet instead of hands to perform workstation cursor-positioning and related functions has been the subject of an on-going investigation. In the exploratory study reported here, a particular foot-operated device, the planar slide mole, was assessed against a mouse in a target-selection task. The study showed that novices can learn to select fairly small targets using a mole; for a target size of 1/8″ square, the response time equaled that of the mouse when keyboard homing time was taken into account.

Abstract We describe a technique for storage allocation and garbage collection in the absence of significant co‐operation from the code using the allocator. This limits garbage collection overhead to the time actually required for garbage collection. In particular, application programs that rarely or never make use of the collector no longer encounter a substantial performance penalty. This approach greatly simplifies the implementation of languages supporting garbage collection. It further allows conventional compilers to be used with a garbage collector, either as the primary means of storage reclamation, or as a debugging tool. Our approach has two potential disadvantages. First, some garbage may fail to be reclaimed. Secondly, we use a ‘stop and collect’ approach, thus making the strategy unsuitable for applications with severe real‐time constraints. We argue that the first problem is, to some extent, inherent in any garbage collection system. Furthermore, based on our experience, it is usually not significant in practice. In spite of the second problem, we have had favourable experiences with interactive applications, including some that use a heap of several megabytes.

Workstations require use of the hands both for text entry and for cursor-positioning or menu-selection. The physical arrangement does not allow these two tasks to be done concurrently. To remove this restriction, various alternative input devices have been investigated. This work focuses on the class of foot-operated computer input devices, called moles here. Appropriate topologies for foot movement are identified, and several designs for realising them are discussed.

Textnet is a new system for structuring text. The Textnet approach uses one uniform data structure to capture graphlike pools of text, as well as embedded hierarchical structures. By using a semantic network formalism of nodes connected by typed links, the relationships between neighboring pieces of text are made explicit. Also described is our partial implementation of the Textnet approach, which makes use of an object-oriented window/menu-driven user interface. Users peruse the network by moving among object menus or by reading text along a path through the network. In addition, critiquing, reader linking, searching, and jumping are easily accessible operations. Finally, the results of a short trial with users are presented.

Abstract The Maryland Window System is a set of programs for manipulating multiple overlapping windows on CRT terminals. Part of the package is the window shell, called the CWSH. The CWSH uses the windowing system to create multiple windows running shell processes. The CWSH differs from the WSH and BRUWIN window systems by permitting processes running in the windows access to window functionality, and by more fully implementing a Unix terminal within each window. Unlike BRUWIN and WSH, CWSH permits programs, such as other shells and editors, that intensively examine or modify their terminal environment to run unmodified in its windows.

Program slicing is a method for automatically decomposing programs by analyzing their data flow and control flow. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a ``slice,'' is an independent program guaranteed to represent faithfully the original program within the domain of the specified subset of behavior. Some properties of slices are presented. In particular, finding statement-minimal slices is in general unsolvable, but using data flow analysis is sufficient to find approximate slices. Potential applications include automatic slicing tools for debuggng and parallel processing of slices.

Abstract DAISTS (Data Abstraction Implementation, Specification and Testing System)1 is a compiler tool‐base for program development. The compiler combines an automated ‘oracle’, which checks consistency conditions derived from algebraic specifications of modules, with run‐time routines that judge the quality of a user's test data according to statement and expression coverage criteria. This paper describes some of the implementation techniques used in DAISTS.