自动化统一算法的推导:演绎程序综合的案例研究

《Journal of Symbolic Computation》:Automating the derivation of unification algorithms: A case study in deductive program synthesis

【字体: 大 中 小 】 时间:2026年07月22日 来源:Journal of Symbolic Computation 0.9

编辑推荐:

  摘要:统一算法长期以来一直是程序综合研究的目标,但完全自动的推导仍是一个研究课题。在演绎程序综合中,计算机编程被视为定理证明中的一个任务;声明式规范以逻辑形式表达并提交给自动定理证明器,然后从证明中提取出符合该规范的程序。程序的正确性由证明来支持,同时证明还提供了程序工作原理的解

  摘要:统一算法长期以来一直是程序综合研究的目标,但完全自动的推导仍是一个研究课题。在演绎程序综合中,计算机编程被视为定理证明中的一个任务;声明式规范以逻辑形式表达并提交给自动定理证明器,然后从证明中提取出符合该规范的程序。程序的正确性由证明来支持,同时证明还提供了程序工作原理的解释。证明是在适当的公理化领域理论中进行的,该理论定义了规范中的概念和目标编程语言中的结构,并提供了连接它们所需的背景知识。对于统一证明,我们对Manna和Waldinger(1981)提出的手工证明进行了泛化和自动化处理。新的程序能够根据给定的“环境”替换,将两个给定的符号表达式(S表达式)统一起来。证明确立了存在一个输出替换,它是给定表达式的最一般幂等统一器,同时也是环境替换的“扩展”。如果不存在这样的替换且表达式无法统一,则程序应生成失败指示符⊥。最初的环境替换是空替换,不会进行任何替换;在递归调用执行过程中,环境替换会记录迄今为止找到的所有替换。我们自己的统一算法使用了环境,这类算法在文献中也有出现(例如,Luger和Stubblefield,2004)。我们认为,除了效率更高之外,带有环境的三参数算法比Manna-Waldinger论文中的两参数版本更易于自动综合。证明是在关于表达式和替换的公理化理论基础上进行的。所衍生程序的结构反映了其来源的证明。程序中的条件表达式来自证明中的案例分析;递归则是通过基于理论中公理化的良基关系的良基归纳引入的。该证明是由一阶解析定理证明器snark(Stickel等人,2001)自动获得的。正如我们所言,提取出的程序在Manna和Waldinger的基础上有所改进,并包含了一些新元素。

