Abstract We analyse the problem of combining linearity, effects, and exceptions, in abstract models of programming languages, as the issue of providing some kind of strength for a monad $$T(- \oplus E)$$ T ( - ⊕ E ) in a linear setting. We consider in particular for T the allocation monad , which we introduce to model and study resource-safety properties. We apply these results to a series of two linear effectful calculi for which we establish their resource-safety properties. The first calculus is a linear (optionally ordered) call-by-push-value language with two allocation effects $${{\,\mathrm{\textbf{new}}\,}}$$ new and $${{\,\mathrm{\textbf{delete}}\,}}$$ delete . The resource-safety properties follow from the linear and ordered character of the typing rules. We then integrate exceptions with linearity and effects by adjoining default destruction actions to types, as inspired by C++/Rust destructors. We see destructors as objects $$\delta : A\rightarrow TI$$ δ : A → T I in the slice category over TI . This construction gives rise to a second calculus, the resource call-by-push-value , featuring exceptions and destructors, and whose weakening and exchange rules perform side-effects. It is therefore affine at the level of types but ordered at the level of derivations. As in C++ and Rust, a “move” operation—the side-effecting exchange rule—is necessary for releasing resources in random order, as opposed to LIFO order.

Given a table with a minimal set of input columns that functionally determines an output column, we introduce a method that tries to gradually decompose the corresponding minimal functional dependency (mfd) to acquire a formula expressing the output column in terms of the input columns. A first key element of the method is to create sub-problems that are easier to solve than the original formula acquisition problem, either because it learns formulae with fewer inputs parameters, or as it focuses on formulae of a particular class, such as Boolean formulae; as a result, the acquired formulae can mix different learning biases such as polynomials, conditionals or Boolean expressions. A second key feature of the method is that it can be applied recursively to find formulae that combine polynomial, conditional or Boolean sub-terms in a nested manner. The method was tested on data for eight families of combinatorial objects; new conjectures were found that were previously unattainable. The method often creates conjectures that combine several formulae into one with a limited number of automatically found Boolean terms.

International audience

Laziness is a powerful concept in functional programming that enables reusing general functions in a specific context, while keeping performance close to the efficiency of dedicated definitions. Lazy evaluation can be used in imperative programming too. Twenty years ago, John Launchbury was already advocating for lazy imperative programming, but the level of laziness of his framework remained limited: a single effect can trigger numerous delayed computations, even if those are not required for the correctness of the evaluation. Twenty years after, the picture has not changed. In this article, we propose an Haskell framework to specify computational effects of imperative programs as well as their dependencies. Our framework is based on the operational monad transformer which encapsulates an algebraic presentation of effectful operations. A lazy monad transformer is then in charge of delaying non-necessary computations by maintaining a trace of imperative closures. We present a semantics of a call-by-need λ-calculus extended with imperative strict and lazy features and prove the correctness of our approach. While originally motivated by a less rigid use of foreign functions, we show that our approach is fruitful for a simple scenario based on sorted mutable arrays. Furthermore, we can take advantage of equations between algebraic operations to dynamically optimize imperative computations composition.

Component based software engineering and aspect orientation are claimed to be two complementary approaches. While the former ensures the modularity and the reusability of software entities, the latter enables the modularity of crosscutting concerns that cannot be modularized as regular components. Nowadays, several approaches and frameworks are dedicated to integrate aspects into component models. However, when several aspects are woven, aspects may interact with each other which often results in undesirable behavior. The contribution of this paper is twofold. First, we show how aspectized component models can be formally modeled in UPPAAL model checker in order to detect negative interactions (a.k.a., interferences) among aspects. Second, we provide an extendible catalog of composition operators used for aspect composition. We illustrate our general approach with an airport Internet service example.

