The occur-check problem in Prolog

We present a method for preprocessing Prolog programs so that their operational semantics will be given by the first-order predicate calculus. Most Prolog implementations do not use a full unification algorithm, for efficiency reasons. The result is that it is possible to create terms having loops in them, whose semantics is not adequately described by first-order logic. Our method finds places where such loops may be created, and adds tests to detect them. This should not appreciably slow down the execution of most Prolog programs.     

L-A-S (Linear Algebra and System) language and its use in control system education and research

The paper describes a high level interactive conversational language L-A-S (Linear Algebra and Systems) used in analysis and design of linear control systems. The L-A-S language is written in FOR-TRAN-IV (DEC-PDP 10) but its use does not require the knowledge of standard programming languages. Modular structure of the language permits easy modification updating and extensions. The syntax and semantics are simple and straightforward so that familiarity with the language may be easily attained.     

Structured design,consistency analysis and failure reasoning of business workflows with activity-control templates and causal ordering

The design, analysis, control and diagnosis of business workflows have been major challenges for enterprise information system designers. We propose a structured framework for workflow design, formal semantics, consistency analysis, execution automation and failure reasoning targeting E-commerce applications. A business workflow is modeled by using a visual tool named activity-control (AC) diagram. Frequently occurring business procedures are captured by the adoptions of reusable AC templates. With formally defined semantics by a combination of first-order logic and happen-before causal ordering in distributed system theory, workflow consistency can be mechanically analyzed at design time while failure reasoning can be applied at execution time for problem diagnosis. A completely specified model is automatically converted to a workflow by an iterative traversal algorithm that maps an AC diagram to an XML workflow specification which can then be executed automatically by an XML workflow engine. A failure reasoning and diagnosis algorithm is devised to find all possible causes of a failed execution when problems occur. Preliminary proof-of-concept implementation and evaluation results demonstrate the feasibility and effectiveness of our framework and techniques.     

一种基于反馈控制的Web服务组合执行引擎设计

在Web服务组合执行引擎中解耦流程执行和成分Web服务调用,设计和实施了带有双控制反馈控制环的流程执行结构,反馈控制环分别位于流程执行器与服务代理之上。仿真结果表明：解耦流程执行和成分Web服务调用提高了引擎资源的使用效率,增加了流程执行的并发性,提高了引擎的吞吐量;引入QoS反馈控制结构,使得引擎在组合服务负荷变化时,可为不同的请求服务等级提供服务响应时间保障。     

Designing a BPEL Orchestration Engine Based on ReSpecT Tuple Centres

We present the design of a BPEL orchestration engine based on ReSpecT tuple centres, a coordination model extending Linda with the ability of declaratively programming the reactive behaviour of tuple spaces. Architectural and linguistic aspects of our solution are discussed, focussing on how the syntax and semantics of BPEL have been mapped to tuple centres. This is achieved by a translation of BPEL specifications to set of logic tuples, and conceiving the execution cycle of the orchestration engine in terms of ReSpecT reactions.     

Unraveling Iterative Control Structures from Business Processes

Iterative control structures allow the repeated execution of tasks,activities or sub-processes according to the given conditions in a process model.Iterative control structures can significantly increase the risk of triggering temporal exceptions since activities within the scope of these control structures could be repeatedly executed until a predefined condition is met.In this paper,we propose two approaches to unravel iterative control structures from process models.The first approach unravels loops based on zero-one principle.The second approach unravels loops based on branching probabilities assigned at split gateways.The proposed methods can be used to unfold structured loops,nested loops and crossing loops.Since the unfolded model does not contain any iterative control structures,it can be used for further analysis by process designers during the modeling phase.The proposed methods are implemented based on workflow graphs,and therefore they are compatible with modeling languages such as Business Process Modelling Notation(BPMN).In the experiments,the execution behavior of unfolded process models is compared against the original models based on the concept of runs.Experimental results reveal that runs generated from the original models can be correctly executed in the unfolded BPMN models that do not contain any loops.     

A logic programming language based on the Andorra model

