Kathryn Van Stone

A Denotational Approach to Measuring Complexity in Functional Programs Degree Type: Ph.D. in Computer Science
Advisor(s): Stephen Brookes
Graduated: August 2003

Abstract:

Functional languages are considered useful in part because their applicative structure makes it easier to reason about the value returned by a program (its extensional behavior). When one wants to analyze intensional behavior, such as the time a program takes to run, some of the advantages of functional languages turn into disadvantages. In particular, most functional languages treat functional types as standard data types; however, the time it takes to use a functional type (that is, applying it to a value) depends not only on the type but also on the applied value. Also, a number of functional languages use lazy data types, so that we may need to handle cases where parts of a data value do not need to be evaluated. The time it takes to work with such data types depends not only on the type itself but how much of it has already been examined. It is particularly difficult to reason compositionally, in a syntax-directed manner, about intensional behavior of such programs.

In this dissertation we develop a compositional semantics for functional programs that allows us to analyze the time a program takes to run (in terms of the number of times certain operations are required). Our system uniformly handles both higher-order types and lazy types, by using internal costs (time needed to use an expression) as well as external costs (time needed to evaluation an expression). We create semantics for programs using either call-by-value evaluation strategy (where arguments are always evaluated) or call-by-name (where arguments are only evaluated when used). The technique we use to create the semantic functions is almost identical for both evaluation strategies and should be easily adjustable to other languages.

We then use the created semantics in several ways. First, we use the semantics to directly relate programs based on their intensional behavior. We also examine some example programs and compare their behavior with call-by-value and call-by-name evaluation. Lastly, we examine a more complex program, pattern matching using continuations, and derive some nonintuitive results.

Thesis Committee:
Stephen Brookes (Chair)
Frank Pfenning
Dana Scott
Carl Gunter (University of Pennsylvania)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Functional languages, denotational semantics, complexity, intensional semantics, call-by-value, call-by-name,operational semantics, time analysis