归纳编程

归纳编程（IP）是自动编程的一个特殊领域，涵盖了来自人工智能和编程的研究，它解决了从不完整的规格，如输入/输出实例或约束条件，学习典型的陈述性（逻辑或功能）和经常递归的程序。

根据所使用的编程语言，有几种归纳编程的方式。归纳函数式编程，使用函数式编程语言，如表处理语言(Lisp)或哈斯克尔(Haskell)，特别是归纳逻辑编程，使用逻辑编程语言，如逻辑语言(Prolog)和其他逻辑表示，如描述逻辑，一直比较突出，但其他（编程）语言范式也被使用，如约束编程或概率编程。

归纳式编程包含了所有与从不完整的（正式）规范中学习程序或算法有关的方法。

在IP系统中，可能的输入是一组训练输入和相应的输出或输出评估函数，描述预期程序的预期行为，描述计算特定输出的过程的痕迹或动作序列，关于其时间效率或其复杂性的要诱导的程序的约束，各种背景知识，如标准数据类型，要使用的预定义函数，描述预期程序的数据流的程序方案或模板，指导搜索解决方案的启发式方法或其他偏见。

IP系统的输出是某种任意编程语言的程序，包含条件和循环或递归控制结构，或任何其他类型的图灵完备表示语言。

在许多应用中，输出的程序必须对例子和部分规范是正确的，这导致了将归纳编程作为自动编程或程序合成的一个特殊领域来考虑，通常与"演绎"程序合成相反，在后者中，规范通常是完整的。

在其他情况下，归纳编程被看作是一个更普遍的领域，任何陈述性编程或表示语言都可以被使用，我们甚至可以在例子中出现某种程度的错误，如一般的机器学习，更具体的结构挖掘领域或符号人工智能领域。

一个明显的特点是需要的例子或部分规范的数量。通常情况下，归纳编程技术可以从几个例子中学习。

归纳编程的多样性通常来自于应用和使用的语言：除了逻辑编程和函数式编程，其他编程范式和表示语言也被用于或建议用于归纳编程，如函数逻辑编程、约束编程、概率编程、归纳逻辑编程、模态逻辑、行动语言、代理语言和许多类型的命令语言。

关于递归函数式程序的归纳合成的研究开始于20世纪70年代初，并通过萨默斯 (Summers) 的开创性的THESIS系统和别尔曼 (Biermann) 的工作被带入了坚实的理论基础。

这些方法被分成两个阶段：

首先，使用一小套基本运算符将输入输出的例子转化为非递归程序（traces）；其次，寻找痕迹
(traces)中的规律性，并用来将其折叠成递归程序。

20世纪80年代中期之前的主要成果由史密斯 (Smith) 进行了调查。由于在可以合成的程序范围方面进展有限，研究活动在接下来的十年里明显减少。

逻辑编程的出现在80年代初带来了新的活力，但也带来了新的方向，特别是由于夏皮罗的MIS系统最终催生了归纳逻辑编程（ILP）的新领域。

普洛特金的早期作品，以及他的相对最小一般概括（rlgg），对归纳逻辑编程产生了巨大的影响。

大多数ILP工作涉及更广泛的问题类别，因为重点不仅是递归逻辑程序，还包括从逻辑表征中学习符号假设的机器。然而，在学习递归逻辑语言(Prolog)程序方面有一些令人鼓舞的结果，例如从例子中结合适当的背景知识学习快速排序算法 (quicksort)，例如用GOLEM。

但是，在最初的成功之后，社区对归纳递归程序的有限进展感到失望，ILP越来越少地关注递归程序，而越来越倾向于机器学习环境，在关系型数据挖掘和知识发现方面的应用。

在ILP工作的同时，Koza在20世纪90年代初提出了遗传编程作为一种基于生成和测试的学习程序的方法。