We present a novel algorithm that synthesizes imperative programs for
introductory programming courses. Given a set of input-output examples and a
partial program, our algorithm generates a complete program that is consistent
with every example. Our key idea is to combine enumerative program synthesis
and static analysis, which aggressively prunes out a large search space while
guaranteeing to find, if any, a correct solution. We have implemented our
algorithm in a tool, called SIMPL, and evaluated it on 30 problems used in
introductory programming courses. The results show that SIMPL is able to solve
the benchmark problems in 6.6 seconds on average.

我们提出了一种新颖的算法，该算法合成初级编程课程的命令式程序，基于枚举程序合成和静态分析相结合的关键思想，我们的算法在平均 6.6 秒内能够解决基准问题。

从静态分析引导的示例中综合关键程序

Synthesizing Imperative Programs from Examples Guided by Static Analysis

This article presents a new numerical abstract domain for static analysis by
abstract interpretation. It extends a former numerical abstract domain based on
Difference-Bound Matrices and allows us to represent invariants of the form
(+/-x+/-y<=c), where x and y are program variables and c is a real constant. We
focus on giving an efficient representation based on Difference-Bound Matrices
- O(n2) memory cost, where n is the number of variables - and graph-based
algorithms for all common abstract operators - O(n3) time cost. This includes a
normal form algorithm to test equivalence of representation and a widening
operator to compute least fixpoint approximations.

本篇论文介绍了一种新的数值抽象领域，用于静态分析；该数值抽象领域基于差界矩阵（Difference-Bound Matrices）扩展并允许我们表示形式为 (+/-x+/-y<=c) 的不变式。我们关注基于差界矩阵的有效表示 - O (n2) 存储空间成本，其中 n 是变量数量，以及适用于所有常见抽象运算符 - O (n3) 时间成本的基于图形算法。这包括一个正常形式算法来测试表示的等价性，以及一个扩大运算符来计算最小修正点近似。