The Andorra model is a parallel execution model of logic programs which exploits the dependent and-parallelism and or-parallelism inherent in logic programming. We present a flat subset of a language based on the Andorra model, henceforth called Andorra Prolog, that is intended to subsume both Prolog and the committed choice languages. Flat Andorra, in addition todon’t know anddon’t care nondeterminism, supports control of or-parallel split, synchronisation on variables, and selection of clauses. We show the operational semantics of the language, and its applicability in the domain of committed choice languages. As an examples of the expressiveness of the language, we describe a method for communication between objects by time-stamped messages, which is suitable for expressing distributed discrete event simulation applications. This method depends critically on the ability to expressdon’t know nondeterminism and thus cannot easily be expressed in a committed choice language.     

Synthesizing structured analysis and object‐based formal specifications

Structured Analysis (SA) is a widely‐used software development method. SA specifications are based on Data Flow Diagrams (DFD's), Data Dictionaries (DD's) and Process Specifications (P‐Specs). As used in practice, SA specifications are not formal. Seemingly orthogonal approaches to specifications are those using formal, object‐based, abstract model specification languages, e.g., VDM, Z, Larch/C++ and SPECS. These languages support object‐based software development in that they are designed to specify abstract data types (ADT's). We suggest formalizing SA specifications by: (i) formally specifying flow value types as ADT's in DD's, (ii) formally specifying P‐Specs using both the assertional style of the aforementioned specification languages and ADT operations defined in DD's, and (iii) adopting a formal semantics for DFD “execution steps”. The resulting formalized SA specifications, DFD‐SPECS, are well‐suited to the specification of distributed or concurrent systems. We provide an example DFD‐SPEC for a client‐server system with a replicated server. When synthesized with our recent results in the direct execution of formal, model‐based specifications, DFD‐SPECS will also support the direct execution of specifications of concurrent or distributed systems.     

Coordination for fragmented loops and scopes in a distributed business process

As partner relationships become more dynamic and global boundaries give way to a more agile and dynamic environment, the ability to distribute one's processes in an agile manner becomes increasingly important. Such processes may need to be split not only along their explicit dependencies but also along more complex behavior such as recovery behavior and loops. The resulting process fragments can be distributed and wired together, recreating the execution semantics of the original process model. In earlier work, we presented BPEL fragmentation covering data and explicit control dependencies. We now extend the approach to handle fragmenting loops and scopes. Maintaining the focus on standards and maximizing extensibility of Web service runtimes and standards, the solution defines and uses two new coordination protocols that plug into the WS-Coordination framework. The approach uses the standards as much as is feasible and addresses the remaining required functionality by providing architected extensions. This results in layered approach that maximizes transparency and interoperability. After defining the fragmentation approach for scopes and loops, an implementation is presented that extends the Active Endpoints BPEL engine and a WS-Coordination system. A detailed example is used to illustrate how the protocols are used at runtime to enable the coordinator and the process fragments to recreate the behavior of the original, unsplit process model.     

基于BPMN的服务组合执行引擎的研究与实现*

业务模型和执行模型的一致性是当前服务组合研究的一个难点和热点。目前普遍采用模型转换的方式将业务模型映射为可执行模型,但由于两种模型语言的语义和语法不一致,导致了模型转换存在语义失配等缺陷。针对该问题,提出了一种基于业务流程建模标注的Web服务组合执行方案,设计了BPMN模型的解释执行算法,给出了执行引擎的原型系统,并通过具体案例验证了方案的有效性。     

Hierarchies of modal and temporal logics with reference pointers

We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions.     

Stack method in program semantics

In this paper,we describe firstly a formal concept of stack and introduce some operational rules on it.Then we extend the denotational semantics to“the denotational semantics with stacks”,by which we makea formal semantics for a real PASCAL(subset)which can run on a computer.By an example of programwith procedures it will be seen that our method can be used to describe the basic principles of compiling.Finally,we have succeeded in building a formal semantics model of a PROLOG(subset).     

Development and implementation of clinical guidelines: An artificial intelligence perspective

Clinical practice guidelines in paper format are still the preferred form of delivery of medical knowledge and recommendations to healthcare professionals. Their current support and development process have well identified limitations to which the healthcare community has been continuously searching solutions. Artificial intelligence may create the conditions and provide the tools to address many, if not all, of these limitations.. This paper presents a comprehensive and up to date review of computer-interpretable guideline approaches, namely Arden Syntax, GLIF, PROforma, Asbru, GLARE and SAGE. It also provides an assessment of how well these approaches respond to the challenges posed by paper-based guidelines and addresses topics of Artificial intelligence that could provide a solution to the shortcomings of clinical guidelines. Among the topics addressed by this paper are expert systems, case-based reasoning, medical ontologies and reasoning under uncertainty, with a special focus on methodologies for assessing quality of information when managing incomplete information. Finally, an analysis is made of the fundamental requirements of a guideline model and the importance that standard terminologies and models for clinical data have in the semantic and syntactic interoperability between a guideline execution engine and the software tools used in clinical settings. It is also proposed a line of research that includes the development of an ontology for clinical practice guidelines and a decision model for a guideline-based expert system that manages non-compliance with clinical guidelines and uncertainty.     

Abstract Interpretation for Termination Analysis in Functional Active Databases

An active database consists of a traditional database supplemented by a set of Event-Condition-Action (ECA) rules. One of the key questions for active database designers is that of termination of the ECA rules. The behaviour of the ECA rules may be obscure and their semantics is often not specified formally. Consequently, developing termination analysis algorithms and proving their correctness is a challenging task. In this paper we address this problem for functional active databases by adopting an abstract interpretation approach. By functional active databases we mean active databases whose transaction execution semantics have been expressed in a purely functional language. Although we demonstrate our techniques for a specific active DBMS which supports a functional database programming language interface, these techniques are directly applicable to other active DBMSs whose execution semantics have been specified using a functional or a denotational approach.     

基于XML的UML模型向AADL模型的自动转换

UML已经成为复杂系统建模的工业标准,并可借助代码自动生成工具实现从分析到编码的开发过程自动化;AADL具有精确的语义和严格的语法规范,可用于描述嵌入式实时系统的软、硬件体系结构,并能分析系统的功能及非功能属性。 UML和AADL模型的基本元对象有相互对应关系,并且两种模型的表示都能够采用标准的XML的交换格式。为充分发挥两种语言的优势,文中研究了UML模型向AADL模型的自动转换,以XML为媒介实现两种模型的元对象的对应转换,最终达到两种模型的转换,使用户在设计阶段能够结合运用AADL、UML工具的优点对系统进行分析。     

Generic semantics of feature diagrams

Feature Diagrams (FDs) are a family of popular modelling languages used to address the feature interaction problem, particularly in software product lines, FDs were first introduced by Kang as part of the FODA (Feature-Oriented Domain Analysis) method back in 1990. Afterwards, various extensions of FODA FDs were introduced to compensate for a purported ambiguity and lack of precision and expressiveness. However, they never received a formal semantics, which is the hallmark of precision and unambiguity and a prerequisite for efficient and safe tool automation.The reported work is intended to contribute a more rigorous approach to the definition, understanding, evaluation, selection and implementation of FD languages. First, we provide a survey of FD variants. Then, we give them a formal semantics, thanks to a generic construction that we call Free Feature Diagrams (FFDs). This demonstrates that FDs can be precise and unambiguous. This also defines their expressiveness. Many variants are expressively complete, and thus the endless quest for extensions actually cannot be justified by expressiveness. A finer notion is thus needed to compare these expressively complete languages. Two solutions are well-established: succinctness and embeddability, that express the naturalness of a language. We show that the expressively complete FDs fall into two succinctness classes, of which we of course recommend the most succinct. Among the succinct expressively complete languages, we suggest a new, simple one that is not harmfully redundant: Varied FD (VFD). Finally, we study the execution time that tools will need to solve useful problems in these languages.     

Sequential Prolog machine PEK

The sequential Prolog machine PEK currently under development is described. PEK is an experimental machine designed for high speed execution of Prolog programs. The PEK machine is controlled by horizontal-type microinstructions. The machine includes bit slice microprocessor elements comprising a microprogram sequencer and ALU, and possesses hardware circuits for unification and backtracking. The PEK machine consists of a host processor (MC68000) and a backend processor (PEK engine). A Prolog interpreter has been developed on the machine and the machine performance evaluated. A single inference can be executed in 89 microinstructions, and execution speed is approximately 60–70 KLIPS.     

On implementing Prolog in functional programming

This report surveys techniques for implementing the programming language Prolog. It focuses on explaining the procedural semantics of the language in terms of functional programming constructs. The techniquessuccess continuations andproof streams are introduced, and it is shown how Horn clause interpreters can be built upon them. Continuations are well known from denotational semantics theory, in this paper it is shown that they are viable constructs in actual programs. Other issues include implementation of logical variables, structure sharing vs. structure copying, determinacy, builtin predicates, andcut.