The Experts below are selected from a list of 63 Experts worldwide ranked by ideXlab platform

Stephen Brookes - One of the best experts on this subject based on the ideXlab platform.

  • LICS - The essence of parallel Algol
    Information and Computation, 2002
    Co-Authors: Stephen Brookes
    Abstract:

    We consider a parallel algol-like language, combining the /spl lambda/-calculus with shared-variable parallelism. We provide a denotational semantics for this language, simultaneously adapting the possible worlds model of Reynolds and Oles (1981, 1982) to the parallel setting and generalizing the "transition traces" model to the procedural setting. This semantics supports reasoning about safety and liveness properties of parallel programs, and validates a number of natural laws of program equivalence based on noninterference properties of local variables. We also provide a relationally parametric semantics, to permit reasoning about relation-preserving properties of programs, and adapting work of O'Hearn and Tennent (1995) to the parallel setting. This semantics supports standard methods of reasoning about representational independence. The clean design of the programming language and its semantics supports the orthogonality of procedures and shared-variable parallelism.

  • Category Theory and Computer Science - A Category-Theoretic Treatment of a Parallel algol-like language
    Category Theory and Computer Science, 1995
    Co-Authors: Stephen Brookes
    Abstract:

    Sequential algol-like languages augment a simple imperative language with a procedure mechanism based on the λ-calculus. We consider a parallel algol-like language combining the λ-calculus with shared-variable parallelism. This allows the design of efficient programs that take advantage of parallelism inherent in a problem. Such programs are normally designed to cooperate in solving a common task, by reading and wri ting to shared memory; but parallel commands may also interfere in unexpected ways, causing undesirable behavior such as deadlock. Local variable declarations provide a convenient way to delimit interference. Procedure de finitions provide a convenient abstraction mechanism and permit encapsulation of common parallel programming idioms such as mutual exclusion.

R.d. Tennent - One of the best experts on this subject based on the ideXlab platform.

  • Parametricity and local variables
    Journal of the ACM, 1995
    Co-Authors: Peter W. O'hearn, R.d. Tennent
    Abstract:

    We propose that the phenomenon of local state may be understood in terms of Strachey's concept of parametric (i.e., uniform) polymorphism. The intuitive basis for our proposal is the following analogy: a non-local procedure is independent of locally-declared variables in the same way that a parametrically polymorphic function is independent of types to which it is instantiated. A connection between parametricity and representational abstraction was first suggested by J.C. Reynolds. Reynolds used logical relations to formalize this connection in languages with type variables and user-defined types. We use relational parametricity to construct a model for an algol-like language in which interactions between local and non-local entities satisfy certain relational criteria. Reasoning about local variables essentially involved proving properties of polymorphic functions. The new model supports straightforward validations of all the test equivalences that have been proposed in the literature for local-variable semantics, and encompasses standard methods of reasoning about data representations. It is not known whether our techniques yield fully abstract semantics. A model based on partial equivalence relations on the natural numbers is also briefly examined.

  • Regular ArticleSemantical Analysis of Specification Logic, 2
    Information and Computation, 1993
    Co-Authors: P.w. Ohearn, R.d. Tennent
    Abstract:

    The "specification logic" of J. C. Reynolds (in "Tools and Notions for Program Construction" (D. Neel, Ed.), pp. 121-161, Cambridge Univ. Press, Cambridge, 1982) is a formal system for proving partial-correctness properties of programs in an algol-like language with higher-order procedures. In a previous publication (Tennent, Inform. and Comput.85, 135-162 (1990)), a model was presented that validates all axioms of the system except those involving non-interference formulas for procedural phrases. Following Reynolds, non-interference for procedural phrases was there defined syntactically, by induction on types. Here, we present a new semantic interpretation of non-interference (for phrases of arbitrary type) which is equivalent to the interpretation given earlier for phrases of basic type. This interpretation provides the first model for all of Reynold′s axioms (except the equivalences formerly used to define procedural non-interference). A slightly more refined model is used to validate also a new axiom which formalizes a method used by Reynolds ("The Craft of Programming," Prentice-Hall, London, 1981) to reason about programs with multiple levels of abstraction.

