Pasar al contenido principal

METODOS RIGUROSOS PARA EL DESARROLLO DE SISTEMAS SOFTWARE DE CALIDAD Y FIABILIDAD CERTIFICADAS (SUBPROYECTO IMDEA)

PID2019-108528RB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario FUNDACION IMDEA SOFTWARE

Resultados relacionados

Resultados totales (Incluyendo duplicados): 10
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Some Thoughts on How to Teach Prolog

  • Hermenegildo, Manuel V.
  • Morales, José F.
  • López-García, Pedro
Lecture Notes in Computer Science (LNCS, volume 13900) 13 páginas, 5 figuras, Prolog, and (Constraint) Logic Programming in general, represent a unique programming paradigm. Prolog has many characteristics that are not present in other styles of programming, and this is one of the reasons why it is taught. At the same time, and precisely because of this uniqueness, teaching Prolog presents some special challenges. In this paper we present some lessons learned over many years of teaching Prolog, and (C)LP in general, mostly to CS college students, at several universities. We address how to show the beauty and usefulness of the language, and also how to avoid some common pitfalls, misconceptions, and myths about it. The emphasis of our discussion is on how, rather than what. Despite some focus on CS college students, we believe that many of the ideas that we propose also apply to teaching Prolog at any other education level., Partially funded by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021-047102-I, by the Comunidad de Madrid program P2018/TCS-4339 BLOQUES-CM, and by the Tezos foundation.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A Rule-Based Approach for Designing and Composing Abstract Domains

  • Jurjo, Daniel
  • Morales, José F.
  • López-García, Pedro
  • Hermenegildo, Manuel V.
Logic-Based Program Synthesis and Transformation. 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings Logic-Based Program Synthesis and Transformation. LOPSTR 2023. Lecture Notes in Computer Science, vol 14330. 19 páginas, Abstract interpretation allows constructing sound static analysis tools by safely approximating program semantics. Frameworks for abstract interpretation typically provide an implementation of a specialized iteration strategy to compute an abstract fixpoint, as well as a number of abstract domains in order to approximate different program properties. However, the design and implementation of additional domains, as well as their combinations, is eventually necessary to successfully prove arbitrary program properties. We propose a rule-based methodology for rapid design and prototyping of new domains and combining existing ones, with a focus on the analysis of logic programs. We provide several examples for domains combining numerical properties and data types and apply them to proving complex program properties., Partially funded by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021-047102-I, and by the Tezos foundation.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation

  • Gallagher, John P.
  • Hermenegildo, Manuel V.
  • Morales, José F.
  • López-García, Pedro
International Symposium on Logic-Based Program Synthesis and Transformation, Cascais, Portugal, October 23-24, 2023 LOPSTR 2023. Lecture Notes in Computer Science, vol 14330, Natural semantics (big-step) and structural operational semantics (small-step) each have advantages, so it can be useful to produce both semantic forms for a language. Previous work has shown that big-step semantics can be transformed to small-step semantics. This is also the goal of our work, but our main contribution is to show that this can be done by specialisation of an interpreter that imposes a small-step execution on big-step transition rules. This is arguably more direct, transparent and flexible than previous methods. The paper contains two examples and further examples are available in an online repository., Partially funded by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021-047102-I, and by the Tezos foundation.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Types, Modes and so Much More - The Prolog Way

  • Hermenegildo, Manuel V.
  • Morales, José F.
  • López-García, Pedro
  • Carro, Manuel
Prolog: The Next 50 Years. Lecture Notes in Computer Science, vol 13900, We present in a tutorial way some ideas developed in the context of the Ciao Prolog system that we believe could be useful for the future evolution of Prolog. We concentrate primarily on one area: the use of assertions with types, modes, and other properties, and how the unique characteristics of Prolog have made early advances possible in the area of combining static and dynamic language features. However, we also address briefly some other issues related to extending the expressiveness and functionality of the language., Partially funded by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021-047102-I, by the Comunidad de Madrid program P2018/TCS-4339 BLOQUES-CM, and by the Tezos foundation.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Solving Recurrence Relations using Machine Learning, withApplication to Cost Analysis

  • Klemen, Maximiliano
  • Carreira-Perpiñán, Miguel Á.
  • López-García, Pedro
