Subject: Semantics Seminar Schedule
From: Mitchell Wand (wand@ccs.neu.edu)
Date: Fri Mar 09 2001 - 09:54:52 EST
NU Programming Languages Seminar
Wednesday, March 14, 2001
149 Cullinane Hall, Northeastern University
(building 9 on the map at http://www.neu.edu/maps/maps.html)
Jens Palsberg (Purdue University) will present
Efficient and Flexible Matching of Recursive Types
(Joint work with Tian Zhao; presented at LICS 2000)
Abstract:
Equality and subtyping of recursive types have been studied in
the 1990s by Amadio and Cardelli; Kozen, Palsberg, and
Schwartzbach; Brandt and Henglein; and others. Potential
applications include automatic generation of bridge code for
multi-language systems and type-based retrieval of software
modules from libraries. Auerbach, Barton, and Raghavachari
advocate a highly flexible combination of matching rules for
which there, until now, are no efficient algorithmic techniques.
In this paper, we present an efficient decision procedure for a
notion of type equality that includes unfolding of recursive
types, and associativity and commutativity of product types, as
advocated by Auerbach et al. For two types of size at most n,
our algorithm decides equality in O(n^2) time. The algorithm
iteratively prunes a set of type pairs, and eventually it
produces a set of pairs of equal types. In each iteration, the
algorithm exploits a so-called coherence property of the set of
type pairs produced in the preceding iteration. The algorithm
takes O(n) iterations each of which takes O(n) time, for a total
of O(n^2) time.
This archive was generated by hypermail 2b28 : Fri Mar 09 2001 - 09:55:21 EST