Degrees of Parallelism

Abstract

In 1975 Plotkin introduced the theoretical functional programming language PCF, which consists of a special simply typed lambda-calculus, including the elementary arithmetic, in order to study the relations between denotational and operational semantics. The evaluation of PCF-terms has the following property: At each step there is only one subterm to be transformed, i.e. the evaluation goes sequentially. If it exists a step where more than one subterm has to be evaluated simultaneously to get the correct result, the term is called parallel. By adding the parallel conditional "pcond" to PCF Plotkin achieved the coincidence of operational semantics and the denotational semantics w.r.t. Scott's model of the complete partial orders (cpo-s) and continuous functions. With extending the calculus moreover with the parallel term "exists", whose semantics is the best continuous approximation to the existential quantifier, exactly all computable functions can be described. There is a difference in "parallelism" of the two terms. Whereas "exists" is able to consider an infinite amount of informations, "pcond" merely can handle a finite amount. On the other hand it is not possible to describe "pcond" by a PCF-term that makes only use of "exists", neither.

My thesis deals with various extensions of the class of sequentially computable Scott-continuous functions with non-sequential ones. The used measure for parallelism of a continuous function is defined analogous to the Turing-degree of a partial function in common theory of computability: A function f is called sequentially reducible on a function g, if f can be described by a PCF-term making use of an additional constant, whose semantic equals g. Two functions are said to be of equal parallelism, if PCF is able to describe the same set of functions with either. The equivalence classes we get in this way are called degrees of parallelism. These degrees form an upper semilattice, whose structure is not exactly known yet. The paper is intended to give a survey over former results referring to computable functions, to represent methods for analysing the semilattice and to insert further functions in this structure. The main tool for separating the degrees are the sequentiality relations, a special sort of logical relations, the only containing all semantics of PCF-terms. In 1976 Sazonov already found different degrees of non-sequentiality. His results are mostly proved in the paper, extended e.g. by the parallel convergence tester, the Gustave-function and the Berry-Plotkin-function, whose degree is greatest among all stable functions. Functions with different degree of parallelism can be element of the same sequentiality relations, i.e. separating the degrees can not be done with these relations only. In the last section, adopting Bucciarelli's constructions, we specify ascending and descending sequences of degrees and sequences, in which each pair of degrees is incomparable.

Last Change: 18.06.97