May 7, 1997 Meeting
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
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