Software Engineering Commons^™

Grace's Inheritance, James Noble, Andrew P. Black, Kim B. Bruce, Michael Homer, Timothy Jones

Computer Science Faculty Publications and Presentations

This article is an apologia for the design of inheritance in the Grace educational programming language: it explains how the design of Grace’s inheritance draws from inheritance mechanisms in predecessor languages, and defends that design as the best of the available alternatives. For simplicity, Grace objects are generated from object constructors, like those of Emerald, Lua, and Javascript; for familiarity, the language also provides classes and inheritance, like Simula, Smalltalk and Java. The design question we address is whether or not object constructors can provide an inheritance semantics similar to classes.

A Constraint Language For Static Semantic Analysis Based On Scope Graphs, Hendrik Van Antwerpen, Pierre Néron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth

Computer Science Faculty Publications and Presentations

In previous work, we introduced scope graphs as a formalism for describing program binding structure and performing name resolution in an AST-independent way. In this paper, we show how to use scope graphs to build static semantic analyzers. We use constraints extracted from the AST to specify facts about binding, typing, and initialization. We treat name and type resolution as separate building blocks, but our approach can handle language constructs—such as record field access—for which binding and typing are mutually dependent.We also refine and extend our previous scope graph theory to address practical concerns including ambiguity checking and support for …

Object-Oriented Programming: Some History, And Challenges For The Next Fifty Years, Andrew P. Black

Computer Science Faculty Publications and Presentations

Object-oriented programming is inextricably linked to the pioneering work of Ole-Johan Dahl and Kristen Nygaard on the design of the Simula language, which started at the Norwegian Computing Centre in the Spring of 1961. However, object-orientation, as we think of it today—fifty years later—is the result of a complex interplay of ideas, constraints and people. Dahl and Nygaard would certainly recognize it as their progeny, but might also be amazed at how much it has grown up. This article is based on a lecture given on 22nd August 2011, on the occasion of the scientific opening of the Ole-Johan …

Interactive Ambient Visualizations For Soft Advice, Emerson Murphy-Hill, Titus Barik, Andrew P. Black

Computer Science Faculty Publications and Presentations

Some software packages offer the user soft advice: recommendations that are intended to help the user create high quality artifacts, but which may turn out to be bad advice. It is left to the user to determine whether the soft advice really will improve quality, and to decide whether or not to adopt it. Visualizations can help the user in making this decision, but we believe that conventional visualizations are less than ideal. In this paper, we describe an interactive ambient visualization to help users identify, understand and interpret soft advice.

Our visualization was developed to help programmers interpret code …

Resizable, Scalable, Concurrent Hash Tables Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Presentation focusing on software synchronization, thread locking, transactional memory, and relativistic programming. Hash table algorithms are presented with examples of relativistic list insertion and removal, and related data structures. Existing approaches are compared to new methodologies and future work with relativistic data structures.

A Relativistic Enhancement To Software Transactional Memory, Philip William Howard, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Relativistic Programming is a technique that allows low overhead, linearly-scalable concurrent reads. It also allows joint access parallelism between readers and a writer. Unfortunately, it has so far been limited to a single writer so it does not scale on the write side. Software Transactional Memory (STM) is a technique that allows programs to take advantage of disjoint access parallelism on both the read-side and write-side. Unfortunately, STM systems have a higher overhead than many other synchronization mechanisms so although STM scales, STM starts from a lower baseline. We propose combining relativistic programming and software transactional memory in a way …

A Comparison Of Relativistic And Reader-Writer Locking Approaches To Shared Data Access, Philip William Howard, Josh Triplett, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper explores the relationship between reader-writer locking and relativistic programming approaches to managing accesses to shared data. It demonstrates that by placing certain restrictions on writers, relativistic programming allows more concurrency than reader-writer locking while still providing the same isolation guarantees. Relativistic programming also allows for a straightforward model for reasoning about the correctness of programs that allow concurrent read-write accesses.

Haskell For The Cloud, Andrew P. Black

Computer Science Faculty Publications and Presentations