Aspect Oriented Programming can arbitrarily distort the semantics of programs. In particular, weaving can invalidate crucial safety and liveness propertiesof the base program. In this article, we identify categories of aspects that preserve some classes of properties. It is then sufficient to check that an aspect belongs to a specific category to know which properties will remain satisfied by woven programs.

The development of grid algorithms is frequently hampered by limited means to describe topologies and lack of support for the invasive composition of legacy components in order to pass data between them. In this paper we present a solution to overcome these limitations using the notion of invasive patterns for the construction of distributed algorithms, a recent extension of well-known computation and communication patterns. Concretely, we present two contributions. First, based on a study of how patterns are instantiated in NAS Grid, a well-known benchmark used for evaluating performance of computational grids, we show how invasive patterns can be used for the declarative definition of large-scale grid topologies and checkpointing algorithms. Second, we qualitatively and quantitatively evaluate how our approach can be used to implement the checkpointing on top of grid applications.

Aspect oriented programming can arbitrarily distort the semantics of programs. In particular, weaving can invalidate crucial safety and liveness properties of the base program. In previous work, we have identified categories of aspects that preserve classes of temporal properties. We have formally proved that, for any program,the weaving of any aspect in a category preserves all properties in the related class. In this article, after a summary of our previous work,we present, for each aspect category, a specialized aspect language which ensures that any aspect written in that language belongs to the corresponding category. It can be proved that these languages preserve the corresponding classes of properties by construction.The aspect languages share the same expressive point cut language and are designed w.r.t. a common imperative base language. Each language is illustrated by simple examples. We also prove that all aspects written in one of the languages belong to the corresponding category.

Aspect-Oriented Programming (AOP) promises the modularization of so-called crosscutting functionalities in large applications. Currently, almost all approaches to AOP provide means for the description of sequential aspects that are to be applied to a sequential base program. In particular, there is no formally-defined concurrent approach to AOP, with the result that coordination issues between aspects and base programs as well as between aspects cannot precisely be investigated.This paper presents Concurrent Event-based AOP (CEAOP), which addresses this issue. Our contribution can be detailed as follows. First, we formally define a model for concurrent aspects which extends the sequential Event-based AOP approach. The definition is given as a translation into concurrent specifications using Finite Sequential Processes (FSP), thus enabling use of the Labelled Transition System Analyzer (LTSA) for formal property verification. Further, we show how to compose concurrent aspects using a set of general composition operators. Finally, we sketch a Java prototype implementation for concurrent aspects, which generates coordination specific code from the FSP model defining the concurrent AO application.

To understand the behavior of a program, a maintainer reads some code, asks a question about this code, conjectures an answer, and searches the code and the documentation for confirmation of her conjecture. However, the confirmation of the conjecture can be error-prone and time-consuming because the maintainer has only static information at her disposal. She would benefit from dynamic information. In this paper, we present Caffeine, an assistant that helps the maintainer in checking her conjecture about the behavior of a Java program. Our assistant is a dynamic analysis tool that uses the Java platform debug architecture to generate a trace, i.e., an execution history, and a Prolog engine to perform queries over the trace. We present a usage scenario based on the n-queens problem, and two real-life examples based on the Singleton design pattern and on the composition relationship.

We introduce a unified framework to describe, relate, compare, and classify functional language implementations. The compilation process is expressed as a succession of program transformations in the common framework. At each step, different transformations model fundamental choices. A benefit of this approach is to structure and decompose the implementation process. The correctness proofs can be tackled independently for each step and amount to proving program transformations in the functional world. This approach also paves the way to formal comparisons by making it possible to estimate the complexity of individual transformations or compositions of them. Our study aims at covering the whole known design space of sequential functional language implementations. In particular, we consider call-by-value, call-by-name, call-by-need reduction strategies as well as environment- and graph-based implementations. We describe for each compilation step the diverse alternatives as program transformations. In some cases, we illustrate how to compare or relate compilation techniques, express global optimizations, or hybrid implementations. We also provide a classification of well-known abstract machines.