CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
This thesis is about the theory and practice of intensional semantics. Traditional denotational models of programming languages are usually extensional in that they concern themselves only with inputoutput properties of programs. The meaning of a program is typically taken to be a function from input to output containing no information about the way that function computes its result. In an intensional denotational semantics, the meaning of a program is an object embodying aspects of the computation strategy. The structure of the object varies, depending on the language one models and the intended usage. For instance, previous intensional semantics have been developed using functions on richer domains, pairs of a function and a computation strategy, and sequential algorithms, and they were used to reason about efficiency, complexity, order of evaluation, degrees of parallelism, efficiency-improving program transformations, and so on. In the first part of this thesis, we develop an intensional semantics based on abstract circuits. A program is mapped to a circuit, whose dimensions tell us how much parallel work and time is required to execute the program. We relate the circuit dimensions to various execution strategies, and to more traditional models of parallel execution such as the PRAM. Our main application for circuit semantics is the establishment of relative intensional expressiveness results. Extensional expressiveness is concerned with whether a construct enables us to compute new functions. Since most programming languages are Turing-complete this is usually not very interesting. On the other hand, intensional expressiveness is concerned with whether a construct enables us to write more efficient programs. Utilizing a somewhat surprising connection with the field of circuit complexity, we study the relative intensional expressive power of various deterministic and nondeterministic parallel extensions of PCF.
- Numerical Mathematics
- Computer Programming and Software