May 7, 1997 Meeting

10:00am Philip Wadler : How to add laziness to a strict language, without even being odd

It's easy to add laziness to a strict language. A number of schemes have been proposed, all variants of the following idea: add a type constructor for suspensions, and language constructs to delay and force evaluation. However, although easy to understand and implement, these schemes are not necessarily easy to use. In particular, every scheme I know of encourages a style of programming that forces more evaluation than traditional lazy languages (I call this style odd), and discourages a style of programming that delays evaluation as in traditional lazy languages (I call this style even).

This talk explicates the two styles, showing how the odd style is easy to encode in the traditional `delay' and `force' syntax, while the even style is harder to encode. It then presents a new `lazy' syntax, and shows how the even style is easy to encode in this syntax, while the odd style is harder to encode. The new `lazy' syntax is defined by translation into the `delay-force' syntax. Comparisons are drawn with two other syntaxes, one used in CAML and one proposed by Chris Okasaki. Standard ML is taken as the strict language to be extended with lazy constructs.

10:45am Richard Kelsey : Engines and hierarchical schedulers

Engines [1] are a simple abstraction of timed preemption. We extend them to include mechanisms for synchronization, mutual exclusion, and handling asynchronous events. Engines give programmers control over the scheduling of multiple threads of execution. They have two big advantages over traditional threads: engines can be nested (engine A runs engine B which in turn runs engine C) and running an engine is completely synchronous for the caller. The first advantage makes it possible to write user-level schedulers and the second makes it easy. Our extensions make engines a practical alternative to conventional threads and are used in the current release of Scheme 48.

[1] Abstacting timed preemption with engines, Haynes and Friedman, Computer Languages 12(2), 1987.

11:30am Break

11:45am Daniel C. Wang : The Zephyr Abstract Syntax Description Language (ASDL)

In this talk I will describe the Abstract Syntax Description Language, a language for specifying tree like data structures in an implementation language independent way. I will also outline a tool that automatically translates an ASDL specification into equivalent C, C++, Java, and ML data structures.

The purpose of ASDL is to provide a method to describe compiler intermediate representations and to automatically generate infrastructure needed from those descriptions. This reduces compiler implementation effort and allows research groups to share existing compiler technology such as code generators and optimizers. Jeff Korn will also demo a browser/editor that is able to graphically manipulate and inspect ASDL trees. This work is part of the larger Zephyr National Compiler Infrastructure.

12:00pm Lunch

1:15pm New Business

1:20pm Riccardo R. Pucella : Modular User Interfaces Through Reactive Controllers

We present a compositional framework for writing user interfaces, where the interactive components are described via physical views and controllers. The physical view of a component interacts with the user, providing feedback, while the controller interacts with other components of the interface and the underlying windowing system, and drives the physical view of the component. While this idea is hardly new, the interest of this framework is that it allows one to program controllers (which are fundamentally reactive) in a reactive language. We provide examples of common controllers and show how they may be composed. Along the way, we discuss some issues surrounding the choice of a reactive language to describe controllers for interactive components.

This is joint work with John Reppy.

1:50pm Break

2:00pm David McAllester : On the cubic bottleneck in subtyping and flow analysis

We prove that certain data-flow and control-flow problems are 2NPDA-complete. This means that these problems are in the class 2NPDA and that they are hard for that class. The fact that they are in 2NPDA demonstrates the richness of the class. The fact that they are hard for 2NPDA can be interpreted as evidence they can not be solved in sub-cubic time --- the cubic time decision procedure for an arbitrary 2NPDA problem has not been improved since its discovery in 1968.

This is joint work with Nevin Heintze.

2:45pm Break

3:00pm Niki Afshartous : First-class conditional synchronization in CML

First-class synchronous operations (events) as defined in Concurrent ML are useful in defining abstract operations that represent synchronous protocols. As shown in [Reppy92], events can be used to define the abstract interface of the RPC protocol or a multicast channel where the synchronous nature of the interface is preserved. Since events are represented by a data type, event values can be passed to operators (i.e. select) that act on synchronous operations.

In this talk we suggest an extension of the concept of a first-class synchronous operation. By associating a boolean condition with an event we derive a first-class value that corresponds to a conditional synchronization point. Thus offering greater flexibility and means of abstraction in managing concurrency.

To only re-evaluate synchronization conditions when necessary we propose a static analysis that identifies for the run-time system those expressions that could affect the value of a synchronization condition. The static analysis therefore precludes polling of synchronization conditions.

3:45pm Talks End