理论计算机科学电子笔记57(2001)网址:http://www.elsevier.nl/locate/entcs/volume57.html4页减少战略- 一个pancreatic的观点-TetsuoIda1;2日本筑波大学信息科学与电子学研究所,筑波1什么是热门话题?让我们先来澄清一下热点话题的含义。 至少有两种方法可以解释这些主题的温度第一个是以下内容。由于我们的研究社区很小,如果我们中的几个人,谁的启发和指导一些有趣的以前的结果,正在研究同一个主题,该主题成为引人注目的社区,并成为热点。二是将温度归结于社会语境。如果研究解决了我们社会面临的问题,那么研究主题就是热门的在本说明中,前者被称为社区热点,后者被称为挑战热点这两者将结合在一起。大多数研究者认为,他们的研究主题是温暖的措施,由社区和由挑战。我认为,理想的情况是,我们的研究课题是热门的挑战。然而,在这个先进的科学和技术的世界里,处于理想状态并不容易。一个人不容易发现一个对我们社会有直接影响的问题我们甚至需要一长串的论据来证明我们的研究是正确的。我们处理一个问题P0,因为P 0解P1,,而Pn1解Pn。解决方案Pn 对人们来说是有形的。 当n变大时,要说服人们P 0是热门挑战就变得更加困难。2什么是减排战略?我试图回答,在一个一年级计算机科学学生的教室里说话的方式,没有使用严格的形式主义,上述问题。这将有助于在更广泛的背景下思考减少战略研究的相关性。假设你正在用一种未来的语言写一个程序,比如说一种类似于我们的自然语言的语言,在这种语言中你不必写太多的控制1 本说明是为裁减战略中的热点问题小组编写的。2 电子邮件地址:ida@score.is.tsukuba.ac.jpc 2001年由Elsevier Science B出版。V. CC BY-NC-ND许可下的开放访问。Ida2如何评估方案的信息你不太关心程序片段的求值顺序(当然,你必须意识到程序的某些片段的求值顺序)。你的程序可以由智能解释器执行。你可能会发现解释器不够聪明,或者不够顺从,无法运行你想要的程序。然后你看你的程序,并开始指定程序应该如何被评估。您将有各种自由如何评估该计划。您希望有一个评估指南。这一指导方针被称为战略。策略可能是从左到右、从右到左或更复杂的方式来评估程序。当我们的程序是一个由一组项重写规则重写的项时,该策略称为归约策略。例如,您可能想知道这些策略是否会为相同的程序提供相同的结果。要回答这个问题,你必须发展还原策略的理论。3减排策略的热点是什么?现在让我们重新思考裁减战略的热点问题。自从我们研究项目评估以来,减少策略是很有趣的程序是把我们的请求全部送到计算机上的东西。我恐怕很多人对这个论点并不感到兴奋,因为它过于模糊和简单。然而,如果我们立即开始用我们的正式语言谈论约简的定义、约简策略等,人们可能不会跟着我们走。对于热门的挑战性研究,我们需要找到好的应用程序,一些介于计算机和术语重写之间的东西,吸引人们,gu-粘性地说。下面我将尝试回答Gramlich[2]提出的问题。4减排战略研究的主要挑战是什么?笔者提供了一些研究成果和未来的研究课题,可以回答上述问题。归约策略理论已成功地用于解释计算过程,更具体地说,用于解释程序的行为。以Huet和Levy关于按需调用计算的开创性工作为例[4]。 它以非常优雅和严格的方式解释了函数式编程语言的惰性计算的本质。 他们的工作不仅解释了懒惰的评价,但澄清类程序的懒惰评价的可靠性是有保证的。约简策略的理论已被用于设计新的规划Ida3语言将按需调用计算的概念提升到函数逻辑程序设计中,发展了函数逻辑程序设计中的惰性缩窄,并将其用于设计我们的函数逻辑程序设计语言CFLP。类似的解释对于函数逻辑语言Curry是可能的。关于这些语言的计算模型,分别参见[5]和[3]语言ELAN[1]在利用约简策略的概念方面更有野心。它可以编程减少策略。作为应用归约策略理论的一个具体例子,我想指出一种基于高阶重写的符号计算语言Mathmartica。Mathematica提供了许多有用的功能,我们可以设计自己的策略。然而,似乎仍然缺少解释计算模型的好理论约简策略理论可以用于程序转换。程序转换是用来从效率较低的程序中导出效率较高的程序实现这一点的一种方法是在不影响计算结果的情况下改变求值顺序。减少策略的理论可以作为实现这一目标的指导方针。现在许多程序都运行在分布式或并行环境中。尽管并行和分布式计算的理论在不同的研究领域得到了发展,但约简策略理论可能能够为开发更复杂的计算机制提供良好的理论基础。5取得相关进展的巨大潜力在哪里?这个问题很难回答。当它解决涉及更多技术的更大问题时,这个问题就更相关了,比如如何实现真正的无处不在的计算。然而,我应该匆忙地补充一点,术语重写是计算的一个抽象概念,如果我们对复杂的计算系统有了正确的认识,它将是分析和理解它们的一个强大工具,而且还可以在相关领域中提出计算系统的新模型。6不同区域之间有希望的联系在哪里我已经暗示了这个问题的答案。减少战略首先与方案拟订有关。在现有技术中,在术语重写的框架内制定约简策略。因此,我们可以将约简策略的研究与函数程序和逻辑程序的研究当我们将研究对象从术语扩展到那些我们日常处理的事物的模型时,例如图像,音乐和大型文本文档,Ida4将能够定位与其他ELD的更多链接。虽然对这些对象的重写研究仍然是冷的社区,他们肯定是热的挑战。引用[1] P. Borovansky,C. Kirchner,H.基什内尔从功能语言学的角度看ELAN的改写及其语义策略。在Fuji International Symposium on Functional and LogicProgramming,第143{166}页,Kyoto,1998中。[2] B.格拉姆利克 个人电子邮件通信,2001年5月[3] M.哈纳斯函数式和逻辑式程序设计的统一模型。在proc 第24届SIGPLAN-SIGACT编程语言原理研讨会,第80页,巴黎,1997年。[4] G. Huet和J. -J. Levy。正交重写系统中的计算。《计算逻辑:纪念艾伦·罗宾逊的论文集》,第395页,麻省理工学院出版社,1991年。[5] A. Middeldorp,S. Okui和T.艾达懒惰缩小:强完备性和急切的变量消除。Theoretical Computer Science,167(1,2):95{130,1996.