TOYTOY可在www.sciencedirect.com在线获取理论计算机科学电子笔记282（2012）19-34www.elsevier.com/locate/entcs函数逻辑语言J.M. Almendros-Ji m′ene z a，1，R. Caballerob，1，Y. Garc'ıa-Ruizb，1，F. S'aenz-P'erezc，1，aDpto。西班牙阿尔梅里亚大学英语与计算机学院b人口与发展部。deSistemasInform'aticosyComputaci'onUniversidadComplutense de Madrid，SpaincDpto。deIngenier'ıadelSoftwareeeInteligenciaArtificialUniversidad Complutense de Madrid，Spain摘要XML是一种著名的查询语言，用于从XML文档中查找和提取信息。本文展示了这种特定于领域的语言的特征如何非常适合函数逻辑范式。建议的框架允许用户编写类似XPath的查询作为函数逻辑语言的第一类公民，使用高阶组合子来构造查询和非确定性，以获得查询可以返回的不同答案。 这一结果是两个不同地区杂交的一个很好的例子。在的情况下，用户现在可以在程序中集成XML查询，而无需使用任何外部库或专用接口。在这种情况下，高阶模式的使用允许我们定义函数，以便轻松处理查询。 特别是，该文件显示如何跟踪和调试错误的查询，以及如何检测一个查询是另一个查询的细化，这对于提高查询处理的效率非常有用关键词：函数逻辑程序设计，非确定函数，高阶模式1这项工作得到了西班牙项目STAMP（TIN 2008 -06622-C 03 -01，TIN 2008 -06622-C 03-03），S-0505/TIC/0407，Prometidos-CM（S2009 TIC-1465）和GPD（UCM-BSCH-GR35/10-A-910502）的支持。1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.12.00320J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）19TOYTOYTOY1引言在过去的几年中，可扩展标记语言XML [18]已经成为在纯文本文件中交换结构化数据的事实标准。这是它成功的关键，因为数据结构被揭示出来，因此它们很容易被处理（即使是普通的文本编辑器，如果你想手动编辑它们）。结构化数据意味着必须设计新的、更复杂的访问方法。XQuery [21，23]被定义为一种从XML文档中查找和提取信息的查询语言。它扩展了Java语言[19]，这是一种特定领域的语言，已成为通用语言的一部分。尽管表达能力不如XQuery，但XML的简单性使其成为许多类型查询的完美工具。由于其公认的重要性，XML及其查询语言已经体现在许多应用中，如数据库管理系统中，其包括在数据表示和查询语言（例如， Oracle和SQL Server）。 它们中的一些扩展了SQL以包括对XQuery的支持，因此XML查询的结果可以在数据库上下文中由更具声明性的SQL语言使用，从而可以共享关系和XML数据源。许多通用的声明式编程语言都支持XML和XQuery。在函数式编程领域，关于Haskell的作品可以在[17，2，22，16]中找到。也有基于逻辑编程的建议[15，14，3，12，7，13]。在函数逻辑语言领域[10]提出了一种用于处理半结构化数据的基于规则的语言，该语言在函数逻辑语言Curry中实现和嵌入。最近，在[5]中，我们提出了一种在函数逻辑语言[11]中的查询的实现，其中查询同时成为实现（代码）和表示（数据项）。在这个建议中，XML文档是通过数据项来表示的，而子项、自项、后代项等基本的子项被定义为可以应用于XML项的非确定性高阶函数本文继续这一工作，表明它非常适合功能逻辑范式。建议的框架允许用户编写类似XPath的查询作为函数逻辑语言的第一类公民。为此，高阶组合子用于构造查询，我们利用非确定性，以获得不同的答案，重复查询可能会返回。结果是两个不同地区交叉施肥的一个很好的例子：• 对于（在第2节中介绍），用户现在可以在程序中集成XML查询，而无需使用任何外部库或自组织J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）1921TOY∈⊂||TOY∈||接口.• 在函数的情况下（在第3节中介绍），高阶模式的使用允许我们定义函数来轻松处理查询。本文还以两种形式提供了嵌入的合理性，这构成了我们的主要贡献：首先，我们在第4节中展示了如何调试和跟踪错误查询。第二，我们运用补偿的思想[24]在关系数据库领域，我们的计划。这是指重用以前缓存的查询结果以增强查询解决性能的能力（第5节）。最后，在第六节中，我们得出了一些结论，并指出了一些未来的工作。2函数逻辑语言T OY一个[11]程序由数据类型声明、类型别名、整型运算符、函数类型声明和函数符号的定义规则组成。在e Exp中，表达式的语法是e：：=X h（eeJ），其中X是一个变量，h是一个函数符号或数据构造函数。形式为（eeJ）的表达式代表表达式e（作为函数）应用于表达式eJ（作为参数）。类似地，（total）模式t Pat Exp的语法可以定义为t：：= X c t1.. t mft1.其中X表示变量，c表示arity大于或等于m的数据构造函数，f表示arity大于m的函数符号，而t i表示模式1≤i≤m。数据类型声明和类型别名对于在T OY中表示XML文档很有用：数据节点=txt 字符串| 注释字符串| 标签字符串[属性][节点]数据属性= att字符串字符串type xml = node数据类型节点表示简单XML文档中的节点。它区分了三种类型的节点：文本、标记（元素节点）和注释，每种节点都由一个合适的数据构造函数表示，并带有表示节点信息的参数例如，constructor标签包括标签名称（字符串类型的参数），后跟属性列表，最后是子节点列表。数据类型属性包含属性的名称及其值（均为字符串类型）。最后一个类型别名xml重命名数据类型节点。当然，这个列表并不是详尽的，因为它遗漏了几种类型的XML节点，但对于本文来说已经足够下一页中的图1显示了一个XML文档及其表示22J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）19RTOYTOY在T OY<？XML version<食品>- <名称>西瓜/名称><价格>32/价格><产品展示
- oranges/name><品种>肚脐/品种><价格>74/价格><产品展示
- <名称>洋葱/名称><价格>55/价格><产品展示
- <名称>草莓/名称><品种>高山/品种><价格>210/价格><产品展示tag“root”[att“version”“1.0”][ tag“food”[][tag“item”[att“type”“fruit”][标签“name”[] [txt“watermelon”]，标签“价格”[] [txt“32”]]，tag“item”[att“type”“fruit”][标签“name”[] [txt“oranges”]，标签“variety”[] [txt“navel”]，标签“价格”[] [txt“74”]]，标签“item”[att“type”“vegetable”][标签“name”[] [txt“onions”]，标签“价格”[] [txt“55”]]，tag“item”[att“type”“fruit”][标签“name”[][txt“strawberries”]，标签“variety”[] [txt“alpine”]，标签“价格”[] [txt“210”]]]]Fig. 1. XML示例（左）及其在T OY中的表示（右）T OY中函数f的每个规则具有以下形式：ft1. .. tn→“我的天，图1，. ......你好。，ek其中s1= u1，. .. ，s m= u mle`ft-hapouch-npouch-dsixde右手侧`conpuzzonx`local定义x其中ei，ui和r是表达式（可以包含新的额外变量），ti，si是模式。In变量名必须以小写字母或下划线开头（对于匿名变量），而其他标识符则以小写字母开头。包括两个用于加载和保存XML文档的原语，分别称为加载XML文件和写入XML文件。为了方便起见，所有文档都以虚拟节点根开始。这用于对多个XML片段进行分组。如果文件在外层只包含一个节点N，则可以删除root，定义以下简单函数：loaddocF =N ==load xml file F ==tag“root”[att“version”“1.0”][N]其中F是包含文档的文件的名称。注意，条件中的严格相等==强制执行 加 载 xml 文 件 F 的 计 算 ， 如 果 结 果 的 格 式 标 记 为“root”[att“version”“1.0”]，则计算成功[N]对于一些N。如果是这种情况，则返回N。J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）1923TOYTOY我的天TOY3代表中国本节介绍我们打算与之集成的fashion的子集的方法，省略了所有支持但本文没有用到的反求特征，如反求轴的预处理等见[5，4]为更详细的介绍，以totoy。通常，XML表达式返回XML文档的几个片段- 是的 因此，xPath在函数语言中的预期类型可以是xPath = xml -> [xml]类型，这意味着结果的列表或序列得出这是[1]中考虑的方法，也是函数式编程[8]中的常用方法。然而，在我们的例子中，我们利用了语言的非确定性，单独返回每个结果。我们将一个XML表达式定义为一个函数，该函数以一个XML（片段）作为输入，并返回一个XML（片段）作为结果：type xPath = xml-> xml。为了将一个表达式应用于一个特定的文档，我们使用以下的整型运算符定义：中缀20（--）：：string->xPath->xmlS--Q=Q（load_xml_file S）这个操作符的输入参数是一个表示文件名的字符串S和一个查询Q。该函数将Q应用于文件S中包含的XML文档。此操作符在Oracle中扮演doc的角色分别对应于步骤之间以及轴和测试之间的连接的组合符/和：：被定义为函数组合：infixr55.：：.infixr 40./.（.：：.）xPath-> xPath-> xPath（./.）：：xPath ->xPath -> xPath（F.：：. G）X=G（FX）（F. G）X=G（FX）函数操作符名称.：：。和./. 因为标准的分隔符：：和/已经用 不同的含义定义。请注意，这两个定义是相同的，因为它们代表一个函数表达式应用于另一个函数表达式，并返回一个函数表达式，尽管它们旨在应用于函数：./的不同片段。步骤和。：：。用于组合轴和测试生产步骤。实际上，我们会使用一个操作符来表示两个组合子，但我们决定这样做是为了让更习惯使用这种符号的工程师保持类似的语法此外，我们不检查这些操作符的变量X表示输入XML片段（上下文节点）。规则规定了24J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）19TOYTOYTOY自我，孩子，后代：：xPath后代或self：：xPathself X = Xchild（tag L）=成员L后代X= child X后代X =如果子X == Y则后代Y后代或自我=自我？ 后裔nodeT，elem：：xPathnameT，textT，commentT：：string->xPathnodeT X = X名称T S（标签S属性L）=标签S属性L文本T S（txt S）= txt S注释T S（注释S）=注释Selem = name图二. T OY中的主轴和测试组合子应用第一个表达式（F），然后是第二个表达式（G）。图2显示了主轴和测试的定义。第一个是self，它返回上下文节点。在我们的设置中，它简单地对应于恒等函数。一个更有趣的轴是child，它使用非确定性函数成员返回上下文节点的所有子节点。注意，在XML中，只有元素节点有子节点，并且在表示中，这些节点对应于以构造函数为根的术语标签一旦定义了孩子，后代和后代或自我只是概括。该函数的第一条规则指定必须使用一次child，而第二条规则对应于两次或多次使用child。在此规则中，使用if语句来确保child在应用于输入XML片段时成功，从而避免可能的无限递归调用。最后，轴的定义是直接的。请注意，在这个自然定义中，XML输入参数是不必要的。关于测试节点，图2中定义的第一个测试是nodeT，它对应于通常的语法中的node（）这测试只是身份。例如，下面是返回XML文档中所有节点的XML表达式，以及它的TOY等价物：XML→doc（“food.xml”）/descendant-or-self：：node（）T OY →（“food.xml”<--后代或自身.：：. nodeT）== R唯一的区别是表达式在变量R中一次返回一个结果，询问用户是否需要更多的结果如果用户希望一次获得所有的解，就像通常的计算器一样，那么使用原语collect就足够了。例如，以下问题的答案：Toy> collect（“food.xml”-- descendant_or_self.：：. nodeT）==RJ.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）1925TOYTOYTOY产生一个单一的答案，R实例化为一个列表，其元素是“food.xml”中的节点。当axis child：：后面跟有名称时，它的缩写语法允许程序-mer 从 位 置 步 骤 中 省 略 axischild ： ： 。 因 此 ， 查 询 child ： ：food/child ： ： item/child ： ： price 在 XML 中 简 单 地 变 为food/item/price。在 中， 我 们 不 能 直 接 这 样做，因为我们是在一个类型化语言和组合子中。需要的是表达式而不是字符串。然而，我们可以通过定义新的酉运算符name（和类似的text）来引入类似的缩写，它将字符串转换为正则表达式：name：：string-> xPathname S = child.：：.（姓名S）所以，我们可以写在名称“食物”。/。name“item”./.名字叫“价格”。其他测试如nameT和textT选择XML输入的片段，这些片段可以在逻辑变量中返回，如下所示：XPath→child：：food/child：：item/child：：price/child：：text（）T OY →孩子。名字叫“食物”。孩子。nameT“item”./.孩子。名称T“price”./.孩子。文本TP逻辑变量P获得示例文档中包含的价格。另一个缩略语是//，它代表/descendant-or-self：：node（）/. 在T OY中，我们可以定义：infixr 30.（.//.）：：xPath -> xPath -> xPathA.//. B = append A（descendant_or_self.：：. nodeT./.B）append：：xPath -> xPath -> xPathappend（A.：：. B）C =（A.：：. B）./. Cappend（X./. Y）C = X. （附录YC）注意，一个新的函数append用于连接表达式。这个函数类似于著名的列表的append，但定义在xPath术语上。这是我们第一个关于高阶模式有用性的例子，因为例如模式（A.：：）。B）具有类型xPath，即，XML-> xml。可选地，重复测试可以包括谓词或过滤器。图中的过滤器括在方括号中。在 中，它们被括在圆括号中，并通过运算符连接到其关联的表达式。# ：infixr 60.#（.#）：：xPath -> xPath -> xPath（Q. #F）X=ifFY==_thenYwhereY=QX这个定义可以理解如下：首先，查询Q被应用于26J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）19TOY上下文节点X，返回一个新的上下文节点Y。然后if条件检查Y是否满足过滤器F，简单地通过检查F Y没有失败，这意味着它返回由F Y ==中的匿名变量表示的某个值。尽管过滤器谓词允许多种可能性，但在本演示中，我们仅限于过滤器表达式。多个谓词可以链接在一起，以过滤与运算符一样的项目，可以公式化如下：infixr60/&（X/Y）Z=ifXZ==_则YZ4Debugging XPath Queries我们设置的最吸引人的特性之一是可以操纵查询。在本节中，我们将使用此功能来跟踪和调试查询。我们区分两种类型的可能的错误，在一个错误的查询取决于产生的错误结果：错误的查询时，查询返回一个意外的结果，和失踪时，查询不产生一些预期的结果。我们提出了一个不同的建议，根据错误。4.1错误的密码例 如 ， 考 虑 目 标 （ “bib.xml”<-- name“bib”./.name“book”./.name“author”./.name“last”）== R和假设它产生意外的答案R ->（tag“last”[] [（txt“Abiteboul”）]）（参见[20]，样本数据1.1.2和1.1.4以检查这些文档的结构和示例）。如果错误只是作者姓氏的拼写错误，那么很容易在文档中查找错误信息以纠正错误。然而，在某些情况下，特别是在处理复杂的大型文档时，错误可能出现在XML查询中，即在文档中选择了错误的路径。在这些情况下，在文档中找到答案，然后回溯查询直到找到错误也是很有用的。注意，错误的答案可能只是生成的答案之一（在本例中，查询可以生成许多其他预期的答案），我们只对文档中产生意外结果的部分在中，我们可以通过定义一个合适的函数wrong来获得每个中间步骤及其相关的答案，该函数接收三个参数：查询，输入（最初是整个文档）和意外输出（最初是意外答案）。实现很简单：错误（A.：：。B）I/O =[（（A）：：. B），I，O）]<==（A.：：. B）I == O错误（A./. B）I O =[（A，I，O 1）|[错误B O1 O]J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）1927<==AI==O1，BO1==O在单个步骤的情况下（A.：：. B）第一个规则检查应用于输入的步骤确实产生返回三个元素的输出。在两个或多个步骤的情况下，第二个规则寻找由单个步骤A产生的值O1，使得应用于O1的查询B的其余部分产生错误结果O。变量O1是一个新的逻辑变量，并且代码使用函数式语言的典型生成和测试特性。函数wrong生成一个列表，其中每个步骤都与其输入和输出相关联。但是，由于XML元素表示为数据术语，直接使用wrong会产生冗长、难以理解的输出在T OY这可以通过构建一个包含所有信息的新XML文档并使用基本的write xml文件将其保存到文件中来改进：traceStep（Step，I，O）=tag“step”[] [ tag“query”[][txt（显示步骤）]，标签“input”[][I]，标签“输出”[] [O]]generateTraceL = tag“root”[]（map traceStep（rev L））writeTrace错误InputFile错误Output OutputFile=write_xml_file（generateTrace（load_xml_file InputFile）WrongOutput））OutputFile显示（A.：：. B）=（显示A）++".：：.“++（显示B）显示节点T =“节点T”...show child =“child”...第一个函数traceStep生成一个XML元素step，其中包含与一个步骤相关的信息：步骤组合子、其输入和输出。此函数使用辅助函数show来获取步骤的字符串表示形式（仅此函数的部分代码显示）。然后函数generateTrace将traceStep应用于步骤列表。它使用函数map和rev，其定义与函数式编程中的定义相同。特别是，rev用于确保查询的最后一步是文档中的第一步，这便于追溯结果。最后，writeTrace结合了前面的函数。它接收四个参数：查询、初始文档的名称、我们打算跟踪的意外XML片段以及输出28J.M. Almendros-Jiménez等人/理论计算机科学电子笔记282（2012）19TOYTOY保存结果的文件现在我们可以试试这个目标：Toy> writeTrace（name“bib”./. name“book”./. name“author”./.name“last”）“bib.xml”(tag“last”[][txt“Abiteboul”]）“trace.xml”在这种情况下，不使用符号==，这表明该表达式的结果必须为真。目标解决后，我们可以参考文档“trace.xml”：<步骤>child.：：. name T last/query><作者>Abiteboul/last><首页>Serge/首页><作者/Author<联系我们
