nach oben

2017 | Buch

Kapitel lesen Erstes Kapitel lesen

Logic-Based Program Synthesis and Transformation

26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6–8, 2016, Revised Selected Papers

herausgegeben von: Manuel V Hermenegildo, Pedro Lopez-Garcia

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 26th International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR 2016, held in Edinburgh, UK, in September 2016.

The 20 revised full papers presented together with the abstracts of 3 invited talks were carefully reviewed and selected from 38 submissions. The aim of the LOPSTR series is to stimulate and promote international research and collaboration on logic-based program development. LOPSTR is open to contributions in all aspects of logic-based program development, all stages of the software life cycle, and issues of both programming-in-the-small and programming-in-the-large. LOPSTR traditionally solicits contributions, in any language paradigm, in the areas of synthesis, specification, transformation, analysis and verification, specialization, testing and certification, composition, program/model manipulation, optimization, transformational techniques in SE, inversion, applications, and tools.

Inhaltsverzeichnis

Frontmatter

Program Transformation

Frontmatter

Partial Evaluation of Order-Sorted Equational Programs Modulo Axioms

Abstract

Partial evaluation (PE) is a powerful and general program optimization technique with many successful applications. However, it has never been investigated in the context of expressive rule-based languages like Maude, CafeOBJ, OBJ, ASF+SDF, and ELAN, which support: rich type structures with sorts, subsorts and overloading; and equational rewriting modulo axioms such as commutativity, associativity–commutativity, and associativity–commutativity–identity. In this paper, we illustrate the key concepts by showing how they apply to partial evaluation of expressive rule-based programs written in Maude. Our partial evaluation scheme is based on an automatic unfolding algorithm that computes term variants and relies on equational least general generalization for ensuring global termination. We demonstrate the use of the resulting partial evaluator for program optimization on several examples where it shows significant speed-ups.

María Alpuente, Angel Cuenca-Ortega, Santiago Escobar, José Meseguer

A Formal, Resource Consumption-Preserving Translation of Actors to Haskell

Abstract

We present a formal translation of an actor-based language with cooperative scheduling to the functional language Haskell. The translation is proven correct with respect to a formal semantics of the source language and a high-level operational semantics of the target, i.e. a subset of Haskell. The main correctness theorem is expressed in terms of a simulation relation between the operational semantics of actor programs and their translation. This allows us to then prove that the resource consumption is preserved over this translation, as we establish an equivalence of the cost of the original and Haskell-translated execution traces.

Elvira Albert, Nikolaos Bezirgiannis, Frank de Boer, Enrique Martin-Martin

Verification of Time-Aware Business Processes Using Constrained Horn Clauses

Abstract

We present a method for verifying properties of time-aware business processes, that is, business processes where time constraints on the activities are explicitly taken into account. Business processes are specified using an extension of the Business Process Modeling Notation (BPMN) and durations are defined by constraints over integer numbers. The definition of the operational semantics is given by a set OpSem of constrained Horn clauses (CHCs). Our verification method consists of two steps. (Step 1) The specialization of OpSem with respect to a given business process and a given temporal property to be verified. This specialization produces a set of CHCs whose satisfiability is equivalent to the validity of the given property. (Step 2) The use of any state-of-the-art solver for CHCs to check the satisfiability of such sets of clauses. We have implemented our verification method using the VeriMAP transformation system and the Z3 solver for CHCs.

Emanuele De Angelis, Fabio Fioravanti, Maria Chiara Meo, Alberto Pettorossi, Maurizio Proietti

Constraint Programming

Frontmatter

MiniZinc with Strings

Abstract

Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

Roberto Amadini, Pierre Flener, Justin Pearson, Joseph D. Scott, Peter J. Stuckey, Guido Tack

Slicing Concurrent Constraint Programs

Abstract

