并发约束程序设计语言COPS及其执行模型

约束程序设计尤其是约束逻辑程序设计与并发约束程序设计在AI程序设计领域占据着越来越重要的位置。传统逻辑程序设计的基“计算即为定理证明”的计算风格虽获得了简洁优美的操作语义特性,但也付出了执行效率低的代价,当应用系统规模增大时,其性能严重下降以致崩溃。针对传统逻辑程序设计的这种可伸缩性问题,设计了一个基于并发约束程序设计概念的说明性语言COPS,旨在从语言设计与执行模型两方面降低说明性程序的不确定性,提高搜索与运行效率。在语言设计方面,通过引入确定性语言成分,避免不确定计算用于确定性目标所浪费的系统开销;在执行模型方面,在目标的并发穿叉执行与数据驱动的并发同步机制的基础上,实现“优先执行确定目标”策略与“最少假定”策略,作为约束传播的延伸,最大幅度地剪枝搜索空间,降低搜索复杂性。COPS提供的知识表示、推理与并发机制使其成为构造agent程序的理想语言。论文给出COPS语言的语法规范与执行模型的操作语义描述。     

面向对象、泛型程序设计与类型约束检查

该文对面向对象和泛型程序设计(generic programming)的核心思想和方法进行了较为深入的分析．阐明了各自的目标、技术特征及其优缺点所在．介绍了泛型程序设计针对对象技术的不足所引进的重大革新，即通过类型需求抽象来设计通用、高效的数据结构和算法；着重论述了作者在进一步增强泛型程序设计实际运用方面所提出的改进工作．以C 语言的一个泛型编程扩充语言C**为实施例，详细说明了如何通过一种叫做“命名类型约束”的新的机制来比较完整地实现静态类型需求的直接语言支持和编译检查，为当前泛型程序设计模型的首例编程语言实例．     

基于扩展SysML活动图的嵌入式系统设计安全性验证方法研究

能源、交通等领域中复杂嵌入式系统设计的安全性分析与验证工作已经成为当前的重要研究热点之一;本文提出一种结合MARTE语义信息的扩展Sys ML活动图模型,用于描述安全关键应用中的嵌入式系统动态行为的设计,并对此扩展模型展开基于模型转换的系统设计安全性特征的形式化分析与验证方法的研究;包括:构建了Sys ML活动图与MARTE中非功能性质建模语义相结合的元模型,以及验证工具UPPAAL的时间自动机元模型,并且给出了二者之间的语义映射规则;建立了从时间自动机模型描述到UPPAAL工具输入格式之间的语法转换方法;设计了一个基于AMMA平台的面向扩展Sys ML活动图的模型转换与验证框架;最后,给出了一个高铁控制系统设计模型的安全性验证的实例分析.     

基于关键迹和ASP的CSP模型检测

模型检测是通信顺序进程(communicating sequential processes,简称CSP)形式化验证的重要手段.当前, CSP模型检测方法基于操作语义,需将进程转化为迁移系统,进而提取语义模型,但转化过程较为复杂;待验证性质采用CSP语言进行描述,虽然有利于精炼检测(refinement checking),但描述能力较弱,通用性不强.鉴于此,提出了一种新的CSP指称语义模型——关键迹模型(critical-trace model)及基于该指称语义模型的CSP模型检测方法,并证明了其验证的可靠性,避免了上述问题.关键迹模型采用递归策略计算,待验证性质采用线性时态逻辑(linear temporal logic,简称LTL)描述.基于回答集程序设计(answer set programming,简称ASP)实现了关键迹模型的自动生成及LTL的自动验证,并开发了一个CSP模型检测原型系统——T_ASP.实验结果表明:与类似系统相比,该系统的描述能力更强,验证结果的准确性更高,且可同时验证多条性质,在性质不满足时还可提供多条反例.     

动态约束下的联盟形成

联盟形成是多Agent系统中一种重要的合作方式。人们设计了一系列联盟形成框架,较好地解决了联盟值最大化、任务分配、组合拍卖等问题。已有关于联盟形成的研究,较多地从效用、任务等角度来考虑问题。在一些情况下,仅从这些角度考虑联盟形成是不够的,于是我们从约束的角度来研究联盟形成。首先深刻分析了联盟形成时的约束问题,采用命题逻辑来描述对Agent的约束,给出了联盟偏好语言及其语义描述;接着给出了它的一些性质;最后将动态约束下的联盟形成机制与常见的一些联盟形成机制作了对比,体现了动态约束下联盟形成机制的特点。     

