wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (04/17/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
PROGRAMMING LANGUAGES SEMINAR
-Thursday, April 20, 1989
Mr. Scott Vorthmann, of the School of Information and
Computer Science at the Georgia Institute of
Technology, will speak on "Syntax-Directed Editor
Support for Incremental Consistency Maintenance."
TIME: 3:30 PM
ROOM: DC 1302
ABSTRACT
The technology of syntax-directed editors offers
characteristics which are ideally suited to the task of
incremental consistency maintenance. In particular,
the use of attribute grammars to provide static
semantic analysis has several specific advantages: a
fine granularity of processing, a fine granularity of
dependencies to direct that processing, caching of
derived data, and algorithms which update that data
with a minimal amount of processing. However, several
shortcomings of this approach have been identified.
The described research addresses these shortcomings
with extensions to the technology of syntax-directed
editor generation.
The principal extension is the addition of a naming
layer to the editor kernel architecture. The naming
layer supplements the tree structure provided by the
syntax with non-local references (from identifier usage
sites to declaration sites), presenting a directed-
graph as the structure now underlying the attribute
propagation. Naturally, the naming layer must map
certain syntactic modifications to appropriate
adjustments to this binding graph, and must produce a
unique state of the binding graph for a given syntactic
state.
The behaviour of the naming layer with respect to the
syntactic and attribute grammar layers is specified by
a Naming Specification Language, which is simply a set
of extensions to an existing attribute grammar
notation. NSL supports the designation of name
declaration and reference sites, the designation of
productions that embody scopes, and specification of
visibility of names between related scopes. The
visibility mechanisms provided by NSL are its most
important features.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (05/05/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
PROGRAMMING LANGUAGES SEMINAR
-Monday, May 8, 1989
Mr. Richard Stroobosscher, a graduate student of the
Dept. of Computer Science, University of Waterloo, will
do a Master's Essay Presentation on ``Light Weight
Processes in a Shared Memory Multiple Processor
Environment.''
TIME: 1:30 p.m.
ROOM: DC 1304
ABSTRACT
Light-weight processes are a mechanism for expressing
medium-grain concurrency. When the cost of
manipulating light-weight processes approaches the cost
of manipulating procedures, they become a viable
alternative to procedures. Light-weight processes have
the added benefit of being able to take advantage of
any parallelism in the hardware on which they are
implemented.
This talk discusses an engineering exercise in the
implementation of light-weight processes for the C
programming language. The light-weight processes are
provided through a library of functions called the
uSystem.
The uSystem is designed to be portable across various
flavours of the UNIX operating system. On single
processor machines, the uSystem time-slices light-
weight processes, but on multiple processor machines,
the uSystem executes light-weight processes in
parallel.
The single processor uSystem is implemented on various
VAXen, Sun 68020s, a Symmetry 80386 and two MIPS
processors. The uSystem is capable of passing 16 byte
messages between processes at 120 microseconds on some
of these machines. The multiple processor uSystem is
implemented on a Symmetry with 6 80386 processors.
Program execution has shown linear improvement with the
addition of more processors.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (06/22/89)
Glasgow, Scotland, will speak on
``Some Thoughts on the Algebraic Theory of Concurrent Process.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
PROGRAMMING LANGUAGES SEMINAR
-Thursday, June 29, 1989
Professor Faron Moller, University of Strathclyde,
Glasgow, Scotland, will speak on "Some Thoughts on the
Algebraic Theory of Concurrent Process."
TIME: 3:30 p.m.
ROOM: DC 1302
ABSTRACT
In this talk, we consider several aspects of the
mathematical foundations of processes algebras.
Starting from the basic notion of finite automata and
regular expressions, we introduce parallelism (in the
form of the so-called shuffle operator), and discuss
some results and conjectures on the existence and
uniqueness of the decompositions of machines.
Next, we argue for a tightening of the semantics of
finite automata, and move from a discussion of trace
equivalence to the more restrictive notion of
bisimulation equivalence. We ask the same questions on
decomposability, and find ourselves able to prove more
here than in the language equivalence case.
We then consider properties of equational
axiomatisations for our equivalence and show that no
finite characterisation can exist. We extend our result
to cover all reasonable notions of equivalence, and use
this as an explanation to the difficulty faced in
trying to find algebraic characterisations of sensible
noninterleaving semantic equivalences.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (10/26/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
PROGRAMMING LANGUAGES SEMINAR
-Friday, November 3, 1989
Professor R.A. Frost, School of Computer Science, University
of Windsor will speak on ``Use of Algebraic
Identities in the Calculation of Programs Constructed as
Executable Specifications of Attribute Grammars.''
TIME: 1:30 p.m.
ROOM: DC 1304
ABSTRACT
There is a growing interest in the notion that programs can
be `calculated' by transforming executable specifications to
more efficient provably equivalent forms using algebraic
identities. Such calculation is facilitated if the
executable specifications are variable-free and have no
explicit recursion. This can be achieved by expressing
specifications as compositions of higher order functions
which capture common patterns of computation. These
specifications can then be transformed using algebraic
identities that have been proven for the higher order
functions. In this seminar we describe how this approach can
be used in the calculation of programs constructed as
executable specifications of attribute grammars. Programs
are regarded as language processors and are calculated using
algebraic identities proven for higher order ``language
processor generators.'' The approach is tolerant of
inaccurate and incomplete initial specifications and is
`environmentally friendly' in that there is little wasted
effort. We give an example showing how a program which
converts arbitrary expressions of propositional logic to
clausal form can be transformed to an efficient theorem
prover for propositional logic; the original executable
attribute grammar uses synthesised attributes only, the more
efficient form uses inherited as well as synthesised
attributed.
The programming environment that we have built may be
thought of as a realization of a suggestion made by Knuth in
1971 that executable attribute grammars might provide a
viable declarative programming language. The integration of
this idea with transformations based on algebraic identities
as suggested by Backus and Bird has been greatly facilitated
by the availability of Turner's higher order, pure, lazy
functional programming language Miranda.* The contribution
-----------
Miranda is a trademark of Research Software Ltd.
- 2 -
of the work described in the seminar is to bring these
things together to form a viable new programming paradigm.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (02/07/90)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
PROGRAMMING LANGUAGES SEMINAR
-Thursday, February 15, 1990
Laurie Hendren, will speak on ``Parallelizing Programs
with Recursive Data Structures.''
TIME: 3:30 p.m.
ROOM: DC 1304
ABSTRACT
Interference estimation is a useful tool in developing
parallel programs and is a key aspect of automatically
parallelizing sequential programs. Interference
analysis and disambiguation mechanisms for programs
with simple data types and arrays have become a
standard part of parallelizing and vectorizing
compilers. However, efficient and implementable
techniques for interference analysis in the presence of
dynamic data structures have yet to be developed.
We have been addressing the problem of estimating
interference and parallelizing programs in the setting
of an imperative language that supports dynamic data
structures. By focusing on analysis methods for
recursively-defined pointer data structures such as
trees and DAGs, we developed efficient and
implementable interference analysis tools and
parallelization techniques.
In this talk, I will present an overview of the
approach including:
(1) an introduction to the problem,
(2) a description of the interference analysis tools
of the interference analysis tools and
parallelization techniques, and
(3) a summary of some results from experiments on
the BBN Butterfly.