Toward a programming theory for rational agents

An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish that an agent programming language is both conceptually well-founded and well-behaved, as well as yield a way to reason about agent programs by means of agent logics. As a step toward bridging this gap, we study several issues that need to be resolved in order to establish a precise mathematical relation between a modal agent logic and an agent programming language specified by means of an operational semantics. In this paper, we present an agent programming theory that provides both an agent programming language as well as a corresponding agent verification logic to verify agent programs. The theory is developed in stages to show, first, how a modal semantics can be grounded in a state-based semantics, and, second, how denotational semantics can be used to define the mathematical relation connecting the logic and agent programming language. Additionally, it is shown how to integrate declarative goals and add precompiled plans to the programming theory. In particular, we discuss the use of the concept of higher-order goals in our theory. Other issues such as a complete axiomatization and the complexity of decision procedures for the verification logic are not the focus of this paper and remain for future investigation. Part of this research was carried out while the first author was affiliated with the Nijmegen Institute for Cognition and Information, Radboud University Nijmegen.     

Reasoning about plan revision in BDI agent programs

Facilities for handling plan execution failures are essential for agents which must cope with the effects of nondeterministic actions, and some form of failure handling can be found in most mature agent programming languages and platforms. While such features simplify the development of more robust agents, they make it hard to reason about the execution of agent programs, e.g., to verify their correctness. In this paper, we present an approach to the verification of agent programs which admit exceptional executions. We consider executions of the BDI-based agent programming language 3APL in which plans containing non-executable actions can be revised using plan revision rules, and present a logic for reasoning about normal and exceptional executions of 3APL programs. We provide a complete axiomatization for the logic and, using a simple example, show how to express properties of 3APL programs as formulas of the logic.     

On the automated translational execution of the action language for foundational UML

To manage the rapidly growing complexity of software development, abstraction and automation have been recognised as powerful means. Among the techniques pushing for them, model-driven engineering has gained increasing attention from industry for, among others, the possibility to automatically generate code from models. To generate fully executable code, models should describe complex behaviours. While pragmatically this is achieved by employing programming languages for defining actions within models, the abstraction gap between modelling and programming languages can undermine consistency between models and code as well as analysability and reusability of models. In light of this, model-aware action languages should be preferred. This is the case of the Action Language for Foundational UML (ALF). In this paper, we provide a solution for the fully automated translational execution of ALF towards C++. Additionally, we give an insight on how to simplify the transition from the use of programming languages for modelling fine-grained behaviours to model-aware action languages in industrial MDE. The solution presented in this paper has been assessed on industrial applications to verify its applicability to complex systems as well as its scalability.     

Scaling up visual programming languages

The directness, immediacy, and simplicity of visual programming languages are appealing. The question is, can VPLs be effectively applied to large scale programming problems while retaining these characteristics. In scaling up, the problem is how to expand applicability without sacrificing the goals of better logic expression and understanding. From a size standpoint, scaling up refers to the programmer's ability to apply VPLs in larger programs. Such programs range from those requiring several days' work by a single programmer to programs requiring months of work, large programming teams, and large data structures. From a problem domain standpoint, scaling up refers to suitability for many kinds of problems. These range from visual application domains-such as user interface design or scientific visualization-to general purpose programming in such diverse areas as financial planning, simulations, and real time applications with explicit timing requirements. To illustrate the scaling up problem, we discuss nine major subproblems and describe emerging solutions from existing VPL systems. First, we examine representation issues, including static representation, screen real estate, and documentation. Next, we examine programming language issues-procedural abstraction, interactive visual data abstraction, type checking, persistence, and efficiency. Finally, we look at issues beyond the coding process     

AN ACL FOR SPECIFYING FAULT-TOLERANT PROTOCOLS

Agent communication languages (ACLs) should allow the developer to adopt human-like communication mechanisms in agent programming, facilitating the development of distributed protocols in multi-agent systems (MASs). However, to implement robust protocols, ACLs should provide a way to deal with the failures of agents, as MASs are prone to the same failures that can occur in any distributed software system. In this paper, we address this issue showing how an asynchronous ACL that provides high-level mechanisms to deal with crash failures of agents can be effectively used to specify fault tolerant protocols.     

Formal verification of concurrent programs using the Larch prover

The paper describes the use of the Larch prover to verify concurrent programs. The chosen specification environment is UNITY, whose proposed model can be fruitfully applied to a wide variety of problems and modified or extended for special purposes. Moreover, UNITY provides a high level of abstraction to express solutions to parallel programming problems. We investigate how the UNITY methodology can be mechanized within a general purpose first order logic theorem prover like LP, and how we can use the theorem proving methodology to prove safety and liveness properties. Then we describe the formalization and the verification of a communication protocol over faulty channels, using the Larch prover LP. We present the full computer checked proof, and we show that a theorem prover can be used to detect flaws in a system specification     

Temporal Development Methods for Agent-Based