Kurt Sieber - One of the best experts on this subject based on the ideXlab platform.

  • MFCS - Full Abstraction for the Second Order Subset of an algol-like language
    Theoretical Computer Science, 1996
    Co-Authors: Kurt Sieber
    Abstract:

    Abstract We present a denotational semantics for an Algol -like language Alg , which is fully abstract for the second order subset of Alg . This constitutes the first significant full abstraction result for a block structured language with local variables. As all the published ‘test equivalences’ [8, 13,22] for Algol -like languages are contained in the second order subset, they can all be validated (easily) in our denotational model. The general technique for our model construction — namely ‘relationally structured locally complete partial orders’ with ‘relation preserving locally continuous functions’ — has already been developed in [13], but our particular model differs from the one in [13] in that we now use a larger set of relations. In a certain sense it is the ‘largest possible’ set of relations, an idea which we have successfully used in [32] to obtain a fully abstract model for the second order subset of the functional language PCF [26]. The overall structure of our full abstraction proof is also taken from [32], but for the single parts of the proof we had to solve considerable new problems which are specific to the imperative ( Algol -like) setting.

  • Full abstraction for the second order subset of an algol-like language (preliminary report)
    1994
    Co-Authors: Kurt Sieber
    Abstract:

    The search for fully abstract models of block structured languages with local variables began in the mid 80s. A series of observationalcongruences in [MeyerS88] revealed the shortcomings of existing models and served as test cases for new ones. The most recently developed models in [OHearnT93, Sieber93] could prove all these test equivalences, but it was not known whether they are fully abstract. In this paper we show that (a slight variant of) the model in [Sieber93] IS fully abstract for the second order subset of an algol-like language (which subsumes all the test equivalences). The general technique for constructing our model is still the same as in [MeyerS88], namely we use `relationally structured locally complete partial orders` with `relation preserving locally continuous functions`. The particular model differs from the one in [MeyerS88] by having the `finest possible relation structure`, an idea which we have developed in [Sieber92] for constructing a fully abstract model for the second order subset of sequential PCF. The full abstraction proof also uses some ideas from [Sieber92], but for its main part we had to develop new techniques in order to cope with the more complicated (in comparison with PCF) setting of an algol-like language.

Dan R. Ghica - One of the best experts on this subject based on the ideXlab platform.

  • The geometry of synthesis: how to make hardware out of software (abstract)
    Lecture Notes in Computer Science, 2012
    Co-Authors: Dan R. Ghica
    Abstract:

    High-level synthesis or "hardware compilation" is a behavioural synthesis method in which circuits are specified using conventional programming languages. Such languages are generally recognised as more accessible than hardware description languages, and it is expected that their use would significantly increase design productivity. The Geometry of Synthesis is a new hardware compilation technique which achieves this goal in a semantic-directed fashion, by noting that functional programming languages and diagrammatic descriptions of hardware share a common mathematical structure, and by using the game-semantic model of the programming language to reduce all computational effects to signal-like message passing. As a consequence, this technique has mature support for higher-order functions [1], local (assignable) state [2], concurrency [3] and (affine) recursion [4]. Moreover, the compiler can support features such as separate compilation, libraries and a foreign-function interface [5]. The programming language of GoS, Verity, is an "algol-like" language [6] extended with concurrency features [7]. The interplay between the call-by-name function mechanism and local effects, an approach specific to Algol, is the key ingredient which makes it possible for a large class of programs in this language to have finitely representable semantic models which can be synthesised as stand-alone static circuits. The compiler is available as an open-source download.

P.w. Ohearn - One of the best experts on this subject based on the ideXlab platform.

  • Regular ArticleSemantical Analysis of Specification Logic, 2
    Information and Computation, 1993
    Co-Authors: P.w. Ohearn, R.d. Tennent
    Abstract:

    The "specification logic" of J. C. Reynolds (in "Tools and Notions for Program Construction" (D. Neel, Ed.), pp. 121-161, Cambridge Univ. Press, Cambridge, 1982) is a formal system for proving partial-correctness properties of programs in an algol-like language with higher-order procedures. In a previous publication (Tennent, Inform. and Comput.85, 135-162 (1990)), a model was presented that validates all axioms of the system except those involving non-interference formulas for procedural phrases. Following Reynolds, non-interference for procedural phrases was there defined syntactically, by induction on types. Here, we present a new semantic interpretation of non-interference (for phrases of arbitrary type) which is equivalent to the interpretation given earlier for phrases of basic type. This interpretation provides the first model for all of Reynold′s axioms (except the equivalences formerly used to define procedural non-interference). A slightly more refined model is used to validate also a new axiom which formalizes a method used by Reynolds ("The Craft of Programming," Prentice-Hall, London, 1981) to reason about programs with multiple levels of abstraction.