Refinement of a typed WAM extension by polymorphic order-sorted types

We refine the mathematical specification of a WAM extension to typeconstraint logic programming given in [BeB96]. We provide a full specification and correctness proof of the PROTOS Abstract Machine (PAM), an extension of the WAM by polymorphic order-sorted unification as required by the logic programming language PROTOS-L, by refining the abstract type constraints used in [BeB96] to the polymorphic order-sorted types of PROTOS-L. This allows us to develop a detailed and mathematically precise account of the PAM's compiled type constraint representation and solving facilities, and to extend the correctness theorem to compilation on the fully specified PAM.The first author was partially funded by the German Ministry for Research and Technology (BMFT) in the framework of the WISPRO Project (Grant 01 IW 206). He would also like to thank the Scientific Center of IBM Germany where the work reported here was started.     

DWAM — A WAM model extension for disjunctive logic programming

Answering queries in disjunctive logic programming requires the use of ancestry-resolution. The resulting complication makes it difficult to implement a Prolog-type query answering procedure for disjunctive logic programs. However, SLO-resolution provides a mechanism which is similar to SLD-resolution and hence offers a solution to this problem. The Warren Abstract Machine has been a very effective model for implementing Prolog. In this paper, we extend the WAM model of Prolog and adapt it for DISLOG — a language for disjunctive logic programming. We describe the extensions and additional instructions needed to make WAM viable for modeling and executing DISLOG. The extension is made in such a way that the original architecture is not disturbed and a Prolog program will execute as efficiently as it does in the original WAM.This work was done while the author was at the University of Kentucky.     

A typed functional extension of logic programming

A logic language is suitable for specification if it is equipped with features for data abstraction and modularization. In this paper, an effective mechanism to incorporate function and type into logic programming is presented as the means to embed data abstraction mechanism into logic programming. This incorporation is essentially based on Horn clause logic with equality and a polymorphic type system that is an extension of Mycroft and O’Keefe’s system. This paper also presents an implementation based on Warren Abstract Machine (WAM) and shows the performance, along with a comparison with WAM.     

Translating a Linear Logic Programming Language into Java

There have been several proposals for logic programming language based on linear logic: Lolli [8], Lygon [7], LO [3], LinLog [2], Forum [11], HACL [10]. In these languages, it is possible to create and consume resources dynamically as logical formulas. The efficient handling of resource formulas is, therefore, an important issue in the implementation of these languages. Lolli, Lygon, and Forum are implemented as interpreter systems; Lolli is on SML and λProlog, Lygon is on Prolog, Forum is on SML, λProlog and Prolog. However, none of them have been implemented in Java.In this paper, we describe the Prolog Café ¹ system which translates a linear logic programming language called LLP to Java via the LLPAM [12] [5], an extension of the standard WAM [16] [1] for LLP. LLP is a superset of Prolog and a subset of Lolli. The main difference from the first implementation [4] is resource compilation. That is to say, resource formulas are compiled into closures which consist of a reference of compiled code and a set of bindings for free variables. Calling these resources is integrated with the ordinary predicate invocation.Prolog Café is portable to any platform supporting Java and easily expandable with increasing Java's class libraries. In performance, on average, Prolog Café generate 2.2 times faster code for a set of classical Prolog benchmarks compared with jProlog.     

Prolog抽象机及运行模型研究

文中实现Ｐｒｏｌｏｇ集成开发环境在功能和效率方面的要求出发,通过对Ｗａｒｒｅｎ抽象机（ＷＡＭ）的改进与扩充,提出了一种改进的Ｐｒｏｌｏｇ抽象机ＰＡＭ及相应的基于Ｃｌｉｅｎｔ－Ａｇｅｎｔ结构的运行控制机制。     

Efficient prolog programming

