下载掌阅APP，畅读海量书库
立即打开
“让计算机自动编写代码”是一项新的技术成果。根据给定的问题描述或规范，计算机自动编写满足条件的程序，这个过程被称为程序合成（program synthesis）。
程序合成有很广泛的应用前景，微软公司Excel产品中集成的Flash Fill功能就是程序合成技术的一个成功应用。此功能可以根据用户输入的少量数据推理出其中的模式，并根据此模式自动处理其他的数据（图2-6），从而简化了终端用户的重复性工作。数据库查询语言Seq2SQL是程序合成技术另外一项有意义的应用 ［24］ 。此技术可以将自然语言转化成可执行的数据库查询语句，从而大大提高了终端使用者的数据处理效率。另外，程序合成也可以应用于软件的自动调试与修复、程序理解、代码补全、新算法发掘以及教学等领域。
图2-6 Excel的Flash Fill功能可以推断用户意图并自动处理数据
程序合成的本质涉及问题描述的表达形式与程序空间的高效搜索两个问题。
第一个问题是如何描述符合要求的程序。自然语言是最直观的表达方式。比如“将位向量最右端的1置为0”，但自然语言天然具有不规范与歧义性，使其难以直接作为程序的表达形式。为了使描述严谨，可以将自然语言描述转化为逻辑规范（表2-1），这需要有相应的数学逻辑背景知识与经验，一般终端用户难以实现。
表2-1 对同一问题的三种表达形式 ［25］
对于程序合成技术的终端用户来说，直接提供输入/输出范例是最便捷的一种方式。但是，这种方式也有缺点，其程序合成的效果与输入/输出范例的数量和质量有关。
程序合成需要解决的另一个问题是如何在巨大的程序空间内进行高效搜索。首先，程序合成的研究者需要确定一个足够大的搜索空间。针对终端用户想要合成的程序类型，研究者还要有足够的表达能力。同时，此搜索空间又必须有足够的限制，使得高效的搜索计算可行 ［25］ 。例如根据用户的具体需求，搜索空间可以限制一些操作符，包括数学操作、位运算、指定库的应用编程接口等，同时也会对程序的控制流做出一些限制 ［26］ 。
接下来，程序合成方法会在限定的搜索空间内进行搜索，从而编写出满足问题描述的程序。最简单的搜索策略即暴力求解。然而，暴力求解效率低且代价高。虽然暴力求解有较为成功的应用，但是其事先采用了一些优化方法对搜索空间进行删减，通过将问题适度简化后才得以实现。另一类方法是通过约束求解的方式，搜索满足条件的程序。此外，版本空间计算、概率推断和演化计算技术也经常被用于程序合成。近期，基于神经网络的程序合成技术也初步取得了令人瞩目的成果 ［27，28］ 。
程序合成是人工智能领域的一个主要研究内容。为了使程序合成技术更加智能化，并能广泛地应用于人们的生活中，未来还需要解决以下问题：如何在满足功能正确性的基础上，同时提升合成程序的自身性能？如何在使用者接口统一化的基础上，同时支持多种问题描述的表达形式？如何设计模块化的架构，从而重新利用不同领域的程序生成技术与工具？
这些问题虽具有挑战性，但是我们相信在不久的将来，程序合成会给程序开发、企业运作以及人们的日常生活带来深刻的变革。
刘烨庞，南方科技大学计算机科学与工程系助理教授，香港科技大学博士。主要研究智能软件工程，在国际学术期刊及会议上发表论文30余篇，获ACM SIGSOFT杰出论文奖2次和杰出软件制品奖1次。