Background on the Workshop


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 rather 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 such problems. However, there has been little synergy between the various pockets of researchers conducting this work. The groups come from diverse communities, speak distinct technical languages, and have quite different perspectives on the core phenomena.

Thus, the idea behind the workshop was 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 Workshop

The quality of the talks, both invited and contributed, turned out to be very high. Topics covered in presentations included: While no synergistic miracles occured, there were apparent themes that cut across talks from different areas. For example:

Back to the list of talks