程序综合 — 让代码自己编写
Program synthesis - let the code write itself
从术语到直觉(第一部分)
你可能听说过但不完全理解的一个术语是“程序合成”,通常被称为人工智能进军编写代码的一种尝试。本文是一个三部分系列的第一部分,旨在揭示这个概念的神秘面纱。在这里,我们专注于理解“程序合成”的语义本质。虽然我努力保持清晰和简单,但为了易读性,可能会忽略一些技术细节。
要理解“程序合成”,我们首先必须解决“程序”这个术语。所以,让我们先问一下,什么是程序。

程序
基本上,编程是告诉计算机该做什么的行为。在手机上设置提醒、自定义社交媒体照片、优化交通或设置这篇VoAGI文章,所有这些都是编程。为了确保我们保持同步,让我们来看看编程三要素:
- 一个程序员将任务转化为一个
程序
。 程序员
提供的程序
是解释器
理解的东西。解释器
接收程序
并执行操作。

那么为什么要花时间学习编程呢?因为计算机提供了我们无法匹敌的能力。我们不需要手动将十几张照片拼接成全景照片,我肯定无法在没有手机的提示下记住所有朋友的生日,我不能亲自给大家递送博客。
程序合成
程序合成是使编程变得更容易的系统。GCC让您无需编写汇编语言,您的智能手机操作系统可以将十几张照片制作成全景照片。此页面顶部的小绿色“发布”按钮将把所有内容发送给您。通过程序合成,您可以在一个增强版的编程语言中工作,让我们称之为“Program++”。这比原始的程序更简单。

合成器充当中间人,将您的Program++转换回原始程序。当您将这个合成器与一个解释器配对使用时,您将获得一个高级解释器,让我们称之为“Interpreter++”。这个升级版接收您的Program++(通常称为spec
或规范)并执行任务。这个过程是递归的,您可以不断添加合成器和解释器的层次,使编程变得越来越容易。因此,程序合成就是“更容易的编程”。
现代的程序合成
程序合成的艺术就是尽量简化Program++/spec
。如今,程序合成技术变得越来越复杂,比如ChatGPT或CoPilot,它们从高级需求生成代码,减少了“手写”代码的需求,从而减少人为错误。

在我们定义了程序和程序综合的概念之后,我们需要准确定义一个问题。
问题
让我们先问一个问题:程序员如何编写程序,以便解释器对某个任务执行正确的操作?

以任务为规范
任务可以以各种方式进行规范 – 想象一下制作沙拉的不同食谱。验证程序的正确性也有多个角度 – 考虑判断沙拉是否美味、健康或者视觉上吸引人的不同标准。然而,许多现实世界任务的细微差别常常逃脱了计算机的理解。
规范作为问题
规范或者spec
是一种陈述任务的方式,使得人类和计算机都能够就需要完成的任务达成一致。输入-输出(或者简称为I/O)是一种稀有而特殊的沟通形式,人类和计算机都能够轻松理解。

还有其他形式的规范,例如,它可以是一个要最大化的目标函数,一组对计算机行为的约束,或者一个自然语言句子。但是在编写spec
时有很大的灵活性。不同的spec
可以从不同的角度、语法或粒度级别描述同一个问题。例如,如果你想要对一个包含n个数字的列表(L)进行排序,我们可以提供:
- 一系列的输入-输出对: In₁[
3,2,1
] Out₁[1,2,3
] | In₂[0,-1,2
] Out₂[-1,0,2
] | In₃[5,8,100
] Out₃[5,8,100
] | In₄[9
] Out₄[9
] … - 一个句子:“将整数列表按升序排序。”
- 一个数学函数: f( X ) = x₁≤ x₂≤ x₃ … ≤ xₙ
- 一个递归定义: Sorted(L) ⇔ L[1] ≤ min( L[2:n] ) ∧ Sorted( L[2:n] )
类似地,对于制作沙拉,spec可能如下:
- 输入-输出对: In₁[
lettuce
,tomatoes
,cucumber
] Out₁[salad
] | In₂[cucumber, caesar
,tomatoes
] Out₂[not salad
] - 自然语言:
将莴苣、番茄和黄瓜混合在一起。
- 基于约束: 必须包含[
至少一种绿色蔬菜和一种蛋白质来源。
]
正确性
有了spec
,计算机可以通过检查在输入上执行程序是否产生相应的输出来自动判断程序是否“做对了”。我们称这个过程为验证器。

现在,一个简单的验证器会给你一个直接的答案:True或False。 is_sorted( [1,2,4] ) =
True。组合元素 [西红柿
, 凯撒沙拉
] 是沙拉的配料吗?False。但我们可以进一步提高它 —— 一些验证器超越了简单的二进制答案,深入到衡量程序表现的度量或尺度中。
从逻辑到学习
传统上,程序合成是一个由严格的逻辑规则和算法推理主导的领域。然而,由于机器学习技术的融入,这一格局正在迅速改变。基于学习的方法的转变正在革新程序合成的速度、准确性和效率。

多样的方法:程序合成的分类程序合成不是一种“一刀切”的解决方案。根据任务的需求,不同的方法或合成类型可能更有优势。让我们深入了解其中一些类型。
- 演绎合成 —— 传统派。依赖于形式方法、逻辑框架和算法原理。非常准确,但可能需要大量的计算资源。适用于可靠性至关重要的关键系统。
- 归纳合成 —— 现代派。主要依靠机器学习技术和启发式方法。在速度和适应性方面表现出色,但可能缺乏演绎方法的严格准确性。最适合快速开发周期和非关键任务。
- 随机合成 —— 现实主义派。利用概率模型处理规范或环境中的不确定性。提供平衡的方法,但可能需要微调以达到所需的可靠性。非常适合预期存在一定程度的不确定性或变化的应用。
让我用一些思考来结束……
程序合成 —— 超越人类能力
我们不需要局限自己。 我们的目标是构建一个能够超越更远的合成器! 目标不仅仅是复制人类的能力,而是超越人类的能力,因为程序合成发现了人类目前无法解决的新问题。我们谈论的是在医学、金融甚至解码宇宙方面有可能开创新局面的可能性……

进一步阅读和参考资料
- Armando对演绎合成的讲座笔记 ↩︎
- 2021年关于神经符号程序合成的调查 ↩︎
- 使用AlphaCode进行竞技编程 ↩︎
- 评估基于代码训练的大型语言模型 ↩︎
- 通过Percy Liang将机器学习和组合语义学结合起来 ↩︎
- ACL 2018年关于神经语义解析的教程 ↩︎
- 儿童作为黑客 ↩︎
- 认知的概率模型 ↩︎
- Armando对程序合成定义和历史的讲座笔记 ↩︎
- 一个极简主义者的程序合成指南
- 微软员工对程序合成的2017年调查 ↩︎