We address the verification of mutable, heap-allocated abstract data types (ADTs) in Dafny, and their traversal via iterators. For this purpose, we devise a verification methodology that makes it possible to implement ADTs based on already existing ones, while maintaining proper encapsulation. Then, we apply this methodology to the specification and implementation of linear collections such as stacks, queues, deques, and lists with iterators. The approach introduced in this paper allows one to progressively refine some aspects of the specification such as iterator invalidation, so that clients of the library can reason about how structural changes to a list affect existing iterators. Finally, we extend our methodology to the verification of client code (i.e., code that makes use of the implemented ADTs) and identify the boilerplate conditions common to all methods that receive and manipulate ADTs.

The Robot Operating System (ROS) is a framework for building robust software for complex robot systems in several domains. The Navigation Stack stands out among the different libraries available in ROS, providing a set of components that can be reused to build robots with autonomous navigation capabilities. This library is a critical component, as navigation failures could have catastrophic consequences for applications like self-driving cars where safety is crucial. Here we devise a general methodology for verifying this kind of complex systems by specifying them in different executable specification languages with verification support and validating the equivalence between the specifications and the original system using differential testing techniques. The complex system can then be indirectly analyzed using the verification tools of the specification languages like model checking, semi-automated functional verification based on Hoare logic, and other formal techniques. In this paper we apply this verification methodology to the NavFn planner, which is the main planner component of the Navigation Stack of ROS, using Maude and Dafny as specification languages. We have formally proved several desirable properties of this planner algorithm like the absence of obstacles in the planned path. Moreover, we have found counterexamples for other concerns like the optimality of the path cost.

Databases are a key subject in several technical degrees.Because they have a strong practical nature, students require a large number of problems to master them.However, these problems are useful only if accurate and timely feedback is provided.In this paper, we present the learning improvements obtained by using LearnSQL, an automatic judge that has been designed to complement face-to-face lectures.We have measured the impact of this judge during the 2021/22 academic year and report promising results both in student engagement and final grades.

A liquid type is an ordinary Hindley-Milner type annotated with a logical predicate that states the properties satisfied by the elements of that type. Liquid types are a powerful tool for program verification, as programmers can use them to specify pre- and post conditions of their programs, whereas the predicates of intermediate variables and auxiliary functions are inferred automatically. Type inference is feasible in this context, as the logical predicates within liquid types are constrained to a quantifier-free logic to maintain decidability. In this article, we extend liquid types by allowing them to contain quantified properties on arrays so that they can be used to infer invariants on array-related programs (e.g., implementations of sorting algorithms). Although quantified logic is, in general, undecidable, we restrict properties on arrays to a decidable subset introduced by Bradley et al. We describe in detail the extended type system, the verification condition generator, and the iterative weakening algorithm for inferring invariants. After proving the correctness and completeness of these two algorithms, we apply them to find invariants on a set of algorithms involving array manipulations.

Erlang is a dynamically typed concurrent functional language of increasing interest in industry and academia. Official Erlang distributions come equipped with Dialyzer, a useful static analysis tool able to anticipate runtime errors by inferring so-called success types, which are overapproximations to the real semantics of expressions. However, Dialyzer exhibits two main weaknesses: on the practical side, its ability to deal with functions that are typically polymorphic is rather poor; and on the theoretical side, a fully developed theory for its underlying type system –comparable to, say, Hindley-Milner system– does not seem to exist, something that we consider a regrettable circumstance. This work presents a type derivation system to obtain polymorphic success types for Erlang programs, along with correctness results with respect to a suitable semantics for the language.

SUMMARY For real‐time and embedded systems, limiting the consumption of time and memory resources is often an important part of the requirements. Being able to predict bounds on the consumption of such resources during the development process of the code can be of great value. In this paper, we focus mainly on memory‐related bounds. Recent research results have advanced the state of the art of resource consumption analysis. In this paper, we present a toolset that makes it possible to apply these research results in practice for (real‐time) systems enabling JAVA developers to analyse symbolic loop bounds, symbolic bounds on heap size and both symbolic and numeric bounds on stack size. We describe which theoretical additions were needed in order to achieve this. We give an overview of the capabilities of the RESANA (Radboud University Nijmegen, The Netherlands) toolset that is the result of this effort. The toolset can not only perform generally applicable analyses, but it also contains a part of the analysis that is dedicated to the developers' (real‐time) virtual machine, such that the results apply directly to the actual development environment that is used in practice. Copyright © 2013 John Wiley & Sons, Ltd.

Shape analysis is concerned with the compile-time determination of the 'shape' the heap may take at runtime, meaning by this the pointer chains that may happen within, and between, the data structures built by the program. This includes detecting alias and sharing between the program variables.

We present a destruction-aware type system for the functional language Safe, which is a first-order eager language with facilities for programmer controlled destruction and copying of data structures. It provides also regions, i.e. disjoint parts of the heap, where the program allocates data structures. The runtime system does not need a garbage collector and all allocation/deallocation actions are done in constant time.

A natural way of quantifying the degree of linear dependence between two fuzzy random variables in certain models is analyzed. In these models, the linear relationship is formalized in terms of a regression model based on the usual arithmetic for fuzzy sets. The degree of linear relationship is proposed to be measured by means of a kind of determination coefficient, that is, through the proportion of variability of the response fuzzy random variable explained by the regression model. Some properties of both the models and the determination coefficient are analyzed in order to verify the suitability of this coefficient as a measure of linear dependence. Finally, the meaning of a correlation coefficient which mimics the usual one for real-valued random variables is discussed.