Concurrent Constraint Programming (CCP) is a declarative model for concurrency where agents interact by telling and asking constraints (pieces of information) in a shared store. Some previous works have developed (approximated) declarative debuggers for CCP languages. However, the task of debugging concurrent programs remains difficult. In this paper we define a dynamic slicer for CCP and we show it to be a useful companion tool for the existing debugging techniques. We start with a partial computation (a trace) that shows the presence of bugs. Often, the quantity of information in such a trace is overwhelming, and the user gets easily lost, since she cannot focus on the sources of the bugs. Our slicer allows for marking part of the state of the computation and assists the user to eliminate most of the redundant information in order to highlight the errors. We show that this technique can be tailored to timed variants of CCP. We also develop a prototypical implementation freely available for making experiments.

Moreno Falaschi, Maurizio Gabbrielli, Carlos Olarte, Catuscia Palamidessi

Compilation and Optimization

Frontmatter

A New Functional-Logic Compiler for Curry: Sprite

Abstract

We introduce a new native code compiler for Curry codenamed Sprite. Sprite is based on the Fair Scheme, a compilation strategy that provides instructions for transforming declarative, non-deterministic programs of a certain class into imperative, deterministic code. We outline salient features of Sprite, discuss its implementation of Curry programs, and present benchmarking results. Sprite is the first-to-date operationally complete implementation of Curry. Preliminary results show that ensuring this property does not incur a significant penalty.

Sergio Antoy, Andy Jost

lpopt: A Rule Optimization Tool for Answer Set Programming

Abstract

State-of-the-art answer set programming (ASP) solvers rely on a program called a grounder to convert non-ground programs containing variables into variable-free, propositional programs. The size of this grounding depends heavily on the size of the non-ground rules, and thus, reducing the size of such rules is a promising approach to improve solving performance. To this end, in this paper we announce lpopt, a tool that decomposes large logic programming rules into smaller rules that are easier to handle for current solvers. The tool is specifically tailored to handle the standard syntax of the ASP language (ASP-Core) and makes it easier for users to write efficient and intuitive ASP programs, which would otherwise often require significant hand-tuning by expert ASP engineers. It is based on an idea proposed by Morak and Woltran (2012) that we extend significantly in order to handle the full ASP syntax, including complex constructs like aggregates, weak constraints, and arithmetic expressions. We present the algorithm, the theoretical foundations on how to treat these constructs, as well as an experimental evaluation showing the viability of our approach.

Manuel Bichler, Michael Morak, Stefan Woltran

Symbolic Execution and Thresholding for Efficiently Tuning Fuzzy Logic Programs

Abstract

Fuzzy logic programming is a growing declarative paradigm aiming to integrate fuzzy logic into logic programming. One of the most difficult tasks when specifying a fuzzy logic program is determining the right weights for each rule, as well as the most appropriate fuzzy connectives and operators. In this paper, we introduce a symbolic extension of fuzzy logic programs in which some of these parameters can be left unknown, so that the user can easily see the impact of their possible values. Furthermore, given a number of test cases, the most appropriate values for these parameters can be automatically computed. Finally, we show some benchmarks that illustrate the usefulness of our approach.

Ginés Moreno, Jaime Penabad, José A. Riaza, Germán Vidal

Analysis and Verification

Frontmatter

Hierarchical Shape Abstraction for Analysis of Free List Memory Allocators

Abstract

We propose a hierarchical abstract domain for the analysis of free list memory allocators that tracks shape and numerical properties about both the heap and the free lists. Our domain is based on Separation Logic extended with predicates that capture the pointer arithmetics constraints for the heap list and the shape of the free list. These predicates are combined using a hierarchical composition operator to specify the overlapping of the heap list by the free list. In addition to expressiveness, this operator leads to a compositional and compact representation of abstract values and simplifies the implementation of the abstract domain. The shape constraints are combined with numerical constraints over integer arrays to track properties about the allocation policies (best-fit, first-fit, etc.). Such properties are out of the scope of the existing analyzers. We implemented this domain and we show its effectiveness on several implementations of free list allocators.

Bin Fang, Mihaela Sighireanu

A Productivity Checker for Logic Programming

Abstract

