大家好，欢迎来到IT知识分享网。

1. 引用

Ellis, Kevin & Nye, Maxwell & Pu, Yewen & Sosa, Felix & Tenenbaum, Josh & Solar-Lezama, Armando. (2019). Write, Execute, Assess: Program Synthesis with a REPL.

2. 摘要

我们提出了一种神经程序合成方法，该方法集成了编写，执行和评估代码以导航可能程序的搜索空间的组件。我们为搜索过程配备了解释程序或 read-eval-print-loop（REPL）。REPL 会立即执行部分编写的程序，并获取并公开其语义。REPL 解决了程序合成的一个基本挑战：语法上的微小更改所导致的语义上的巨大变更。我们训练了一对模型，提出了编写新代码的策略，并评估到目前为止编写的代码前景的价值函数。在测试时，我们可以将这些模型与顺序蒙特卡洛算法结合使用。我们将方法可以应用于两个领域：合成文本编辑程序以及推导 2D 和 3D 图形程序。

3. 方法介绍

我们的程序合成方法集成了编写，执行和评估代码的组件，以在程序的语义空间上执行随机搜索。这种方法的关键在于三个主要组成部分：第一，搜索空间的定义；第二，对代码编写策略和代码评估价值功能进行训练；第三，序列化蒙特卡洛算法，该算法利用策略和值通过维护大量候选搜索分支来进行搜索。

3.1 程序的语义搜索空间

可能程序的空间通常由上下文无关文法（Context Free Grammar，CFG）定义，上下文无关文法指定语法上有效的程序集。但是，在编写代码时，程序通常是分段构建的。因此，很自然地将程序的搜索空间表示为部分构造的程序集上的马尔可夫决策过程（Markov Decision Process，MDP），下面给出相关定义：

状态。状态是元组 s =（pp，spec），其中 pp 是一组部分构造的程序树（直观上是“范围内的变量”），而 spec 是目标规范。因此，我们的 MDP 受目标限制。起始状态为（{}，spec）。

动作。动作 a 是 CFG 的生产规则（在 REPL 中键入的代码行）。

过渡。过渡 T 接受部分程序 pp 的集合并将动作 a 应用于以下任一情况：

1.如果 a 是终结符，则实例化新的子树：T（pp，a）= pp∪{a}

2.如果 a 是非终结符，则合并多个子树：T（pp，a）=（pp∪{a（t1 …tk）}）-{t1…tk}。注意，在非终结符的情况下，被删除或“垃圾回收”。奖励如果存在满足规范的程序 p∈pp，则奖励为 1，否则为 0。请注意，我们的 MDP 状态是在语法空间 pp 和语义空间 spec 中共同定义的。为了弥合这种差距，我们使用 REPL，它将部分程序 pp 的集合评估为语义或“执行”表示。令 pp 为 n 个程序的集合，pp = {p1… pn}并让[[p]]表示程序 p 的执行，那么我们可以将 REPL 状态写为[[pp]] = {[[p1]]… [[pn]]}。

3.2 训练代码编写策略 π 和代码评估值 v

给定一对评估的程序状态和规范（[[pp]]，规范），策略 π 输出动作的分布，写为 π（a | [[pp]]，规范），而值函数 v 预测期望值 从状态（[[pp]]，规格）开始的奖励。 在我们的 MDP 中，预期的总报酬与从部分程序 pp 开始的推出满足规格的概率相符：

因此，值函数仅执行二进制分类，从而预测状态导致成功程序的可能性。

3.3 预训练 π

因为我们假设存在 CFG 和 REPL，所以我们可以通过从 CFG 采样随机程序，执行它们以获得规格，然后恢复实际操作序列来生成无限的训练数据流。具体来说，我们从分布在合成训练数据 D 上的样本中抽取样本，样本 D 由三部分规范，动作序列以及每一步中部分构建的程序组成：（spec，{at}t≤T，{ppt }t≤T）〜D。在预训练期间，在策略下，我们将这些动作序列的对数可能性最大化：

训练 π 和 v。我们通过以 REINFORCE 的形式针对规格〜D 抽样策略的推出，对策略进行微调并训练价值函数。具体来说，给定规范〜D，策略的推出包括一系列动作{at}t≤T，一系列部分程序{ppt}t≤T 以及奖励 R = 1 [[ppT]]满足规范。 给定特定的部署，我们训练 v 和 π 以最大化：

3.3 交错编写，执行和评估代码的 SMC 推理算法

在测试时，我们交错编写代码，即从策略中提取动作，并交错评估代码，即查询值函数（因此也交错执行，这总是在运行这些网络之前发生）。顺序蒙特卡洛方法（其中最著名的例子是粒子过滤器）是一种灵活的框架，可用于设计采样器，这些采样器可推导以一对观测变量序列为条件的 T 个潜在变量{xt}t≤T 的序列{yt}t≤T，我们通过设置随时间变化的策略隐性变量序列（即 xt = ppt），并在每个时间步长（即 yt = spec）中将规范标识为观察到的变量，来构造一个 SMC 采样器进行设置，通过定义将其连接到政策和价值网络

就像粒子过滤器一样，我们通过维持 K 个粒子的总体来近似地从 P（{ppt}t≤T| spec）中采样-通过从 π 采样，通过 v 进行重要性加权，然后重新采样，使粒子总数及时向前发展。与 MCMC 不同，顺序蒙特卡罗方法不会遇到“老化”问题，但可能需要大量粒子。我们重复运行 SMC 采样器，每次将粒子计数加倍，直到达到超时。

4. 实验

我们研究了一系列模型和测试时间推断策略，其主要目的是回答三个问题：对 REPL 指导的程序合成器有用的价值函数；在实践中，如何在测试时使用值函数；以及在实践中，我们的完整模型如何与执行指导合成的现有方法进行比较。我们针对每种模型和推理策略，通过测量其可以有效搜索程序空间的效率来回答这些问题，即找到的最佳程序是搜索时间的函数。

我们通过比较 SMC 与策略推出情况，以及通过比较使用 π＆v 的波束搜索与仅在 π 下的波束解码来测试值函数的重要性。正交地，为了测试在测试时如何最好地使用值函数，我们将 SMC（w /值）与波束搜索（w /值）以及 A ∗（w /值作为启发式函数）进行了对比。最后，我们将最好的方法 SMC 与最新的执行指导方法进行了对比，这两种方法都在学习策略下执行波束搜索解码。

为了进行健全性检查，我们还训练了“ no REPL”基线，该基线仅使用规范和中间程序语法一次即可解码整个程序。这测试了 REPL 是帮助还是阻碍。这些“ no REPL”架构分别遵循先前的 CSGNet 和 RobustFill 进行的 CAD 和字符串编辑

5 致谢

本文由南京大学软件学院2019级硕士研究生刘芳潇翻译转述