Computer Science Department
School of Computer Science, Carnegie Mellon University
A Denotational Approach to Measuring
Kathryn Van Stone
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.