OOPSLA 12: Higher-Order, Continuations, Futures

Thu 10:30-12:00 pm - Ponderosa A
Random testing for higher-order, stateful programs
Casey Klein, Northwestern University, United States
Matthew Flatt, University of Utah, United States
Robert Bruce Findler, Northwestern University, United States

Testing is among the most effective tools available for finding bugs. Still, we know of no automatic technique for generating test cases that expose bugs involving a combination of mutable state and callbacks, even though objects and method overriding set up exactly that combination. For such cases, a test generator must create callbacks or subclasses that aggressively exercise side-effecting operations using combinations of generated objects.

This paper presents a new algorithm for randomly testing programs that use state and callbacks. Our algorithm exploits a combination of contracts and environment bindings to guide the test-case generator toward interesting in- puts. Our prototype implementation for PLT Scheme (which has a Java-like class system, but with first-class classes as well as gbeta-like augmentable methods) uncovered dozens of bugs in a well-tested and widely used text-editor library.

We describe our approach in a precise, formal notation, borrowing the techniques used to describe operational semantics and type systems. The formalism enables us to provide a compact and self-contained explanation of the core of our technique.

The Two-State Solution: Native and Serializable Continuations Accord
Jay McCarthy, Brigham Young University, United States

Continuation-based Web servers provide advantages over traditional Web application development through the increase of expressive power they allow. This leads to fewer errors and more productivity for the programmers that adopt them. Unfortunately, existing implementation techniques force a hard choice between scalability and modularity.

Our technique allows a smoother path to scalable, continuation-based Web programs. We present a modular program transformation that allows scalable Web applications to use third-party, higher-order libraries with higher-order arguments that cause Web interaction. Consequently, our system provides existing Web applications with more scalability through significantly less memory use than the traditional technique.

Back to the Futures: Incremental Parallelization of Existing Sequential Runtime Systems
James Swaine, Northwestern University, United States
Kevin Tew, University of Utah, United States
Peter Dinda, Northwestern University, United States
Robert Bruce Findler, Northwestern University, United States
Matthew Flatt, University of Utah, United States

Many language implementations, particularly for high-level and scripting languages, are based on carefully honed runtime systems that have an internally sequential execution model. Adding support for parallelism in the usual form — as threads that run arbitrary code in parallel — would require a major revision or even rewrite to add appropriate and efficient locking and communication. We describe an alternative approach to incremental parallelization of runtime systems. This approach can be applied inexpensively to many sequential runtime systems, and we demonstrate its effectiveness in the PLT Scheme runtime system and Parrot virtual machine. Our evaluation assesses both the performance benefits and the developer effort needed to implement our approach. We find that incremental parallelization can provide useful, scalable parallelism on commodity multicore processors at a fraction of the effort required to implement conventional parallel threads.

Keywords: Scheme, functional programming, parallel programming, runtime systems


2009 Highlights

Barbara Liskov

In a reprise of her ACM Turing Award lecture, Barbara Liskov discusses the invention of abstract data types, the CLU programming language, clusters, polymorphism, exception handling, iterators, implementation inheritance, type hierarchies, the Liskov Substitution Principle, polymorphism, and future challenges such as new abstractions, parallelism, and the Internet.

Watch the video on InfoQ.

More Highlights