We present Cloud Haskell, a domain specific language for developing programs for a distributed-memory computing environment. Implemented as a shallow embedding in Haskell, it provides a message-passing communication model, inspired by Erlang, without introducing incompatibility with Haskell's established sharedmemory concurrency. A key contribution is a method for serializing function closures for transmission across the network. Cloud Haskell has been implemented; we present example code and some preliminary performance measurements.

Better Refactoring Tools For A Better Refactoring Strategy, Andrew P. Black

Computer Science Faculty Publications and Presentations

Refactoring tools can improve the speed and accuracy with which we create and maintain software – but only if they are used. In practice, tools are not used as much as they could be; this seems to be because they do not align with the refactoring strategy preferred by the majority of programmers: floss refactoring. We propose five principles that characterize successful floss refactoring tools – principles that can help programmers to choose the most appropriate refactoring tools and also help toolsmiths to design more usable tools.

A Framework For Relationship Pattern Languages, Sudarshan Murthy, David Maier

Computer Science Faculty Publications and Presentations

A relationship pattern is an abstraction of a recurring need when establishing relationships among information elements in specific contexts. By developing or leveraging a relationship pattern, modelers can solve a class of problems once and describe many relationship types at once. We have developed a framework for specifying relationship patterns and pattern languages (sets of patterns) in both modeling-language-independent and modeling-language-specific ways. We describe this framework both informally and formally. We provide examples of some commonly observed relationship patterns and show how to use them in ER with the help of a relationship pattern language called Exemplar. We also provide …

Scalable Concurrent Hash Tables Via Relativistic Programming, Josh Triplett

Computer Science Faculty Publications and Presentations

Existing approaches to concurrent programming often fail to account for synchronization costs on modern shared-memory multipro- cessor architectures. A new approach to concurrent programming, known as relativistic programming, can reduce or in some cases eliminate synchronization overhead on such architectures. This approach avoids the costs of inter-processor communication and memory access by permitting processors to operate from a relativistic view of memory provided by their own caches, rather than from an absolute reference frame of memory as seen by all processors. This research shows how relativistic programming techniques can provide the perceived advantages of optimistic synchronization without the useless parallelism …

Refactoring Tools: Fitness For Purpose, Emerson Murphy-Hill, Andrew P. Black

Computer Science Faculty Publications and Presentations

Refactoring tools can improve the speed and accuracy with which we create and maintain software -- but only if they are used. In practice, tools are not used as much as they could be: this seems to be because sometimes they do not align with the refactoring tactic preferred by the majority of programmers, a tactic we call floss refactoring. We propose five principles that characterize successful floss refactoring tools -- principles that can help programmers to choose the most appropriate refactoring tools and also help toolsmiths to design tools that fit the programmer's purpose.

Cache Coherence Protocol Verification Using Ωmega, Ki Yung Ahn

Computer Science Faculty Publications and Presentations

We verify some correctness properties of the DASH cache coherence protocol using Ωmega. Ωmega is a language with a rich type system featuring GADTs, type functions, and user-guided type checking rules. Cache coherence protocols have both safety properties and liveness properties. We show how to describe some of the safety properties of DASH cache coherence protocol in mega. Since liveness properties are not easily expressed by types, we investigate invariants sufficient to imply some of the liveness properties of concern, and assert those invariants as well in the type system of Ωmega. Using Ωmega, we can have both a working …

A Pattern Language For Extensible Program Representation, Andrew P. Black, Daniel Vainsencher

Computer Science Faculty Publications and Presentations

For the last 15 years, implementors of multiple view programming environments have sought a single code model that would form a suitable basis for all of the program analyses and tools that might be applied to the code. They have been unsuccessful. The consequences are a tendency to build monolithic, single-purpose tools, each of which implements its own specialized analyses and optimized representation. This restricts the availability of the analyses, and also limits the reusability of the representation by other tools. Unintegrated tools also produce inconsistent views, which reduce the value of multiple views. This article describes a set of …

Toward A Sound Integration Of Isabelle With A Combined Decision Procedure, Tom Harke

Computer Science Faculty Publications and Presentations