Proceedings 39th International Conference on Logic Programming, ICLP 2023, Imperial College London, UK, 9th July 2023 - 15th July 2023 14 páginas, 1 figura, 1 tabla, Automatic static cost analysis infers information about the resources used by programs without actually running them with concrete data, and presents such information as functions of input data sizes. Most of the analysis tools for logic programs (and other languages) are based on setting up recurrence relations representing (bounds on) the computational cost of predicates, and solving them to find closed-form functions that are equivalent to (or a bound on) them. Such recurrence solving is a bottleneck in current tools: many of the recurrences that arise during the analysis cannot be solved with current solvers, such as Computer Algebra Systems (CASs), so that specific methods for different classes of recurrences need to be developed. We address such a challenge by developing a novel, general approach for solving arbitrary, constrained recurrence relations, that uses machine-learning sparse regression techniques to guess a candidate closed-form function, and a combination of an SMT-solver and a CAS to check whether such function is actually a solution of the recurrence. We have implemented a prototype and evaluated it with recurrences generated by a cost analysis system (the one in CiaoPP). The experimental results are quite promising, showing that our approach can find closed-form solutions, in a reasonable time, for classes of recurrences that cannot be solved by such a system, nor by current CASs., This work has been partially supported by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021-047102-I, and the Tezos foundation.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

VeriFly: On-the-fly Assertion Checking via Incrementality

  • Sánchez-Ordaz, Miguel A.
  • García-Contreras, Isabel
  • Pérez, Víctor
  • Morales, José F.
  • López-García, Pedro
  • Hermenegildo, Manuel V.
16 páginas, 11 figuras, 2 tablas, Assertion checking is an invaluable programmer¿s tool for finding many classes of errors or verifying their absence in dynamic languages such as Prolog. For Prolog programmers, this means being able to have relevant properties, such as modes, types, determinacy, nonfailure, sharing, constraints, and cost, checked and errors flagged without having to actually run the program. Such global static analysis tools are arguably most useful the earlier they are used in the software development cycle, and fast response times are essential for interactive use. Triggering a full and precise semantic analysis of a software project every time a change is made can be prohibitively expensive. This is specially the case when complex properties need to be inferred for large, realistic code bases. In our static analysis and verification framework, this challenge is addressed through a combination of modular and incremental (context- and path-sensitive) analysis that is responsive to program edits, at different levels of granularity. In this tool paper, we present how the combination of this framework within an integrated development environment (IDE) takes advantage of such incrementality to achieve a high level of reactivity when reflecting analysis and verification results back as colorings and tooltips directly on the program text ¿ the tool¿s VeriFly mode. The concrete implementation that we describe is Emacs-based and reuses in part off-the-shelf ¿on-the-fly¿ syntax checking facilities (flycheck). We believe that similar extensions are also reproducible with low effort in other mature development environments. Our initial experience with the tool shows quite promising results, with low latency times that provide early, continuous, and precise assertion checking and other semantic feedback to programmers during the development process. The tool supports Prolog natively, as well as other languages by semantic transformation into Horn clauses., Research partially funded by MINECO MICINN PID2019-108528RB-C21 ProCode project, FPU grant 16/04811, the Madrid M141047003 N-GREENS and P2018/TCS-4339 BLOQUES-CM programs, and the Tezos foundation. We are also grateful to the anonymous reviewers for their comments
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A Machine Learning-Based Approach for Solving Recurrence Relations and Its use in Cost Analysis of Logic Programs

  • Rustenholz, Louis
  • Klemen, Maximiliano
  • Carreira-Perpiñán, Miguel Á.
  • López-García, Pedro
45 páginas, 6 figuras, 3 tablas., Automatic static cost analysis infers information about the resources used by programs without actually running them with concrete data and presents such information as functions of input data sizes. Most of the analysis tools for logic programs (and many for other languages), as CiaoP, are based on setting up recurrence relations representing (bounds on) the computational cost of predicates and solving them to find closed-form functions. Such recurrence solving is a bottleneck in current tools: many of the recurrences that arise during the analysis cannot be solved with state-of-the-art solvers, including computer algebra systems (CASs), so that specific methods for different classes of recurrences need to be developed. We address such a challenge by developing a novel, general approach for solving arbitrary, constrained recurrence relations, that uses machine learning (sparse-linear and symbolic) regression techniques to guess a candidate closed-form function, and a combination of an SMT-solver and a CAS to check whether such function is actually a solution of the recurrence. Our prototype implementation and its experimental evaluation within the context of the CiaoPP system show quite promising results. Overall, for the considered benchmark set, our approach outperforms state-of-the-art cost analyzers and recurrence solvers and can find closed-form solutions, in a reasonable time, for recurrences that cannot be solved by them., Research partially supported by MICINN projects PID2019-108528RB-C21 ProCode, TED2021- 132464B-I00 PRODIGY, and by the Tezos Foundation., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An Order Theory Framework of Recurrence Equations for Static Cost Analysis – Dynamic Inference of Non-Linear Inequality Invariants

  • Rustenholz, Louis
  • López-García, Pedro
  • Morales, J.F.
  • Hermenegildo, Manuel V.