This paper presents some basic programming strategies for Prolog programmers. The strategies are based on knowledge about the operational behaviour of the Warren Abstract Machine (WAM). The aim is to provide simple principles for making programs both faster and less space-consuming. The programming hints given are mostly local, i.e. only a single clause or procedure need be considered at a time.     

Concerned with the unprivileged: user programs in kernel refinement

It is a great verification challenge to prove properties of complete computer systems on the source code level. The L4.verified project achieved a major step towards this goal by mechanising a proof of functional correctness of the seL4 kernel. They expressed correctness in terms of data refinement with a coarse-grained specification of the kernel’s execution environment. In this paper, we strengthen the original correctness theorem in two ways. First, we convert the previous abstraction relations into projection functions from concrete to abstract states. Second, we revisit the specification of the kernel’s execution environment: we introduce the notion of virtual memory based on the kernel data structures, we distinguish individual user programs that run on top of the kernel and we restrict the memory access of each of these programs to its virtual memory. Through our work, properties like the separation of user programs gain meaning. This paves the way for proving security properties like non-interference of user programs. Furthermore, our extension of L4.verified’s proof facilitates the verification of properties about complete software systems based on the seL4 kernel. Besides the seL4-specific results, we report on our work from an engineering perspective to exemplify general challenges that similar projects are likely to encounter. Moreover, we point out the advantages of using projection functions in L4.verified’s verification approach and for stepwise refinement in general.     

A prolog constraint handling rules compiler and runtime system

The most recent and advanced implementation of constraint handling rules (CHR) is introduced in a logic programming language. The Prolog implementation consists of a runtime system and a compiler. The runtime system utilizes attributed variables for the realization of the constraint store with efficient retrieval and update mechanisms. Rules describing the interactions between constraints are compiled into Prolog clauses by a compiler, the core of which comprises a small number of compact code generating templates in the form of definite clause grammar rules.     

Oracle Semantics for Prolog

This paper proposes to specify semantic definitions for logic programming languages such as Prolog in terms of an oracle which specifies the control strategy and identifies which clauses are to be applied to resolve a given goal. The approach is quite general. It can be applied to Prolog to specify both operational and declarative semantics as well as other logic programming languages. Previous semantic definitions for Prolog typically encode the sequential depth-first search of the language into various mathematical frameworks. Such semantics mimic a Prolog interpreter in the sense that following the "leftmost" infinite path in the computation tree excludes computation to the right of this path from being considered by the semantics. The basic idea in this paper is to abstract away from the sequential control of Prolog and to provide a declarative characterization of the clauses to apply to a given goal. The decision whether or not to apply a clause is viewed as a query to an oracle which is specified from within the semantics and reasoned about from outside. This approach results in simple and concise semantic definitions which are more useful for arguing the correctness of program transformations and providing the basis for abstract interpretations than previous proposals.     

SLT-Resolution for the Well-Founded Semantics

Global SLS-resolution and SLG-resolution are two representative mechanisms for top-down evaluation of the well-founded semantics of general logic programs. Global SLS-resolution is linear for query evaluation but suffers from infinite loops and redundant computations. In contrast, SLG-resolution resolves infinite loops and redundant computations by means of tabling, but it is not linear. The principal disadvantage of a nonlinear approach is that it cannot be implemented by using a simple, efficient stack-based memory structure nor can it be easily extended to handle some strictly sequential operators such as cuts in Prolog. In this paper, we present a linear tabling method, called SLT-resolution, for top-down evaluation of the well-founded semantics. SLT-resolution is a substantial extension of SLDNF-resolution with tabling. Its main features are the following. First, it resolves infinite loops and redundant computations while preserving the linearity. Second, it is terminating and is sound and complete w.r.t. the well-founded semantics for programs with the bounded-term-size property with nonfloundering queries. Its time complexity is comparable with SLG-resolution and polynomial for function-free logic programs. Third, because of its linearity for query evaluation, SLT-resolution bridges the gap between the well-founded semantics and standard Prolog implementation techniques. It can be implemented by an extension to any existing Prolog abstract machines such as WAM or ATOAM.     

