没有合适的资源?快使用搜索试试~ 我知道了~
1理论计算机科学电子笔记70第二次(2002年)URL:http://www.elsevier.nl/locate/entcs/volume 70. html10页s在线性逻辑证明搜索中隔离资源消耗(扩展摘要)PabloLo'peza,1,ErnestoPime n tel a,JoshuaS. 你好,Je Escherey Polakowb和Lubomira Stoilovab,2aDepartamentodeLenguaajesyCienciasdelaComputacio'nUniversidadeMa'laaCampusdeTeatinos,29071M'alaga,Spain[lopez,ernesto]@lcc.uma.eshttp://www.lcc.uma.es/~[lopez,ernesto]计算机科学系Harvey MuddCollegeClaremont,CA 91711,USA[hodas,jpolakow,lstoilova]@cs.hmc.eduhttp://www.cs.hmc.edu/~hodas摘要这项工作提出了一个扩展的标记帧资源管理系统以前开发的作者。扩展的证明系统能够隔离给定目标/子句的消费,而不会产生显著的额外运行时成本。我们相信这个特性可能有许多应用,特别是在证明理论环境中调试线性逻辑程序和规范。这一点是通过一个简单的例子来说明的。1介绍众所周知,线性逻辑语言和逻辑框架都是用于指定许多系统的强大概念工具的1L'opez和Pimentel部分由项目TIC 2001 -2705-C 03 -02提供由SpanishMi nis tryofS c ien c eandtTech nology提供。在2001年,Lopez作为访问研究员也得到了哈维·穆德学院的旅行补助金的部分支持。2斯托伊洛娃的部分资助来自哈维·穆德学院计算机科学诊所项目。2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。LO'PEZ等人2T FDTF由线性提供的状态的干净的、声明性的概念打开了顺序和并发系统的elegant和明晰的编码的大门然而,线性逻辑的表达能力给实现者带来了困难的问题。简单地说,线性逻辑中的有效证明搜索很难实现。在过去的几年里,已经见证了大量的工作,旨在提供有效的证据搜索策略。本文深入地研究了这些规则的可置换性和可逆性,并将所得结果有效地应用于制定聚焦策略[1,2]和均匀策略[12]。资源管理的重要(也许更具体到线性逻辑)主题也吸引了相当多的兴趣,并且已经为逻辑的不同片段开发了相当多的证明系统然而,令人惊讶的是,调试线性逻辑程序和规范的主题在很大程度上被忽视了。通常,一个线性逻辑程序失败仅仅是因为资源消耗的模式不是程序员所期望的例如,一些资源可能仍然被消耗,从而阻止证明被完成。面对这种情况,简单的否定回答是完全没有用的。在这项工作中,我们提出了一个传统的输入/输出操作语义的资源管理系统的扩展。扩展的系统能够隔离给定目标/子句的消费,而不会产生显著的额外运行时成本。我们认为,消费的隔离提供了第一步,以证明理论的方法来调试。此功能的其他一些可能的应用可能包括分析,程序分析和优化,以及编程习惯。本文的结构如下。第二节资源问题提出了线性逻辑中的分布问题,并简要地评述了解决它的两种基本方法下一节简要介绍了TF资源管理系统,以前由作者开发[8]。第4节介绍了证明系统,资源管理系统的扩展,隔离资源的消耗。扩展系统的调试能力,然后通过一个简单的例子来说明。最后,结论和进一步的工作进行了概述。2资源管理系统简介线性逻辑中的资源管理问题最好的例子是自下而上应用−EML规则:1−→AA− →B−→C−L =12当自底向上应用此规则时,必须在两个上下文中分割上下文对象01和02。分裂的数量是公式数量的指数,因此简单地LO'PEZ等人3T F在证明搜索中的选择点。这对于编程语言或定理证明器的实际实现来说显然是不能容忍的。有两种方法来克服这个问题:ad hoc操作语义和分布约束。特设操作语义方法修改了证明系统的上下文和该策略的关键思想是上下文对象不被拆分,而是作为输入传递给左前提。然后左子证明消耗输入的一部分(101)并返回剩余部分(102)作为输出。这个输出最终作为右前提的输入转发。通过这种方式,可以将p2p延迟地拆分为p2p1和p2p2。虽然固定证明策略可能会降低这种方法的适用性,但它也赋予了证明搜索可预测的操作语义,这是逻辑编程语言的基本特征 许多这样的系统已经被开发出来[9,7,6,3,11,8],并且大多数已经被有效地和高效地实施。此外,实现技术已经足够成熟,可以为Lolli语言的重要片段产生编译版本[10]。通过约束分配资源[5,2]是一种更一般的算法方法,其中问题的具体化和解决方法被清楚地区分开来。布尔表达式(可能包含布尔变量)附加到上下文中的每个公式这个想法背后的直觉是,当且仅当附加的布尔表达式;即,一个公式在上下文中真正存在分布约束的值为true。然后修改证明系统的规则以生成和传播分布约束,从而证明搜索构成约束系统- 即一个分配问题求解方法决定了最终分布和证明策略。从理论的角度来看,这些系统的通用性使它们成为框架,可以分析,组合和比较不同的分销策略。 从实践的角度来看,约束的生成/传播及其解决方案之间的关系尚未得到解决[5],因此实现问题并不像ad hoc操作语义方法那样进化。事实上,作者所知道的唯一实现是在Concert项目中开发的Iktara并行定理证明器[4]。3标签框架系统图1中所示的标记框架系统[8]()是一个资源管理系统,它遵循ad hoc操作语义传统,并体现了以前开发的此类系统的大多数最佳方面这包括输入/输出的精液溶液流[9],T的懒惰处理[7],将上下文分为宽松和严格区域[3],以及优化的LO'PEZ等人4TF−→GTTTF我关于《易经》的讨论[11]。该系统的主要贡献是一种新的优化的添加剂连接。Hierarchy,已知处理加法合取的最佳实现技术是Cervesato,Hodas和Pfenning在[3]中提出的优化然而,为了使这种优化正常工作,左前提的输入和输出都必须被存储和处理,以计算右前提的输入。此外,在某些情况下,必须计算两个前提的输出的交集,在实践中,这是一个严重的加载在内存和时间性能。TF系统避免了这些额外的计算。TF矩阵的一般形式为:\δ::π σσJv其中:•I是输入上下文,一个标记公式的多重集合。•CNOO是输出上下文,一个标记公式的多集合。请注意,它们具有相同的基数。TF系统中的公式在使用时不会这是对于优化工作至关重要。此外,它可能有助于有效地实现回溯。• δ是一组标记。标记有δ成员的输入公式是严格的。与Frame系统[11]相反,严格公式不是连续的,而是可能分散在输入上下文中。系统因此保留子句顺序,这是逻辑编程语言所期望的行为。• π是标签的帧(即,集合)的堆栈。标记有π成员的输入公式是可选的(或lax)。• σ是一组标签,通常称为消费标记。每次使用输入公式时,它的标记都被σ的任意元素替换。• σJ是一组标记。标记有σ j成员的输出公式已被有效消耗。• v是通常的output-sag,表示在子树中遇到了a,并且未消耗的资源可能会被隐式地削弱。• G是目标公式。的内部运作系统是复杂的,超出了本文的范围在[8]中解释了该系统,并讨论了其可靠性和完整性。尽管如此,下面的形式结果(在这里稍微简化了它的陈述)对于证明本文提出的扩展系统是 必 要 的。引理3.1(局部消耗)对于所有的πI, πO,δ,π,σ,σJ,v和GOLO'PEZ等人5−→GTF TFDt∈t∈/δI\δ::πσTF原子I\δ::πσTF TRσ\∆\nI M{t}::πM Oπσ'−{ t}σ0σ"→v−G\π σIOTF − 100(tnew)σ"vσ\一个人I M{t}::δ::π{t}::δ::πσ'−{t}σ'M O1σ−→G''vI\δ::πσG−DA1TF −10(t新)李明博DLR OD−→DAπ σσ'vDtI\D O−→Gδ::πσσ'v你好π σL R O−→ATF镐δ::πσTF−BRRσ'vt∈π,d ∈σ<$I\<$O −→D −<$Gσ'v(t∈δ)联系我们−'→G1M\Oσ−“”→vG2π{ d}σ'::nilσσ0I\π σTF0R(d新设)<$I \<$M−“→G1<$M\<$Oσ−”“→v G2δ::π{d}σ'::π σσ1I\δ::πσTF1R(d新设)Ds∈s∈/δ联系我们我{t}::nilσGI\Gδ::πσTF!R(t新)Fig. 1. 标签-框架证明系统这样,\δ::π σ是可证明的,它认为:I OσJv[O]σJ−[I]σ=[I]δ([I]π−[O]π)当reπ表示包含ackπ和d[k]的函数的联合时,表示公式D的多重集,使得D t∈ N且t ∈ N。这个性质表明,G,[0]σJ−[I]σ消耗的公式是那些在输入([I]δ)中严格的公式加上消耗的松散资源部分,[I]π−[O]π。4标签-框架系统该系统的核心思想是R规则的左前提 提供了它的消费的踪迹,所以正确的前提有这个踪迹可以遵循。这是通过引入新的消耗标记d来实现的,LO'PEZ等人6πσ--πσT FDDT FDπσDσJσ vJσ v隔离左前提的消耗这个想法实际上可以应用于任何一个目标规则,这样任何一个目标的消费都可以被隔离。特别是,考虑TFpick规则:LDdσJv<$LDt<$R\<$O−→ATFt∈π,d∈σπ σ 截齿可以定义一个新的挑选规则,以隔离由给定子句D引入的目标的消费,如下所示:LDs\r\nπ dσ−J→vDA联系我们 \r\nσJ−εσ→v 一个TFpickt∈π,s∈σ,d new注意,已经引入了新的消耗标记d来标记和从而隔离D的消耗A. 因为d是新的,所以[LDtR]=然后,通过局部消费引理,D{d}A是简单地说,此外,总消耗现在是[O]σJ <$σ;即已经消耗的资源加上DA消耗的资源。一个新的证明系统(见图2)被定义为保留两个版本的选择规则,而不是用这个新的规则替换原来的TF选择统治该系统不仅是一个资源管理系统,因为标签不仅用于施加消耗约束,而且用于调试目的。据我们所知,这是第一次将资源管理系统的操作语义扩展到处理消费约束以外的概念当然,并不是每个条款都需要调试。新版本的选择规则将仅应用于用户选择的条款这类似于在调试器中设置监视点条款是被调试的在证明中用波浪号显示()。两人挑那么T FD系统的规则LDdσJv<$LDt<$R\<$O−→AT FDt∈π,d∈σπ σ 截齿埃克塞特π{d}LDOσ−J→vDA拉克莱特π σ T FD拾取&标记LD<$R\<$OσJ−<$σ→vAt∈π,s∈σ,d新使用T FD拾取标记规则,应用程序DA被调试的子句的值是[O] J。可以认为,将局部消耗引理应用于原始的结论,也可以确定DATF拾取规则;即:[O]σJ−[I]σ=[I]δ([I]π−[O]π)LO'PEZ等人7Dt∈t∈/δI\δ::πσT FD原子I\δ::πσT FDTRσ\一\I M{t}::π'σ'M Oπσ−{ t}0σ"v\π σIOT FD −T0(tnew)σ"vσ\一个人I M{t}::δ::π{t}::δ::πσ−{t}'σ'M O1σ"−→GvI\δ::πσG−DA1T FD −10(t新)σ'vπ σ李明博dπσLR OD−→DA你好L R O−→AT FD截齿σ v't∈π,d ∈σ李明博˜ SLR OD−→DAπ{ d}σ'vLD<$R\<$Oσ'<$−σ→vA阿勒特π σT FD拾取标记t∈π,s ∈σ,d新不δ::πσσ'v<$I\<$Oσ−'→vD−<$GD\ IOD−→Gδ::πσT FD− R(t∈δ)DI\DOσ−'→vGI\˜t˜δ::πσδ::πσT FD双金属(t∈δ)I\σ−“”→vG2I\联系我们σ−'→1G1<$M\<$Oσ−"→vG2I\π{ d}σ'::nilσπ σT FD0R(d新设)δ::π{d}σ'::πσδ::πσT FD1R(d新设)Ds∈s∈/δ联系我们我{t}::nilσGI\Gδ::πσT FD!R(t新)图二. 标签-框架证明系统然而,这涉及存储输入逻辑程序<$I=<$LDt <$R。另一方面,T FD系统不会引起这种空间过载。线性逻辑程序的一个显著特征是它们会增长和收缩在执行过程特别地,子句可以通过线性蕴涵被动态地然而,用户只能在原始逻辑程序中存在的子句上设置监视点。这个概念可以进一步扩展到处理动态子句。为此,新的LO'PEZ等人8T FDT FD我OσJv调试线性蕴涵定义如下:˜t˜δ::π σD<$I\D<$Oσ−J→vG\δ::π σ每次应用TFD调试规则时,都将行条款D标记为待调试并添加到逻辑程序中值得注意的是,对D的形式施加了约束,因此对高阶编程支持没有限制该系统的主要贡献在于,它能够隔离给定目标/子句的消费,而不干扰资源管理系统的传统操作语义。我们目前正在研究这一功能的实际应用虽然这些并不局限于调试,但这似乎是最有前途的一个。特别是,该系统可以与逐步证明调试过程相结合,以提供基本的证明理论调试框架。5一个简单的Lolli程序我们将通过一个简单的例子来说明T FD让我们考虑一个简单的Lolli程序,它有两个谓词p和q代表两个乒乓球运动员。这个转向由两个线性事实ping和pong表示。必须确保两匝之间的互斥。玩家p等待轮到他的乒乓球到来,然后击中球,将回合改为乒乓球,然后继续玩。参与人q表现出与参与人p对偶的行为。谓词go开始比赛,将回合分配给其中一名球员并面对他们。没有经验的Lolli程序员可能会编写以下代码:p :- pong,(ping -o p).q :- ping,(pong -o q).go:- pong -o(p,q).然后发现它失败了,用一个简洁的“不”。这并没有提供太多的线索,以什么在这个简单的例子中,一个更好的线索是知道球被击中了多少次以及被谁击中。在资源消耗方面,有多少线性事实在哪里消耗,谁消耗了它们。为了找到答案,我们可以在谓词p的第一个也是唯一的子句上设置一个窥探点,这个子句应该被称为CP。(同样,谓词q的唯一子句应称为Cq。)然后,系统可以向用户提供条款Cp的消费行为的踪迹。构建的(不可证明的)偏导数应该类似于下面描述的:LO'PEZ等人9˜{ 联系我们−→p无法证明...布吕德{t2}::nil{d}.C p,C q,pong,ping\−→p. ˜˜d{t2}::nil{d}dd{t2}::nil{d}. Cp,Cq,pong\Cp,Cq,pong−→pong Cp,Cq,pong\Cp,Cq,pong.−→ping−p.C, C,pong\{t2}::nil {d}p q−→C pp{t2}::nil {s}T FD拾取标记未尝试Cp,C q,pong\−→p−→q{t1}::nil {s}Cp,Cq,pong\−→ p<$qCp,Cq不*nils−→pong−(p<$q)当应用条款Cp时,T FD拾取标记规则引入新的消耗标记d。因此,解决目标CPp应标有此新标签。相继式˜Cp,Cq,pong,ping\{t2}::nil{d}是不可证明的,因为CP需要一个pong被证明,既没有pong也没有参与者q来提供一个。对输出上下文的简单检查表明,Cp只消耗了一个pong,因此匹配只持续了一次命中。6结论进一步的工作在这项工作中,我们已经扩展了传统的资源管理系统的操作语义,以提供一个资源消耗的痕迹,而不会产生额外的运行时成本。尽管所提出的思想的应用并不局限于与调试相关的应用,但我们的讨论仍然围绕着这个重要(不幸被遗忘)的主题。从长远来看,我们的目标是双重的。一方面,我们希望探索新的应用隔离的资源消耗在线性逻辑证明搜索。另一方面,这项工作可能是为声明式调试提供严格的证明理论方法的第一步。引用[1] Andreoli,J.M.,逻辑程序设计与线性逻辑中的聚焦证明,逻辑与计算杂志(1992)。[2] Andreoli,J. M.,聚焦和证明结构,纯粹和应用逻辑年鉴107(2001),pp。131-163.DLO'PEZ等人10[3] 切尔韦萨托岛J.S. Hodas和F.李文,线性逻辑证明搜索的有效资源管理,计算机科学,2000年,第232页。[4] Chang , E. , “Iktara in ConCert : Realizing a Certified Grid ComputingFramework from a Programmer 's Perspective , ”硕 士 论 文 , 计 算 机科学学院,卡内基梅隆大学(2002年)。[5] Harland,J. 和D. Pym,Resource distribution via boolean constraints,ACM Transactions on Computational Logic(2001)。[6] Harland,J.和M.李文,线性逻辑程序设计语言的实现。Lloyd,editor,Proceedings of the 1995 International Logic Programming Symposium ,1995,pp. 66比80[7] Hodas,J. 美国, 论文,宾夕法尼亚大学计算机与信息科学系(1994年)。网址http://www.cs.hmc.edu/~hodas/papers/[8] 你好,J。 S. ,P. 别这样,J。 波拉科湖 我们辛苦了。 Pimentel,ATag-Framesystem of resource management for proof search in linear-logicprogramming,in:Proceedings of the Annual Conference of the EuropeanAssociation for Computer Science Logic(CSL'02 ) , Lecture Notes inComputer Science(2002),to appear.[9] 霍达斯,J.S.和D. Miller,Logic Programming in a Fragment of IntuitionisticLinear Logic,Information and Computation110(1994).327[10] 霍达斯,J.S.,K. Watkins,N. Tamura和K.- S. Kang,线性逻辑编程语言的有效实现,1998年联合国际会议和逻辑编程研讨会论文集,1998年,pp.145- 159[11] L'opez,P。和E.Pimentel,Resorcemangementinlinearlogicprofserchrevisited , in : H. Ganzinger ,D.McAllester 和 A.Voronkov , 编 辑 , Proceedings of the 6th InternationalConference on Logic for Programming and Automated Reasoning(LPAR304-319.[12] Miller,D.,G. Nadathur,F. Pfenning和A. Scedrov,Uniform proofs as afoundation for logic programming , Annals of Pure and Applied Logic51(1991)。125-157
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功