A Software Product Line (SPL) is a family of similar programs, called variants, generated from a common artifact base. A Multi SPL (MPL) is a set of interdependent SPLs: each variant can depend on variants from other SPLs. MPLs are challenging to model and to implement efficiently, especially when different variants of the same SPL must coexist and interoperate. We address this challenge by introducing the concept of a variability module (VM), a new language construct. A VM constitutes at the same time a module and an SPL of standard (variability-free), possibly interdependent, modules. Generating a variant of a VM triggers the generation of all variants required to satisfy its dependencies. Consequentially, a set of interdependent VMs represents an MPL that can be compiled into a set of standard modules. We illustrate the VM concept with an example from an industrial modeling scenario and formalize it in a core calculus. We define family-based analyses to check that a VM satisfies certain well-formedness conditions and whether all variants can be generated. Finally, we provide an implementation of VM for the Java-like modeling language ABS, and evaluate it with case studies.

Abstract A Featured Transition System (FTS) models the behaviour of all products of a Software Product Line (SPL) in a single compact structure, by associating action-labelled transitions with features that condition their presence in product behaviour. It may however be the case that the resulting featured transitions of an FTS cannot be executed in any product (so called dead transitions) or, on the contrary, can be executed in all products (so called false optional transitions). Moreover, an FTS may contain states from which a transition can be executed only in some products (so called hidden deadlock states). It is useful to detect such ambiguities and signal them to the modeller, because dead transitions indicate an anomaly in the FTS that must be corrected, false optional transitions indicate a redundancy that may be removed, and hidden deadlocks should be made explicit in the FTS to improve the understanding of the model and to enable efficient verification—if the deadlocks in the products should not be remedied in the first place. We provide an algorithm to analyse an FTS for ambiguities and a means to transform an ambiguous FTS into an unambiguous one. The scope is twofold: an ambiguous model is typically undesired as it gives an unclear idea of the SPL and, moreover, an unambiguous FTS can efficiently be model checked. We empirically show the suitability of the algorithm by applying it to a number of benchmark SPL examples from the literature, and we show how this facilitates a kind of family-based model checking of a wide range of properties on FTSs.

We study an extension of Plotkin's call-by-value lambda-calculus via two commutation rules (sigma-reductions). These commutation rules are sufficient to remove harmful call-by-value normal forms from the calculus, so that it enjoys elegant characterizations of many semantic properties. We prove that this extended calculus is a conservative refinement of Plotkin's one. In particular, the notions of solvability and potential valuability for this calculus coincide with those for Plotkin's call-by-value lambda-calculus. The proof rests on a standardization theorem proved by generalizing Takahashi's approach of parallel reductions to our set of reduction rules. The standardization is weak (i.e. redexes are not fully sequentialized) because of overlapping interferences between reductions. Comment: 27 pages

Intersection type assignment systems can be used as a general framework for building logical models of λ-calculus that allow to reason about the denotation of terms in a finitary way. We defineessentialmodels (a new class of logical models) through a parametric type assignment system using non-idempotent intersection types. Under an interpretation of terms based on typings instead than the usual one based on types, every suitable instance of the parameters induces a λ-model, whose theory is sensible. We prove that this type assignment system provides a logical description of a family of λ-models arising from a category of sets and relations.

Linearity is a multi-faceted and ubiquitous notion in the analysis and development of programming language concepts. We study linearity in a denotational perspective by picking out programs that correspond to linear functions between domains. We propose a PCF-like language imposing linear constraints on the use of variable to program only linear functions. To entail a full abstraction result, we introduce some higher-order operators related to exception handling and parallel evaluation. We study several notions of operational equivalence and show them to coincide with our language. Finally, we present a new operational evaluation of the language that provides the base for a real implementation. It exploits the denotational linearity to provide an efficient evaluation semantics SECD-like, that avoids the use of closures.

Types support reliable reasoning in many areas such as logic, linguistics, programming languages, software and hardware verification, among others.A comprehensive background is settled in the upcoming book by H.B. Barendregt, W. Dekkers and R. Statman [1].Intersection types have been introduced in the late 1970s as a language for describing properties of lambda calculus which were not captured by all previous type systems.They provided the first characterisation of strongly normalising lambda terms and become a powerful syntactic and semantic tool for analysing various normalisation properties as well as lambda models.Over the last thirty years the scope of research on intersection types has broadened.Recently, there have been a number of breakthroughs in the use of intersection types and similar technology for practical purposes such as program analysis, verification and concurrency.This issue is devoted to the latest developments in the theory and practice of intersection types and related systems.The aim of the ITRS workshop series is to bring together researchers working both on theoretical developments and practical applications of intersection types and related systems with union types, recursive types, refinement types, behavioural types, etc..While this issue is inspired by The Fourth Workshop on Intersection Types and Related Systems -ITRS'08 held in Turin, Italy on March 25, 2008, submissions were not restricted to the papers presented at the workshop.The Program Committee members of ITRS'08 were:

Linearity is a multi-faceted and ubiquitous notion in the analysis and the development of programming language concepts. We study linearity in a denotational perspective by picking out programs that correspond to linear functions between coherence spaces.

We propose a paradigmatic programming language (called SlPCF) which is linear in a semantic sense. SlPCF is not syntactically linear, namely its programs can contain more than one occurrencies of the same variable. We give an interpretation of SlPCF into a model of linear coherence spaces and we show that such semantics is fully abstract with respect to our language. Furthermore, we discuss the independence of new syntactical operators and we address the universality problem.