基于集合的非确定性声明编程在SINGLETON

216理论计算机科学电子笔记76（2002）网址：http://www.elsevier.nl/locate/entcs/volume76.html17页基于集合的非确定性声明编程在SINGLETONGianfranco Rossi1，2Dipartimento diMatematicaUniversit`adiParma 43100帕尔马，意大利摘要在本文中，我们提出了一种声明式语言，旨在结合CLP语言的有价值的功能，即，非确定性，统一，约束求解，动态数据结构，与传统的编程语言的功能，我们习惯了，我们不想放弃，如程序的语法形式，确定性控制结构，特别是迭代的，过程和参数传递的概念。实现这些目标的一个关键作用是集合的概念：集合不仅是一种强大的数据抽象，而且是非确定性的（唯一）来源，也是声明式（约束）编程的主要支持。此外，整个语言的语义可以用CLP语言的集合来描述，这也被用作所提出的语言的直接实现1介绍许多设计声明式编程语言的工作都在一定程度上基于（约束）逻辑编程（（C）LP）语言。然而，众所周知，这些语言（特别是Prolog）存在一些特殊性，这些特殊性在实践中使它们没有得到应有的重视这种在LP语言经常受到批评的方面中，我们可以列举：• 程序的语法形式，它与我们通常习惯的常规语言的通常语法形式相去甚远1这项工作得到了MURST项目Ragionamento su aggregati e numeri a programmazione erelative veri fiche的部分支持。2电子邮件：gianfranco. unipr.it2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。罗西河217• 理解LP计算模型的困难，特别是非确定性计算• 缺少通常的迭代控制结构（例如，for，while），因此许多LP程序都是基于递归的。相反，LP语言还有许多其他特性，尽管有时受到批评，但它们确实代表了支持真正声明式编程风格的有价值的特性其中，使用包含未初始化的变量）。从LP移动到CLP [5]，我们可以添加确定公式在特定域上的满足性的能力，而不管它们遇到的顺序和其中出现的变量的实例化最后但并非最不重要的是，精确的形式语义的可用性也是（C）LP语言的一个特征，这当然值得保留。在本文中，我们描述了一种语言，称为辛格尔顿-它试图尽可能多地保留CLP语言的有价值的功能，同时尽可能避免其有争议的方面。所提出的语言表面上类似于传统语言（例如，Pascal，C），但在它的深度类似于CLP语言。具体来说，辛格尔顿的一些显着特点是：• 类似Pascal的语法，具有类似Pascal的控制结构，特别是迭代控制结构• 非确定性，但限定为集合操作，其本质上是非确定性的，因此提供了对非确定性的更自然和更容易的[7]）• 一个强大的集合约束求解器，允许以真正的声明方式处理集合和集合此外，辛格尔顿仍然保留了LP语言的各种功能，例如（仅）“逻辑”变量（没有赋值）的可用性其他显著的特征是使用表达式作为陈述的可能性由属性定义的集合）。集合在辛格尔顿中起着关键作用。事实上，集合不仅可以用作强大的数据抽象，而且它们还提供了语言中的（唯一）非确定性来源和声明式（约束）编程的主要支持实际上，整个语言语义可以用CLP语言的术语，即CLP（SET）[3]。CLP（SET）也用于提供简单的单例实现。罗西河218设置本文的结构如下。在第2节中，我们给出了一个非正式的介绍，通过显示一个简单的SINGLETON程序。在第3节中，我们介绍了单例的基本数据结构，即集合和列表。在第4节中，我们定义了一些关于程序计算和表达式与语句的使用的在第5节中，我们介绍了未初始化的变量，然后在第6节中，我们简要描述了（集合）语言支持的约束处理设施。非决定论的基本概念及其与集合的关系将在第7节中讨论。在第8节中，我们介绍了用于模拟通常的迭代控制结构的构造，而过程定义和参数传递将在第9节中简要讨论。在第10节中，我们提供了一些关于处理可能表示有限集合的内涵集合的技巧的接下来，在第11节中，我们展示了转换函数的核心部分，它将SINGLETON构造映射到CLP（）条款和条件。最后，在第12节中，我们简要讨论了相关和未来工作。2对Singleton的非正式介绍首先，我们展示了一个简单的例子，一个程序写在辛格尔顿，这使我们能够得到的编程风格支持的语言的支持。问题：从标准输入中读取一个整数序列（以文件结尾结束），计算并打印其最大值。我们首先介绍计算整数集合S的最大值的子程序。然后我们展示实现所需输入/输出设施并调用子程序的主程序。注意，建议的实现没有考虑执行效率。事实上，SINGLETON主要被认为是一个快速软件原型的工具，在那里程序开发和程序理解的容易性胜过效率。程序最大值（单位：S;inoutx）开始xinS;对于S中的y，x>=yend端子程序是作为一个过程实现的，名为max。总体语法是常规块结构语言的语法（例如，Pascal）。过程是辛格尔顿中唯一可用于定义子程序的抽象过程中的形式参数可以是输入参数（in），也可以是输出参数（out），或者两者都是（inout）。第一个语句使用了一个可能未初始化的变量x。 语句是布尔表达式（实际上是一个约束表达式）用作语句。 如果表达式是如果它被评估为true，则语句成功;如果它被评估为false，则状态（因此max的计算）失败。如果S是，则S中的x被评估为真。罗西河219一个集合，x属于S。如果在计算表达式时x未初始化，这相当于非确定性地将S的元素分配给x。for语句允许测试条件x >= y是否对所有y属于S，其中x初始化为S的特定元素。y在for构造中被隐式声明为局部变量每次执行for的语句部分时，都会为S的每个元素创建一个新的y实例同样，表达式（x >= y）被用作语句。如果此表达式的计算结果为false，则整个for语句将失败。如果for成功终止（即，对于每个y，x >= y被评估为真），则整个过程成功终止。x的值表示我们要查找的整数。相反，如果x >= y对于某个y被评估为假，则会发生回溯，计算返回到最近的选择点。在这种情况下，最近的和唯一的选择点是由in操作符创建的。它的执行将非确定性地将x一个接一个地绑定到S的每个元素。如果已经尝试了S的所有值，则没有进一步的替代方案来探索，并且程序失败。对于max的第二个参数使用inout模式，允许使用该过程来检查x的指定值是否是集合S的最大值，并生成S的最大值。使用max的主程序可以定义如下：main（）开始varLinlist;varS，m;L =[x| read（x）&x in integer];ListToSet（L，S）;int max（m）;writel（“最大值为“<+ m）端主程序被声明为具有特殊名称main的过程。var关键字引入变量声明。L、S和m是三个局部变量。没有类型声明。但是，可以使用集合约束（因此，在运行时检查）将变量的值约束为一组可能的值。例如，L被限制为一个列表，列表是一个预定义的集合（即所有可能列表的集合L的值通过使用内涵列表定义来计算。一般来说，内涵形式符用于通过属性来定义集合/列表，而不是通过枚举它们的所有元素。在这个例子中，内涵定义用于将所有可以从标准输入中读取的x值收集到一个列表中，并且满足整数约束。一旦遇到文件结束标记，ListToSet操作是一个将列表转换为集合的库过程罗西河220∪{}···{}{}∩∅这种转换允许程序随后将已读取的数字集合作为一个集合传递给maxmax需要在一个集合上工作（而不是在一个列表上），以便能够利用集合操作（特别是集合成员资格）所带来最后，writel指令在标准输出上打印传递给它的列表的所有元素。字符串字面量（双引号中）只是其组成字符列表的语法符号，而<+是列表管理的内置操作符之一：结果是将m的值作为尾元素添加到字符串字面量表示的列表中获得的列表语言的大多数特性（例如，原子数据对象、表达式）非常类似于由常规编程语言提供的那些，并且将被跳过。在下文中，我们将集中精力，而不是，在那些功能，区分SINGLETON从传统的语言（和，另一方面，使它更接近CLP语言）。3原子和复合数据对象SINGLETON提供了两种复合数据对象：集合和列表。在集合中，元素的顺序和重复并不重要。我们将使用术语集合/列表聚合表达式来指代表示集合或列表数据对象的数据表达式。集合/列表聚合表达有三种，即外延的、内涵的和复合的定义3.1可拓集合集合是以下形式的数据表达式：{e1，.，en}（n≥ 0），其中e1，.，n是数据表达式。这个表达式表示的集合是集合val（e1）val（en）。特别地，用于表示空集。定义3.2内涵集合集合是以下形式的数据表达式：{DExpr|varVarList; BoolExpr}其中DExpr是一个包含非空变量集C的数据表达式，VarList是一个（可能为空）变量列表，CVarList=，BoolExpr是一个布尔表达式，涉及CVarList中的所有变量。所表示的集合是通过对DExpr中出现的变量的所有可能值进行求值而获得的所有值的集合，使得布尔表达式BoolExpr为真。出现在DExpr和VarList中的变量是局部变量，即，其范围是内涵的集合。当列表VarList为空时，整个变量声明可以省略。从逻辑的角度来看，S ={T|varV1，.，Vn; E}，其中T包含变量Y1，...，Ym，是x（x∈SParticipantV1， . . ，Vn，Y1， . . ，Ym（x=TE））罗西河221例3.3给定一个集合S，建立一个新的集合R，其元素是S的元素递增1。• R ={z +1|在S中的z}(or，等价地，R ={x|varz;x = z + 1且z在S中}）。内涵集合集合的一种特殊形式是区间集合。定义3.4区间集合是一个形式为{ei. ef}，其中ei和ef是整数表达式并且val（ei）≤ val（ef）。{ei.. ef}表示集合{val（ei），val（ei）+1，.， val（ef）− 1，val（ef）}.集合也可以作为计算复合集合聚合表达式的结果而获得。定义3.5设e是一个数据表达式，s是一个集合集合。复合集聚合是以下形式之一的数据表达式：(i) e>>s（元素插入）（ii）es（元素移除）<<表达式（i）表示通过从s中移除其值等于val（e）的元素（如果存在）而获得的集合（即，val（s）\{val（e）}）。表达式（ii）表示通过将val（e）加到s而获得的集合（即，s{val（e）}）。实施例3.6（化合物集合聚集体）• 3 + 2 >>{1，3，7}和5 >> 1 >>{1，3，7}表示集合{1， 3， 7， 5}• 0 1{1，2}表示集合{2}。列表聚合与集合聚合的语法形式几乎相同，只是使用方括号而不是花括号。然而，元素的插入和移除操作符与集合的操作符不同.事实上，在处理列表时，通常必须将插入和删除应用于列表的第一个（头部）或最后一个（尾部）元素，而元素的顺序在集合中并不重要。定义3.7设e是一个数据表达式，l是一个列表集合，x是一个未初始化的变量。复合列表聚合是以下形式的数据表达式(i) e+>l（头部元素插入）（iii）x<-l（头部元素移除）(ii) l<+e（尾元素插入）（iv）l->x（尾元素移除）表达式（i）和（ii）表示通过分别将val（e）添加为列表l的第一个和最后一个元素而获得的列表，而表达式（iii）和（iv）表示通过将val（e）添加为列表l的第一个和最后一个元素而获得的列表。（iv）表示分别从l中去掉第一个和最后一个元素而得到的列表表达式（iii）和（iv）的求值也会导致被移除元素的值变为x的值。字符列表聚合可用于表示字符串。还介绍了一种更方便的语法表示法：字符列表聚集罗西河222[JcJ1，JcJ2， . . ，JcJn]，n≥0，cn可以是相等的整数形式，例如，Jc1c2. . cnJJ.该语言还提供了一些预定义的集合：char，integer，realde，分别注意字符、整数和实数的集合;列表和集合分别表示所有可能的列表和集合的（无限）集合然而，对预定义集合和区间集合的操作仅限于成员关系而不是成员关系。4表达式、语句和程序计算在SINGLETON中，所有用户定义的子程序都采用过程的形式，并带有隐式关联的布尔结果，只要过程调用用作表达式，就可以利用根据以下定义，过程的计算可以以成功或（运行时）错误或失败终止定义4.1（失败）一个语句失败，如果它是一个布尔表达式用作语句，或者它包含一个布尔表达式用作语句，表达式的计算结果为假，或者它是一个过程调用，过程体中的语句序列失败。如果语句序列中的一个语句失败，则该语句序列 如果主过程中的语句序列失败，则程序计算失败。否则，计算成功。辛格尔顿的计算是不确定的。非决定论引入了选择点和回溯。一旦计算分支以失败而终止，则计算回溯到最近创建的选择点。如果没有选择点是开放的，则整个计算失败。没有赋值语句。控制结构类似于传统编程语言的控制结构（至少表面上），将在第8节中更精确地描述。不同于大多数传统语言（但类似于，例如，Alma-0[1]），SINGLETON允许语句被用作布尔表达式，反之亦然，布尔表达式被用作语句。定义4.2（表达式作为语句）设B是一个用作语句的布尔表达式。如果B的计算结果为false，则语句的计算如果B的计算结果为真，则计算继续。定义4.3（语句作为表达式）设S是用作表达式的语句如果S的执行成功，则状态返回的值为true;否则，值为false。特别是，如果被调用的过程成功终止，则过程调用成功（因此返回true值）此外，复合语句以S1; S2;...;Sn端为真，当且仅当所有陈述S1; S2;...; 是真的。任何语句执行都返回布尔结果。因此，语句可以在任何可能出现普通布尔表达式的地方使用特别是罗西河223语句可以用作if或while语句，并作为更大的布尔表达式的一部分例4.4检查集合S的所有成员是否都是负整数。if forxinS doxin integer andx 0 endthenwritel（“allnegative numbers”）端for语句用作布尔表达式，而整数中的布尔表达式x和x 0用作语句。3特别相关的是使用平等作为一个声明和作为一个布尔表达式。在约束求解过程的上下文中（见第6节），等式总是一致地被处理为统一（特别是集合统一[4]）5未初始化的变量一个变量在声明时没有与之关联的值，也就是说该变量未初始化。一个变量保持未初始化状态，直到一个值t被赋给它。当变量x得到一个值后，对x的任何其他赋值都是不可行的。也就是说，所有变量都被当作真正的“逻辑”变量来处理未初始化的变量可以出现在：（i）集合/列表扩展聚合和复合集合/列表聚合（在列表聚合的情况下有一些限制）;（ii）相等，不等式和其他约束表达式（见下一节）;（iii）在过程调用中，与out和inout参数相对应（见第9节）。任何其他表达式都不能包含未初始化的变量，如果不遵守这一点，将检测到运行时错误。4包含未初始化变量的集合/列表聚合部分表示特定的集合/列表，即，集合/列表，其中一些元素或集合/列表本身的一部分是未知的。实际上，每个部分指定的集合/列表表示不同对象的可能无限集合，也就是说，可以通过将值分配给未初始化的变量来获得的例5.1（部分指定的集合/列表）3注意，一个声明 它包含一个条件E和一个语句部分S， 例如如果E然后S，只有当语句部分S失败时才失败。此外，E被假定为确定性的：评估E不会留下任何开放选择点。4未初始化的变量只能出现在有限数量的不同表达式中，可能有限制，这主要取决于语言提供的约束求解器例如，如果算术运算符也是作为约束处理，那么我们也可以计算包含uninitialized变量的算术表达式。包括其他约束域和相关的求解器将是我们语言未来可能的扩展。罗西河224--C设置设置• 可拓集合集合3+2，x，y，其中x和y是未初始化的变量，表示包含两个未知元素的部分指定集合，表示为x和y;注意，由这个集合表示的集合的基数可以从3到1变化，这取决于分配给x和y的值（如果x和y都得到值5，则为1）。• 复合集合x+1 >> x+2 >> S，其中S是一个未初始化的变量，x的值为3，表示一个部分指定的集合，包含两个元素4和5，以及一个未知部分S;在这种情况下，所表示的集合的基数没有上限（下限为2）。未初始化的变量也可以出现在约束表达式中。虽然包含未初始化的变量，但这些表达式总是可以计算的，并产生true或false结果。下一节将更详细地讨论约束6(Set)约束基本的集合理论操作，以及等式和不等式，处理作为约束在辛格尔顿。包含此类操作的表达式的评估在当前活动约束集 合 （全局约束存储）的上下文中使用特定于域的约束求解器进行。这些表达式中不能完全求解的部分（通常涉及一个或多个未初始化的变量）被添加到约束存储，并将用于缩小可以分配给未初始化变量的可能值的集合在SINGLETON中用于约束求解的方法是针对CLP（）[3]所定义的方法。基本上，约束存储是使用基本集合论运算符以及等式和不等式构建的原子公式在集合论域中检查满足性，使用合适的约束求解器，该约束求解器试图将约束的任何结合减少到简化形式-求解形式-可以容易地测试满足性。稳定性。这个简化过程的成功使人们能够得出原始约束集合的满足性的结论。相反，还原为假意味着原始约束的不满足性已求解的表单约束保留在当前约束存储中，并传递到新状态。因此，成功的计算可以在最终计算状态下以非空的已求解形式约束集合终止SINGLETON中的约束基本上是CLP（）的集合约束，即原子约束表达式的合取，基于：相等、不相容、（严格）包含、联合、析取、交集、集合差异，以及它们中的大多数，也是它们的负对应。例6.1假设x，y，R，S和T是未初始化的变量，并且让全局约束存储最初为空。罗西河225--• 在S和！subset（{x}，S）：true，具有已解决的形式约束S = y>> Aset（A）x！=你好！中添加到约束存储区，其中A是新的未初始化变量，set（A）一个解出的形式约束（set（t）在t表示集合时为真• S = y >> R和un（{x}，S，T）和disj（{x}，S）：真，约束为解出的形式T = x >>y >> R x！= 你好！R中添加到约束存储中。约束求解器总是能够决定约束是假还是真，即使它的所有参数都是未初始化的变量。此外，原子约束的顺序是完全无关紧要的。所有这些功能都有助于支持高度声明性的编程风格。还提供了一种隐式延迟机制，用于动态推迟对某些约束的评估。具体来说，T中形式为x的成员约束，其中T是预定义集合，或者A中形式为x的成员约束，其中A是任何聚合，但约束出现在变量中或者在形式参数声明中（例如， var x in {1.. 10000}）总是自动延迟，直到x被初始化为某个值。 延迟在阻止条件不成立之前，不会对约束进行评估在计算结束时，仍然保持阻塞的延迟约束（如果有的话）无论如何都被评估，而不管它们的阻塞条件。最后，注意到将成员资格约束与变量声明相关联的可能性为程序中的变量提供了一种运行时类型7非决定论单例计算可以是不确定的。非确定性是编程语言支持声明式编程的另一个关键特性。然而，辛格尔顿的一个显著特点是，非决定论被限定为集合运算。非决定论的概念非常自然地适合于集合的概念（例如见[7]）。 集合统一和许多其他集合运算本质上是不确定的。例如，x在1，2，3其中x是未初始化的变量，不确定-tically返回x = 1，x = 2，x = 3中的一个。 由于set操作通常是很好理解的，并且非常此外，将选择点的创建和处理限制为集合操作可能会使非确定性运行时支持更易于实现。罗西河226--∃ ∈另一方面，其他类型的非确定性构造可以使用集合操作提供的非确定性工 具 轻 松 地 例 如 ， Alma-0[1] 非 确定 性 语句 EITHER S OXISSE T END 在SINGLETON中模拟为：x在1，2;如果x = 1，则S，否则T结束类似地，Alma-0非确定性语句SOME i：=s TO t DO S END，其中，elogicalmeningisthebondundedexistialquanini[s.]。t]S由SINGLETON语句模拟：iin{s.. t};S利用辛格尔顿非决定论的一个简单方法是使用内涵集。这种强大的抽象允许人们探索非确定性计算的整个搜索空间，并将所有计算的解决方案收集到一个集合然后可以处理收集的集合，例如，通过使用for语句迭代它的所有元素。 例如，一个可以很容易地模拟相当复杂的FORALL S DO T的行为ALMA-0的END语句，其目的是遍历S创建的所有选择点。例7.1计算并打印字符串p在字符串s中出现的次数。假设StringMatch（p，s，k）是一个过程，它能够检查p是否是s的子串，并返回子串p开始的位置k（参见第9节）。write（#{k|S t r i n g s（String s，String s，String s）;其中#A产生由A表示的集合/列表的元素的数量。我们再次强调，在辛格尔顿中，非决定论完全局限于集合运算。用户只需要理解这些操作的语义：非确定性自然嵌入其中。8控制结构SINGLETON提供了一些用于实现常见控制结构的结构，即if、for和while语句。if语句的定义是非常标准的。相反，for和while语句虽然表面上与通常的语句相似，但实质上与它们不同。实际上，缺少赋值语句会阻止使用可修改的循环控制变量。通过几个简单的例子，我们直观地了解了for和while语句的语法形式和语义罗西河227例8.1写出前10个自然数的平方，每个输出行一个对于{ 1..中的i10}做write（i*i）; nl端for语句用于指定要对给定集合/列表（特别是区间）的每个元素执行某个操作在每次迭代中，循环变量的一个新实例（在上面的例子中是i）被获得，并且集合/列表中的一个新元素的值被分配给它。如果语句部分对于循环变量的某个值失败，那么整个语句for失败。否则，它将成功终止。例8.2检查字符序列L是否对称。当#（L）> 1时，varfirst，last，NewL;NewL =first<- L ->last;first=lastend（NewL => L）while语句重复执行，直到L中的元素数#（L）小于或等于1。在while语句体中声明的所有变量--以及for语句的变量--都是该语句的局部变量本身在每次迭代中，所有局部变量的新副本都会被分配，就像块结构语言中的局部变量一样在例8.2中，在每次迭代中，分配一个新的变量NewL，并通过从L中删除其第一个和最后一个元素而获得的列表来初始化Uni化被用作初始化NewL的赋值，以及检查first是否等于last的测试。如果此测试失败，则while语句失败。否则，while语句在#（L）/2次迭代后成功终止。由于for/while循环中涉及的变量x的值不能改变，因此提供了一种机制，该机制允许将从x计算的新值存储在新的（局部）变量y中，并声明后者将在下一次迭代中代替前者使用。从语法上讲，这是由loop语句的end关键字后面的子句y => x指定的一般来说，一个循环语句可以由一系列的对Vi=> Vj结束，其中Vi和Vj是变量标识符，其含义是Vi在下一次迭代中字面上替换Vj（注意这不是赋值：可能绑定到Vj的值保持不变）。例如，在例8.2中，子句（NewL => L）要求在下一次迭代中使用NewL的当前实例代替L罗西河228----9过程定义和参数传递SINGLETON中的过程声明和过程调用基本上具有通常的类似Pascal的形式。当用作布尔表达式时，过程调用总是（隐式地）返回布尔值：即，如果过程的执行成功终止，则过程调用返回true结果;否则返回false。形式参数必须是变量，可能受到约束条件的约束（例如，inoutXininteger）。 参数传递方式可以是：（i）在（默认模式）中，实际参数必须是完全指定的value;（ii）out，实际参数必须是未初始化的变量;inout，实际参数可以是部分指定的值。灵活的参数传递机制，以及使用未初始化变量进行计算的能力，通常允许以非常灵活的方式使用过程，例如，使用相同的程序进行测试和计算解决方案（例如，参见第2节中的程序max）。过程定义也可以是递归的。 下一个示例显示一个经典列表连接过程的完全非确定性递归定义例9.1L3是通过连接两个列表L1和L2得到的列表。L2.程序concat（inoutL1，L2，L3）开始varx，R，NewL3;L1in []，x+>R;如果L1 =[]，则L3 = L2elseL3 = x +> NewL3;concat（R，L2，NewL3）端端当L1被初始化时，[]，x+> R中的语句L1只是测试L1是一个列表。相反，如果L1未初始化（或者它被初始化为一个部分指定的列表），则该语句将L1非确定性地统一为两个可能值之一，[]或x +> R。如果没有此语句，concat只能用于测试或生成L3，前提是L1或L2被初始化为列表;使用此语句（以及inout模式），concat可以使用这两种方法来检查一个给定的链表连接是否成立，并从其他两个链表中的任何一个开始构建三个链表中的任何一个（就像在Prolog中常见的append 利用这种不确定性版本的过程concat，很容易编写一个声明性的定义，例7.1中的StringMatch过程（与Prolog中通常的方式完全相同）。罗西河229--例9.2检查p是否是s的子串，并返回子串p开始的位置k（相对于s的开头）过程前缀（inoutL1;inL2）\\L1是L2的前缀开始vara; concat（L1，a，L2）end;StringMatch（inp，s; outpos）过程开始vara，b; prefix（a，s）;concat（a，b）;prefix（b，s）;pos =#a+1end;10处理无限集合/列表内涵聚合表达式的值是满足内涵定义所述属性的所有元素的集合/列表然而，并不总是评价一个内涵的总量必然需要明确的这 张 专 辑 /列 表 例 如 ， x 中 的c| P（ x） 可 以 等 价 地 被 评 估 为P（c），而不必生成和收集P（x）为真的所有可能的x值。如果集合/列表由内涵集合表示的是无限集合。处理{x}中的c|P（x）}|P(x)}表示无限集合。在[2]之后，我们假设处理内涵聚合是为了减少执行集合/列表收集的需要。具体地说，我们假设涉及内涵聚合的成员谓词总是像上面的例子那样被转换，从而完全避免了枚举所有构成元素的需要。此外，形式为x=e的等式（其中x是未初始化的变量，e是内涵集合）不会强制对e求值：集合会原封不动地通过计算传递一旦需要评估内涵总量例如，当它出现在写语句中时，则执行适当的集合收集操作。例10.1考虑语句序列var嵌套列表={z|（z= [x]和嵌套列表中的x）或z=[]};嵌套列表中的[[]];内涵集合集合表示形式为[]、[[]]、[]、.有任意的嵌套深度，这显然是一个无限集。罗西河230设置设置设置然而，这个集合不是显式生成的，而是以内涵形式保持因此，当执行第二条语句时，实际求值的表达式（[[]]=[x]和嵌套列表）或[[]]=[]。在嵌套列表中计算or表达式的左边部分gets[]这反过来又被评估为（[]=[x]和嵌套列表中的x）或[]=[]成功（具体来说，或的左边部分失败，而右边部分成功）。同样的技术可以应用于其他集合/列表谓词和运算符，如[2]中所建议的由于这种一般的内涵集约束管理还没有深入探讨，我们更愿意在这里限制我们的语言的当前版本的成员谓词，留下其他情况下为未来的工作。11语义SINGLETON程序可以用一种相对简单的方式转换成CLP（）程序。这种翻译可以作为一个精确的（逻辑）语义的辛格尔顿。此外，由于CLP（）是一种可执行语言，这种翻译也提供了S语言的快速实现。事实上，我们的语言目前可用的实现是基于一个用Prolog（使用DCG）编写的翻译器，它生成CLP（SET）代码。从SINGLETON到CLP的翻译）的定义是考虑到首先是数据表达式的翻译，然后是布尔表达式，最后是语句和过程。此后，我们将展示函数φ定义的核心部分，该函数将任何单例数据表达式t转换为对应的CLP（SET）定义。我们假设φ可以访问全局CLP（SET）原子Cφ的集合，并且函数add（a）用于将新原子a添加到Cφ。φ（t）将返回对应于t的CLP（SET）项，并且可能将修改Cφ作为侧效应。定义11.1设s，t，t1，.，tn是单个数据表达式，X1，.， Xn是Cφ中没有出现的新CLP（SET）变量，V（v） 是将每个单例变量v映射到新的不同CLP（SET）变量Xi的函数。φ （ c ） ， c 数 值 或 字 符 文 字 <$→c φ（v），v变量<$→V（v）φ（{t1，.，tn}）›→ {φ（t1），.，φ（t1）}φ（t>> s）›→ {φ（t）|φ（s）}罗西河231φ（t s）›→X1;add（diφ（s），{φ（t）}，X1））其中，di是集合差异操作的CLP（SET）约束φ（{t|varx1， . . ，xn;b）}→<${X：exists（[X1， . . . ，Xm]， X=φ（t）<$（b））}哪里 {X1，.，Xm}={φ（X1），.，φ（xn）}双变量（φ（t））φ（a），算术表达式<$→X1;add（X1isa）12结论、相关工作和今后的工作我们已经提出了一种语言，旨在融合的功能，强制性编程语言的CLP语言的功能集合的概念在这一结合中起着根本性的作用特别是，非确定性完全局限于集合运算。这种语言的程序表现出很好的声明性阅读，同时保持了传统语言的大部分程序结构其中两个作品对我们的工作影响更大：SETL [6]和Alma- 0[1]。像SETL一样，SINGLETON强烈地基于集合的概念。然而，SETL在处理集合的原始设施方面比辛格尔顿丰富得多。因此，SETL也比辛格尔顿更此外，一个值得注意的区别是SETL不是一种约束语言。SETL中完全没有约束的概念用未指定的值（SETL术语中的om）进行计算相当麻烦。相反，Alma-0是一种非常小巧优雅的命令式语言，具有不确定性结构和逻辑变量。约束出现在Alma-0的最新版本中，但尚未完全开发。数据结构基本上是Pascal的，因此是静态的。Alma-0和SETL都提供了许多结构来支持非确定性，其语义并不总是容易理解的。相反，在辛格尔顿中，集合运算自然支持非确定性。Alma-0和SETL都有赋值语句。不可否认，赋值在许多编程情况下非常有用和自然也很清楚，当它必须与逻辑变量和非决定论共存时，它使语言定义和实现变得非常复杂为此，我们更倾向于将我们的语言限制为逻辑变量，提供通常循环结构的合适变体，以保持几乎传统的编程风格。作为未来的工作，我们计划investigate的可能性，也引入“编程语言”变量作为一个“不纯”的许多其他新的功能也可以添加到基础语言之上，主要是特别是，集合和成员约束（可能在无限集合上）可以用来以一种非常自然和灵活的方式为变量提供运行时类型信息然后，静态程序分析工具可以利用这些信息在编译时执行类型检查可以引入数组，至少在逻辑上是这样。罗西河232--级别，作为使用现有集合和列表操作工具的有序对的集合。函数也可以表示，至少在逻辑层次上，通过它们的图，即有序元组的集合（可能是内涵定义的，可能是无限的）。例如，函数f（x）= 2 x + 1可以等价地定义为集合f=[x，y]。|y =2x+1，并且计算z = f（2）相当于求解f中的约束[2，z]（实际上已经是在SINGLETON中可解）。将函数作为集合将允许将它们作为数据进行操作，例如，设计语言的面向对象扩展，使用（嵌套）集合作为封装数据和相关函数的构造致谢我想感谢Barbara Baiocchi对SINGLETON编译器的开发所做的贡献引用[1] K.R. Apt，J. Brunekreef，V. Partington，and A.舍夫Alma-0：一种支持声明式编程的ACM TOPLAS，20（5）1998，1014四、七、十二[2] R. Carmona ， A. Dovier 和 G. 罗 西在 CLP 中 处 理无 限 内 涵 集。In M.Falaschi，M. 纳瓦罗和A.警察，EDS，AGP'97。Joint Conf. onDeclarative Programming，467 - 4 7 7 （ 可 在http：//www.math.unipr.it/pagiannfr/PAPERS/AGP.CDR97.p）。 十，十[3] A. 多 维 耶 角 Piazza ， E. Pontelli 和 G. 罗 西 集 合 和 约 束 逻 辑 编 程 。 ACMTOPLAS，22（5）2000，861-931. 1、6[4] A. Dovier，E.Pontelli和G.罗西设置统一。TR-CS-001/2001，部门 计算机科学，新墨西哥州立大学，美国，2001年1月（可在www.example.com上http://www.cs.nmsu.edu/TechReports）。4[5] J. JaZarar 和 M. J. 马 赫 约 束 逻 辑 程 序 设 计 ： 综 述 。 Journalof LogicProgramming 19-20，1994，503-581. 1[6] J. T. 施瓦茨河，西-地B. K. Dewar，E.Dubinsky和E.舍恩伯格用集合编程，SETL入门。Springer-Verlag，1986. 12[7] M. Walicki，S.梅铎集合与非决定论号手术Omodeo和G. Rossi，eds，ICLP93 Post-ConferenceWorkshop on Logic Programming withSets ，Budapest，1993. 第1、7条