I present work on a project to integrate Isabelle, an extremely versatile interactive proof assistant, with a combined decision procedure, the Cooperating Validity Checker (CVC). Isabelle is sound and flexible, however it is often tedious to use. CVC is fully automatic, but only handles decision problems expressible over a relatively weak set of theories including linear arithmetic, uninterpreted functions, data types, and firstorder quantifier-free logic. My goal is to increase the amount of automation in Isabelle, by making it use CVC as an oracle for such problems, but without compromising Isabelle’s soundness.

In this paper I report on the progress …

A Browser For Incremental Programming, Andrew P. Black

Computer Science Faculty Publications and Presentations

Much of the elegance and power of Smalltalk comes from its programming environment and tools. First introduced more than 20 years ago, the Smalltalk browser enables programmers to “home in” on particular methods using a hierarchy of manually-defined classifications. By its nature, this classification scheme says a lot about the desired state of the code, but little about the actual state of the code as it is being developed. We have extended the Smalltalk browser with dynamically computed virtual categories that dramatically improve the browser’s support for incremental programming. We illustrate these improvements by example, and describe the algorithms used …

Implementing Infopipes: The Sip/Xip Experiment, Calton Pu, Galen Swint, Charles Consel, Younggyun Koh, Ling Liu, Koichi Moriyama, Jonathan Walpole, Wenchang Yan

Computer Science Faculty Publications and Presentations

We describe an implementation of the Infopipe abstraction for information flow applications. We have implemented software tools that translate the SIP/XIP variant of Infopipe specification into executable code. These tools are evaluated through the rewriting of two realistic applications using Infopipes: a multimedia streaming program and a web source combination application. Measurements show that Infopipe-generated code has the same execution overhead as the manually written original version. Source code of Infopipe version is reduced by 36% to 85% compared to the original.

Gscope: A Visualization Tool For Time-Sensitive Software, Ashvin Goel, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper describes gscope, a visualization tool for time-sensitive applications. Gscope provides an oscilloscope-like interface that can be integrated with applications. It focuses on software visualization and is thus designed to handle various types of signal waveforms, periodic or event-driven, in single or multithreaded environments as well as local or distributed applications. Gscope helps in visually verifying system correctness and modifying system parameters and thus can complement standard debugging techniques and be used to build compelling software demos. Initial experiments with using gscope show that the library has low overhead.

Control Challenges In Multi-Level Adaptive Video Streaming, Dylan Mcnamee, Charles Krasic, Kang Li, Ashvin Goel, Erik Walthinsen, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Streaming video is one of the fastest-growing applications of the Internet. The Internet’s diversity and dynamism demands that video streams adapt to ensure maximum quality at all times. This paper describes the control challenges we have encountered in the Quasar project’s “multi-level” adaptive streaming video player. We first describe the framework and environment of the player. This framework uses software feedback to control resource allocation as well as the quality of media delivery. We present the control challenges raised by our framework, which include horizontal and vertical feedback composition, difficult to model systems, and unpredictable, non-linear actuators. We describe some …

Adaptive Prefetching For Device-Independent File I/O, Dan Revel, Dylan Mcnamee, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Device independent I/O has been a holy grail to operating system designers since the early days of UNIX. Unfortunately, existing operating systems fall short of this goal for multimedia applications. Techniques such as caching and sequential read-ahead can help mask I/O latency in some cases, but in others they increase latency and add substantial jitter. Multimedia applications, such as video players, are sensitive to vagaries in performance since I/O latency and jitter affect the quality of presentation. Our solution uses adaptive prefetching to reduce both latency and jitter. Applications submit file access plans to the prefetcher, which then generates I/O …

Benchmarking Parallel Machines Via A Software Architecture, Srikanth Kambhatla, Jon Inouye, Jonathan Walpole

Computer Science Faculty Publications and Presentations

The diversity in parallel architectures and the programming styles induced thereof, make benchmarking of parallel machines a hard problem. Current benchmarking techniques are limited in applicability due to the issues of portability. We present a different approach to benchmarking parallel machines, which would make the resulting benchmarks portable, easy to use and widely applicable. The approach involves the use of a software architecture to mask the diversities of the underlying architectures. The benchmarks are based on the Linda Tuple Space, and is called BeLinda. In this report, we motivate the use of a software architecture, give a specification of the …