A controlling scheme for Prolog through count terms

We propose an extension to Prolog called the count term for controlling Prolog execution. The purpose is to allow the programmers as well as the users to have greater flexibility in controlling the execution behavior of Prolog programs and for limiting the number of answers or proofs retrieved when Prolog is used as a database query language. Both syntax and operational semantics of the count term are defined. An implementation strategy based on WAM (Warren Abstract Machine) is provided. We analyze the possible meanings one might associate with the count term. The possible replacement of cut and fail by the count term is presented. The ease of analysis of programs with count terms is discussed.     

逻辑语言中启发式控制

本文论述从逻辑程序本身提取启发式控制信息,以克服由于逻辑语言系统中控制策略的机械性所带来的不完备性和低效性。具体地给出若干启发式控制规则,并证明了这些规则的正确性。运用这些控制规则可以大大地提高系统的运行效率或改善逻辑程序的语义性质。文章最后给出启发式WAM(记作HWAM),并且用实例说明HWAM比WAM更有效,更完善。     

Normalising the associative law: An experiment with Martin-Löf's type theory

Martin-Löf's type theory contains a logic, a specification language and a programming language, so it is a tool with different uses. Although it is traditionally used as anintegrated programming logic, it may well be used as anexternal logic, which is necessary if one wants to use the formalism of type theory to verify the correctness of an external program. Different tools, such as well founded recursion, measure functions, or the separation of correctness into termination and partial correctness, may be used to obtain a correct type theory program. Type theory is viewed as anopen system with respect toinductively defined types and predicates, which makes it easy to represent an external program as agraph. Formal proofs have been edited using Larry Paulson's ISABELLE.     

Uniform Closures: Order-Theoretically Reconstructing Logic Program Semantics and Abstract Domain Refinements

The notion of uniform closure operator is introduced, and it is shown how this concept surfaces in two different areas of application of abstract interpretation, notably in semantics design for logic programs and in the theory of abstract domain refinements. In logic programming, uniform closures permit generalization, from an order-theoretic perspective, of the standard hierarchy of declarative semantics. In particular, we show how to reconstruct the model-theoretic characterization of the well-known s-semantics using pure order-theoretic concepts only. As far as the systematic refinement operators on abstract domains are concerned, we show that uniform closures capture precisely the property of a refinement of being invertible, namely of admitting a related operator that simplifies as much as possible a given abstract domain of input for that refinement. Exploiting the same argument used to reconstruct the s-semantics of logic programming, we yield a precise relationship between refinements and their inverse operators: we demonstrate that they form an adjunction with respect to a conveniently modified complete order among abstract domains.     

Performance analysis of probabilistic action systems

Formal notations like B or action systems support a notion of refinement. Refinement relates an abstract specification A to a concrete specification C that is as least as deterministic. Knowing A and C one proves that C refines, or implements, specification A. In this study we consider specification A as given and concern ourselves with a way to find a good candidate for implementation C. To this end we classify all implementations of an abstract specification according to their performance. We distinguish performance from correctness. Concrete systems that do not meet the abstract specification correctly are excluded. Only the remaining correct implementations C are considered with respect to their performance. A good implementation of a specification is identified by having some optimal behaviour in common with it. In other words, a good refinement corresponds to a reduction of non-optimal behaviour. This also means that the abstract specification sets a boundary for the performance of any implementation. We introduce the probabilistic action system formalism which combines refinement with performance. In our current study we measure performance in terms of long-run expected average-cost. Performance is expressed by means of probability and expected costs. Probability is needed to express uncertainty present in physical environments. Expected costs express physical or abstract quantities that describe a system. They encode the performance objective. The behaviour of probabilistic action systems is described by traces of expected costs. A corresponding notion of refinement and simulation-based proof rules are introduced. Probabilistic action systems are based on discrete-time Markov decision processes. Numerical methods solving the optimisation problems posed by Markov decision processes are well-known, and used in a software tool that we have developed. The tool computes an optimal behaviour of a specification A thus assisting in the search for a good implementation C.Received September 2002 Accepted in revised form January 2004 by E.C.R. Hehner     