In this paper we overview one specific approach to the formal development of multi-agent systems. This approach is based on the use of temporal logics to represent both the behaviour of individual agents, and the macro-level behaviour of multi-agent systems. We describe how formal specification, verification and refinement can all be developed using this temporal basis, and how implementation can be achieved by directly executing these formal representations. We also show how the basic framework can be extended in various ways to handle the representation and implementation of agents capable of more complex deliberation and reasoning.This revised version was published online in August 2005 with a corrected cover date.     

Data abstraction in Modula-2

Data abstraction is one of the most fundamental principles of software engineering. The increasing realization of this is reflected in the design of programming languages, from the tentative user-defined data types of Pascal through to the more extensive facilities provided today by languages such as Ada and Modula-2.This tutorial paper examines how the data abstraction facilities provided by Modula-2 can be used in a sophisticated application. We demonstrate that data abstraction facilitates the production of code which is highly modularized, is easy to write and easy to read. The application, garbage collection, is an important part of system software, and is particularly interesting because it highlights the conflict between efficiency and expressive power. We show the extent to which a functional style of programming can be utilized in solving a problem which is inherently concerned with ‘state’, and we also show how formal semantics can be provided for the abstract data types.     

Using FP as a query language for relational data-bases

FP is the programming language defined by J. Backus to demonstrate the virtues of functional programming as opposed to conventional programming in Von Neumann-like languages.In this paper we investigate the use of FP in the framework of relational data bases. In particular, we show how the language can be used to define base relations, to derive views from a collection of relations, and to express complex database queries.The language provides all capabilities of pure algebraic relational languages, but is considerably more powerful. As such, it can be used as a formal specification language to describe the semantics of queries expressed in relational languages, such as Query-By-Example. In addition the algebra of FP programs allows one to formally prove properties of such queries.     

Relational Program Reasoning Using Compiler IR

Relational program reasoning is concerned with formally comparing pairs of executions of programs. Prominent examples of relational reasoning are program equivalence checking (which considers executions from different programs) and detecting illicit information flow (which considers two executions of the same program). The abstract logical foundations of relational reasoning are, by now, sufficiently well understood. In this paper, we address some of the challenges that remain to make the reasoning practicable. Two major ones are dealing with the feature richness of programming languages such as C and with the weakly structured control flow that many real-world programs exhibit. A popular approach to control this complexity is to define the analyses on the level of an intermediate program representation (IR) such as one generated by modern compilers. In this paper we describe the ideas and insights behind IR-based relational verification. We present a program equivalence checker for C programs that operates on LLVM IR. To extend the reach of the approach and to make it more efficient, we show how dynamic analyses can be employed to support and strengthen the static verification. The effectiveness of the approach is demonstrated by automatically verifying equivalence of functions from different implementations of the standard C library.     

Abstraction for model checking multi-agent systems

Model checking multi-agent systems (MAS) always suffers from the state explosion problem. In this paper we focus on an abstraction technique which is one of the major methods for overcoming this problem. For a multi-agent system, we present a novel abstraction procedure which reduces the state space by collapsing the global states in the system. The abstraction is automatically computed according to the property to be verified. The resulting abstract system simulates the concrete system, while the universal temporal epistemic properties are preserved. Our abstraction is an overapproximation. If some universal temporal epistemic property is not satisfied, then we need to identify spurious counterexamples. We further show how to reduce complex counterexamples to simple structures, i.e., paths and loops, such that the counterexamples can be checked and the abstraction can be refined efficiently. Finally, we illustrate the abstraction technique with a card game.     

An Introduction to the Construction and Verification of Alphard Programs

The programming language Alphard is designed to provide support for both the methodologies of "well-structured" programming and the techniques of formal program verification. Language constructs allow a programmer to isolate an abstraction, specifying its behavior publicly while localizing knowledge about its implementation. The verification of such an abstraction consists of showing that its implementation behaves in accordance with its public specifications; the abstraction can then be used with confidence in constructing other programs, and the verification of that use employs only the public specifications.     

Aspects as Modular Language Extensions

Extensible programming languages and their compilers use highly modular specifications of languages and language extensions that allow a variety of different language feature sets to be easily imported into the programming environment by the programmer. Our model of extensible languages is based on higher-order attribute grammars and an extension called “forwarding” that mimics a simple rewriting process. It is designed so that no additional attribute definitions need to be written when combining a language with language extensions. Thus, programmers can remain unaware of the underlying attribute grammars when building customized languages by importing various extensions. In this paper we show how aspects and the aspect weaving process from Aspect-Oriented Programming can be specified as a modular language extension and imported into a base language specified in an extensible programming language framework.     

The Branching-Time Transformation Technique for Chain Datalog Programs

The branching-time transformation technique has proven to be an efficient approach for implementing functional programming languages. In this paper we demonstrate that such a technique can also be defined for logic programming languages. More specifically, we first introduce Branching Datalog, a language that can be considered as the basis for branching-temporal deductive databases. We then present a transformation algorithm from Chain Datalog programs to the class of unary Branching Datalog programs with at most one IDB atom in the body of each clause. In this way, we obtain a novel implementation approach for Chain Datalog, shedding at the same time new light on the power of branching-time logic programming.     

