Curien P.-L. Categorical Combinators, Sequential Algorithms, and Functional Programmimg

Издательство Birkh?user, 1993, -424 pp.

The goal of this monograph is to give a concrete approach to the semantics of sequential programming languages, with application to the design and implementation of programming languages. Just as machines do not manipulate numbers, but representations of numbers, we do not present sets and functions, but concrete representations of these sets and functions. The motivation behind our constructions is to ensure that any two program pieces have the same meaning as soon as they behave the same way on a computer. Restricting this known problem, entitled the full abstraction problem, to sequential programming languages implies giving a semantic account to sequentiality. Sequential languages are languages in which constructs are evaluated one at a time; as a consequence, if the evaluation of a given construct loops, the next construct in the program text will not be evaluated. The construction of sequential objects in the semantics has led us to replace sets and functions with descriptions of sets and functions: concrete data structures and sequential algorithms. A sequential algorithm is a pair of a function and a computational strategy. The intensionality of our model, that is, the fact that it does not account only for the input-output behavior of the interpreted programs and procedures, constitutes one of its most original features. The concrete nature of our semantics has led us naturally to the design of a programming language, calles CDS0, where the full abstraction property we sought holds true.

Categorical Combinators
Sequential Algorithms
CDSO:The Keel of the Functional Language
The Full Abstraction Problem