引言:程序综合,即自动构建计算机程序,是自动定理证明最早的应用之一,至今仍极具吸引力。早期的一些研究人员(例如,Slagle,1965;Waldinger和Lee,1969;Green,1969)通过展示简单程序的合成作为示范。NASA的Amphion系统(Lowry等人,1994)利用定理证明器为包括土星卡西尼任务在内的多种任务构建软件。然而,尽管编程和定理证明在认知上似乎相似,而且软件工程师在程序构建中遇到的许多困难与数学家在定理证明中遇到的困难类似,但演绎程序综合对软件工程实践的影响却很小。考虑到近年来定理证明器取得的进展,人们自然会想知道它们在程序构建方面的表现如何。在演绎程序综合中,我们将构建程序的任务视为证明定理的任务。给定的规范描述了所需程序的目的,但没有说明实现这一目的的方法。因此,正确的规范可能比完整的程序更容易构建。规范被表述为一个猜想,即一个待证明的潜在定理,然后提交给定理证明器。对于应用型程序,该猜想通常表明存在一个输出实体,对于给定的输入实体,它能满足规范要求。证明是在领域理论的基础上进行的,这种公理化理论定义了规范语言的概念、目标编程语言的结构以及连接它们所需的背景知识。证明被限制为具有足够的构造性,即在证明所需输出的存在时,必须指出找到此类实体的方法。该方法成为从证明中提取出的算法的基础。我们关注在统一算法推导中起作用的概念。大致来说,统一是通过用其他表达式替换变量来找到使两个数学表达式相同的方法。统一作为解析原则的一部分被引入到定理证明领域(Robinson,1965)。Robinson将其归功于Herbrand在[1930]年的论文,但他对其概念进行了补充。统一不仅对定理证明至关重要,对于逻辑编程、类型检查以及自然语言理解等应用也同样重要。令人惊讶的是,由资深作者编写并纳入至少一种推理系统的广泛使用的教科书中的统一算法是不正确的(Norvig,2026)。统一是演绎程序综合研究早期的目标之一。Manna和Waldinger(1981)提出了一种推导方法,从非正式的手工证明中提取出了统一算法。Nardi(1989)展示了从Manna和Waldinger的演绎表格形式主义中的证明手工合成统一算法的方法,我们在本文中也采用了这种方法。Paulson(1985)使用交互式证明检查系统证明了Manna和Waldinger的算法符合其规范,但该论证是将算法视为既定事实,因此属于半自动验证而非综合。Eriksson(1984)和Armando等人(1997)实现了部分交互式综合。因此,似乎完全自动地综合整个统一算法仍然是一个研究目标。在本文中,我们首先介绍了一个表达式和替换理论,它作为推导的领域理论。我们概述了如何调整用于程序综合的解析风格定理证明器,特别强调了使用案例分析来生成条件表达式以及使用数学归纳法来生成递归。我们的讨论仅限于使用一阶逻辑定理证明器来生成无副作用的应用型程序。我们的示例将来自基于证明的统一算法推导。snark(Stickel等人,2001)能够从同一规范中为符号表达式生成数十种统一算法。在本文中,我们选择了一种相对简单且高效的算法。我们重新阐述了snark针对该算法的推导证明,以提高可读性。我们介绍了该算法,其中包含了一些由snark发现的创新点。我们希望这个例子能作为演绎程序综合的入门。由于篇幅有限,它无法提供所有必要的逻辑背景——更详细的教程可见于(Manna和Waldinger,1993)——但具备一定数学基础的读者应该能够在不阅读先前著作的情况下理解本文。

章节节选:

表达式、替换和统一器的理论:我们的介绍简洁且半正式,省略了一些已知结果的证明。我们并不试图全面介绍表达式理论;如需更一般的介绍,请参阅(Baader和Snyder,2001)。即使熟悉该理论的人也可能想浏览以下章节,因为我们修改了一些概念以便于证明的自动化。

表达式:本理论版本中的表达式是基于Lisp的S表达式建模的符号表达式。

演绎程序综合简介:我们首先介绍领域理论的概念。我们不期望这一章节能作为逻辑学的入门,但我们会明确相关的术语。

领域理论:程序综合需要大量关于应用领域的知识,这部分知识由领域理论提供。它以数理逻辑中的一组逻辑公式来表示。

公式和项:我们从一个包含无限多个常量的词汇表开始,还有一个无限的……

统一算法的推导:我们通过从统一算法的推导中选取的示例,来说明演绎表格框架的使用。

规范和初步步骤:对于统一算法的规范,我们假设环境替换是幂等的;这样可以使算法更简单,并便于证明终止性。因此,统一算法的输入输出条件将为idem(θ0)?mgiu(θ0,e1,e2,Θ),其中输入为θ0、e1和e2,输出为Θ。

我们的初步讨论:正如我们所提到的,从中提取程序的证明不仅确立了衍生程序的正确性,还提供了其工作原理的解释。当然,程序的正确性取决于规范的正确性以及我们提供的断言;如果这些有错误,一切都将失去意义。在本文的早期版本中,审稿人发现证明依赖于一个错误的断言,从而质疑了算法的正确性。

致谢:本文献给Zohar Manna、Mark Stickel和Cordell Green,没有他们,这项工作就不可能完成。我们要感谢SRI人工智能中心多年的支持以及他们的意见和建议。我们还收到了SRI计算机科学实验室、SRI创意研讨会、Kestrel研究所以及斯坦福逻辑午餐会(SLUGS)成员的宝贵意见。本文也受到了Kestrel研究所Flex项目的影响。

Richard Waldinger
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号