==================================== REFEREED PUBLICATION AuthorLine: S. P. Reiss POC: spr@cs.brown.edu TitleLine: A framework for abstract 3-D visualization PublishedByLine: Proc. Visual Languages '93 FileName: ? Abstract: This paper describes a package, PLUM, we have developed for visualizing abstract data in three dimensions. We are particu larly interested in visualizing information about programs, both static and dynamic, but the package should have a more general applicability. The package provides a framework to support a wide variety of different 3D visualization techniques, many of which have been implemented. The package also provides sup port for 3D graph layout using a variety of different layout heu ristics. ==================================== REFEREED PUBLICATION AuthorLine: S. P. Reiss POC: spr@cs.brown.edu TitleLine: Presentation and editing of structured 3-D graphics PublishedByLine: Proc. HCI '93 FileName: ? Abstract: This paper provides an overview of our efforts at providing high-quality, 3D visualizations of information about programs. This data is generated by querying the different information sources through a single object-oriented database schema. The result of the query is a set of abstraction objects that are then mapped, through a set of user-definable translations, into a set of abstract graphical objects that represent the display. A separate package handles layout, constraints, and presentation of these graphical objects. The resultant display is interactive at three levels. Syntactic interactions allow the user to pan, zoom and fly around in 3-D space. Semantic interactions allow user actions to affect the translations from abstraction objects into abstract graphical objects and to change the set of abstraction objects by modifying the initial query. ==================================== REFEREED PUBLICATION AuthorLine: M. Sarkar, S. S. Snibbe, O J. Tversky, S. P. Reiss POC: spr@cs.brown.edu TitleLine: Stretching the rubber sheet: a metaphor for viewing large layouts on small screens PublishedByLine: Proc. ACM SIGGRAPH UIST '93 FileName: ? Abstract: We propose the metaphor of rubber sheet stretching for viewing large and complex layouts within small display areas. Imagine the original 2D layout on a rubber sheet. Users can select and enlarge different areas of the sheet by holding and stretching it with a set of special tools called handles. As the user stretches an area, a greater level of detail is displayed there. The technique has some additional desirable features such as areas specified as arbitrary closed polygons, multiple regions of interest, and uniform scaling inside the stretched regions. ==================================== TECHNICAL REPORT AuthorLine: Isabel F. Cruz POC: ifc@cs.brown.edu TitleLine: Expressing constraints for data display specification: A visual approach PublishedByLine: Brown University CS Techreport AvailableByFtpOn: ftp.cs.brown.edu FileName: /pub/techreports/93/cs93-57.ps.Z Abstract: In this paper we introduce a constraint-based language that has a visual syntax and allows the declarative specification of the display of data. Other features of the proposed language include: (1) simplicity and genericity of the basic constructs; (2) ability to specify a variety of displays (graphs, bar charts, pie charts, etc.); (3) compatibility with the object-oriented framework of the database language DOODLE. We provide the syntax and the semantics of the language, and examples of applications that demonstrate the expressiveness of our language. ==================================== TECHNICAL REPORT AuthorLine: Isabel F. Cruz POC: ifc@cs.brown.edu TitleLine: User-defined visual languages for querying data PublishedByLine: Brown University CS Techreport AvailableByFtpOn: ftp.cs.brown.edu FileName: /pub/techreports/93/cs93-58.ps.Z Abstract: DOODLE is the first language to be proposed for querying object-oriented databases with user-defined visual languages. A DOODLE program defines a visual language in a by-example fashion. In this paper we continue the preliminary exposition of DOODLE (SIGMOD'92). We refine the language, and provide complex examples that illustrate the extensive capabilities of DOODLE in a variety of applications. The contributions of DOODLE to other areas of Computer Science, such as constraint languages and graph drawing are also outlined. DOODLE explores the limits of declarative languages by making data and its manipulation visual, while staying within the bounds of the formal database field. The formal basis of DOODLE motivates the study of visual expressiveness and points to further research. ==================================== REFEREED PUBLICATION AuthorLine: Steven P. Reiss, Isabel F. Cruz POC: ifc@cs.brown.edu TitleLine: Practical software visualization PublishedByLine: Software Visualization (SIGCHI) Workshop FileName: TBD Abstract: Our research is aimed at providing a usable visualization environment for understanding large software systems. We are attempting to design and develop the frameworks that are needed to allow the programmer to take an existing software system and use visualization techniques to answer the questions that arise during development, maintenance, and reengineering. The task of providing practical visualizations of software systems can be broken into three problems. The first is determining what to visualize. Large software systems contain an enormous amount of information in a wide variety of forms. To understand a particular aspect of the system or to answer a particular question, one needs only a tiny subset of this information. Determining the "right" subset, however, is very difficult. The second problem is presenting the information. Again, the large amount of information to present and the need to do the presentation quickly require high-quality presentations and a variety of different presentation techniques. The third problem involves specifying the visualization. The need to understand and not just see the information requires that we allow the user to select and experiment with different visualization techniques and views as well as to intelligently browse over the result. ==================================== REFEREED PUBLICATION AuthorLine: Tiziana Catarci, Isabel F. Cruz POC: ifc@cs.brown.edu TitleLine: On expressing stratified Datalog PublishedByLine: Second ICLP-Workshop on Deductive Databases Databases and Logic Programming FileName: TBD Abstract: We consider the broad class of stratified Datalog queries (which includes both linear and non-linear queries) and propose an extended closure operator that expresses such queries when added to the relational algebra. We show that there exists a canonical form for stratified Datalog queries, and that suitable hypergraphs can be used to express them. We anticipate the use of such hypergraphs in identifying special classes of stratified Datalog queries and in devising efficient algorithms for these classes, and outline the use of the visual representation of hypergraphs in a user interface for querying databases. ==================================== REFEREED PUBLICATION AuthorLine: Isabel F. Cruz POC: ifc@cs.brown.edu TitleLine: User-defined visual query languages PublishedByLine: IEEE 10th International Symposium on Visual Languages, VL '94 FileName: TBD Abstract: Previous research in visual query languages has focused on pre-defined visual representations of data and queries, which are suitable for specific applications, but difficult to extend and generalize. In this paper we investigate the possibility of querying an object-oriented database with pictures that belong to user-defined visual languages. By manipulating these pictures, the user can extract information about the data, in a purely visual fashion. The specification of the pictures is performed with constraints that are visually expressed and combined. Using a small set of primitives, it is possible to specify complex displays, such as graphs, bar charts, and pie charts. Our approach extends object-oriented concepts, such as inheritance and genericity, to visual languages. We provide examples that illustrate the expressiveness of the visual languages to display and query data. ==================================== REFEREED PUBLICATION AuthorLine: R. H. B. Netzer, S. Subramanian, J. Xu POC: rn@cs.brown.edu TitleLine: Critical-path-based message logging for incremental replay of message-passing programs PublishedByLine: IEEE International Conf. on Distributed Computing Sys. '94 FileName: pub/techreports/94/cs94-19.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: Debugging requires repeated execution. However, the potential nondeterminacy in message-passing parallel programs makes repeated execution difficult, turning bugs into moving targets. Special tools are required that trace an execution so it can be replayed as needed. To be usable, replay tools must be efficient (tracing too much data is impractical), and they must provide fast replay (reexecuting long-running programs from the beginning incurs lengthy delays). To be efficient we must avoid tracing every message. However, to provide fast replay we must log enough messages (and checkpoint processes periodically) to provide incremental replay, to allow restarting from intermediate states. These goals conflict. We achieve a balance by presenting an adaptive message logging strategy that keeps run-time overhead down while logging enough to guarantee a bound on the replay time. We let the user specify a bound on the maximum time any replay request is allowed to take. A replay is a reexecution of an interval between two checkpoints of some process. Our technique exploits this bound by tracking what each interval's critical path will be during replay, and logs enough messages to ensure that the critical path will never exceed the bound. Logging overhead is kept low by not logging messages that can be recomputed during the replay. Experiments indicate that we log about 0.1-5% of the messages. We achieve both a substantial reduction in the number of messages logged and a bound on the time to complete any replay request. ==================================== REFEREED PUBLICATION AuthorLine: R. H. B. Netzer, M. H. Weaver POC: rn@cs.brown.edu TitleLine: Optimal tracing and incremental reexecution for debugging long-running programs PublishedByLine: ACM SIGPLAN Conf. Prog. Lang. Des. and Imp., to appear 1994 FileName: pub/techreports/94/cs94-11.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: Debugging requires execution replay. Locations of bugs are rarely known in advance, so an execution must be repeated over and over to track down bugs. A problem arises with repeated reexecution for long-running programs and programs that have complex interactions with their environment. Replaying long-running programs from the start incurs too much delay. Replaying programs that interact with their environment requires the difficult (and sometimes impossible) task of exactly reproducing this environment (such as the connections over a one-day period to an X server). We solve these problems by incremental checkpointing and replay. By periodically checkpointing parts of the execution's state, it can be restarted from intermediate points, bounding the delay to replay any part of the execution and allowing parts of the execution to be skipped. We present adaptive tracing strategies that provide bounded-time incremental replay and that are nearly optimal. Our techniques track reads and writes to memory using space-efficient two-level bitvectors. Our implementation on a Sparc 10 traces less than 15 kilobytes/sec for CPU-intensive programs and for interactive programs the slowdown is low enough that tracing can be left on all the time. ==================================== REFEREED PUBLICATION AuthorLine: R. H. B. Netzer, J. Xu POC: rn@cs.brown.edu TitleLine: Necessary and sufficient conditions for consistent global snapshots PublishedByLine: IEEE Trans. on Parallel and Dist. Systems, to appear 1994 FileName: pub/techreports/93/cs93-32.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: Consistent global snapshots are important in many distributed applications. We prove the exact conditions for an arbitrary checkpoint, or a set of checkpoints, to belong to a consistent global snapshot, a previously open problem. To describe the conditions, we introduce a generalization of Lamport's happened-before relation called a zigzag path. ==================================== REFEREED PUBLICATION AuthorLine: J. Xu, R. H. B. Netzer POC: rn@cs.brown.edu TitleLine: Adaptive independent checkpointing for reducing rollback propagation PublishedByLine: IEEE Symposium on Parallel and Distributed Processing '94 FileName: pub/techreports/93/cs93-25.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: Independent checkpointing is a simple technique for providing fault tolerance in distributed systems. During execution, processes periodically and independently checkpoint their state, and upon detecting a fault, execution is rolled back and resumed from earlier checkpoints. However, independent checkpointing suffers from the domino effect, which causes the rollback of one process to potentially propagate to others. In the worst case, rollback propagation can force recovery to start from the execution's start, preventing forward progress from being made in the presence of faults. In this paper we present an adaptive checkpointing algorithm to practically eliminate rollback propagation for independent checkpointing. Our algorithm is based on proofs of the conditions necessary and sufficient for a checkpoint to belong to a consistent global state, previously an open question. We characterize these conditions with a generalization of Lamport's happened-before relation, called a zigzag path. Our algorithm tracks zigzag paths on-line and checkpoints when certain paths are detected. Experiments on an iPSC/860 hypercube show that we reduce the average rollback required to recover from any fault to less than one state interval per process, and checkpoint only 10% more often than traditional periodic checkpointing algorithms. We thus eliminate rollback propagation without the run-time overhead of coordinated checkpoints or other schemes that attempt to reduce rollback propagation. ==================================== REFEREED PUBLICATION AuthorLine: R. H. B. Netzer POC: rn@cs.brown.edu TitleLine: Trace size vs parallelism in trace-and-replay debugging of shared-memory programs PublishedByLine: Lecture Notes in Computer Science 768 FileName: pub/techreports/93/cs93-27.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: Execution replay is a debugging strategy in which a program is run over and over on an input that manifests bugs. Replaying nondeterministic parallel programs requires special tools; otherwise, successive runs (on the same input) can differ, making bugs impossible to track. These tools must trace an execution so it can be replayed. We present improvements over our past work on an adaptive tracing strategy for shared-memory programs. Our past approach makes run-time tracing decisions by detecting and tracing exactly the non-transitive dynamic data dependences among the execution's shared data. Tracing the non-transitive dependences provides sufficient information for a replay. In this paper we show that tracing exactly these dependences is not necessary. Instead, we present two algorithms that introduce and trace artificial dependences among some events that are actually independent. If no data dependence exists between two memory references during execution, we are free to artificially force them to execute in a specific order during replay. Artificial dependences reduce trace size, but introduce additional event orderings that have the potential of reducing the replay's parallelism. We present one algorithm that always adds dependences guaranteed not to be on the critical path (which do not slow replay). Another algorithm adds as many dependences as possible, slowing replay but reducing trace size further. Experiments show that we can improve the already high trace reduction of our past technique by up to two more orders of magnitude, without slowing replay. Our new techniques usually trace only 0.00025-0.2% of the shared-memory references, a 3-6 order of magnitude reduction over past approaches that trace every access. ==================================== REFEREED PUBLICATION AuthorLine: R. H. B. Netzer, J. Xu POC: rn@cs.brown.edu TitleLine: Adaptive message logging for incremental replay of message-passing programs PublishedByLine: IEEE Parallel and Distributed Technology '93 FileName: pub/techreports/93/cs93-26.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: Cyclic debugging is a common strategy where a program is executed over and over to track down bugs. However, for message-passing parallel programs, cyclic debugging is impossible without support of special tools. Variations in message latencies and process scheduling can cause different executions on the same input to produce different results. To provide repeatability, an execution must be traced so it can be replayed as many times as needed during the debugging cycle. Since parallel programs are long-running, it is impractical to always restart the replay from the execution's beginning and wait for it to reach the desired point. Providing fast response to debugging queries requires incremental replay, where reexecution can start from intermediate states. To support incremental replay, processes' states must be saved periodically along with the contents of some messages, but the cost of saving these messages can be prohibitive. This paper presents an adaptive message-logging algorithm that keeps this cost low by logging only a fraction of the messages. Our algorithm tracks dependences among messages and checkpoints to decide at run-time which messages cause a domino effect, and traces only these messages. The domino effect forces a replay request to start arbitrarily far back in the execution, and domino-free replay ensures that any part of the execution can be quickly reexecuted. Experiments on an iPSC/860 hypercube indicate that our algorithm typically logs only 1-10% of the messages, a 1 to 2 order of magnitude reduction over past schemes which log every message. In addition, our experiments show that the resulting logs (which allow domino-free replay) provide a small bound on the amount of reexecution needed to satisfy any replay request. Our new logging algorithm thus reduces the overhead of message logging while bounding the response time to replay requests. ==================================== REFEREED PUBLICATION AuthorLine: H. - I. Lu, P. N. Klein, R. H. B. Netzer POC: rn@cs.brown.edu TitleLine: Detecting race conditions in parallel programs that use one semaphore PublishedByLine: Workshop on Algorithms and Data Structures '93 FileName: pub/techreports/93/cs93-29.ps.Z AvailableByFtpOn: ftp.cs.brown.edu Abstract: We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that use many semaphores. For the case of a single semaphore, we give an algorithm that takes O(n^1.5 p) time, where p is the number of processes and n is the total number of semaphore operations executed. Our algorithms constructs a representation from which one can determine in constant time whether a race exists between two given events. ==================================== TECHNICAL REPORT AuthorLine: R. H. B. Netzer, S. K. Damodaran-Kamal POC: rn@cs.brown.edu TitleLine: Accurate race condition detection for message-passing programs PublishedByLine: Brown University Technical Report AvailableByFtpOn: ftp.cs.brown.edu FileName: u/rn/papers/msgrace.ps.Z Abstract: The hard part of debugging parallel programs intended to be deterministic is accurately locating the nondeterminacy. We present the first technique for accurately locating nondeterminacy (race conditions) in executions of explicitly parallel message-passing programs. Our algorithm takes a trace of an execution's receive operations and locates the points at which races occurred. In addition, we filter the race reports so that only those races that are direct manifestations of bugs are reported. Some races can be caused by others and are not indications of bugs. Our algorithm points the user directly to the manifestation of the problems, providing a starting point for debugging. ==================================== TECHNICAL REPORT AuthorLine: T. W. Doeppner POC: twd@cs.brown.edu TitleLine: The thread-monitor library: a system for monitoring solaris-threads programs PublishedByLine: Brown University Technical Report AvailableByFtpOn: ftp.cs.brown.edu FileName: /pub/techreports/93/cs93-53.ps.Z Abstract: Debugging a multi-threaded program involves all the difficulties of debugging a single-threaded program with the additional concern of the interaction between threads. Multithreaded programs can be nondeterministic -- the outcome of the program depends upon the ordering of the executions of the various threads. When testing a program, one would like to exert some control over this ordering, to force certain execution sequences to occur so that they can be tested. The Thread-Monitor Library is an experimental system that allows one to monitor and control the execution of a multithreaded program (written using the Solaris Threads package). It creates separate windows for controlling each thread and separate windows for monitoring each synchronization object (currently, only mutexes and condition variables are supported). Whenever a thread enters a synchronization construct, its execution is immediately suspended and the programmer is prompted for permission to resume execution. The operations applied to each of the synchronization objects are listed in the synchronization object windows, allowing one to keep track of their state. All of this is accomplished through a collection of "wrappers" for the Solaris Threads API. Rather than call the standard Solaris routine, one instead calls the appropriate wrapper which calls upon the monitor code as well as completing the call to the Solaris routine. ==================================== REFEREED PUBLICATION AuthorLine: T. W. Doeppner POC: twd@cs.brown.edu TitleLine: Open software: UNIX, DCE, and competitors PublishedByLine: Proc. CERN School of Computing, to appear in 1994 AvailableByFtpOn: ftp.cs.brown.edu FileName: /pub/techreports/93/cs93-59.ps.Z Abstract: Open software is software contributing to a general goal of systems that do not depend on any one hard ware or software vendor and are easily extensible by adding new software built upon the functionality of existing software. We discuss some of the defining characteristics of open software and frameworks that ease its production. These frameworks include operating systems and software supporting distributed computing. Examples are UNIX, NT, and DCE. We also examine two technological developments that are becoming very important in the development and use of these frameworks. The first is a structuring technique for operating systems -- microkernels. The second is a technique for doing concurrent and parallel computation -- multithreaded programming. ==================================== TECHNICAL REPORT AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Computer Literacy for Undergraduates: A Computer Literacy Approach PublishedByLine: Brown University CS Techreport TR CS 94-21 AvailableByFtpOn: WILMA FileName: TR CS 94-21 Abstract: Brown's computer literacy course for undergraduates with no previous experience of computing aims to elevate the collection of practical techniques associated with word processing, spreadsheets, and hypertext into a systematic discipline of document engineering. It starts with a Macpaint competition whose prizewinners in 1994 were publicly exhibited. It includes Hypercard assignments on "how computers execute programs" and on "can machines think?", and a network treasure hunt that requires students to correspond by e-mail, retrieve an ftp file, and report on their favorite newsgroups. The one-month final project requires design and implementation of a substantial document in Hypercard, Mosaic, or Excel, with a high-level design at the end of the first week and a detailed design at the end of the second week that is worth 20% of the project grade. The 1994 projects included a Startrek adventure game, the archeoology of Mesopotamia, multimedia guides to Ghana, Prague, and New York, the Bible with illustrations (Leonardo's last supper), and music lessons with audio examples and composition facilities (we used it to compose three blind mice). We examine the structure of the course, show examples of student work, and suggest that such courses are not only more practical than but as conceptually challenging as first courses on programming. ==================================== Refereed Publication AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Models and Paradigms of Interaction PublishedByLine: Springer Verlag LNCS Monograpgh, also TR CS-93-48 AvailableByFtpOn: not available by ftp FileName: not available by ftp Abstract: Models of interaction deserve a first-class status comparable to that of models of computation, and time also deserves a first-class status in computational modeling. We view programs as collections of autonomous interacting components rather than as sequences of actions. Objects are units of interaction with a functional semantics specified by their interface of procedures, a serial semantics specified by the power set of interface procedures, and a fully abstract semantics that specifies behavior over time for all possible execution contexts. Components are defined by distinguishing necessary from accidental properties of objects: they are noun-like, persistent entities with commutative composition, time-dependent effects and semantics, and life-cycle complexity. The fully abstract interactive behavior of objects and components cannot be expressed by computable functions, while their complexity is expressed by life-cycle rather than execution resource costs. Procedures in an object interface are context-dependent actions whose interactive effect over time has no neat mathematical characterization. Early models of computing stressed computation over interaction for both theoretical reasons (greater tractability) and practical reasons (there were no software components with which to interact). However, object-oriented programming, programming in the large, personal computers, and distributed systems require models of interaction rather than computation. A variety of interactive systems are reviewed and classified by increasing interaction power to indicate the orthogonality of computation and interaction power. We examine functions and procedures, objects and processes, APIs and frameworks, GUIs, robots, and virtual-reality systems. Though models of interaction are not as tractable as models of computation, they express the de facto behavior of actual software systems and support inherently richer behaviors than computable functions that accord time a first-class status in computational modeling. ==================================== TECHNICAL REPORT AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Towards Component-Based Software Technology PublishedByLine: Brown University CS Techreport, TR 93-11 AvailableByFtpOn: not available by ftp FileName: not available Abstract: Component-based software technology views programs as interacting software components rather than as instruction sequences. A conceptual framework for component-based technology is developed by both empirical and theoretical analysis. The component-based design space is explored by describing representative object-based, distributed, information, end-user, and rule-based systems. Component-based models of communication, logic programming, declarative specification, and complexity are examined. Open research problems of component-based software technology are discussed. This is a long (130-page) paper that represents work in progress. ==================================== REFEREED PUBLCIATION AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Beyond computable functions, or Escape from the Turing Tarpit PublishedByLine: Brown University CS Techreport, TR 94-01, to be published by the AMS in Proc. DIMACS Workshop on Parallel Specification AvailableByFtpOn:not available by ftp FileName: not available Abstract: Objects have inherently greater computation power than functions because they provide clients with continuing services over time. They determine a \fImarriage contract\fP for interactive services that cannot be expressed by a pattern of time-independent \fIsales contracts\fP. Objects express the programming-in-the-large paradigm of software engineering, while functions express the programming-in-the-small paradigm of the analysis of algorithms. Escape from the Turing tarpit extends the notion of ``observable behavior'' from the sales-contract paradigm of functions and algorithms to the marriage-contract paradigm of objects and software systems. Section 1 shows that passing the Turing Test requires the computing power of objects rather than of functions, section 2 presents technical arguments to support the claim that objects have greater expressive power than functions (see [We] for more details), while section 3 examines the deep parallels between function versus object abstraction, mathematical versus scientific modeling, and rationalist versus empiricist philosophy. Section 1 shows that Turing's question-answering agents are objects whose behavior is that of embedded software systems rather than Turing machines. Proving computers intelligent requires showing that their speed as well as their functionality can simulate humans for all possible tasks. Comparing human agents with objects is shown to be both more natural and more interesting than comparing them with functions. Section 2 shows that nonserializable object behavior that cannot be expressed by any serial execution of its interface procedures is nonfunctional. An object's interface procedures are not functions because they are context-dependent (on the object's state). Software engineering is nonalgorithmic because algorithmic techniques are not powerful enough to model the behavior of software systems. Section 3 contrasts the notion of abstraction for object and function models, suggesting that the greater descriptive power of object over function abstraction reflects that of empirical over rationalist models. The debate between advocates of functional and object-oriented programming is a computational analog of the almost 2500-year-old philosophical debate between rationalists and empiricists. The elimination of legitimately observable properties of objects by function abstraction is a computational analog of the elimination of legitimately observable properties of the real world by rationalist abstraction. Models of software systems require strong object abstraction in the tradition of scientific modeling, since function abstraction is insufficient. Computer science provides a framework for comparing transformational models of functions with interactive models of objects becasue it is fundamentally a science of modeling. ==================================== REFEREED PUBLICATION AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Reasoning, modeling and component-based technology PublishedByLine: Proc. 4th Int. Conf. of Logic Programming and Automatic Programming, Springer Verlag FileName: not available Abstract: This paper demonstrates that though logic programming is as powerful as a Turing machine in what it can compute, it is less powerful in its interactive behavior. ==================================== REFEREED PUBLICATION AuthorLine: Peter Wegner, Gul Agha and Akinori Yonezawa (edited by) POC: pw@cs.brown.edu TitleLine: Research directions in concurrent object-oriented programming PublishedByLine: The MIT Press (book) FileName: not available Abstract: This book contains papers by leading researchers in the field of Concurrent Object-Oriented Programming, and is selling well, since it is the most comprehensive book on this subject at the present time. ==================================== REFEREED PUBLICATION AuthorLine: Peter Wegner, Gul Agha and Akinori Yonezawa POC: pw@cs.brown.edu TitleLine: Tradeoffs between reasoning and modeling PublishedByLine: The MIT Press FileName: not available by ftp Abstract: This paper develops the notion that reasoning and Turing machines cannot capture the notion of modeling and interaction, showing that concurrent logic programming chooses don't care nondeterminism over completeness in order to permit components to be reactive (interactive). ==================================== REFEREED PUBLICATION AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Dimensions of object-oriented modeling PublishedByLine: IEEE Computer Publication FileName: not available by ftp Abstract: It is shown that object-oriented programming is a modeling paradigm, and the role of encapsulation, distribution, concurrency, and reactiveness in object-oriented programming is examined. ==================================== REFEREED PUBLICATION AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: Concepts and paradigms of object-oriented programming (Japanese translation) PublishedByLine: not available by ftp FileName: not available Abstract: This is a book version of an 80-page paper presenting the concepts and paradigms of object-oriented programming. This paper was originally developed as an expansion of an OOPSLA keynote address, and examines design issues, concurrency models, and mathematical models of object-oriented programming. ==================================== REFEREED PUBLICATION AuthorLine: Peter Wegner POC: pw@cs.brown.edu TitleLine: New directions in the introductory computer science curriculm PublishedByLine: Proc. 1994 ACM Computer Science Conference FileName: not available by ftp Abstract: This paper reviews the history of computer science curriculum development with special emphasis on introductory courses in computer science. The coauthor (Alan Tucker) was the chairman of the committee that developed curriculum '91, the joint ACM/IEEE curriculum in computer science. ==================================== REFEREED PUBLICATION AuthorLine: B. Le Charlier and P. Van Hentenryck POC: pvh@cs.brown.edu TitleLine: Experimental evaluation of a generic abstract interpretation algorithms for prolog PublishedByLine: ACM Transactions on Programming Languages and Systems AvailableByFtpOn: ftp.cs.brown.edu FileName: u/pvh/toplas.ps Abstract: Abstract interpretation of Prolog programs has attracted many researchers in recent years partly because of the potential for optimization in Prolog compilers and partly because of the declarative nature of logic programming languages that makes them more amenable to optimization than procedural languages. Most of the work however has remained at the theoretical level, focusing on the developments of frameworks and the definition of abstract domains. This paper reports our effort to verify experimentally the practical value of this area of research. It describes the design and implementation of the generic abstract interpretation algorithm (GAIA) that we originally proposed, its instantiation to a sophisticated abstract domain containing modes, types, sharing, and aliasing, and its evaluation both in terms of performance and accuracy. The overall implementation (over 5000 lines of Pascal) has been systematically analyzed on a variety of programs and compared with its complexity analysis and specific analysis systems. ==================================== REFEREED PUBLICATION AuthorLine: P. Van Hentenryck POC: pvh@cs.brown.edu TitleLine: Scheduling and packing in the constraint language cc(FD) PublishedByLine: Intelligent Scheduling, Morgan Kaufman AvailableByFtpOn: ftp.cs.brown.edu FileName: pub/techreports/92/CS-92-43 Abstract: Constraint Logic Programming (CLP), and its generalization in the cc framework, define a class of declarative constraint languages combining nondeterministic goal-directed programming with constraint techniques over an arbitrary domain. CLP languages are particularly attractive for combinatorial search problems as they offer a short development time and a reasonable efficiency. In this paper, we present the application of cc(FD), a CLP language using consistency techniques over finite domains, to two applications: the perfect square problem and a digital signal processing (DSP) problem. The perfect square problem amounts to placing squares of different sizes in a master square in an exact manner (i.e. no empty space remains). We show a natural and very short cc(FD) program solving the problem for 21 and 24 squares in a couple of seconds. The DSP application amounts to scheduling tasks on a multiprocessor in presence of precedence, capacity, and delay constraints. The complexity of the problem is exacerbated by the non-uniform communication delays coming from the architecture which combines pipeline and master-slave processing. We present a short cc(FD) program which compares very well with a special-purpose branch and bound algorithm. Both applications show the versatility of languages such as cc(FD) for the solving of discrete combinatorial search problems. ==================================== REFEREED PUBLICATION AuthorLine: P. Van Hentenryck and V. Ramachandran POC: pvh@cs.brown.edu TitleLine: Backtracking without trailing in CLP(Rlin) PublishedByLine: Proceedings of the ACM-SIGPLAN Conference (PLDI-94) AvailableByFtpOn: ftp.cs.brown.edu FileName: pub/techreports/93/CS-93-51 Abstract: Constraint logic programming (CLP) is a generalization of logic programming where unification is replaced by constraint solving as the basic operation of the language. The combination of constraint solving and nondeterminism (approximated by backtracking) makes these languages appealing for a variety of combinatorial search problems. Existing CLP languages support backtracking by generalizing traditional Prolog implementations: modifications to the constraint system are trailed and restored on backtracking. Although simple and efficient, trailing may be very demanding in memory space, since the constraint system may potentially be saved at each choice point. This paper proposes a fundamentally new implementation scheme for backtracking in CLP languages over linear (rational or real) arithmetic. The new scheme, called semantic backtracking, does not use trailing but rather exploits the semantics of the constraints to undo the effect of newly added constraints. Semantic backtracking reduces the space complexity by an order of magnitude compared to implementations based on trailing and makes space complexity essentially independent of the number of choice points. In addition, semantic backtracking introduces negligible space and time overhead on deterministic programs. The price for this improvement is an increase in backtracking time, although constraint-solving time may actually decrease. The scheme has been implemented as part of a complete CLP system and compared analytically and experimentally with an optimized trailing implementation. Experimental results indicate that semantic backtracking produces significant reduction in memory space, while keeping the time overhead reasonably small. ==================================== REFEREED PUBLICATION AuthorLine: P. Van Hentenryck,A. Cortesi and B. Le Charlier POC: pvh@cs.brown.edu TitleLine: Type analysis of Prolog using type graphs PublishedByLine: Proceedings of the ACM-SIGPLAN Conference on Programming Lanuguage Design and Implementation (PLDI-94) AvailableByFtpOn: ftp.cs.brown.edu FileName: pub/techreports/93/CS-93-52 Abstract: Type analyis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a few. However, these optimizations often require a sophisticated type inference system capable of inferring disjunctive and recursive types and hence expensive in computation time. The purpose of this paper is to describe a type analysis system for Prolog based on abstract interpretation and type graphs (i.e. disjunctive rational trees) with this functionality. The system (about 15,000 lines of C) consists of the combination of a generic fixpoint algorithm, a generic pattern domain, and a type graph domain. The main contribution of the paper is to show that this approach can be engineered to be practical for medium-sized programs without sacrificing accuracy. The main technical contributions to achieve this result are (1) a novel widening operator for type graphs which appears to be accurate and effective in keeping the sizes of the graphs, and hence the computation time, reasonably small; (2) the use of the generic pattern domain to obtain a compact representation of equality constraints between subterms and to factor out sure structural information. ==================================== REFEREED PUBLICATION AuthorLine: A. Cortesi, B. Le Charlier and P. Van Hentenryck POC: pvh@cs.brown.edu TitleLine: Combinations of abstract domains for logic programming PublishedByLine: Proceedings of the ACM-SIGPLAN Symposium on Principles of Programming Languages (POPL-94) AvailableByFtpOn: ftp.cs.brown.edu FileName: pub/techreports/93/CS-93-13 Abstract: Abstract interpretation is a systematic methodology to design static program analysis which has been studied extensively in the logic programming community, because of the potential for optimizations in logic programming compilers and the sophistication of the analyses which require conceptual support. With the emergence of efficient generic abstract interpretation algorithms for logic programming, the main burden in building an analysis is the abstract domain which gives a safe approximation of the concrete domain of computation. However, accurate abstract domains for logic programming are often complex because of the variety of analyses to perform, their interdependence, and the need to maintain structural information. The purpose of this paper is to propose conceptual and software support for the design of abstract domains. It contains two main contributions: the notion of open product and a generic pattern domain. The open product is a new way of combining abstract domains allowing each combined domain to benefit from information from the other components through the notions of queries and open operations. The open product is general-purpose and can be used for other programming paradigms as well. The generic pattern domain PAT(R) automatically upgrades a domain D with structural information yielding a more accurate domain PAT(D) without additional design or implementation cost. The two contributions are orthogonal and can be combined in various ways to obtain sophisticated domains while imposing minimal requirements on the designer. Both contributions are characterized theoretically and experimentally and were used to design very complex abstract domains which would be very difficult to design otherwise. On this last domain, designers need only contribute about 20% (about 3,400 lines) of the complete system (about 17,700 lines). ==================================== REFEREED PUBLICATION AuthorLine: V. Ramachandran and P. Van Hentenryck POC: pvh@cs.brown.edu TitleLine: Incremental algorithms for constraint solving and entailment over rational trees PublishedByLine: Proceedings of the 13th Conference on Foundations of Software Technology and Theroretical Computer Science AvailableByFtpOn: ftp.cs.brown.edu FileName: TBD Abstract: Equations and disequations over rational trees arise naturally in the context of constraint logic programming. In this paper, we reconsider (after Colmerauer and Jaffar) the problem of solving these constraints incrementally (semi-dynamically) and consider the problem of determining entailment of these constraints with respect to a monotonically increasing constraint store of equations and disequations. The main contributions of the paper are new algorithms for disequation solving and disequality entailment. The algorithms exploit systematically three simple ideas: global caching, lazy evaluation and detection of implicit equalities. The disequation algorithm is a direct algorithm (contrary to Colmerauer's algorithm which uses unification as a subroutine). Its on-line version, which is almost-quadratic, is shown to be superior to Colmerauer's superior off-line. Incremental disequality entailment is much more subtle, and to our knowledge was not considered before. We present a direct algorithm whose off-line version is almost-quadratic, and on-line version is almost-cubic. Its key idea is to reduce disequality entailment to a Boolean combination of equality entailments. Both versions improve upon a naive indirect algorithm by an order of magnitude asymptotically. ==================================== REFEREED PUBLICATION AuthorLine: P. Van Hentenryck, O. Degimbe, B. Le Charlier and L. Olivier POC: pvh@cs.brown.edu TitleLine: The impact of granularity in abstract interpretation of prolog PublishedByLine: International Workshop on Static Analysis (WSA-93) AvailableByFtpOn: ftp.cs.brown.edu FileName: u/pvh/WSA-93-1.ps Abstract: Abstract interpretation of Prolog has received much attention in recent years leading to the development of many frameworks and algorithms. One reason for this proliferation comes from the fact that program analyses can be defined at various granularities, achieving a different trade-off between efficiency and precision. The purpose of this paper is to study this tradeoff experimentally. We review the most frequently proposed granularities which can be expressed as a two dimensional space parametrized by the form of the inputs and outputs. The resulting algorithms are evaluated on three abstract domains with very different functionalities, Mode, Prop, and Pattern to assess the impact of granularity on efficiency and accuracy. This is, to our knowledge, the first study of granularity at the algorithm level and some of the results are particularly surprising. ==================================== REFEREED PUBLICATION AuthorLine: O. Degimbe, B. Le Charlier, L. Olivier and P. Van Hentenryck POC: pvh@cs.brown.edu TitleLine: Practical efficiency of three general purpose fixpoint algorithms applied to the abstract interpretation of prolog PublishedByLine: International Workshop on Static Analysis (WSA-93) AvailableByFtpOn: ftp.cs.brown.edu FileName: u/pvh/WSA-93-2.ps Abstract: Fixpoint computation is a major issue in abstract interpretation. However, little attention has been devoted to the design and implementation of efficient general purpose fixpoint algorithms. This paper provides an experimental evaluation of several general-purpose optimization techniques: stabilization detection, manipulation of the sets of call patterns, and caching of abstract operations. All techniques can be included in a general fixpoint algorithm which can then be proven correct once for all and instantiated to a large variety of abstract semantics. For the sake of the experiments, we focus on a single abstract semantics for Prolog and shows the instantiations of the general-purpose algorithms to this semantics. The experiments are done on two abstract domains and a significant set of benchmarks programs. They seem to demonstrate the practical value of the approach. ==================================== REFEREED PUBLICATION AuthorLine: R. Cole, P. N. Klein and R. E. Tarjan POC: pnk@cs.brown.edu TitleLine: A linear-work parallel algorithm for finding a minimum spanning tree PublishedByLine: Proc. 6th ACM Sym. on Parallel Algorithms and Architectures FileName: //ftp.cs.brown.edu/pub/techreports/93/cs94_30.ps.Z Abstract: We give the first linear-work parallel algorithm for finding a minimum spanning tree. It is a randomized algorithm and requires slightly more than logarithmic expected time. It is a modification of the sequential linear-time algorithm of Klein and Tarjan. ==================================== REFEREED PUBLICATION AuthorLine: P. N. Klein, S. Rao, M. Rauch, and S. Subramanian POC: pnk@cs.brown.edu TitleLine: Faster shortest-path algorithms for planar graphs PublishedByLine: Proc. 26th Sym. on Theory of Computing FileName: //ftp.cs.brown.edu/pub/techreports/93/cs94_12.ps.Z Abstract: We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. Thus we give the first optimal algorithms for these problems. For the case where negative edge-lengths are allowed, we give an algorithm whose running time improves by a fractional polynomial on previous algorithms. We obtain corresponding improvements in the running time for finding a perfect matching in a planar bipartite graph and for maximum flow in a directed planar graph. ==================================== REFEREED PUBLICATION AuthorLine: P. N. Klein and S. Subramanian POC: pnk@cs.brown.edu TitleLine: A linear-processor, polylog-time algorithm for shortest paths in planar graphs PublishedByLine: Proc. 34th Sym. on Foundations of Computer Science FileName: //ftp.cs.brown.edu/pub/techreports/93/cs93_35.ps.Z Abstract: We give an algorithm requiring polylog time and a linear number of processors to solve single-source shortest paths in directed planar graphs, bounded-genus graphs, and two-dimensional overlap graphs. More generally, the algorithm works for any graph provided with a decomposition tree constructed using square-root-size separators. ==================================== REFEREED PUBLICATION AuthorLine: P. N. Klein and R. E. Tarjan POC: pnk@cs.brown.edu TitleLine: A randomized linear-time algorithm for finding a minimum spanning tree PublishedByLine: Journal of the ACM, Proc. 26th Sym. on Theory of Computing FileName: //ftp.cs.brown.edu/pub/techreports/93/cs93_49.ps.Z Abstract: We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons. ==================================== REFEREED PUBLICATION AuthorLine: P. N. Klein, A. K. Agrawal, R. Ravi POC: pnk@cs.brown.edu TitleLine: When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks PublishedByLine: SIAM Journal Comput. FileName: hardcopy available by request from author Abstract: We give the first approximation algorithm for the generalized network Steiner tree problem, a problem in network design. An instance consists of a network with link-costs and, for each pair {i,j} of nodes, an edge-connectivity requirement. The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within 2 log R of optimal, where R is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial min-max approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network. ==================================== REFEREED PUBLICATION AuthorLine: P. N. Klein, S. Plotkin, C. Stein and E. Tardos POC: pnk@cs.brown.edu TitleLine: Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts PublishedByLine: SIAM Journal Comput. FileName: hardcopy available by request from author Abstract: We describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. Our algorithms are much faster than previously known algorithms. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications. Leighton and Rao used uniform-capacity concurrent flow to find an approximately ``sparsest cut'' in a graph, and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical, as it required solving a large linear program. We show that their method might be practical by giving a fast randomized algorithm for their concurrent flow problem on an $m$-edge graph. Raghavan and Thompson used uniform-capacity concurrent flow to approximately solve a channel width minimization problem in VLSI. We give a fast randomized algorithm for this problem. ==================================== REFEREED PUBLICATION AuthorLine: P. N. Klein POC: pnk@cs.brown.edu TitleLine: Efficient parallel algorithms for chordal graphs PublishedByLine: SIAM Journal Comput. FileName: hardcopy available by request from author Abstract: We give the first efficient parallel algorithms for recognizing chordal graphs, finding a maximum clique and a maximum independent set in a chordal graph, finding an optimal coloring of a chordal graph, finding a breadth-first search tree and a depth-first search tree of a chordal graph, recognizing interval graphs, and testing interval graphs for isomorphism. The key to our results is an efficient parallel algorithm for finding a perfect elimination ordering. ==================================== REFEREED PUBLICATION AuthorLine: R. Tamassia and I.G. Tollis POC: rt@cs.brown.edu TitleLine: Reachability in planar digraphs with one source and one sink PublishedByLine: Theoretical Computer Science A, vol. 119 FileName: TBD Abstract: We investigate the reachability problem on spherical st-graphs, which are planar acyclic digraphs with one source and one sink. First, we show that reachability queries in can be answered in O(1) time using an O(n)-space static data structure. Next, we present a dynamic data structure that uses O(n) space and supports reachability queries and updates in O(log n) time. ==================================== REFEREED PUBLICATION AuthorLine: A. Garg and R. Tamassia POC: rt@cs.brown.edu TitleLine: Advances in graph drawing PublishedByLine: Proc. CIAC'94, Lect. notes in CS, vol.778, Springer-Verlag FileName: TBD Abstract: Overview of recent advances in graph drawing (invited lecture). ==================================== REFEREED PUBLICATION AuthorLine: R. F. Cohen and Roberto Tamassia POC: rt@cs.brown.edu TitleLine: Combine and conquer: a general technique for dynamic algorithms PublishedByLine: Proc. Eurpoean Sym., Lect. Notes in CS, vol.726, Springer-Verlag FileName: TBD Abstract: We present a general technique for dynamizing a class of problems whose underlying structure is a computation graph embedded in a tree. We introduce linear attribute grammars, which are tree-based expressions where the values at a node are calculated from the values at the parent, siblings, and/or the children of the node, and all dependencies are linear. We show that a linear attribute grammar can be dynamically maintained in a fully dynamic environment using linear space and logarithmic time per operation, and present many examples of application of our technique to dynamic graph and geometric problems. ==================================== REFEREED PUBLICATION AuthorLine: P. Bertolazzi, G. Di Battista, C. Mannino and R. Tamassia POC: rt@cs.brown.edu TitleLine: Optimal upward planarity testing of single-source digraphs PublishedByLine: Proc. European Symp., Lect. Notes in CS, vol.726, Springer-Verlag FileName: TBD Abstract: We investigate upward planarity testing of single-source digraphs: we provide a new combinatorial characterization of upward planarity, and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with n loglog n / log n processors, using O(n) space. The algorithm also constructs an upward planar drawing if the test is successful. ==================================== REFEREED PUBLICATION AuthorLine: G. Kant, G. Liotta, R. Tamassia and I.G. Tollis POC: rt@cs.brown.edu TitleLine: Area requirement of visibility representations of trees PublishedByLine: Proc. 5th Canadian Conf. on Computational Geometry FileName: TBD Abstract: We study the area requirement of visibility representations of trees in the plane, where nodes are associated with isothetic rectangles, and edges are associated with horizontally or vertically visible pairs of rectangle. We prove tight lower and upper bounds on the area of such representations, and linear-time algorithms for constructing representations with optimal area ==================================== REFEREED PUBLICATION AuthorLine: K. Miriyala, S.W. Hornick and R. Tamassia POC: rt@cs.brown.edu TitleLine: An incremental approach to aesthetic graph layout PublishedByLine: Proc. Int. Workshop on Computer-Aided Software Engineering CASE'93 FileName: TBD Abstract: A practical technique for the incremental restructuring of a drawing in a sequence of updates is investigated. The method uses a special edge-routing routing algorithm, and its effectiveness is shown with software visualization examples. ==================================== REFEREED PUBLICATION AuthorLine: J. E. Savage POC: jes@cs.brown.edu TitleLine: A model for multigrained parallelism PublishedByLine: 6th Annl. ACM Symp. on Parallel Algorithms and Architectures FileName: Copyrighted publication. Available on Request Abstract: Multi-grained parallel computers can be very effective on computationally intensive problems that have important serial and parallel components. We introduce the Mesh SuperHet, a model of this type consisting of the close coupling of a d-dimensional toroidal mesh of coarse-grained processors to a serial machine consisting of memory modules connected via a low-diameter network to a serial processor. We exhibit problems for which the Mesh SuperHet is superior to its serial or parallel components alone and develop tight performance bounds for sorting, the fast Fourier transform, and matrix multiplication. As multi-grained machines become more common, studies such as this will both reveal the fundamental limitations on such architectures and set the context for algorithm development. ==================================== REFEREED PUBLICATION Authorline: F.P. Preparata, J.S. Vitter POC: franco@cs.brown.edu TitleLine: A simplified technique for hidden-line elimination in terrains PublishedByLine: International Computational Geometry and Applications FileName: TBD Abstract: In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d+n)log^2n) time and uses O(n alpha(n)) space, where d is the size of the final display, and alpha(n) is a (very slowly growing) functional inverse of Ackermann's function. Our implementation is especially simple and practical, because we try to take full advantage of the specific geometrical properties of the terrain. The asymptotic speed of our algorithm has been improved upon theoretically by other authors, but at the cost of higher space usage and/or high overhead and complicated code. Our main data structure maintains an implicit representation of the convex hull of a set of points that can be dynamically updated in O(log^2n) time. It is especially simple and fast in our application since there are no rebalancing operations required in the tree. ==================================== Authorline: N.M. Amato, F.P. Preparata POC: franco@cs.brown.edu TitleLine: A time-optimal parallel algorithm for 3D convex hulls PublishedByLine: Algorithmica-to appear FileName: TBD Abstract: In this paper we present an O((1/ alpha) log n) time parallel algorithm for computing the convex hull of n points in R^3. This algorithm uses O(n^{1+alpha}) processors on a CREW PRAM, for any constant 0