归纳编程是人工智能的一个子领域，关注从不完备规格说明中自动合成计算机程序。与传统编程中人类编写显式指令不同，归纳编程从期望行为的示例、逻辑属性或其他部分约束中推断出程序。术语“归纳”反映了从具体实例推广到一般规则的过程，这种推理形式在人类学习和自动化程序合成中均居核心地位。
该领域借鉴了机器学习、自动推理和编程语言理论的思想。20世纪70年代和80年代的早期工作侧重于从输入-输出对合成小型递归函数，通常通过对可能程序空间的搜索来实现。随着时间推移，研究范围扩展到更复杂的数据结构、高阶函数以及与现代学习范式的集成。归纳编程不同于演绎程序合成，后者从形式逻辑规格说明中推导程序，尽管这两种方法在实践中常常互补。
历史基础
归纳编程的根源可追溯至人工智能的早期阶段。20世纪70年代，施乐帕克研究中心及其他机构的研究人员探索了能从示例中学习Lisp程序的系统。一个显著的里程碑是1975年THESYS系统的开发，该系统从输入-输出对合成递归Lisp函数。这项工作表明，简单的基于搜索的方法能发现用于列表反转和算术运算等任务的程序。
20世纪80年代，随着逻辑编程的兴起，该领域获得了发展动力。MIS（模型推断系统）等系统以及后来的方法使用归纳逻辑编程（ILP）从正反示例中推断Prolog子句。ILP成为一个独立的研究领域，在生物信息学和自然语言处理中有应用。到20世纪90年代，卡内基梅隆大学和麻省理工学院计算机科学与人工智能实验室的研究人员已形式化了许多理论基础，包括程序搜索的复杂性和背景知识的作用。
2010年代深度学习的出现为归纳编程带来了新工具。神经网络，特别是序列到序列模型，被应用于程序合成任务，将程序生成视为翻译问题。这种混合方法通常称为神经程序合成，结合了机器学习的模式识别优势与传统搜索的形式保证。
核心技术
归纳编程方法可大致分为基于搜索和基于学习两类。基于搜索的方法在结构化空间中枚举候选程序，由评分函数引导，该函数衡量每个候选与给定示例的匹配程度。该空间通常由文法或程序模板集定义。枚举搜索、遗传编程和约束求解等技术属于此类。例如，微软研究院2011年开发的FlashFill系统使用字符串变换和搜索的组合，从用户提供的示例合成电子表格公式。
基于学习的方法使用统计模型直接预测程序结构。常见架构是编码器-解码器模型，其中编码器处理输入-输出示例，解码器逐词元生成程序。这些模型通常在大型程序-示例对数据集上训练，使用损失函数如交叉熵。2017年引入的Transformer架构已成为此类系统的标准骨干，因其能处理长距离依赖。然而，纯神经方法常难以保证精确正确性，因此常与搜索结合：模型提出候选程序，验证器对照示例检查它们。
另一重要技术是使用课程学习，即模型在逐渐变难的示例上训练以改善泛化。此外，数据增强用于生成合成训练数据，扩展程序模式的覆盖范围。这些方法已应用于从字符串操作到数据库查询乃至大语言模型辅助代码生成等领域。
应用
归纳编程在多个领域找到了实际应用。一个突出用途是终端用户编程，非专家用户可通过示例指定期望行为。微软的FlashFill集成在Excel中，是广泛部署的实例：用户输入几个期望变换的示例，系统为列中其余部分合成公式。这种方法节省了无数手动数据清洗的时间。
在软件工程中，归纳编程支持自动化缺陷修复和测试生成。给定一个失败的测试用例，合成系统可推断出使测试通过的补丁，通常通过对程序编辑的搜索实现。该技术已在学术工具和商业产品中探索，但由于确保语义正确性的难度，仍是一个活跃研究领域。
生成式人工智能的兴起也影响了归纳编程。现代大语言模型，如OpenAI和Anthropic开发的模型，能从自然语言描述生成代码，这可视为一种归纳编程形式，其中规格说明是文本提示。这些模型通常在代码语料库上微调，能为广泛任务生成功能程序。然而，它们缺乏形式保证，其输出通常通过测试或人工审查验证。
挑战与局限
归纳编程的核心挑战是搜索空间爆炸。可能程序的数量随程序长度呈指数增长，使穷举搜索对除最简单任务外的所有任务都不可行。启发式方法，如类型导向搜索或束搜索，有助于剪枝空间，但可能遗漏有效程序。这种完整性与效率之间的权衡是一个基本开放问题。
另一个问题是规格说明的歧义性。给定有限示例集，有无限多个程序适合它们，且大多数对未见输入在语义上不正确。因此，归纳系统必须纳入归纳偏置，如偏好较短程序或具有特定结构属性的程序。这种偏置通常编码在搜索文法或训练数据中，但可能根据任务导致过拟合或欠拟合。
神经方法面临额外挑战，包括对大量训练数据的需求以及确保语法和语义有效性的难度。虽然Transformer在基准任务上表现出色，但可能生成语法无效的代码或在边缘案例上失败的程序。验证和修复机制通常对弥合预测与正确性之间的差距是必要的。
未来方向
该领域正朝着结合神经模型和符号推理优势的混合系统发展。例如，一些近期工作使用大语言模型生成候选程序，然后采用剪枝搜索或形式验证器精炼输出。这种方法利用预训练模型的广泛知识，同时保持正确性保证。
另一个方向是交互式归纳编程，系统在合成过程中向用户请求额外示例或澄清。这减少了歧义性，提高了生成预期程序的可能性。人机协同系统的研究在学术和工业环境中均显示出有前景的结果。
最后，归纳编程与机器学习流水线的集成可能会增长。随着深度学习模型能力增强，它们可同时作为程序假设的来源和行为验证器。最终目标是创建能从自然语言、示例和反馈中学习编程的系统，接近人类程序员的灵活性。