基于Time Petri Net的实时系统冲撞检测与消解

time Petri net(TPN)在实时控制系统的建模中得到广泛应用,而冲撞是Petri网及其扩展模型的重要行为,解决冲撞是正确分析模型动态行为的关键.由于引入时间约束,使得TPN模型的使能和触发语义比Petri网模型的语义复杂,冲撞的检测及消解变得更加困难.首先根据时间约束,给出了变迁持续使能时延迟区间的计算方法,并证明了该方法的正确性;然后在此基础上定义并证明了TPN模型中冲撞的检测方法;给出了冲撞时间区间及修改时间约束的冲撞消解方法;最后通过实例验证说明了该方法的有效性和正确性.     

基于组织的面向Agent 程序设计及其语言Oragent

当前,面向Agent程序设计在支持动态开放多Agent系统开发方面存在一系列的不足,如缺乏高层抽象、底层实现模型与高层设计模型相脱节、在支持系统动态性方面缺乏有效的运行机制和语言设施等.针对这些问题,提出一种基于组织的面向Agent程序设计方法.该方法将组织、Group、角色和Agent等高层抽象作为一阶实体,缩小了多Agent系统的设计模型与实现模型之间的概念鸿沟;借助于组织学中的机制——角色扮演机制、基于角色的交互——支持系统动态性的规约和实现,如Agent行为的动态组合、动态的交互等,基于该程序设计思想,设计了基于组织的面向Agent程序设计语言——Oragent,定义了其抽象语法和形式语义,并通过案例分析说明了如何基于该程序设计思想和Oragent语言来构造和实现动态而灵活的多Agent系统.     

基于XYZ/E的混成系统

混成系统是由计算机和物理设备组成的嵌入式实时计算系统.它允许在交互式实时系统中引入连续变化的单元.XYZ/E 是基于Manna-Pnueli的线性时序逻辑的程序设计语言.它将程序的动态语义与静态语义统一在同一框架中,支持从抽象的程序规范到可执行代码的逐步求精的全过程.该文使用XYZ/E语言描述和验证混成系统.首先介绍了计算模型,然后介绍了XYZ语言对混成系统的形式化描述,最后介绍了混成系统的验证.与同类工作相比,XYZ/E支持状态转换,从而可以方便地描述复杂的控制算法.     

基于OCL的服务构件特征语义描述模型

构件的语义特征是构件检索的主要依据,也是构件库的重点研究内容.然而,由于网络系统中存在分布、动态、数量众多的服务构件,很多构件之间存在一定的关联和依赖,因此如何有效地描述这些服务构件特征间的关联,是构件库管理模型需要进一步研究的一个重要问题.提出一种基于特征的构件语义描述模型,首先分别给出特征、特征空间和构件特征空间表示模型的定义.接着将构件特征间的各种关联和依赖关系分成自身约束、父子关系约束、显性约束和隐性约束4类,并采用对象约束语言对这些关系进行形式化描述,从而为模型提供了精确的语义支持.面向电子商务的构件特征子树的实例研究及其模型验证和实验结果证明了该模型的正确性与有效性.     

Generic Programming and High-Performance Libraries

Generic programming is an especially attractive paradigm for developing libraries for high-performance computing because it simultaneously emphasizes generality and efficiency. In the generic programming approach, interfaces are based on sets of specified requirements on types, rather than on any particular types, allowing algorithms to inter-operate with any data types meeting the necessary requirements. These sets of requirements, known as concepts, can specify syntactic as well as semantic requirements. Besides providing a powerful means of describing interfaces to maximize software reuse, concepts provide a uniform mechanism for more closely coupling libraries with compilers and for effecting domain-specific library-based compiler extensions. To realize this goal however, programming languages and their associated tools must support concepts as first-class constructs. In this paper we advocate better syntactic and semantic support to make concepts first-class and present results demonstrating the kinds of improvements that are possible with static checking, compiler optimization, and algorithm correctness proofs for generic libraries based on concepts.     

Efficient run-time dispatching in generic programming with minimal code bloat

