Question

1. 程序合成 program synthesis 的目标是使编码过程自动化，并生成一个满足用户指定意图的计算机程序。成功的program synthesis不仅可以提高有经验的程序员的生产力，还可以让更多人了解编程。

   在实现program synthesis时，有两个关键的挑战：搜索空间的不可控性、正确指定用户意图的困难。

   • 为了使得搜索空间有表达能力，人们需要一个大的搜索空间，这给高效搜索带来了挑战。以前的工作利用 domain-specific language 来限制搜索空间，然而，这限制了 synthesized program 的适用性。相反，通用编程语言（如 C、Python ）虽然适用性更广，但是引入了一个更大的搜索空间。为了在巨大的 program space 中搜索，论文 《CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis》 将任务公式化为语言建模 language modeling ：给定前序 tokens 的条件下，学习 next token 的条件分布，并利用 Transformer 和大规模的自监督预训练。这种方法在各种模式中都取得了成功。同样，之前的工作也为 programming language understanding 开发了预训练好的语言模型。

   • 为了成功地实现program synthesis，用户必须采用一些手段将他们的意图传达给模型，如逻辑表达式logical expression （指定程序的输入和输出之间的逻辑关系）、伪代码pseudo-code 、input-output examples 、或以自然语言方式的口头规范。

     • 一方面，完整的正式的规范 specification 受益于用户意图的精确规范 exact specification ，但可能需要领域的专业知识、以及用户的努力来将意图转化为这样的形式。

     • 另一方面，仅仅基于 input-output examples 的规范，其成本较低，但可能对意图的规范不足 under-specify ，导致不准确的解决方案。

     以前的工作得益于各种方法（及其组合）作为 program synthesis model 的输入，包括伪代码、程序的一部分及其文档、或带有 input-output examples 的自然语言段落。然而，论文 《CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis》 认为：真正用户友好的意图的形式是自然语言文本。

   为了克服这些挑战，论文 《CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis》 提出了一种多轮program synthesis （ multi-turn program synthesis ）方法：用户通过逐步提供自然语言的规范与合成系统 synthesis system 进行交流，同时从系统中接收以 synthesized subprogram 为形式的响应。这样，用户与系统一起在 multiple steps 中完成 program 。以下两点考虑是这种方法的动机：

   • 首先，作者推测，将一个潜在的长而复杂的规范分解成多个步骤，会使模型更容易理解，从而改善program synthesis。在 multi-turn 方法中，模型可以专注于与一个子程序相关的规范，而避免艰难地追踪子程序之间复杂的依赖关系。这除了方便指定用户意图外，还有效地减少了搜索空间。事实上，作者的推测在论文的实验中得到了证实，通过 multi-turn 方法合成的程序的质量更高。

   • 其次， code 表现出一种弱模式 weak pattern：自然语言和编程语言交错。这种模式可以被利用。这种模式是由程序员用注释comment 来解释程序的 functionality 而形成的。在 language modeling objective 下，作者假设交错模式为模型提供了一个监督信号，用于在 multiple turn 中生成给定的自然语言描述的程序。这个信号是高度噪音的或微弱的，因为只有一部分数据会表现出这样的模式，注释可能是不准确的、或没有信息 uninformative 的，有些注释甚至可能被放置在不相关的位置。然而，扩大模型和数据规模可能会克服这种弱监督，使模型能够发展出 multi-turn program synthesis 的能力。这使得用户的意图可以用 multiple turn 来表达，也就是说，意图可以被分解并逐一实现，而每个 turn 可以很容易地用自然语言表达。

   在这项工作中，论文开发了一个 multi-turn programming benchmark 来为 multi-turn program synthesis 衡量模型的能力。为了解决 benchmark 中的问题，一个模型需要在多个步骤中合成一个程序，其中用户用自然语言指定每个 turn 的意图。如下图所示，该模型合成了一个程序来提取电子邮件地址的用户名。benchmark 的性能是通过专家编写的测试用例的通过率来衡量的。据作者所知，这是第一个 multi-turn program synthesis benchmark ，它允许对 multi-turn program synthesis 进行定量分析。随着大型语言模型中 multi-turn program synthesis 的涌现 emergence ，作者相信这个 benchmark 将促进未来的program synthesis 研究。

   下图中，$p_i$$ p_i $ 为用户提供的 prompt ，$s_i$$ s_i $ 为模型返回的 subprogram 。最终的结果是所有的 subprogram 组合在一起而形成的。因此，用户提供的 prompt 对于最终结果是至关重要的，这是优点也是缺点：优点是用户可以对代码生成过程进行更精细的控制，缺点是需要用户具备一定程度的专业知识（需要知道怎么描述程序的每一步）。

   ①为整个过程的示意图，②为模型生成的过程（以之前的 prompts 和 subprograms 为条件），③为最终结果。

   

   论文贡献： 论文与最近同时进行的、使用 single-turn user intent specification 的工作的基本想法一致，即用采用语言模型来执行 program synthesis 。此外：

   • 论文研究了在 scaling law 下自回归模型中的 multi-turn program synthesis 。

   • 论文利用这种能力引入了一个 multi-turn program synthesis 范式。

   • 论文用一个新的 multi-turn programming benchmark （https://github.com/salesforce/CodeGen/tree/main/benchmark）对其特性进行定量研究。

   • 论文将开源 model checkpoint （https://github.com/salesforce/CodeGen）和自定义训练库：JAXFORMER （https://github.com/salesforce/jaxformer）。对于 program synthesis 来说，目前还没有可以与 Codex 竞争的、开源的大型模型。这阻碍了 program synthesis 的发展，因为训练这些模型所需的昂贵的计算资源只有数量有限的机构可以获得。作者的开源贡献允许广泛的研究人员研究和改善这些模型，这可能大大促进研究进展。

