Maude语言：主动网络编程和形式化分析的应用

240《理论计算科学》电子注71（2003）网址：http://www.elsevier.nl/locate/entcs/volume71.html21页在Maude主动网络编程语言Mark-Oliver Stehra，1和Carolyn L.Talcottb，2aFa c hbe re ei c hInformatik，Unive r sit a？tHam b u rg，D-22527Ham b u rg，German y.b计算机科学实验室，SRI International，Menlo Park，CA 94025，USA。摘要ESTA是一种为主动网络编程而设计的语言，可以更普遍地被视为移动计算的模型JavaScript以一种优雅的方式概括了命令式函数编程的范式，允许递归的远程函数调用，并且它为主机和移动代码之间的交互提供了一种清晰的机制指定和推理这些语言的技术越来越重要。在本文中，我们描述了我们的规范的重写逻辑语言Maude的。我们展示了如何使用技术指定的操作语义的命令式函数程序（基于语法的语义）和形式化变量绑定结构和移动环境（CINNI演算）结合自然的并发性和分布的我们还说明了广泛的方法，以正式建模支持Maude：执行mathematics程序，分析mathematics程序，使用搜索和模型检查，证明特定的mathematics程序的属性，并证明mathematics语言的一般属性。关键词：可执行规约，可执行规约，CINNI演算，形式化分析1介绍在[24]中，我们报告了我们在主动网络背景下使用重写逻辑[23]语言Maude[2]的经验。在那篇论文中，我们简要地概述了Maude在主动网络基础设施的两个不同层次上的应用，即在AER/NCA协议集的面向对象规范和在主动网络1电子邮件：stehr@informatik.uni-hamburg.de2电子邮件：clt@cs.stanford.edu2003年由Else vier Science B.V. 操作访问根据C CB Y-NC-N D许可证进行。斯特尔和T奥尔科特241编程语言.在本文中，我们提出了第二个应用程序更深入，并特别强调以下两个方面：（1）使用操作语义技术从编程语言理论增强CINNI显式替换演算;（2）广谱的方法，以正式建模支持Maude。我们首先简要介绍主动网络和主动网络。什么是主动网络？在Switchware项目[11]的网站上，一个与主动网络基础设施的设计和实现有关的项目，我们可以找到以下解释：主动网络探索了允许路由元素被通过它们的数据包广泛编程的想法。这使得以前只能在端点进行的计算能够在网络本身内进行，从而实现对当前协议的优化和扩展，以及开发全新的协议。主动网络是具有不根据固定方案（例如，如传统路由器）操作而是完全可编程的节点的网络，并且为可以经由网络从其他节点接收的程序提供执行环境主动网络可以是有线网络、无线网络或混合网络。人们可以认为主动网络是对传统网络的概括，也是朝着更大灵活性迈出的一步：在传统网络中由路由器按照严格的方案解释的数据包变成了程序，这些程序在主动网络中以通用的方式执行参见[31]对活跃网络研究的调查和最近DARPA关于这个主题的会议[3，4]。什么是“？WEB[10]介绍了作为主动网络的分组语言，并给出了以下解释：CORBA是一种资源受限的函数式编程语言，它使用远程过程调用的形式来实现主动网络数据包编程。它是SwitchWare项目的一部分。XML[13，12，25，14，19]，是一种类似于ML的命令式函数语言，但具有许多附加功能，如远程函数执行和资源感知。远程功能执行意味着可以以这样的方式调用功能，即执行不在本地发生，而是在不同网络节点的执行为此，函数调用被视为所谓的块，即作为一段数据，其通过分组被发送到目的地资源感知是指一种跟踪计算资源并确保所有可执行程序都终止的机制此外，VoIP程序通过服务包接口与其主机节点进行交互。基本服务包括提供有关本地网络的信息斯特尔和T奥尔科特242拓扑、本地节点属性、时间和路由。其他可能的服务包括用于（限时）数据存储和检索的驻留数据服务。我们的非正式语义来源包括（除了与Switchware团队成员的讨论之外）EJB规范文档[17]和论文[19]（对操作语义的相当详细的描述），用于推理安全性的抽象版本EJB [18]，以及EJB程序员指南[15]。我们已经指定了一种更通用的语言，我们称之为扩展的XML语言（简称xXML）。xcloud基于完整的按值调用λ-演算（也称为具有急切求值的λ-演算）和无限制递归，而xcloud的函数核心语言类似于ML的一阶片段，但只允许某种形式的有界递归。这种概括导致了一个语法上更简单、更优雅的模型，具有许多移动代码的互操作可能性。官方的XML语言自然地映射到由简单语法限制定义的XML子集。主要的限制是，递归调用只能发生在块内部，并且块的本地或远程此外，转发一个数据包到下一跳消耗一个单位，使标准的跳计数器方案，以避免路由的不终止是由这个概念。我们的规范完全捕获了规范[17]和[18]的意图，但具有形式化和可执行的优点。此外，正如我们将在下面说明的那样，这个规范可以在非常不同的级别上使用[5]，从执行测试配置，符号搜索和模型检查分析到验证程序和语言本身的一般属性。2莫德我们的规范分为三个主要部分：语法、网络和语义。语法部分是Maude中将xarrow语法作为代数数据类型的相当直接的形式化。网络部分对基本的网络概念（如位置、地址、连接和路由）进行建模，并尽可能少地保留了XML规范所需的细节。语义部分是问题的核心。主动网络的多级并发性非常直接地反映在计算状态中，计算状态的结构为影响范围和信息访问提供了明确的边界。• 网络配置被建模为包含节点和数据包的多集。• 对于每个节点，我们关联一个多组本地进程到节点，作为程序的执行环境，并可以在节点内同时执行。• 每个进程都封装了执行环境的本地状态以及抽象归约机。斯特尔和T奥尔科特243- -规则根据其范围进行分组 为了指定抽象机器，我们使用了一种适用于具有副作用的函数语言的通用方法，该方法基于[8，16，22]。 其主要思想是，抽象机的归约状态是一对，由一个归约上下文（即一个带洞的表达式）和在此上下文中要归约的表达式组成。此外，该规范使用CINNI演算[28]来指定语言的绑定结构。CINNI是显式替换的通用一阶演算，其在对象语言，并且不抽象变量的名称。3通过将环境直接形式化为显式替换，规范被大大简化，从而消除了在多个环境中显式处理环境的需要。几个地方。4它还为递归远程函数调用上下文中的绑定和环境处理的微妙问题提供了一个优雅的解决方案。2.1语法xcloud的抽象语法对绑定变量使用CINNI表示法。定义（绑定）变量的出现被表示为标识符。一个变量的引用出现被写为X n，引用X的第n个定义出现（从内部开始计数，从0开始）。假设一个自然数的排序Nat，和一个标识符的排序Id，这通过声明形式化排序变量op _{_}：Id Nat -> Var.排序常量包含内置数据对象的常量，以及函数、服务等的常量其被分类为构造函数（sortCstr）和非构造函数（sortNonCstr）。排序Cstr NonCstr Const .Subsorts Cstr NonCstrConst.ops Nil Dummy：->常量。ops Pair Cons Chunk Foldr：-> Cstr.操作Foldr Foldl Hd Tl：-> NonCstr.Foldr和Foldl提供了覆盖列表的功能。与使用LetRec的一般递归（见下文）相比，这两个函数提供了一种总是终止的有界递归形式，因此不会占用程序可用的计算资源。通过将相应的Maude排序注入到Const排序中来建模XML的基本数据类型。因此，它们同构于莫德类，但不与莫德类混淆。除了标准的Maude排序外，我们还预设了一个主机地址的排序Addr。主机地址对于给定的主机不一定是唯一的，因为每个主机可以有几个网络设备，并且每个网络设备都有一个相关的主机地址。[3]这与λ-演算模α-转换的表示或基于de Bruijn指标的表示相反。在这两种表示中，关于名称的信息都丢失了。4这与例如SECD机器形成对比，后者将环境作为一个明确的组成部分。在显式替代方法中，环境不能作为机器组件访问，而是通过CINNI方程尽快隐式消除。斯特尔和T奥尔科特244op Bool_：Bool ->Const.opInt_：Int -> Const.操作String_：String ->Const.op Addr_：Addr -> Const.op Key_：Int -> Const.每个服务功能都有常量。以下是一些例子。ops GetRB GetSource GetSrcDev：-> NonCstr . * 程序level opsThisHostIs GetNeighbors：-> NonCstr . * 节点级操作OnNeighborOnRemote：-> NonCstr.* 数据包创建操作列表获取放置：->非Cstr。* 数据存储库服务调用GetRB（）、GetSource（）和GetSrcDev（）用于访问关于当前进程的信息，即剩余的计算资源量、发起主机的地址以及发起当前进程的分组到达的网络设备的地址服务ThisHostIs（a）检查给定地址a是否引用当前节点本地的网络设备，GetNeighbors（）返回当前节点的邻居列表。OnNeighbor（chunk，dest，int，dev）使用dev作为传出设备在邻居dest调用给定的块chunk，并传递其资源单元的int，OnRemote类似，但允许在任意节点上执行，因此可能涉及通过必须作为附加参数传递的路由函数进行的数据包路由。最后，Rists（str，i）、Get（str，i）和Put（str，i，val，exp）提供对当前节点本地的驻留数据字典的访问，（str，i）是复合访问键，val是要存储的值，exp是到期前的时间注意，我们只对表示函数的常量使用构造函数和非构造函数的分类。这样做是为了识别表示值的表达式的子集。粗略地说，常量是值，而应用于值列表的构造函数是值。应用于任何表达式列表的非构造函数是需要一个或多个计算步骤的非值此外，应用于包含非值的列表的构造函数也是非值。在规范中，值和非值分别被形式化为排序Val Ex和NonVal Ex该语言的表达式是使用典型的函数式语言构造从常量和变量构建的。下面给出了xtexture的主要构造。5排序Ex.subsorts常量变量Ex.op：Ex ExList -> Ex.操作If_Then_Else_：Ex Ex Ex -> Ex.op5.有额外的结构用于顺序执行和异常处理。斯特尔和T奥尔科特245opop请注意，代表空语法，因此函数应用程序由函数表达式与参数列表的并置表示，反引号将mixfix声明中的词法标记分开。这些构造的含义是按值调用λ-caluclus的标准含义，但函数应用和λ-抽象被推广到任意n元函数（因此不需要currying），相应地，单个（递归）Let构造允许多个同时绑定。为了简洁起见，我们省略了类型注释的排序PlanType的声明以及排序IdList、ExList、ValList和PlanTypeList的明显声明。它们分别表示Id、Ex、Val和Plan Type上的列表，其中包含Id IdList、ExExList、Val ValList、PlanType PlanTypeList。我们总是使用构造函数_，_来连接列表。此外，我们使用一个常数empty-exl的空列表在Ex，我们扩展包含Val Ex到ValList ExList。2.2语义为了说明xmos的语义，我们首先解释如何表示全局活动然后，我们讨论的减少机器，这是为功能性编程原语的操作语义的基础。最后，我们讨论了过渡规则，并给出了主要类型的过渡的代表性的例子。2.2.1活动网络状态主动网络的全局状态是一个以节点、进程、数据包、数据集和唯一全局密钥为元素的多集模型排序和构造函数声明如下。我们假设对主机地址、位置、连接（即src>>dest形式的对）、路由（即destviacon形式的对，意味着dest可以通过连接con到达）的Addr、Loc、Connection、Route进行排序，并对相应列表的AddrList、Connection List、RouteList进行排序排序配置。排序节点包处理FreshKey数据DataItem。子分类节点分组处理FreshKey数据配置。opempty-conf：->配置。op：配置配置->配置[aslogid：empty-conf]。op节点：Loc AddrList ConnectionList RouteList -> Node。操作数据包：地址地址Int Int常量Val ValList -> Packet。op Process：Loc Addr Addr Int Int RedState -> Process。操作FreshKey：Int -> FreshKey。斯特尔和T奥尔科特246op Data：Loc DataItemList -> Data。操作DataItem：String Int Val Int -> DataItem网络节点具有Node（l，devs，nbrs，rt）的形式。位置l用作其标识符，devs列出其网络设备，nbrs给出到邻居的连接，rt是节点网络拓扑由其所有节点的组合设备和邻居信息给出。传输中的数据包的格式为Packet（dest，fdest，orign，ssn，rb，rf，val，vall），其中dest指定其路由到最终目的地fdest的下一跳目的地地址。每个数据包都有一个始发数据包，由某个应用程序注入网络，并分配了一个唯一的SSN是始发分组的会话密钥，而ORIGN是始发应用的地址RB是可用于分组执行的计算资源量，RF是分组的优选路由功能。最后两个参数与函数val和（已求值的）参数vall组成一个块。进程的形式为Process（l，orign，ardev，ssn，rb，rs）。当以节点l作为其最终目的地的分组到达时，该地址ardev是指数据包进入节点的设备，orign，ssn与数据包中的相同，rb是剩余的计算资源量，rs是归约机状态（见下文）。可接受的配置有一个FreshKey（key）形式的对象，用于为会话和受控数据共享生成新的密钥。每次生成键时，整数键对于驻留数据服务，每个节点Node（1，. . ）具有相关联的数据对象Data（l，dil），其中dil是数据项的列表。数据项的格式为DataItem（id，k，val，ttl），其中（id，k）构成一个复合键，值val存储在该键下最后一个参数ttl确定数据项到期前的时间（为了将来的兼容性而存在，因为当前未对时间提前进行建模）。在图1中，我们示出了示例网络拓扑和Maude术语示例拓扑的定义的片段，其表示具有该拓扑的初始网络配置网络具有六个节点l0，.，l5和六个子网na，...，不，不。在术语example-topology中，此拓扑由Node构造的AddrList和ConnectionList参数表示。该配置还包含有关下一个可用的新键的信息以及与每个节点相关联的初始空数据字典。2.2.2减速机当数据包到达其目的节点时，创建一个进程来执行由块封装一个进程的本地执行是由抽象归约机指定的。一个简单和简洁的形式化的reduc-tion机是至关重要的语义是有用的数学推理。我们已经使用了一种称为基于语法的语义[8，20，30]的方法来简化归约机，并在（部分）斯特尔和T奥尔科特2472niNBna0a11nd5NC4nee4C33op example-topology：-> Configuration.eqexample-topology =FreshKey（10）Node（loc（“l0”），（addr（“i0”），addr（“a0”）），（（addr（“a0”）>> addr（“a1”），（（addr（“a1”）via（addr（“a0”）>> addr（“a1”），（addr（“b1”）via（addr（“a0”）>> addr（“a1”），...））Data（loc（“l0”），empty-dil）Node（loc（“l1”），（addr（“a1”），addr（“b1”），addr（“c1”）），（（addr（“a1”）>> addr（“a0”）），（addr（“b1”）>> addr（“b2”）），（addr（“c1”）>> addr（“c3”），（（addr（“a0”）via（addr（“a1”）>> addr（“a0”），（addr（“b2”）via（addr（“b1”）>> addr（“b2”），...））Data（loc（“l1”），empty-dil）... .Fig. 1.示例拓扑执行）程序和机器状态。这种方法使用（扩展的）程序语法来表示语义实体。特别是，值只是表达式的一个子集，控制堆栈由带有孔的表达式表示，称为约简上下文。在CINNI演算的一个合适的实例中使用显式替换来表示环境。一个reduction machine state的形式为RedState（cx，ex），带有一个构造函数：操作RedState：Cx Ex -> RedState。约简上下文组件cx是一个有洞的表达式，ex是当前约简焦点的表达式。斯特尔和T奥尔科特248排序Cx包含在表达式可能出现的任何位置具有任何数量的孔（包括可能没有）的表达式因此，表达式构造函数被重载以构造上下文，并且有一个额外的常量？表示孔：对Cx进行排序。子分类Ex Cx.OP '？：-> Cx.约简上下文是一种特殊形式的上下文，其中孔对应于可以进行求值的位置在具有确定性求值语义的实例中，归约上下文具有单个孔，并且该孔不在任何绑定操作符的范围内。Redexs对应于机器指令，它们可以立即减少。在纯lambda值演算中，赎回是应用于值的lambda表达式：（λx.e）v。在Python中，它们还包括应用于值列表和let表达式的非构造函数，其中所有绑定都是值表达式。使用约简上下文的确定性求值的数学描述基于一个关键引理，该引理说表达式ex要么是一个值，要么它唯一地分解为约简上下文R和redex r，使得ex是用r填充R中的洞的结果（写作R[r]）[8]。约简上下文集合的归纳定义对应于每次剥离一层基本约简exts，直到达到红色ex：ex=R0[Rn[r]]。这些基本的归约上下文对应于一个控制栈，其中Rn位于顶部。为例如，一个实例应用程序的第一层ex=val（vall，nval，exl），其中vall是一个值列表，nval是非值表达式，约简上下文R = val（vall，？，exl）表示从左到右的求值顺序语义。大多数操作发生在内部基本归约上下文（堆栈顶部）。例如，假设上述应用填充了外部归约上下文RJ的空洞，使得exJ=RJ[ex] =RJ[R[nval]]。当nval的求值结果是VALJ时，这个洞就会被这个值填满，如果表达式仍然包含一个redex，那么这个表达式就会被重新组合。新的分解在外部约简上下文中是参数化的，也就是说，它具有形式RJ[RJJ[rJ]]，其中RJJ[rJ]是R[valJ]的唯一分解。下面我们使用变量ex、exJ等来对表达式进行范围划分（对Ex进行排序），使用变量cx、cxJ等来对上下文进行范围划分（对Cx进行排序）。洞填充的操作是元变量替换的特殊情况（洞是唯一的元变量），并且被推广为允许用上下 文填充洞（上下文组合）并应用于上下文列表（排序CxList），上下文是特殊情况。孔填充的过程通过以下操作形式化。操作：Cx Cx -> Cx。操作：Cx CxList -> CxList。eq？：=cx >？= cx。eq？：= cx > const = const.eq？：= cx >（cx：= cx >：= cx > cxl）。...斯特尔和T奥尔科特249一个朴素的形式化的约简机使用分解来确定下一个约简步骤，然后通过填充洞来将约简置于其上下文中。这涉及到许多孔填充和分解操作。一个更有效的形式化使用的观察，减少上下文层对应于一个堆栈，并表示这个堆栈使用惰性孔填充操作（没有方程简化）：操作：Cx Cx -> Cx。操作：Cx CxList -> CxList。形成约简上下文的规则可以很容易地用成员公理或直接构造来形式化.然而，他们不需要制定减少规则。它们更恰当地属于可执行规范的扩展，其中要证明语义的属性。例如，归约机在RedState（cx，ex）上维护两个不变量：（1）cx组件是一个归约上下文;（2）整个程序（在其当前评估阶段）由下式给出<：：= ex> cx，即通过用焦点表达式ex填充cx中的洞。除了用于填补漏洞的元变量替换之外，在我们的对象变量规范规则中还需要第二个替换概念。这种替换不能简化为简单的文本替换，因为它必须考虑对象语言的绑定结构。因此，我们使用CINNI家族的显式替换演算[28]实例化到xtem的语法。我们通过简单地将所有操作符从Id提升到IdList（这表示同时绑定），将原始的CINNI替换稍微推广到同时有一个基本的显式替换构造函数[_：=_]，两个辅助构造函数shift和lift，用于重定位（通过改变可变索引），以及一个将替换应用于表达式列表的操作（表达式是特殊情况）。sort Subst.op [_：=_]：Id Ex -> Subst.op [_：=_]：IdList ExList ->Subst.op [shift_]：Id -> Subst.op [lift]：Id Subst -> Subst.op [lift]：IdList Subst -> Subst.奥普：Subst Ex -> Ex.：Subst ExList -> ExList。eq（[id：= ex]（id{0}））= ex.* C1eq（[id：= ex]（id{max（m）}））=（id{m}）。*** C2eq（[shift id]（id{m}））=（id{shift（m）}）。* C3eq（[lift id S]（id{0}））=（id{0}）。* C4eq（[lift id S]（id{lift（m）}））=[移位id]（S（id{m}））。* C5当量（S常数）=常数。* C6斯特尔和T奥尔科特250eq（S（ex* C7eq（S（Lam [idl：typel] ex））=(Lam[idl：typel]（[lift idl S] ex））。* C8...2.2.3转变规则该配置通过本地归约机规则和服务规则来演化。后者进一步分为进程、网络、数据包和数据服务规则。简化机器规则。有两种归约机规则：控制规则，将焦点移动到下一个相关的redex;和执行实际归约的归约规则rl [args]：RedState（cx，（val（=>RedState（？：=（val（vall'，？，exl’)) >> cx, nval’)rl [up]：RedState（？：= cx >>=>RedState（：= val > cx）。rl [beta] RedState（cx，（（Lam [idl：typel] ex）vall））=>RedState（cx，[idl：= vall] ex）.规则args是一个控制规则，它将焦点移动到函数应用程序中的下一个未求值的参数。如果当前焦点是一个值，则规则向上将当前焦点移向顶部（将术语视为树）。这是唯一一个使用上下文漏洞填充的beta规则对应于按值调用lambda演算的标准beta归约规则。为了给CINNI如何处理替换的味道，我们展示了使用beta规则和前面给出的CINNI方程来减少和((Lam[x]（Lam [x]（x{0} x{1}）x{0}）= [x：= x{0}]（Lam [x]（x{0} x{1}））* beta=（Lam [x] [lift x [x：= x{0}]]（x{0} x{1}））* C8=（Lam [x]（[lift x [x：= x{0}]]x{0}[lift x [x：= x{0}]]x{1}））=（Lam [x]（x{0}[shift x]x{0}））* C1 C2 C4 C5=（Lam [x]（x{0} x{1}））* C3因此，原始x{0}已变为x{1}，以保持其对外部绑定的引用Process Service规则使用在进程中但在归约机状态之外保存的信息例如，GetRB的应用返回当前进程的资源界限，即剩余计算资源。斯特尔和T奥尔科特251rl Process（l，orign，ardev，ssn，rb，RedState（cx，（GetRB empty-exl）=>Process（l，orign，ardev，ssn，rb，RedState（cx，（Int rb）.网络服务规则使用节点的本地网络信息。例如，服务功能ThisHostIs检查给定地址是否是节点网络设备之一rl节点（l，devs，nbrs，rt）Process（l，orign，ardev，ssn，rb，RedState（cx，（ThisHostIs（Addr a）=>节点（l，devs，nbrs，rt）Process（l，orign，ardev，ssn，rb，RedState（cx，（Bool（contains（devs，a）））））。数据服务规则操纵节点驻留的数据存储。例如，服务函数Put添加或更新数据项。rl数据（l，dil）Process（l，orign，ardev，ssn，rb，RedState（cx，（Put（（String str），（Key key），val，（Int ttl））））=>Data（l，put（dil，str，key，val，ttl））Process（l，orign，ardev，ssn，rb，RedState（cx，Dummy））。分组规则包括用于发送、递送和路由传输中的分组的规则。OnNeighbor构造是发起远程函数调用的两种可能性之一，它由Chunk（val，vall）块给出。正如我们在下面可以看到的，OnNeighbor的执行导致了封装这个块的数据包的发射。crl节点（l，devs，nbrs，rt）进程（l，orign，ardev，ssn，rb，RedState（cx，（OnNeighbor（（Chunk（val，vall）），(Addr dest），（Int int），（Addr dev）=>节点（l，devs，nbrs，rt）Process（l，orign，ardev，ssn，（rb-int），RedState（cx，Dummy））数据包（dest，dest，orign，ssn，（int - 1），NoRoute，val，vall）斯特尔和T奥尔科特252if connection（devs，nbrs，（dev >>dest））and（rb >= int）and（int > 0）.请注意，执行进程的当前资源量rb是de-斯特尔和T奥尔科特253增加给予发射的分组的量，然后将该量减少一个，对应于第一跳使用一个单元。数据包的路由功能组件被设置为上面的一个无关常数NoRoute，因为OnNeighbor只能将数据包发送到直接邻居。更通用的OnRemote服务允许在任意位置进行远程调用，并允许用户指定在数据包中传递的路由功能。当数据包到达其目的地（下一跳与最终目的地一致）时，创建一个过程来评估所包含的块。crl节点（l，devs，nbrs，rt）数据包（dest、fdest、orign、ssn、rb、rf、val、vall）=>节点（l，devs，nbrs，rt）Process（l，orign，dest，ssn，rb，RedState（？，(val vall）if（dest == fdest）and contains（devs，dest）.还有一些规则用于路由尚未到达目的地的数据包，终止规则用于删除已完成任务的进程，以及异常处理规则用于生成，传播和处理运行时异常。3使用Maude Specification的用正式的符号拼写出细节迫使人们澄清概念，并做出明确的许多隐含的假设，但不能保证规范是正确的（代表预期的模型）或可用的。因此，规范必须经过进一步的检查和测试。与系统需求一样，正式规格说明是否正确是主观的，不能进行机械检查。然而，人们可以得出结果（预测），并将其与观察到的或期望的属性进行比较。在这一节中，它扩展了[24]中相应的一节，我们回顾了可编程逻辑程序的几个一般性质，并详细讨论了一个特定的程序及其分析。作为Maude中验证的一部分，我们证明了Maude规范中隐含的一些通用的P2P程序属性：(t)终止：假设所有分组最终都被递送（公平性），如果分组被注入到具有新的会话标识符的网络中，则具有该会话标识符的所有过程以具有以下形式之一的缩减状态终止执行：(t1)在当前规范中故意不计算的非值，例如Print val;(t2)无法执行的非值，因为它会导致运行时类型错误.(ni)无干扰：没有预先存在的（可访问的）数据元素的数据包被注入到网络中，独立地执行，也就是说，具有不同会话标识符的数据包的执行可以被单独考虑，因为用于交互的唯一机制是对数据元素的共享访问。斯特尔和T奥尔科特254−−(r)所需资源：对于一个通过重复发送数据包到所有邻居（一个对一个）来访问网络中每个节点的并行程序来说，从rb >2wd开始就足够了，其中d是直径-节点之间最长路径的长度，w是宽度-任何节点的邻居的最大数量。为了在每个端点处留下k个单位，从rb >（k+ 2）wd开始就足够了。终止结果比所述的更一般，因为它们允许对语言的某些扩展进行这些结果的证明将出现在即将发表的论文中。3.1测试和分析特定的可编程逻辑器件程序为了从程序员的角度测试规范的可用性这些演习的一般做法是，(i) 将程序表示为Maude项（一个简单的语法修改，可以自动化）;(ii) 定义一套测试配置，每个配置由网络配置和程序输入确定-也表示为Maude项;(iii) 使用Maude解释器运行测试配置;(iv) 使用Maude的搜索和模型检查工具进一步分析测试配置的可能计算(v) 证明任意网络配置和输入的感兴趣的属性（使用基于形式模型的普通数学推理）。作为一个具体的例子，我们将使用[19]中公布的一个路由查找程序。该程序的Maude项如图2所示。 该程序有两个主要功能：find，它向前搜索具有目的地址的节点; goback，它通过反向路由返回到源节点，并打印找到的路由。向前搜索，像Hansel和Gretel一样，通过在每个访问的节点上存储一个后指针来标记返回的路径，即离开前一个节点时使用的网络设备的地址。当包含调用find-prog-2（finddest）的数据包被注入到网络中具有给定目的地地址finddest的某个节点时，通过确定起始节点的地址（使用GetSource服务），通过生成用于标记数据的新键（使用GenerateKey服务）以及通过使用此信息初始调用find函数来初始化计算然后，网络中充斥着从先前未访问过的节点传播的数据包。为此，find函数首先使用驻留的数据服务索引来检查与当前键相关联的条目是否存在于当前节点的本地字典中。如果不是这种情况，则该节点先前未被访问过。因此，使用Put在本地字典中的同一个键下创建一个新条目来存储后指针。接下来，使用斯特尔和T奥尔科特255op find-prog-2：Addr -> Ex.等式find-prog-2（find-dest）=（LetRec [“goback”= Lam [（“k”，“route”））：（TKey，（TListTAddr））]（If（ThisHostIs（GetSource empty-exl））然后（打印“路线”{0}）Else（Let [“nexthop”=（Get（（String“”），“k”{0}））]（Let [“d”=（GetDevToHost“nexthop”{0}）](Let[“newroute”=（Cons（“d”{0}，“route”{0}））]（OnNeighbor（（Chunk（“goback”{0}，（“k”{0}，“newroute”{0}），“nexthop”{0}，（GetRB empty-exl），“d”{0}）]（LetRec [“find”= Lam [（“dest”，“previous”，“k”）：（TAddr，TAddr，TKey）]（If（String“”），“k”{0}））然后是傻瓜Else（（Put（（String“”），“k”{0}，“previous”{0}，（Int 200）;（If（ThisHostIs“dest”{0}）Then（“goback”{0}（“k”{0}，Nil））Else（(Let[“neighbors”=（GetNeighbors empty-exl）]（Let [“srcdev”=（GetSrcDev empty-exl）]（Let[“childrb”=.]* 分割rb(Let[“sendchild”= * 发出查找包Lam [（“n”，“u”）：（（TPair TAddr TAddr），TUnit）]（OnNeighbor（（Chunk（“find”{0}，（“dest”{0}，（Snd“n”{0}），“k”{0}），(Fst“n”{0}），“childdb”{0}，（Snd“n”{0}））]（Foldr（“sendchild”{0}，“neighbors”{0}，Dummy）））））]（“find”{0}（（Addr find-dest），（GetSource empty-exl），（GenerateKey empty-exl）。图二.一个路由发现ThisHost表示是否已经到达目的地，如果是这种情况，则通过调用goback将路由报告回源，goback递归地跟踪后指针，直到到达源，并且可斯特尔和T奥尔科特256以打印路由，这是在途中组装的。否则，辅助函数sendchild在find的主体中为每个邻居调用（使用Foldr遍历邻居列表），并且sendchild本身使用OnNeighbor构造递归地调用给定邻居地址上的find剩余的计算资源在所有邻居之间平均分配（相应的数量以childrb计算）。斯特尔和T奥尔科特257作为一个示例执行，我们在节点l0上以目的地e4（网络ne上节点l4的接口地址）开始一个进程。rew example-topologyProcess（loc（“l0”），addr（“i0”），addr（“i0”），1，100，红州（？，find-prog-2（addr（“e4”））））。所得到的最终配置返回路由（a1，c3，e4）（参见图1）通过在起始节点处打印相应的列表。在最后的配置中，我们还看到了数据字典是如何使用的。result配置：FreshKey（11）Data（loc（“l0”），DataItem（“"，10, Addr addr（“i0”），200））Data（loc（“l1”），DataItem（“"，10, Addr addr（“a0”），200））Data（loc（“l2”），DataItem（“"，10, Addr addr（“b1”），200））Data（loc（“l3”），DataItem（“"，10, Addr addr（“c1”），200））Data（loc（“l4”），DataItem（“"，10, Addr addr（“e3”），200））Data（loc（“l5”），DataItem（“"，10, Addr addr（“d3”），200））...Process（loc（“l0”），addr（“i0”），addr（“a0”），1，4，RedState（？，Print（Cons（Addr addr（“a1”），Cons（Addr addr（“c3”），缺点（Addr addr（“e4”），Nil）假设多个find进程可以同时执行，可能是在同一个节点上执行多个find进程，我们可能会问一个进程是否可以覆盖另一个进程写入的数据如果一个节点上的两个进程都在