Automated analysis of recursive derivations in logic programming is known to be a hard problem. Both termination and non-termination are undecidable problems in Turing-complete languages. However, some declarative languages offer a practical work-around for this problem, by making a clear distinction between whether a program is meant to be understood inductively or coinductively. For programs meant to be understood inductively, termination must be guaranteed, whereas for programs meant to be understood coinductively, productive non-termination (or “productivity”) must be ensured. In practice, such classification helps to better understand and implement some non-terminating computations.

Logic programming was one of the first declarative languages to make this distinction: in the 1980’s, Lloyd and van Emden’s “computations at infinity” captured the big-step operational semantics of derivations that produce infinite terms as answers. In modern terms, computations at infinity describe “global productivity” of computations in logic programming. Most programming languages featuring coinduction also provide an observational, or small-step, notion of productivity as a computational counterpart to global productivity. This kind of productivity is ensured by checking that finite initial fragments of infinite computations can always be observed to produce finite portions of their infinite answer terms.

In this paper we introduce a notion of observational productivity for logic programming as an algorithmic approximation of global productivity, give an effective procedure for semi-deciding observational productivity, and offer an implemented automated observational productivity checker for logic programs.

Ekaterina Komendantskaya, Patricia Johann, Martin Schmidt

Symbolic Abstract Contract Synthesis in a Rewriting Framework

Abstract

We propose an automated technique for inferring software contracts from programs that are written in a non-trivial fragment of C, called KernelC, that supports pointer-based structures and heap manipulation. Starting from the semantic definition of KernelC in the \(\mathbb {K}\) framework, we enrich the symbolic execution facilities recently provided by C with novel capabilities for assertion synthesis that are based on abstract subsumption. Roughly speaking, we define an abstract symbolic technique that explains the execution of a (modifier) C function by using other (observer) routines in the same program. We implemented our technique in the automated tool KindSpec 2.0, which generates logical axioms that define the precise input/output behavior of the C routines.

María Alpuente, Daniel Pardo, Alicia Villanueva

Testing

Frontmatter

On the Completeness of Selective Unification in Concolic Testing of Logic Programs

Abstract

Concolic testing is a popular dynamic validation technique that can be used for both model checking and automatic test case generation. We have recently introduced concolic testing in the context of logic programming. In contrast to previous approaches, the key ingredient in this setting is a technique to generate appropriate run-time goals by considering all possible ways an atom can unify with the heads of some program clauses. This is called “selective” unification. In this paper, we show that the existing algorithm is not complete and explore different alternatives in order to have a sound and complete algorithm for selective unification.

Fred Mesnard, Étienne Payet, Germán Vidal

CurryCheck: Checking Properties of Curry Programs

Abstract

We present CurryCheck, a tool to automate the testing of programs written in the functional logic programming language Curry. CurryCheck executes unit tests as well as property tests which are parameterized over one or more arguments. CurryCheck tests properties by systematically enumerating test cases so that, for smaller finite domains, CurryCheck can actually prove properties. Unit tests and properties can be defined in a Curry module without being exported. Thus, they are also useful to document the intended semantics of the source code. Furthermore, CurryCheck also supports the automated checking of specifications and contracts occurring in source programs. Hence, CurryCheck is a useful tool that contributes to the property- and specification-based development of reliable and well tested declarative programs.

Michael Hanus

A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms

Abstract

Contrary to several other families of lambda terms, no closed formula or generating function is known and none of the sophisticated techniques devised in analytic combinatorics can currently help with counting or generating the set of simply-typed closed lambda terms of a given size.

Moreover, their asymptotic scarcity among the set of closed lambda terms makes counting them via brute force generation and type inference quickly intractable, with previous published work showing counts for them only up to size 10.

By taking advantage of the synergy between logic variables, unification with occurs check and efficient backtracking in today’s Prolog systems, we climb 4 orders of magnitude above previously known counts by deriving progressively faster Horn Clause programs that generate and/or count the set of closed simply-typed lambda terms of sizes up to 14. A similar count for closed simply-typed normal forms is also derived up to size 14.

Paul Tarau