Generic programming with C++ templates results in efficient but inflexible code: efficient, because the exact types of inputs to generic functions are known at compile time; inflexible because they must be known at compile time. We show how to achieve run-time polymorphism without compromising performance by instantiating the generic algorithm with a comprehensive set of possible parameter types, and choosing the appropriate instantiation at run time. Applying this approach naïvely can result in excessive template bloat: a large number of template instantiations, many of which are identical at the assembly level. We show practical examples of this approach quickly approaching the limits of the compiler. Consequently, we combine this method of run-time polymorphism for generic programming, with a strategy for reducing the number of necessary template instantiations. We report on using our approach in GIL, Adobe’s open source Generic Image Library. We observed a notable reduction, up to 70% at times, in executable sizes of our test programs. This was the case even with compilers that perform aggressive template hoisting at the compiler level, due to significantly smaller dispatching code. The framework draws from both the generic and generative programming paradigms, using static metaprogramming to fine tune the compilation of a generic library. Our test bed, GIL, is deployed in a real world industrial setting, where code size is often an important factor.     

基于原语的通用起源过滤框架

现有起源过滤机制的通用性差,一个过滤机制仅能过滤某一特定类型的敏感元素,处理包含多种类型敏感元素的综合性起源过滤需求仍然非常困难,为此提出了一种基于原语的通用起源过滤框架。首先,介绍了起源过滤涉及的敏感元素类型以及过滤约束;其次,深入分析已有过滤机制改造起源图的基本操作和过程,形式地定义了一系列起源过滤原语,描述针对起源图的最小改造操作,将起源过滤过程划分为隐藏敏感元素、恢复有用依赖和验证过滤约束三个阶段,提出了一种基于原语组装的分阶段过滤策略空间构造方法;最后设计并实现了基于原语的通用过滤算法,并在公开数据集上验证了该算法的可行性。     

Basic concepts and taxonomy of dependable and secure computing

This paper gives the main definitions relating to dependability, a generic concept including a special case of such attributes as reliability, availability, safety, integrity, maintainability, etc. Security brings in concerns for confidentiality, in addition to availability and integrity. Basic definitions are given first. They are then commented upon, and supplemented by additional definitions, which address the threats to dependability and security (faults, errors, failures), their attributes, and the means for their achievement (fault prevention, fault tolerance, fault removal, fault forecasting). The aim is to explicate a set of general concepts, of relevance across a wide range of situations and, therefore, helping communication and cooperation among a number of scientific and technical communities, including ones that are concentrating on particular types of system, of system failures, or of causes of system failures.     

基于马尔可夫模型的可信性评估研究

研究了安全关键实时系统传统的高可信保障机制,提出了一种可支持多级关键度的新可信性保障机制。使用该机制则可根据各子系统的实际可信性需求采用相应的冗余数进行容错处理。为评估该可信性保障机制,改进了传统的多模型可信性评估方法。基于马尔可夫模型,文章建立了一种统一的可信性评估模型,使用该模型则可按不同关键度子系统的实际可信性需求进行独立的评估。同时,该文使用了大量的实例进行例证。     

基于O''Caml语言的通用编程技术

O’Caml语言是一门优秀的函数式程序语言,具有计算模型简单、语法语义描述清晰等特点,而通用编程技术方法通过高度抽象算法、数据结构及其他软件组件可以避免功能相似代码的重复编写。针对如何将通用编程技术方法和O’Caml语言相结合来提高O’Caml程序复用程度的问题,通过对O’Caml语言语法进行扩展引入类型标记1函数,然后运用类型结构化转换和类型映射机制,实现通用函数,从而达到在O’Caml语言中引入通用编程技术的目的。实例结果表明,在O’Caml语言中实现通用编程技术,有效提高了编程效率和程序的通用性。     

泛型程序设计的研究

泛型程序设计将类型安全的任务从程序员转移给编译器,不再需要程序员编写代码来检测数据类型是否正确,而是在编译时由编译器强制使用正确的数据类型。因此,采用泛型程序设计可以减少类型强制转换的需要和运行时出现错误的可能性。     

A type system for reflective program generators

We describe a type system for a generative mechanism that generalizes the concept of generic types by combining it with a controlled form of reflection. This mechanism makes many code generation tasks possible for which generic types alone would be insufficient. The power of code generation features are carefully balanced with their safety, which enables us to perform static type checks on generator code. This leads to a generalized notion of type safety for generators.     

STL中Generic算法的扩展

Generic程序设计是实现软件重用的重要方法之一，文章介绍了generic程序设计与C＋＋标准模板库（STL），探讨了STL中generic算法的扩展方法。