StreamPI: a stream-parallel programming extension for object-oriented programming languages

Because multicore CPUs have become the standard with all major hardware manufacturers, it becomes increasingly important for programming languages to provide programming abstractions that can be mapped effectively onto parallel architectures. Stream processing is a programming paradigm where computations are expressed as independent actors that communicate via FIFO data-channels. The coarse-grained parallelism exposed in stream programs facilitates such an efficient mapping of actors onto the underlying multicore hardware. We propose a stream-parallel programming abstraction that extends object-oriented languages with stream-programming facilities. StreamPI consists of a class hierarchy for actor-specification together with a language-independent runtime system that supports the execution of stream programs on multicore architectures. We show that the language-specific part of StreamPI, i.e., the class hierarchy, can be implemented as a library-level programming language extension. A library-level extension has the advantage that an existing programming language implementation need not be touched. Legacy-code can be mixed with a stream-parallel application, and the use of sequential legacy code with actors is supported. Unlike previous approaches, StreamPI allows dynamic creation and subsequent execution of stream programs. StreamPI actors are typed. Type-safety is achieved through type-checks at stream graph creation time. We have implemented StreamPI??s language-independent runtime system and language interfaces for Ada?2005 and C++ for Intel multicore architectures. We have evaluated StreamPI for up to 16 cores on a two?CPU 8-core Intel Xeon X7560 server, and we provide a performance comparison with StreamIt?(Gordon et al. in International Conference on Architectural Support for Programming Languages and Operating Systems, 2006), which is the de facto standard for stream-parallel programming. Although our approach provides greater programming flexibility than StreamIt, the performance of StreamPI compares favorably to the static compilation model of StreamIt.     

Ambient contracts: verifying and enforcing ambient object compositions à la carte

Current programming languages do not offer adequate abstractions to discover and compose heterogenous objects over unreliable networks. This forces programmers to discover objects one by one, compose them manually, and keep track of their individual connectivity state at all times. In this paper we propose Ambient Contracts, a novel programming abstraction to deal with the difficulties of composing objects connected over unreliable networks. Ambient Contracts provide declarative heterogenous group discovery and composition while dealing with the unreliability of the network. An ambient contract allows runtime verification and enforcement of the messages sent between the participants in the contract. The use of our abstraction significantly reduces the code base and allows programmers to focus on the core functionality of their application. Our claims are reinforced by comparing the implementation of an example scenario in our contracts with a Java implementation using M2MI.     

Telescoping Languages: A Strategy for Automatic Generation of Scientific Problem-Solving Systems from Annotated Libraries

As machines and programs have become more complex, the process of programming applications that can exploit the power of high-performance systems has become more difficult and correspondingly more labor-intensive. This has substantially widened the software gap—the discrepancy between the need for new software and the aggregate capacity of the workforce to produce it. This problem has been compounded by the slow growth of programming productivity, especially for high-performance programs, over the past two decades. One way to bridge this gap is to make it possible for end users to develop programs in high-level domain-specific programming systems. In the past, a major impediment to the acceptance of such systems has been the poor performance of the resulting applications. To address this problem, we are developing a new compiler-based infrastructure, called TeleGen, that will make it practical to construct efficient domain-specific high-level languages from annotated component libraries. We call these languages telescoping languages, because they can be nested within one another. For programs written in telescoping languages, high performance and reasonable compilation times can be achieved by exhaustively analyzing the component libraries in advance to produce a language processor that recognizes and optimizes library operations as primitives in the language. The key to making this strategy practical is to keep compile times low by generating a custom compiler with extensive built-in knowledge of the underlying libraries. The goal is to achieve compile times that are linearly proportional to the size of the program presented by the user, rather than to the aggregate size of that program plus the base libraries.     

Playing with state-based models for designing better algorithms

State-based models provide a very convenient framework for analyzing, verifying, validating and designing sequential as well as concurrent or distributed algorithms. Each state-based model is considered as an abstraction, which is more or less close to the target algorithmic entity. The problem is then to organize the relationship between an initial abstract state-based model expressing requirements and a final concrete state-based model expressing a structured algorithmic state-based model. A simulation (or refinement) relation between two state-based models allows to structure these models from an abstract view to a concrete view. Moreover, state-based models can be extended by assertion languages for expressing correctness properties as pre/post specification, safety properties or even temporal properties. In this work, we review state-based models and play scores for verifying and designing concurrent or distributed algorithms. We choose the Event-B modeling language for expressing state-based models and we show how we can play Event-B scores using Rodin and methodological elements to guarantee that the resulting algorithm is correct with respect to initial requirements. First, we show how annotation-based verification can be handled in the Event-B modeling language and we propose an extension to handle the verification of concurrent programs. In a second step, we show how important is the concept of refinement and how it can be used to found a methodology for designing concurrent programs using the coordination paradigm.