2. 相关工作：

   • Program Synthesis：虽然 program synthesis 有很长的历史，但两个固有的挑战仍未解决：program space 非常棘手、难以准确表达用户意图。

     • 之前的大量研究试图通过探索随机搜索技术、自上而下的演绎搜索等方法来解决第一个问题，然而，这些方法的可扩展性仍然是有限的。

     • 用户的意图可以用各种方法来表达：正式的逻辑规范、input-output examples 、自然语言描述。完整的和正式的规范需要太多的努力，而非正式的如 input-output examples 往往对问题的规范不足。

     由于大规模的模型和数据，well-learned 的条件分布和语言理解能力可以有效地解决这两个挑战。

     有几项工作研究将对话意图转换为programmable representation ，如 SQL 或 dataflow graph 。我们提出的 benchmark 要求生成 Python ，这是更通用、更复杂的。

   • Large Language Model：Transformer 通过注意力机制捕捉序列的元素之间的依赖关系，并且具有高度的可扩展性。它已被成功地应用于自然语言处理、计算机视觉、以及许多其他领域。之前的工作，如 CuBERT、CodeBERT、PyMT5 和 CodeT5，已经将 Model（即，Transformer ）应用于 code understanding ，但这些大多侧重于代码检索、分类和程序修复。

     最近和同时进行的几项工作探索了使用大型语言模型进行 program synthesis 及其有效性。然而他们关注的是在 single turn 中生成代码，而我们提议将 specification 分解为 multiple turns ，并证明这对提高合成质量非常有效。值得指出的是，《Program synthesis with large language models》探索了在 multiple iterations 中完善代码的方法，但它本质上是一种 single-turn 方法，因为每个 single turn 都会产生一个完整的程序。

     用intermediate information 来 prompting 预训练好的语言模型以提高任务性能已经引起了人们的兴趣。我们提出的 MTPB 也允许模型利用 past turns 作为上下文。

   • Benchmarks for Program Synthesis：为了定量分析 program synthesis模型，人们已经提出了几个具有不同输入形式的 benchmark 。流行的输入形式包括：同一行中的前序代码 preceding code、伪代码、docstring 和函数签名、problem description 。在大多数 case 中，仅仅向模型提供直接相关的输入信息。

     相反，一些以前的工作提出了一些 benchmark，这些 benchmark 衡量在给定目标程序周围的 program context （如变量、其它函数、前序的代码块/文本块）的条件下，生成程序的能力，主要的重点是生成目标程序本身。

     我们提出一个新的 benchmark ，要求通过 multi-turn prompts逐步生成子程序。