| Circuit Semantics and Intensional Expressivity (1996) | |||||||||||||||
Abstract | |||||||||||||||
| We introduce a new denotational semantics for functional programming languages and use it to reason about intensional aspects of programs. Circuit semantics associates a gate with each basic construct of the language, and takes the meaning of a program to be a circuit. The dimensions of the circuit enable reasoning about running time and work required for execution. We use circuit semantics to obtain relative intensional expressiveness results between various deterministic and nondeterministic parallel extensions of PCF. 1 Introduction We are interested in establishing relative intensional expressiveness results for programming languages. Most work in the past has focused on extensional expressiveness: Language L 1 is extensionally more expressive than L 2 if L 1 can compute all the functions computable in L 2 . We say that language L 1 is intensionally more expressive than L 2 , if L 1 can compute all the functions computable in L 2 , with at least the same asymptotic complexity. T... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||