没有合适的资源?快使用搜索试试~ 我知道了~
{|}理论计算机科学电子笔记176(2007)105-124www.elsevier.com/locate/entcs只有最好的才能做到:最佳组件选择Lars Gesellensetter1 Sabine Glesner11德国柏林工业大学软件工程与理论计算机科学研究所电邮地址:lgeselle cs.tu-berlin.de网址:http://pes.cs.tu-berlin.de/摘要在基于构件的软件工程(CBSE)中,构造成本最优的构件系统是一项重要的任务 它不仅要求最佳地选择元件及其适配器,而且还要求他们的相互影响。 本文采用编译器构造的方法,特别是优化代码生成,我们提出了一个统一的方法来构建组件系统,这使我们能够首先选择一组最佳的组件和适配器,然后创建一个工作系统通过提供必要的胶水代码。 通过我们的两个案例研究,我们证明,我们的方法是有效的,并普遍适用于实际情况。关键词:构件化软件工程,构件选择,适配器代码生成,项重写,代价函数1介绍基于协同的软件工程(CBSE)已经成为应对越来越复杂的软件系统和不断增加的应用领域的首选方法。CBSE要求将软件功能封装到软件组件中,这些组件又可以在其他系统中重用。在本文中,我们解决的问题,生成组件系统从指定的个别组件。通常,可以选择不同的替代组件,每个组件都有自己的成本。我们的目标是选择方法,保证生成的组件系统的最优性。特别是在存在巨大的组件存储库的情况下,最好的解决方案是不容易获得的。 我们要求我们的解决方案满足以下要求:为目标系统选择的组件应是最佳的。在经典情况下,成本度量反映了目标组件系统的速度。此外,我们希望能够处理任意的成本函数,特别是那些与嵌入式系统领域,例如代码大小或功耗。而且我们1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.02.034106L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105要求我们的方法能够从现有组件构建组件系统,而不修改组件本身,即将组件视为黑盒。只需生成适配器代码,即可将选定组件连接到工作目标系统。我们的解决方案将从现有组件构造组件系统的问题转化为编译器后端的代码生成问题,这通常是用术语重写方法来解决的。在代码生成过程中,我们必须找到一个最佳的机器指令序列,不仅要完成中间编译器表示中指定的计算,还要遵守目标处理器施加的约束,例如有限数量的寄存器或功能单元。 在编译器中的这个代码生成问题可以通过将程序表示为一棵树来解决,该树可以以自下而上的顺序进行缩减,同时为缩减的中间操作生成语义等效的机器指令。在基于组件的软件工程的上下文中,我们需要选择组件和适配器代码,以便生成的组件系统以最佳成本提供所需的服务。为此,我们将目标组件系统的期望行为指定为术语。重写规则将规范中所需的服务映射到具体的组件。在最佳解决方案中,所有必需的服务都以最小的成本绑定到没有冲突的组件。此外,必要时,组件通过适当的适配器代码连接。我们的工作是对基于组件的软件工程领域的重大贡献,因为它提高了组件的可重用性和组件系统构建过程的自动化。此外,我们的方法是普遍适用的,不仅对软件组件,但也为硬件组件或在该地区的硬件/软件协同设计以及。在所有这些情况下,组件通过它们所提供的功能来描述,并且需要根据它们的单独成本和它们所采用的整个系统的上下文来选择。可能需要适配器代码(其可以是软件或硬件两者)来集成所选择的(软件或硬件)组件。在本文中,我们讨论了两个案例研究。第一个考虑的情况时,设计汽车的电子系统。通常,需要几个子系统,让我们假设,我们需要例如导航系统、CD播放器和汽车防盗系统。这些子系统中的每一个都可以以不同的方式实现,每一种方式都有自己的成本。 例如,一个汽车防盗系统可能会工作通过不断发送汽车的当前位置。在这种情况下,GPS信号传感器是必要的。如果GPS传感器也被其他子系统使用,例如被导航系统使用,则可以补偿该设计决策的成本。一般来说,汽车系统的总成本不仅取决于单个组件的成本,还取决于它们之间的相互作用。 我们将在第7节中更详细地讨论汽车场景。我们的第二个案例研究考虑了聊天机器人系统,该系统实现了作为手机娱乐应用程序的虚拟对话伙伴[8]。该系统提供一系列服务,从用户界面到对话系统再到可视化组件。对于每种服务,不同成本L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105107Fig. 1.的部件存在. 在第7节中,我们展示了我们的构造方法如何自动选择组件,使得最终的组件系统以最优成本提供所有所需的本文的结构如下:在第二节中,我们介绍了我们的组件的概念。基于这一定义,第3节概述了我们的组件选择和集成方法。第4节涉及术语重写和最优代码生成的相关问题,我们需要详细解释我们的概念。第5节给出了我们的方法的全面介绍。在第6节中,我们描述了我们的方法的实现,第7节介绍了更详细的案例研究。 在讨论了第8节中的相关工作之后,我们在第9节中结束。2组件模型我们通过服务的方式来描述系统和组件的行为。服务封装了特定的功能,并通过实现它的方法的接口进行形式化描述。每个方法都通过其名称和命名参数列表进行标识。目前,我们不考虑类型问题,而将参数简单地视为字符串。此外,我们假设一个黑盒组件模型和描述组件的四个特征。组件由它们提供的服务(提供的服务)以及它们正常工作所需的服务(所需的服务)来指定。此外,每个组件可能会造成架构约束(在软件组件、通信标准等情况下所需的底层平台)。此外,关于组件的某些组件属性例如它们的代码大小、它们的能量消耗或它们的价格。图1显示了一个组件:A和B是提供的服务,C是必需的服务。ArchStyle表示架构约束。我们假设以下情况:给定一个组件库和我们想要构建的组件系统的规格,我们需要选择组件并在必要时通过合适的适配器代码连接它们,以便 目标组件系统满足规范。为此,我们需要一个规范,服务是否以及如何相互映射。作为说明,可以将此信息视为(但不一定实现为)一个巨大的表,如表1所示。 在表中,我们看到这样一个映射,指定用于提供m个服务的n个组件的系统。m个108L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105组件/服务C1C2···CnR1R2R3···Rl−1RlC1P1P2P3––––––···–––C2P4–···–..... ...CnPk−1PK–Mk1––···––表1映射服务可以被细分为k个提供的服务(表示为Pi)和l个需要的服务(表示为Rj)。谈到适应性,我们总是想到一个提供的服务映射到一个需要的服务。这样的一对服务可以是不兼容的、可适应的或相同的。适应性意味着所提供服务的方法可以映射到所需服务的方法上。映射不需要是一对一的,方法名和参数都可以转换。正如我们在表中所看到的,P4和R2以及R1是相同的,因此可以直接互操作。服务Pk可以适配于服务R1,并且同样分别适用于Pk-1和R2以及P1和R1。在所有其他情况下,适配是不可能的,服务是不兼容的,由相应的表格单元格1中的破折号指示。从规范中,我们可以看到所需的服务R2可以直接由服务P4提供,也可以通过服务Pk-1进行适配。根据每种选择的成本,人们必须决定做出哪种选择在我们的实现和本文描述的案例研究中,映射是由函数规范有效地给出的,适配器代码可以由通用规则生成。其优点是,这些规则只需要为每个考虑的架构指定一次在几种可能性的情况下,我们感兴趣的是最优的。我们描述了一个组件系统(我们的目标是构建)所需的服务。此外,我们可以定义架构约束。然后,必须根据组件提供的服务来选择组件。 在制度建设过程中,可能需要选择另一个组件,因为不是所有需要的服务都可用。必须确保所选组件的架构约束相互匹配,并与最初给定的系统约束匹配。除了给定的约束之外,新的约束可以在选择过程期间动态地演变。为了选择最优的组件,我们需要一个最优性的概念。为此,必须给出成本函数。通常,它通过考虑组件的属性将成本分配给组件。此外,成本函数将成本分配给连接组件的适配器代码不同的服务可能在功能上是等效的,但是它们的接口可能不直接兼容。在这种情况下,适配器规范说明了如何将一个服务的接口映射到另一个服务的接口。 如果适配器将服务A的接口映射到服务AJ的接口,它可以是1对于表中的某些字段,不允许或不合理地存在映射:组件提供的服务不能映射到组件所需的服务。如果是这种情况,那么相应的服务无论如何都是冗余的。L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105109(i)(二)图二、系统描述的可能组件选择被视为需要服务A并提供服务AJ的组件。从功能适配器规范中,可以生成适配器的实例化。这种适配器的概念允许我们使两个组件在没有入侵的情况下互操作,即不改变组件,因此,很适合我们的黑盒组件模型。对于要构建的目标组件系统的描述和可用组件的存储库,我们指定以下信息:(1) 目标组件系统中服务的描述,由其接口描述指定,(2) 组件规范,包括提供和要求的服务以及架构约束和定义成本度量的相应属性,(3) 适配器规范,它为每对组件指定是否以及通过哪个适配器代码可以将它们的服务(即它们的接口)映射到另一个。例如,考虑图2: 系统必须提供服务A,B.根据给定的存储库,我们手头可能有分别提供服务A和B的组件。如果它们的约束彼此匹配,并且初始约束也匹配,则我们有一个如图2(i)所示的解决方案。但是,我们可能会选择一个提供A和B的组件,但它需要另一个服务C。然后,情况可能是我们只有一个提供服务CJ的组件可用。 如果我们有一个适配器指定从CJ到C的映射,我们最终会得到图2(ii)中所示的解决方案。这取决于成本函数,哪种解决方案是优选的。 例如,如果图2(ii)中的左侧组件比图2(i)中的两个组件一起更便宜,第二种选择可能更好。然而,必须为服务C选择额外组件的成本可能会抵消这种好处,甚至导致次优解决方案。在下面的部分中,我们将概述我们构建成本最优组件系统的方法。110L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)1053利用项重写构造最优构件系统在本节中,我们将概述我们的方法,特别是关于使用编译器构造领域的方法。我们从下面的具体问题开始:我们假设期望的系统行为是给定的,以所需服务的形式,以及可用服务、组件和适配器的规范,以及它们的成本函数和架构约束。鉴于此描述,我们希望找到一组最佳组件,以满足需求并实现互操作性(通过考虑约束和生成适配器)。一般来说,这个问题是NP完全的[10,11],所以我们不能指望一个算法总是有效地解决这个问题的每个实例,即在多项式时间内。然而,我们可以研究启发式策略,在许多实际情况下可能有助于找到最佳解决方案。为此,我们将我们的问题映射到编译器后端的最佳代码选择问题这是特别有用的,因为在这两种情况下,我们都有一个系统行为的描述,我们需要从中生成目标系统。在组件系统的情况下,描述指定了所需的服务。在编译器后端的情况下,它将所需的功能表示为中间编译器表示。在这两种情况下,我们都有实现特定功能的系统部分(目标平台的组件或机器指令)。在这两种情况下,映射是1:n而不是1:1,因为组件可以提供许多服务,同样,机器指令可以执行组合功能。最后,在这两种情况下,我们感兴趣的是最优解。因此,这是一个很有前途的方法,从代码生成问题的解决方案,组件选择。对于最佳代码生成,一种标准技术是项重写。它可以证明找到最优解。 在术语重写中,我们从初始术语开始,尝试使用一组给定的重写规则,以自下而上的顺序将其重写为目标项。每当应用重写规则时,就会发出语义等效的机器代码。发出的机器代码的总序列构成目标机器程序。每一条规则都是有代价的。在代码生成中,使用自下而上的项重写,以限制搜索空间并确保生成的指令的正确排序(cp.[9]; [1]证明了具有共享子表达式的表达式树的最优代码生成是NP完全的)。由于通常有很多方法来重写一个术语,我们处理一个经典的搜索问题。 启发式搜索是处理搜索空间的复杂性的有价值的手段。A* 搜索保证探索搜索空间的最小部分,同时仍然找到最优解,在这个意义上,没有其他算法搜索最优解。保证扩展比A更少的节点,cf.[6、3]为了将组件选择问题建模为项重写问题,我们2考虑复杂的加载操作,它执行加法和乘法来确定地址。因此,具有地址计算的加载可以被映射到多个简单命令或复杂加载指令。另一个例子是乘以2,这可以通过乘法运算或通过更便宜的左移运算来实现。L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105111ΔΔ规则match:carsystem(.,ΔATP,.. . )替换:汽车系统(儿童J)|哪里儿童是获得在PGPS− 传感器将Δ替换为在P儿童GPS传感器GP SLoc和插入Δ,如果没有价格:50}图3.第三章。 组件选择规则示例将期望的系统行为作为一个术语来陈述。重写规则对应于组件(连同其提供的和所需的服务)或适配器的选择。每个规则的成本函数表示所选组件的成本。因此,我们用以下方式表示系统规格系统约束(ΔA,ΔB)该术语表示一个系统,该系统应在以下条件下提供服务A和B给定的架构约束。表示给定的服务仍然未绑定。在重写过程中,每个服务将被绑定到某些组件,如果选定的组件需要,可能会引入更多的服务。最后,我们到达一个最终状态,即所有成分都被束缚的项。 重写过程中收集的信息告诉我们选择哪些组件以及如何实现互操作性(通过生成适配器)。重新考虑我们前面的例子,我们可以通过以下项指定所需的系统行为:汽车系统(Δ防盗保护、Δ立体声、Δ导航系统)一个重写序列可以是(为了方便起见,对服务进行车载系统(ΔATP、Δ立体声、ΔNavSys)→汽车系统(GP SLocATP、Δstereo、ΔNavSys、ΔGPS−传感器)→车载系统(GP SLocATP、CDman100立体声、NAV 200NavSys、ΔGPS−传感器)→车载系统(GP SLocATP、CDman100立体声、NAV 200NavSys、GPS 10GPS−传感器)请注意,在第一个重写步骤中引入了一个新服务。对于第一个重写步骤,应用的规则如图3所示。我们看到该规则是适用的,因为我们有一个ATP3类型的未绑定服务。作为规则应用的结果,服务ATP被绑定到GPSLoc,并且GPS传感器被添加为新的所需服务,因为它在当前系统ESPITON中既不作为绑定服务也不作为所需服务出现。剩余的重写步骤通过相应的规则类似地执行在我们的概念和一些激励性的例子的一般介绍之后,我们现在准备详细描述我们的方法。为此,我们在第4节中介绍了一些概念所需的术语,即术语重写和A* 搜索。在确定了这些先决条件之后,第5节介绍了我们的方法。3在这个例子中,没有进一步的架构约束。112L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105F∅V FV TF VF →F →4术语重写和A*在我们的方法中,我们使用了[9]提出的耦合项重写与A* 的思想。这保证了有效的搜索。我们简要介绍了关于成本函数的项重写,然后介绍了A* 搜索的概念。最后,我们描述了两者之间的耦合,并讨论了复杂性问题。4.1项重写术语重写[2]是代码生成的标准技术术语以通常的方式归纳定义:我们从一组有限的函数符号开始,称为签名。每个函数符号都有一个由函数r:N给出的值。元数为0的函数符号也称为常量符号。我们添加一组变量(= ). 项的集合,记为(,),以通常的归纳方式定义。 对于项t,Var(t)表示其变量。如果V ar(t)=,则t称为基项。定义4.1(成本条款重写系统)成本条款重写系统(CTRS)定义为三元组((F,V),R,C),• F,非空签名• V,变量的有限集合• R,T(F,V)×T(F,V)的非空有限子集• C∈R→R+,代价函数对所有(l,r)∈R满足:(i)l/=r,(ii)l/∈ V,(iii)V ar(r)<$V ar(l)<$我们丰富了一个术语的概念,允许任意arity为某些功能符号(充分模型列表),并附加一个类型4和属性的功能符号。此外,我们扩展了规则的先决条件,它可以引用任何这些信息。注意,这些扩展不会引入额外的复杂性,因为它们可以用经典术语概念直接表达(将属性建模为子项,通过引入n个新函数符号并相应地修改规则来建模n元函数符号)。我们通过以下方式扩展和修改给定的定义:定义4.2(n元项)我们将arity函数的域扩展到N{n},这意味着arity是任意的但有限的。T(F,V)的归纳定义必须相应地修改⬦定义4.3(归属于条款) 我们 介绍 一个函数t:T,它为每个函数符号指定一个类型。函数符号的属性由其类型决定。对于具体术语中的每个函数符号,返回术语属性的属性函数相关联⬦4我们的类型概念目前是非常基本的,主要表示一个特殊的属性,仅指给定函数符号(而不是完整的子项)。L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105113−见图4。 A* 搜索的类型信息允许我们编写更通用的规则。例如,在代码生成的上下文中,用于算术运算+和将两者都是BinOp类型。这允许我们编写一个处理二元运算符的通用规则。对于符号,我们写一个函数的类型符号上标和它的attributes订阅。如果该类型与上下文无关或很清楚,我们只需省略它,就像我们对属性所做的那样。因此,具有属性a1, a2的类型的分量comp表示如下:type a1=val1,a2=val2重写规则规定了如何重写条款,必须满足哪些先决条件以及产生哪些成本。 此外,可以说明哪些代码应该生成。一般来说,有很多方法可以重写一个给定的术语。为了找到最佳的重写顺序,必须考虑所有不同的可能性。搜索空间的复杂性促使启发式搜索方法的利用,其中A*搜索是一个例子。4.2A* 搜索搜索可以由启发式函数来引导,以近似剩余转换的成本。A* 搜索([6])保证最小的探索(w.r.t.启发式函数)的搜索空间,同时找到一个最优解,给定的启发式函数是可接受的。容许意味着函数总是欠近似实际成本。 如果我们把零函数作为搜索函数,我们最终会得到与无信息搜索相同的行为。启发式函数预测的成本越精确,搜索的成本就越低。算法为处理组合爆炸问题提供了一种有价值的手段。搜索的一个常见和描述性的例子是找到从一个位置到另一个位置的最佳路线的问题。节点对应于位置,并且边表示连接,例如街道。给定边的代价是它的距离。节点的启发式函数定义了它的距离(这里是字面意思)comp114L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105到目标节点。直觉上,我们选择航线距离5。例如,考虑图4。我们想从A旅行到Z,我们的搜索树由所有可能的路径组成,从A开始,可能通向Z。在每个节点上,我们标注累积成本(到目前为止行驶的距离)和估计的剩余成本(还有多远)。A* 是广度优先搜索,即,我们考虑所有可能性,但首先考虑最便宜的。 对于给定的例子,我们首先尝试B,因为12+ 40= 52是最便宜的选择。 然而,到达B后,我们有一个比E更便宜的选择。因此,回溯发生,我们继续D. 剩下的搜索直接通过G到达目标Z,遇到的实际距离是60,而不是最初假设的50。图4中的阴影区域描述了搜索空间的已访问部分4.3用A*这是一个通用的搜索问题,以找到给定项的最优解。搜索空间包含所有术语,转换由规则给出。 如果我们采取一个 * 搜索与一个可接受的启发式函数,它保证我们找到最佳解决方案在最短的时间相对于该启发式。 本申请在编译器中代码生成的上下文中,A* 到项重写的方法最初由[9]提出。4.4复杂性如前所述,为给定的服务集选择组件子集是NP完全的(这个问题是NP问题,可以简化为SAT),即使没有找到最优解的约束。考虑到项重写,一般来说,给定项是否可达是不可判定的(对应于找到一个解),甚至仅终止也是不可判定的。限制重写的基础条款(即禁止变量的规则),可达性的目标条款是可判定的。DAG上的最小成本指令选择是NP完全的[1]。虽然基础项重写必须处理组合爆炸的问题,但它仍然产生了一个用于找到解决方案的建设性算法,并且通过限制允许规则的类别和适当减少搜索空间,该问题在实际场景中变得可行。5组成系统:算法系统的组成分两步实现:首先完成组件的选择(包括适配器的选择);在第二步中,生成所需的适配器代码。系统规范被表示为一个术语,组件选择以及适配器代码生成通过术语重写来执行。这些规则部分是通用的(特别是对于适配器代码生成),部分是特定于具体系统的(特别是对于组件[5]很简单,这种计算方法总是低估了实际成本。[6]即使对于只有一个规则的非常简单的系统,这也是成立的;通过将其简化为问题这个词来证明L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105115Δrule匹配:系统[服务] |ΔS∈services:S∈ prov(C)cond:constr(系统)constr(C)满足要求replace:system[servicesJ],其中servicesJ=Δ Sreq|Sreq/∈ services <$Sreq ∈ req(C)}{C Sprov|Δ Sprov ∈ services <$Sprov ∈ prov(C)}断言:费用:{C<$ S∈服务器|(C<$/=Δ)<$(S/∈prov(C))}成本(道具(C))constr(系统)constr(C)满足要求}图五、元件选择的通用规则选择)。然而,具体规则是从系统规范中完全自动生成的。5.1组件选择系统描述包括组件描述、从提供的服务到所需服务的映射描述以及所需功能的描述。此外,还必须具体说明成本措施一般来说,在描述一个系统时,必须识别相关的服务。通过标识,我们的意思是组件的功能被分组为自包含的、有意义的集合,称为服务。系统行为的描述被映射到一个术语,其参数指定所需的服务。在重写过程中,当组件被选择时,相应地绑定相应的提供的服务,并且可能引入新的服务。请记住,选择一个组件意味着该组件提供的系统规范中的所有服务都绑定到该组件,因为它们之前是未绑定的。为此,组件和适配器描述映射到重写规则。从适配器规范生成的规则将一个服务替换为另一个服务。因此,适配器可以被视为组件的特殊情况。因此,在下文中,如果我们谈论组件选择,我们同样意味着适配器选择。在下一步骤中执行相应适配器代码的生成例如,重新考虑我们运行示例中的以下术语车载系统(ΔATP、Δ立体声、ΔNavSys)该术语描述了一个系统规范,该规范规定需要三项服务:防盗保护、立体声和导航系统。每个必需的服务都被建模为根的参数,而参数的类型表示所需的服务,名称表示哪个组件(如果有的话)绑定到服务。特殊名称意味着服务仍将被绑定。组件的选择是通过应用重写规则来实现的,重写规则是根据组件规范自动生成的。组件C的规则,包括所需的服务请求(C)、所提供的服务提供(C)、约束116L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105constr(C)和属性props(C)在图5中描述(cost是给定的成本函数,建立在属性上)。规则由条件、匹配表达式、替换表达式、断言和成本函数构成。要使规则适用,必须满足其条件,并且其匹配表达式必须匹配所考虑的项。对于元件选择,条件声明元件的约束和当前系统约束一致。match表达式声明应该有一个未绑定的服务,该服务由所考虑的组件提供。如果选择并应用了适用的规则,则匹配的表达式将被替换表达式替换。在组件选择的情况下,构成系统行为的服务列表被修改。由所考虑的组件提供的未绑定服务被绑定到该组件。组件所需的服务将作为未绑定的服务添加,除非它们在以前的系统配置中已经绑定。最后,既不绑定也不在已提供服务列表中的服务所考虑的组件的值被简单地保留。这将产生一个新的服务列表(比较图5中的replace-expression)。然后,在应用规则之后,我们可以断言组件的约束和当前系统的约束是一致的。例5.1如果我们回想一下图1中的系统。2(i),该解决方案可以通过以下步骤实现:选择组分C1,选择组分C2。这由以下重写序列表示:系统拱=i386(ΔA,ΔB)→系统拱=i386(C1A,ΔB)→系统拱=i386(C1A,C 2B)另一方面,图2(ii)中的解决方案可以通过首先选择组件C3,然后选择组件C4(在选择适配器A1之后)来建立,其表示为序列:系统拱=i386(ΔA,ΔB)→系统拱=i386(C3A, C3B,ΔC)→系统拱=i386(C3A,C 3B,A 1C,ΔCJ)→系统arch=i386(C3A,C 3B,A 1C,C 4CJ)注意,第二重写步骤(将C改变为CJ)对应于适配器A1的选择,并且表明适配器被作为组件处理 ⬦由于所有重写步骤都有一定的成本,因此应首先考虑最佳选项(即成本最低的选项)。如果我们指定一个搜索引擎,我们可以优化搜索。 A* 搜索需要一个启发式函数,它估计从给定项到目标项的成本。请注意,函数必须始终低估实际成本,以保证A* 搜索的最优性。如果我们知道每项服务的成本至少为cmin,如下所示:从具有n个未绑定服务的给定项,预期成本为L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105117∗→−至少n cmin。虽然这种算法看起来很简单,但它在减少访问节点的数量图6详细说明了我们的组件选择算法。我们的搜索空间不仅包含术语,还包含注释了重写过程当前状态信息的术语,称为xterms。对于每个xtermt,我们有以下内容:• term(t):当前项• constr(t): 目前的制约因素• seq(t):到目前为止遇到的重写序列,每个步骤包括在位置p处应用规则r• estcost(t):术语的估计总成本(包含实际遇到的和估计的剩余成本)此外,我们有一个启发式函数heur:xtermR+,估计一个节点的剩余成本该算法的工作原理如下:我们保留一个当前活动的xterm列表。 在每个迭代步骤中,我们选择以下最小值(相对于成本函数):此列表,并将其替换为应用程序可以生成的所有后继程序重写规则。如果我们达到了一个目标术语,我们就结束,在这种情况下,我们报告成功,或者如果没有任何术语需要检查,这意味着失败。如果我们最终得到一个目标项,那么在循环中选择最小值就保证了我们找到了最优解。xtermt的后继的确定考虑了t的所有规则和所有位置,以找到可能的重写步骤。如果规则r在给定位置匹配p,并且如果规则的约束满足当前系统约束,则根据对于替换表达式,产生新的项TJ。此外,我们扩展了它的重写序列,它的约束条件,和它的估计成本。 由于我们只记得估计的成本,因此必须为此做一点计算:前面遇到的t的成本导致estcost(t)heur(t)。 因此,在节点tJ处,要获得实际成本,我们只需添加规则应用的成本。通过最后加上heur(tJ),我们得到了tJ的估计成本,正如我们在用[j]表示的行中看到的那样。在建立了组件选择的算法之后,下面我们将描述适配器代码的生成过程。5.2适配器代码生成在第一步中我们选择了组件和适配器(作为前者的特殊情况)之后,在第二步中,我们为所选的适配器生成代码。为此,我们需要适配器规范,该规范说明两个服务的接口如何表1)的说明。本说明书涵盖二进制有向映射。适配器规范可以通过通用规则重写到所需的目标平台。对于适配器的规范,我们需要一个关于通信118L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105→∗∗∗→→∧−∪/\n/∗∗funcselectSubscriptsAndAdaptors:(t:XTerm)→XTerm功能过滤器 (terms:XTerm list,newterms:XTerm list)XTerm list( 消除newterms中的冗余xterms(w.r.t. 术语)冗余意味着重写序列的模等价)funcresult(term:XTerm)ResultType(返回所需的结果。 这可以是生成代码的列表,或者(在组件选择的情况下)提供有关组件选择的所有信息的最终项。)funcgetNextTerms(t:XTerm)XTerm listnewTerms=[];对于所有规则r=(cond,match,replace,assert,cost)do对于term(t)的所有位置pdo如果t'=t;”modify term(t’) according to replace , add (p,r) toset estcost(add cond to constr(treturn new Treatment [t'];恩迪夫结束return newTerms;endfuncvarterms:XTerm列表;terms=[t]; selected=t;while(terms=[])and(not(goalTerm(selected)donewTerms= filter(getNextTerms(selected));terms=(terms [selected])newTerms;如果(terms=[]),则selected=selectMinimum terms;endifendwhileif(if)( 我们找到了最佳解决方案 )return result(selected);else return失败endfunc图六、元件选择算法L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105119组件之间的关系。 我们假设组件之间 通过消息交换。每个消息都有一个名称(或类型)和一些命名参数(即属性-值对列表)。如果两个服务在功能上是等效的,但本身不能互操作,则原因可能是以下原因之一• 相关消息具有不同的名称• 相关消息的参数具有不同的名称• 一个服务的n个消息可以映射到另一个服务的一个消息上• 相关论证的域是不同的在这些情况下,可以指定相应服务之间的映射。这种映射可以直接转换为实现。由于目前,适配器规范基本上由这种映射组成,因此可以轻松编写生成适配器代码的规则。只需为每个适配器设置一个固定的框架,并为每个映射生成if-then-statements。 目前,适配器规范必须手动开发。 然而,人们也可以考虑自动生成这些信息,通过考虑给定的组件并弄清楚它们如何互操作。6执行我们已经实现了我们的方法,用于构建基于ML中的术语重写的组件系统。ML由于其高阶功率而特别适合于此目的。在我们的实现中,一个高阶函数实现了generator生成器。给定可用组件的具体规格,它输出一个函数,给定所需的组件系统规格作为输入,输出一组实现所需目标系统的组件和适配器。术语通过通用数据类型表示。术语重写器从输入术语开始,计算所有可能的后继术语并将它们放入候选列表中。在接下来的时间里,最便宜的(w.r.t.先前成本和预期成本)候选从列表中移除并由其后继者替换这个过程一直持续到达到目标期限。系统规格由以下数据表给出数据类型消息=数据类型系统=Msgof Name*(Argumentlist)SystemSpecofServicelistdatatype Service=* 约束列表名称 * 消息列表* 成本函数的* HeurFunction组件和适配器由以下数据库描述(明确适配器是作为组件的特殊情况建模的数据类型组件=名称规范* 约束列表* ProvidedService列表* 服务列表* 属性列表数据类型适配器=名称的适配器规范* ProvidedService* 企业文化* MsgMapping列表映射指定如何将传入消息转换为要发送的消息。在转换中,可以对参数进行转换、重命名、120L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105组件o特许服务需服务成本GPS定位器防盗保护GPS传感器50CDman 100光碟播放器70公司简介导航GPS传感器80公司简介导航100公司简介导航,光盘播放器160GPS 10GPS传感器30表2汽车信息娱乐单元: 构件库消息可以被重命名,并且内部状态可以被更新。术语重写规则有以下起源:• 组件选择规则由组件规范生成。 对于每个组件,都会生成一个规则,并与所选内容相对应(如前一节中详细描述的• 适配器选择的规则也是从规范中生成的,作为组件选择的特殊情况• 适配器代码生成的规则仅取决于目标平台,并且必须手动指定。然而,一旦指定它们,就可以为给定的规范自动生成适配器代码启发函数的作用不可忽视。 作为一个例子,让我们考虑我们建模的第一个玩具示例,由4个服务和7个组件组成。 即使对于如此小的设置,搜索空间也包含174个节点。为了找到最佳的,25个节点被访问与不知情的搜索。如果使用我们前面解释的算法(假设组件选择的最小成本),则只访问了10个节点,但仍然产生相同的结果。7案例研究在本节中,我们将讨论我们的两个案例研究。我们首先回顾一下汽车系统介绍然后,我们提出了一个案例研究,我们已经在EJB(企业Java Bean)框架[4]中建模的软件组件系统假定有一个组件库,一个运行的系统已经从规范中创建出来(包括适配器)7.1汽车信息娱乐单元让我们重新考虑引言中的第一个例子。我们希望在汽车环境中选择组件。我们的系统应该包含以下功能:导航系统,cd播放器,汽车防盗保护。我们假设我们有某些组件可供使用,现在要选择最佳组合。表2概述了各组成部分。对于每个组件,都表示了操作和所需的服务。此外,还显示了相关的成本(例如价格)。考虑到我们的要求,最佳解决方案是组件选择GPS导航CDman 100、NAV-200、GPS 10,成本为230(注意,选择NAV-200和GPS导航中的任一个迫使选择提供以下功能的组件L. Gesellensetter,S.Glesner/Electronic Notes in Theoretical Computer Science 176(2007)105121规则第二:颜色=是,图形=否匹配:系统[服务]|用户界面服务cost:codesize=13assert:color=yes,graphic=noreplace: system[services\{ΔUserInterface}}组件提供的服务需服务约束成本文本输入UserInterfaceb/w,文本10文字输入颜色UserInterface颜色,文本13图形输入UserInterface颜色、图形100伊丽莎对话系统用户
下载后可阅读完整内容,剩余1页未读,立即下载
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 电力电子系统建模与控制入门
- SQL数据库基础入门:发展历程与关键概念
- DC/DC变换器动态建模与控制方法解析
- 市***专有云IaaS服务:云主机与数据库解决方案
- 紫鸟数据魔方:跨境电商选品神器,助力爆款打造
- 电力电子技术:DC-DC变换器动态模型与控制
- 视觉与实用并重:跨境电商产品开发的六重价值策略
- VB.NET三层架构下的数据库应用程序开发
- 跨境电商产品开发:关键词策略与用户痛点挖掘
- VC-MFC数据库编程技巧与实现
- 亚马逊新品开发策略:选品与市场研究
- 数据库基础知识:从数据到Visual FoxPro应用
- 计算机专业实习经验与项目总结
- Sparkle家族轻量级加密与哈希:提升IoT设备数据安全性
- SQL数据库期末考试精选题与答案解析
- H3C规模数据融合:技术探讨与应用案例解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)