Static Analysis, 31st International Symposium, SAS 2024, Pasadena, CA, USA, October 20–22, 2024, Recurrence equations have played a central role in static cost analysis, where they can be viewed as abstractions of programs and used to infer resource usage information without actually running the programs with concrete data. Such information is typically represented as functions of input data sizes. More generally, recurrence equations have been increasingly used to automatically obtain non-linear numerical invariants. However, state-of-the-art recurrence solvers and cost analysers suffer from serious limitations when dealing with the (complex) features of recurrences arising from cost analyses. We address this challenge by developing a novel order-theoretical framework where recurrences are viewed as operators and their solutions as fixpoints, which allows leveraging powerful pre/postfixpoint search techniques. We prove useful properties and provide principles and insights that enable us to develop techniques and combine them to design new solvers. We have also implemented and experimentally evaluated an optimisation-based instantiation of the proposed approach. The results are quite promising: our prototype outperforms state-of-the-art cost analysers and recurrence solvers, and can infer tight non-linear lower/upper bounds, in a reasonable time, for complex recurrences representing diverse program behaviours., This work has been partially supported by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021- 047102-I, and the Tezos foundation, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

An Order Theory Framework of Recurrence Equations for Static Cost Analysis - Dynamic Inference of Non-Linear Inequality Invariants

  • Rustenholz, Louis
  • López-García, Pedro
  • Morales, José F.
  • Hermenegildo, Manuel V.
30 páginas, 5 figuras, 3 tablas, Recurrence equations have played a central role in static cost analysis, where they can be viewed as abstractions of programs and used to infer resource usage information without actually running the pro- grams with concrete data. Such information is typically represented as functions of input data sizes. More generally, recurrence equations have been increasingly used to automatically obtain non-linear numerical in- variants. However, state-of-the-art recurrence solvers and cost analysers suffer from serious limitations when dealing with the (complex) features of recurrences arising from cost analyses. We address this challenge by developing a novel order-theoretical framework where recurrences are viewed as operators and their solutions as fixpoints, which allows lever- aging powerful pre/postfixpoint search techniques. We prove useful prop- erties and provide principles and insights that enable us to develop tech- niques and combine them to design new solvers. We have also imple- mented and experimentally evaluated an optimisation-based instantia- tion of the proposed approach. The results are quite promising: our pro- totype outperforms state-of-the-art cost analysers and recurrence solvers, and can infer tight non-linear lower/upper bounds, in a reasonable time, for complex recurrences representing diverse program behaviours., This work has been partially supported by the Tezos foundation and by MICINN projects PID2019-108528RB-C21 ProCode and TED2021-132464B-I00 PRODIGY.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Checkification: A Practical Approach for Testing Static Analysis Truths

  • Ferreiro, Daniela
  • Casso, Ignacio
  • Morales, José F.
  • López-García, Pedro
  • Hermenegildo, Manuel V.
38 páginas, 1 figura, 7 tablas, Static analysis is an essential component of many modern software development tools. Unfortunately, the ever-increasing complexity of static analyzers makes their coding error-prone. Even analysis tools based on rigorous mathematical techniques, such as abstract interpretation, are not immune to bugs. Ensuring the correctness and reliability of software analyzers is crit- ical if they are to be inserted in production compilers and development environments. While compiler validation has seen notable success, formal validation of static analysis tools remains relatively unexplored. In this paper we present checkification, a simple, automatic method for testing static analyzers. Broadly, it consists in checking, over a suite of benchmarks, that the properties inferred statically are satisfied dynamically. The main advantage of our approach lies in its simplicity, which stems directly from framing it within the Ciao assertion-based validation framework, and its blended static/dynamic assertion checking approach. We demonstrate that in this setting, the analysis can be tested with little effort by combining the following compo- nents already present in the framework: 1) the static analyzer , which outputs its results as the original program source with assertions interspersed; 2) the assertion run-time checking mech- anism, which instruments a program to ensure that no assertion is violated at run time; 3) the random test case generator , which generates random test cases satisfying the properties present in assertion preconditions; and 4) the unit-test framework , which executes those test cases. We have applied our approach to the CiaoPP static analyzer, resulting in the identification of many bugs with reasonable overhead. Most of these bugs have been either fixed or confirmed, helping us detect a range of errors not only related to analysis soundness but also within other aspects of the framework., Partially funded by MICINN projects PID2019-108528RB-C21 ProCode, TED2021- 132464B-I00 PRODIGY , and FJC2021-047102-I, and by the Tezos foundation. We would also like to thank the anonymous reviewers for their very useful feedback. This paper is an extended version of our previous work published in LOPSTR’20, Peer reviewed