逻辑程序设计将逻辑直接作为
程序设计语言并将计算作为受控推理的一种程序设计技术。
介绍
逻辑编程的要点是将正规的逻辑风格带入计算机程序设计之中。数学家和哲学家发现逻辑是有效的理论分析工具。很多问题可以自然地表示成一个理论。说需要解答一个问题,通常与解答一个新的假设是否跟现在的理论无冲突等价。逻辑提供了一个证明问题是真还是假的方法。创建证明的方法是人所皆知的,故逻辑是解答问题的可靠方法。逻辑编程系统则自动化了这个程序。人工智能在逻辑编程的发展中发挥了重要的影响。
猴子和香蕉问题是逻辑编程社区的著名问题。电脑须自行找出令猴子接触香蕉的可行方法,取代程序员指定猴子接触香蕉的路径和方法。
逻辑编程创建了描述一个问题里的世界的
逻辑模型。逻辑编程的目标是对它的模型创建新的陈述。世界上知识不断澎涨。传统来说,我们会将一个问题陈述成单一的假设。逻辑编程的程序通过证明这个假设在模型里是否为真来解决问题。
一些经常用到逻辑编程工具的范畴:
最常用的逻辑编程语言是Prolog,另外有较适用于大型方案的Mercury。详尽的清单可见于Category:逻辑编程语言。
沿革
1972年法国科莫劳埃小组实现了第一个逻辑
程序设计语言PROLOG。1974年以后R.科瓦尔斯基进一步阐明了PROLOG的理论基础,并系统地发展了逻辑程序设计的思想。对于传统的程序设计来说,算法的逻辑意义往往被程序复杂的控制成分所掩盖,使程序的正确性难以得到证明。而且通常的高级
程序设计语言属于过程性语言,需要在程序执行前详细规定运行步骤。科瓦尔斯基对传统的算法或对用通常高级语言编写的程序提出了一个著名的分析公式,即算法=逻辑+控制。其基本思想是要从根本上改变程序设计的方法:用户只需要编写程序的逻辑部分(逻辑程序设计之名由此而来),而系统中的
解释程序则实施控制部分的职能。
优点
这种将
逻辑与控制分开的方法具有下列的优点:①可以在控制部分设计之前不断改进逻辑程序。②可以改进控制部分而无需变动逻辑程序本身。③可以从程序说明中生成逻辑程序,加以验证和变换,而无需考虑其控制部分。④只需在逻辑程序中规定目标和实现这些目标的现有条件,也就是只需告诉系统做什么(What to do),至于如何执行也就是说怎样做 (How to do),则由系统的控制部分,即
解释程序处理解决。
历史
早在二十世纪七十年代,罗伯特·科瓦尔斯基等人提出了逻辑可以作为程序设计语言的基本思想,把逻辑和程序这两个截然不同的概念协调统一为一个概念,于是诞生了逻辑程序设计。这也是早期
自动定理证明和人工智能发展的自然结果。随后,逻辑程序设计得到了迅速发展,特别是基于一阶谓词的逻辑程序设计语言,将逻辑推理对应于计算,具有丰富的表达能力、非确定性等特点,在定理机器证明、关系数据库系统、程序验证、模块化程序设计和
非单调推理等都有了广泛的应用。
现状
现行逻辑程序的基本语句属于一阶谓词演算的一个子集,HORN子句集。HORN子句的一般形式为:A1,…,Am←B1,B2,…,Bn,其中Ai(1≤i≤m)、Bj(1≤j≤n)都是原子公式,分别代表结论和前提的形式。前提部分是各原子的合取式,构成子句体,结论部分最多只有一个原子,称为子句头。由此可将HORN子句分成两个基本类型:①有头HORN子句(用来代表一条规则),例如,grandfather(x,z)←father(x,y),father (y,z)代表:x是y的父亲且y是z的父亲,则x是z的祖父。有头无体的HORN子句是一断言(用来代表一个事实)。例如,father(A,B)代表:A是B的父亲,father(B,C)代表:B是C的父亲。②无头HORN子句,称为目标语句(用来代表结论的否定式),例如,←grandfather(A,C)代表:A不是C的祖父。逻辑学家A.霍恩对这类子句性质作了详尽的研究,HORN子句即因此得名。
从问题
归约的角度看,可将HORN子句解释为一过程,它将问题(目标)A归约为若干子问题(子目标),每一子问题Bi(1≤i≤n)又可解释为对其他过程(HORN子句)的调用。有头无尾的HORN子句则代表一个已知其解的基元问题。过程调用实际上是使构成子句体的一个原子(子目标)与某一子句头匹配,这就是运用
归结原理中的合一的过程。因此逻辑程序的执行过程也就可以看成是定理证明过程,其中
解释程序起定理证明器或问题求解器的作用。
发展
HORN子句的过程调用(B1, B2,…,Bn)可按任意次序进行,适合于平行处理。HORN子句可作过程性的解释也可作陈述性的解释,运用比较方便。因此,以HORN子句为基础的逻辑
程序设计语言PROLOG受到人们的重视(见
PROLOG语言)。日本的第五代计算机系统的计划也推动了逻辑程序设计的研究。也有人认为,不同类型的问题需要不同风格的程序设计方法,在下一代的知识
信息处理系统中除逻辑程序设计之外,还必须重视
面向对象的程序设计、面向存取的程序设计、规则型程序设计,此外,建立与知识信息处理相适应的程序设计环境也是重要的课题。