Effective incorporation of function into logic

During the last decade, the integration of functional and logic languages has received widespread attraction for the purpose of offering two different programming styles in one system simultaneously. The main goal is to incorporate the characteristics of the two paradigms coherently, without degrading the performance of the whole system. However, few languages have achieved this goal. Some of them, even though they have a rich set of functions, perform poorly. Others are efficient, but lose some important facilities. The paper proposes a functional logic language Lazy Aflog and its abstract machine FWAM-II as an expressive and efficient mechanism for this incorporation. Lazy Aflog is an extension of logic language in which functions are reduced in the extended unification, called E-unification with lazy evaluation. This extended unification allows Lazy Aflog to process infinite data structures and higher-order functions naturally. FWAM-II is an extension of the Warren Abstract Machine (WAM) in which the instructions and run-time structures to provide the suspension/reactivation of functional closure are added. These facilities enable FWAM-II to support not only resolution but also infinite data structures and higher-order functions efficiently. In addition, the experimental results show that Lazy Aflog and FWAM-II could be a good compromise between expressiveness and efficiency of the integration.     

Towards a complete framework for parallel implementation of logic languages: the data parallel implementation of SEL

Although logic languages, due to their non-declarative nature, are widely proclaimed to be conducive in theory to parallel implementation, in fact there appears to be insufficient practical evidence to stimulate further developments in this field. The paper puts forward various complications which arise in assuming a solely process parallel approach as a possible explanation for this situation. As an alternative, data parallelism is posited as an underutilized forte of logic programming. The paper illustrates a data parallel implementation of a particular language called SEL which is based on sets. Thus, SEL (set equational language) is introduced as an example of logic language which lends itself to an efficient data parallel implementation. The strategy of this implementation assumes an abstract machine called SAM (set-oriented abstract machine) which is based on the WAM (Warren abstract machine). SAM serves as an intermediary between the SEL language and the target machine for the implementation, the Connection Machine. Finally, some preliminary benchmarks are presented.     

Study of mechanisms that support the implementation of nonlogical components of prolog in WAM-based systems

Most of the recent efficient Prolog systems are based on the WAM (Warren Abstract Machine) [1]. But the original WAM provides little support for the implementation of nonlogical components of Prolog. In this paper, an execution model for nonlogical components proposed by the authors is presented. The ideas of modifiable code and operation modes for DBOP-predicates are proposed in the paper. The semantics of modifiable procedure code and considerations on the implementations of code databases and source databases are discussed.     

A decompositional approach to the design of parallel programs

A methodology for the derivation of parallel implementations from program specifications is developed. The goal of the methodology is to decompose a program specification into a collection of module specifications via property refinement, such that each module may be implemented independently by a subprogram. The correctness of the implementation is then deduced from the correctness of the property refinement procedure and the correctness of the individual subprograms. The refinement strategy is based on identifying frequently occurring control structures such as sequential composition and iteration. The methodology is developed in the context of the UNITY logic and the UC programming language, and illustrated through the solution of diffusion aggregation in fluid flow simulations     

Specification,Verification and Prototyping of an Optimized Compiler

This paper generalizes an algebraic method for the design of a correct compiler to tackle specification and verification of an optimized compiler. The main optimization issues of concern here include the use of existing contents of registers where possible and the identification of common expressions. A register table is introduced in the compiling specification predicates to map each register to an expression whose value is held by it. We define different kinds of predicates to specify compilation of programs, expressions and Boolean tests. A set of theorems relating to these predicates, acting as a correct compiling specification, are presented and an example proof within the refinement algebra of the programming language is given. Based on these theorems, a prototype compiler in Prolog is produced.