Control-Flow Refinement by Partial Evaluation, and its Application to Termination and Cost Analysis
| Autor: | Jesús J. Doménech, John P. Gallagher, Samir Genaim |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Soundness
FOS: Computer and information sciences Computer Science - Programming Languages Horn clause Computer science Context (language use) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Partial evaluation Theoretical Computer Science Control flow Program analysis Computational Theory and Mathematics 010201 computation theory & mathematics Artificial Intelligence Hardware and Architecture Termination analysis 0202 electrical engineering electronic engineering information engineering Programming paradigm 020201 artificial intelligence & image processing Algorithm Software Programming Languages (cs.PL) |
| DOI: | 10.48550/arxiv.1907.12345 |
| Popis: | Control-flow refinement refers to program transformations whose purpose is to make implicit control-flow explicit, and is used in the context of program analysis to increase precision. Several techniques have been suggested for different programming models, typically tailored to improving precision for a particular analysis. In this paper we explore the use of partial evaluation of Horn clauses as a general-purpose technique for control-flow refinement for integer transitions systems. These are control-flow graphs where edges are annotated with linear constraints describing transitions between corresponding nodes, and they are used in many program analysis tools. Using partial evaluation for control-flow refinement has the clear advantage over other approaches in that soundness follows from the general properties of partial evaluation; in particular, properties such as termination and complexity are preserved. We use a partial evaluation algorithm incorporating property-based abstraction, and show how the right choice of properties allows us to prove termination and to infer complexity of challenging programs that cannot be handled by state-of-the-art tools. We report on the integration of the technique in a termination analyzer, and its use as a preprocessing step for several cost analyzers. Under consideration for acceptance in TPLP. Comment: Paper presented at the 35th International Conference on Logic Programming (ICLP 2019), Las Cruces, New Mexico, USA, 20-25 September 2019, 18 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|