Foundations of Programming Meetings 1995
School of Computer Science and ITUniversity of Nottingham
LR(1) parsing is traditionally implemented in an imperative way by making use of shift-reduce tables. Using a functional programming language makes it possible to implement LR(1) parsing in a declarative way. The main contribution of the paper is the following: the shift-reduce tables which traditionally drive the parsing process are not needed any more. By introducing a recursive data structure which corresponds to the LR(0) machine of an LR(1) grammar, we can simply use pattern matching to drive the parsing process. This technique results in time-space efficient functional LR(1) parsers. Furthermore we claim that our declarative approach gives much more insight in the problem domain of LR(1) parsing.
This talk is based upon joint work with Doaitse Swierstra (Utrecht).
The TIM (three instruction machine) is an elegant abstract architecture for
the implementation of lazy functional languages, in particular due to its low
closure creation cost. However, one problem with this kind of architecture is
that it suffers from a very high rate of heap-storage allocation, incurring
frequent garbage collections and reducing overall efficiency on cached memory
and virtual memory systems. This talk will briefly describe a technique that
mitigates the problem, and also gives some simple experimental results.
In functional programming, a popular approach to building recursive
descent parsers is to model parsers as functions, and define
higher-order functions (or combinators) that implement grammar
constructions such as sequencing, alternation, and repetition.
Such parsers are well-known to form a monad, an algebraic structure
from mathematics that has proved useful in addressing a number of
computational problems. The aim of this talk is to give an
introduction to the monadic approach to building parsers, and outline
some of the benefits that result from using monads. No prior knowledge
of parser combinators or monads is assumed. Indeed, this talk can also
been seen as a first introduction to the use of monads in programming.
This talk is based upon joint work with Erik Meijer (Utrecht).
Functional languages like ML and Haskell allow many different
types of objects to be used as first-class values, for
example, to be passed as arguments or results of functions, or
to be stored as components of data structures. The same
languages also offer parametric polymorphism, which
allows the definition and use of general functions that behave
uniformly over a range of different types. But the combination
of these features is not supported - polymorphic values are not
first-class.
In this talk, we question the need for such a restriction. Exploiting
the relationship between types and logic, we develop an extension of
Haskell that enables us to express many applications of both
first-class polymorphism and abstract datatypes. The most obvious result
is a more expressive language, but there are also longer-term
implications for future language design.
As my final-year project at Nottingham Trent University, I implemented the
front-end of a compiler for Gordon, a purely functional language inspired
by Gofer and Haskell. In this talk I will give an overview of the aims of
the project and the phases of the compiler that were implemented, with particular
focus on the offside rule and the translation of expressions into a core language.
Bisimilarity (also known as `applicative bisimulation') has
attracted a good deal of attention as an operational equivalence for
lambda-calculi. It approximates or even equals Morris-style contextual
equivalence and admits proofs of program equivalence via co-induction. It has
an elementary construction from the operational definition of a language. We
consider bisimilarity for one of the typed object calculi of Abadi and
Cardelli. By defining a labelled transition system for the calculus in the
style of Crole and Gordon and using a variation of Howe's method we establish
two central results: that bisimilarity is a congruence, and that it equals
contextual equivalence. So two objects are bisimilar iff no amount of
programming can tell them apart. Our third contribution is to show that
bisimilarity soundly models the equational theory of Abadi and Cardelli. This
is the first study of operational equivalence for an object calculus and the
first application of Howe's method to subtyping. By these results, we intend
to demonstrate that operational methods are a promising new direction for the
foundations of object-oriented programming.
The abstraction mechanisms of functional languages can be powerful tools in the
development of Graphical User Interfaces (GUIs). These tools can be used both
to construct reusable graphical components, and also to specify how these
components are composed to form a GUI. This talk will describe an extension of
the Hugs functional programming system to support the construction of GUIs.
Particular focus will be given to the implementation of this system, and also
to the various high-level abstractions for structuring GUIs.