Targeted Synthesis for Programming with Data Invariants

John Sarracino, Shraddha Barke, Nadia Polikarpova, Sorin LernerarXiv 2019 · OpenReview

Abstract

Programmers frequently maintain implicit data invariants, which are relations between different data structures in a program. Traditionally, such invariants are manually enforced and checked by programmers. This ad-hoc practice is difficult because the programmer must manually account for all the locations and configurations that break an invariant. Moreover, implicit invariants are brittle under code-evolution: when the invariants and data structures change, the programmer must repeat the process of manually repairing all of the code locations where invariants are violated. A much better approach is to introduce data invariants as a language feature and rely on language support to maintain invariants. To handle this challenge, we introduce Targeted Synthesis, a technique for integrating data invariants with invariant-agnostic imperative code at compile-time. This technique is nontrivial due to the complex structure of both invariant specifications, as well as general imperative code. The key insight is to take a language co-design approach involving both the language of data invariants, as well as the imperative language. We leverage this insight to produce two high-level results: first, we support a language with iterators without requiring general quantified reasoning, and second, we infer complicated invariant-preserving patches. We evaluate these claims through a language termed Spyder, a core calculus of data invariants over imperative iterator programs. We evaluate the expressiveness and performance of Spyder on a variety of programs inspired by web applications, and we find that Spyder efficiently compiles and maintains data invariants.

Introduction

In almost every non-trivial program, there are "data invariants"—logical relationships between pieces of data that must remain true throughout execution. For example, in a budget application, a "Total" field must always equal the sum of individual items. Traditionally, programmers maintain these invariants manually by "sprinkling" update logic throughout their codebase. This practice is problematic as it is highly error-prone and brittle; any change to the invariant requires manual updates to every code location that touches the relevant variables.

While existing tools can verify if an invariant is broken, they rarely assist in fixing it. Conversely, declarative constraint solvers can fix data at runtime, but they are often slow, unpredictable, and can accidentally revert intended changes—a challenge known as the "frame problem."

The Spyder Language

To address these issues, we propose Spyder, a core imperative language designed specifically to handle collections and iterators. Spyder's standout feature is the foreach invariant, which allows programmers to define relationships across entire collections. This approach makes invariants first-class features that the compiler can track and maintain automatically.

Targeted Synthesis

The core algorithmic contribution of this work is Targeted Synthesis. Unlike traditional program synthesis, which attempts to generate entire functions from specifications, Targeted Synthesis focuses on generating local, efficient code patches to restore invariants whenever they are broken.

Targeted synthesis (b) identifies the exact location of an invariant violation in a budget application (a) and generates a local patch within the existing loop, contrasting with a less efficient naive approach.

Targeted Synthesis achieves efficiency through three main strategies:

  1. Locality: It identifies the specific basic block where an invariant is violated and inserts a patch at that exact point.
  2. Structural Similarity: If an invariant is defined over a collection and the programmer is already looping over that collection, the algorithm "pushes" the synthesis requirement inside the existing loop. This avoids the need to synthesize complex inductive loop invariants from scratch.
  3. Solving the Frame Problem: The algorithm uses a syntactic check to ensure the synthesized patch only modifies "stale" variables, preventing it from undoing the programmer's intended changes.

Evaluation and Results

We evaluated Spyder using a suite of 11 benchmarks, including arithmetic programs and web-inspired applications like a Budget Planner and a Game of Life implementation. We compared Spyder against manual imperative implementations, Functional Reactive Programming (FRP) models, and Sketch, a state-of-the-art general-purpose program synthesizer.

Key findings include:

  • Succinctness: Spyder specifications were up to 3x smaller than equivalent FRP specifications.
  • Ease of Evolution: Spyder required significantly fewer manual code changes when adding new features that altered data relationships.
  • Performance: Most patches were synthesized in under a second. Spyder scaled much better than Sketch, which struggled with larger array sizes.
  • Compositionality: Multiple invariants can be defined independently, and the synthesizer handles their intersection, ensuring all are maintained simultaneously.

Limitations and Future Work

The current model of Spyder is limited to iterator-based invariants and does not handle complex pointer-based data structures or variable aliasing. Additionally, it assumes fixed collection sizes. Future work will explore extending Targeted Synthesis to object-oriented languages and investigating its application in concurrent programming environments.

Summary updated

Abstract

Programmers frequently maintain implicit data invariants, which are relations between different data structures in a program. Traditionally, such invariants are manually enforced and checked by programmers. This ad-hoc practice is difficult because the programmer must manually account for all the locations and configurations that break an invariant. Moreover, implicit invariants are brittle under code-evolution: when the invariants and data structures change, the programmer must repeat the process of manually repairing all of the code locations where invariants are violated. A much better approach is to introduce data invariants as a language feature and rely on language support to maintain invariants. To handle this challenge, we introduce Targeted Synthesis, a technique for integrating data invariants with invariant-agnostic imperative code at compile-time. This technique is nontrivial due to the complex structure of both invariant specifications, as well as general imperative code. The key insight is to take a language co-design approach involving both the language of data invariants, as well as the imperative language. We leverage this insight to produce two high-level results: first, we support a language with iterators without requiring general quantified reasoning, and second, we infer complicated invariant-preserving patches. We evaluate these claims through a language termed Spyder, a core calculus of data invariants over imperative iterator programs. We evaluate the expressiveness and performance of Spyder on a variety of programs inspired by web applications, and we find that Spyder efficiently compiles and maintains data invariants.
BibTeX
@misc{sarracino2019targeted,
  author = {John Sarracino and Shraddha Barke and Nadia Polikarpova and Sorin Lerner},
  title = {{Targeted Synthesis for Programming with Data Invariants}},
  year = {2019},
  eprint = {1904.13049},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.13049},
}
Figure