Type System

Abstract. Data-centric synchronization groups fields of objects into atomic sets to indicate they must be updated atomically. Each atomic set has associated units of work, code fragments that preserve the consistency of that atomic set. We present a type system for data-centric synchronization that enables separate compilation and supports atomic sets that span multiple objects, thus allowing recursive data structures to be updated atomically. The type system supports full encapsulation for more efficient code generation. We evaluate our proposal using AJ, which extends the Java programming language with data-centric synchronization. We report on the implementation of a compiler and on refactoring classes from standard libraries and a multi-threaded benchmark to use atomic sets. Our results suggest that data-centric synchronization enjoys low annotation overhead while preventing high-level data races.

We study the cube of type assignment systems, as introduced in Giannini et al. (Fund. Inform. 19 (1993) 87–126), and confront it with Barendregt's typed gl-cube (Barendregt, in: Handbook of Logic in Computer Science, Vol. 2, Clarenden Press, Oxford, 1992). The first is obtained from the latter through applying a natural type erasing function E to derivation rules, that erases type information from terms. In particular, we address the question whether a judgement, derivable in a type assignment system, is always an erasure of a derivable judgement in a corresponding typed system; we show that this property holds only for systems without polymorphism. The type assignment systems we consider satisfy the properties ‘subject reduction’ and ‘strong normalization’. Moreover, we define a new type assignment cube that is isomorphic to the typed one.

Meta-programming languages provide infrastructure to generate and execute object programs at run-time. In a typed setting, they contain a modal type constructor which classifies object code. These code types generally come in two flavors: closed and open. Closed code expressions can be invoked at run-time, but the computations over them are more rigid, and typically produce less efficient residual object programs. Open code provides better inlining and partial evaluation of object programs, but once constructed, expressions of this type cannot in general be evaluated.Recent work in this area has focused on combining the two notions into a sound system. We present a novel way to achieve this. It is based on adding the notion of names from the work on Nominal Logic and FreshML to the λ -calculus of proof terms for the necessity fragment of modal logic S4. The resulting language provides a more fine-grained control over free variables of object programs when compared to the existing la...

Abstract. We develop an imperative calculus that provides a formal model for both single and mixin inheritance. By introducing classes and mixins as the basic object-oriented constructs in a λ-calculus with records and references, we obtain a system with an intuitive operational ...

Service-oriented applications are frequently used in highly dynamic contexts: ser- vice compositions may change dynamically, in particular, because new services are discovered at runtime. Moreover, subtyping has recently been identified as a strong requirement for service dis- covery. Correctness guarantees over service compositions, provided in particular by type systems, are highly desirable in this context. However, while service oriented applications can be built using various technologies and protocols, none of them provides decent support ensuring that well-typed services cannot go wrong. An emitted message, for instance, may be dangling and remain as a ghost message in the network if there is no agent to receive it. In this article, we introduce a formal model for service compositions and define a type system with subtyping that ensures type soundness by combining static and dynamic checks. We also demonstrate how to preserve type soundness in presence of malicious agents and...

This paper attempts to define an object-oriented database system. It describes the main features and characteristics that a system must have to qualify as an object-oriented database system. We have separated these characteristics into three groups: o Mandatory, the ones the system must satisfy in order to be termed an object-oriented database system. These are complex objects, object identity, encapsulation,

Almost a year ago, Microsoft has introduced the .NET architecture as a new component-based programming environment, which allows for easy integration of classical distributed programming techniques with Web computing. .NETdefines a type system and introduces notions such ...

Almost a year ago, Microsoft has introduced the .NET architecture as a new component-based programming environment, which allows for easy integration of classical distributed programming techniques with Web computing. .NETdefines a type system and introduces notions such ...

Systems code is almost universally written in the C programming language or a variant. C has a very low level of type and memory abstraction and formal reasoning about C systems code requires a memory model that is able to capture the semantics of C pointers and types. At the same time, proof-based verification demands abstraction, in particular from the aliasing and frame problems. In this paper we present a study in the mechanisation of two proof abstractions for pointer program verification in the Isabelle/HOL theorem prover, based on a low-level memory model for C. The language’s type system presents challenges for the multiple independent typed heaps (Burstall-Bornat) and separation logic proof techniques. In addition to issues arising from explicit value size/alignment, padding, type-unsafe casts and pointer address arithmetic, structured types such as C’s arrays and structs are problematic due to the non-monotonic nature of pointer and lvalue validity in the presence of the unary &-operator. For example, type-safe updates through pointers to fields of a struct break the independence of updates across typed heaps or ∧*-conjuncts. We provide models and rules that are able to cope with these language features and types, eschewing common over-simplifications and utilising expressive shallow embeddings in higher-order logic. Two case studies are provided that demonstrate the applicability of the mechanised models to real-world systems code; a working of the standard in-place list reversal example and an overview of the verification of the L4 microkernel’s memory allocator.