Semantics and Model Checking

Frontmatter

A Reversible Semantics for Erlang

Abstract

In a reversible language, any forward computation can be undone by a finite sequence of backward steps. Reversible computing has been studied in the context of different programming languages and formalisms, where it has been used for debugging and for enforcing fault-tolerance, among others. In this paper, we consider a subset of Erlang, a concurrent language based on the actor model, and formally introduce a semantics for reversible computation. To the best of our knowledge, this is the first attempt to define a reversible semantics for Erlang.

Naoki Nishida, Adrián Palacios, Germán Vidal

Scaling Bounded Model Checking by Transforming Programs with Arrays

Abstract

Bounded Model Checking is one the most successful techniques for finding bugs in program. However, model checkers are resource hungry and are often unable to verify programs with loops iterating over large arrays. We present a transformation that enables bounded model checkers to verify a certain class of array properties. Our technique transforms an array-manipulating (Ansi-C) program to an array-free and loop-free (Ansi-C) program thereby reducing the resource requirements of a model checker significantly. Model checking of the transformed program using an off-the-shelf bounded model checker simulates the loop iterations efficiently. Thus, our transformed program is a sound abstraction of the original program and is also precise in a large number of cases—we formally characterize the class of programs for which it is guaranteed to be precise. We demonstrate the applicability and usefulness of our technique on both industry code as well as academic benchmarks.

Anushri Jana, Uday P. Khedker, Advaita Datar, R. Venkatesh, Niyas C.

Intuitionistic Logic Programming for SQL

Abstract

Intuitionistic logic programming provides the notion of embedded implication in rule bodies, which can be used to reason about a current database modified by the antecedent. This can be applied to a system that translates SQL to Datalog to solve SQL WITH queries, for which relations are locally defined and can therefore be understood as locally added to the current database. In addition, assumptions in SQL queries as either adding or removing data can be modelled in this way as well, which is an interesting feature for decision-support scenarios. This work suggests a way to apply intuitionistic logic programming to SQL, and provides a pointer to a working system implementing this idea.

Fernando Sáenz-Pérez

Types, Unification, and Logic

Frontmatter

Coinductive Soundness of Corecursive Type Class Resolution

Abstract

Horn clauses and first-order resolution are commonly used to implement type classes in Haskell. Several corecursive extensions to type class resolution have recently been proposed, with the goal of allowing (co)recursive dictionary construction where resolution does not terminate. This paper shows, for the first time, that corecursive type class resolution and its extensions are coinductively sound with respect to the greatest Herbrand models of logic programs and that they are inductively unsound with respect to the least Herbrand models. We establish incompleteness results for various fragments of the proof system.

František Farka, Ekaterina Komendantskaya, Kevin Hammond

Nominal Unification of Higher Order Expressions with Recursive Let

Abstract

A sound and complete algorithm for nominal unification of higher-order expressions with a recursive let is described, and shown to run in non-deterministic polynomial time. We also explore specializations like nominal letrec-matching for plain expressions and for DAGs and determine their complexity.

Manfred Schmidt-Schauß, Temur Kutsia, Jordi Levy, Mateu Villaret

Automata Theory Approach to Predicate Intuitionistic Logic

Abstract

Predicate intuitionistic logic is a well established fragment of dependent types. According to the Curry-Howard isomorphism proof construction in the logic corresponds well to synthesis of a program the type of which is a given formula. We present a model of automata that can handle proof construction in full intuitionistic first-order logic. The automata are constructed in such a way that any successful run corresponds directly to a normal proof in the logic. This makes it possible to discuss formal languages of proofs or programs, the closure properties of the automata and their connections with the traditional logical connectives.

Maciej Zielenkiewicz, Aleksy Schubert

Backmatter

Titel: Logic-Based Program Synthesis and Transformation
herausgegeben von: Manuel V Hermenegildo
Pedro Lopez-Garcia
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-63139-4
Print ISBN: 978-3-319-63138-7
DOI: https://doi.org/10.1007/978-3-319-63139-4