[Prev][Next][Index][Thread]

DIMACS Workshop on Computational Complexity and Programming




[------ The Types Forum ------- http://www.dcs.gla.ac.uk/~types ------]


[Theory is often broken into semantics-based and complexity-based.
This call is noteworthy for its emphasis on seeking a good
complexity theory for languages, such as ML, that already have a
good semantic theory.  --  Philip Wadler, moderator, The Types Forum]

  DIMACS Workshop on Computational Complexity and Programming Languages
		            July 25 - 26, 1996  
                  RUTCOR, Busch Campus, Rutgers University 

                   Organizers: Bruce Kapron and Jim Royer
          Email: bmkapron@csr.csc.uvic.ca, royer@top.cis.syr.edu


Background

The theory of programming languages is one of the most technically
sophisticated theoretical areas in computing, and, for all its
abstractness, it has been reasonably successful in having its
insights applied in practice.  Most successes in programming
language theory have been in studying the input/output behavior of
programs, procedures, etc.  The successes in studying other aspects
of the behavior of programs (e.g., their time and space complexity)
have been extremely limited-especially in regard to more advanced
programming constructs.  For example, while ML is a wonderful
language in which to state algorithms, there is no adequate
theoretical support for the complexity analysis of ML programs and
modules.  This is in part due to the fact that ML includes features
such as higher-type procedures for which there is only a rudimentary
theory of their computational complexity.  For another example,
program specifications can be very detailed and formal when it comes
to laying out requirements for module interfaces and such, but in
the matter of stating performance specifications (e.g., time
complexity requirements) one has to resort to loose informal
narratives.  This is weak engineering, but it is the result of weak
scientific support -- there is currently no precise way to talk
about the computational complexity of a module or an ``object.''

There has been scattered work in the past few years in extending the
theories of programming languages and computational complexity to
deal with these problems.  However, there is little synergy between
the various pockets of researchers working on these problems.  The
groups come from very different communities, speak different
technical languages, and have quite different perspectives on the
core phenomena.

Workshop Goals

The aim of the workshop is to bring together researchers in
computational complexity and in programming languages to start a
discussion between the various parties, explain each other's
concerns to one another, define problem areas, and possibly start
some collaborations.

The planned format consists of a series of invited talks on the 25th
on a broad range of topics, concluding in the afternoon with a
pannel discussion.  The morning of the 26th will be general
discussion of problem areas, general goals, and particular problems
of interest.  In addition we hope to schedule an evening rump
session on the 25th for participants to report on technical results.