The Ciao Module System: A New Module System for Prolog

It is now widely accepted that separating programs into modules has proven very useful in program development and maintenance. While many Prolog implementations include useful module systems, we feel that these systems can be improved in a number of ways, such as, for example, being more amenable to effective global analysis and transformation and allowing separate compilation or sensible creation of standalone executables. We discuss a number of issues related to the design of such an improved module system for Prolog. Based on this, we present the choices made in the Ciao module system, which has been designed to meet a number of objectives: allowing separate compilation, extensibility in features and in syntax, amenability to modular global analysis and transformation, etc.     

逻辑程序模块化的研究与实现

模块化结构是当今智能语言或工具系统商品化和标准化的一个重要部分。我们在ＧＫＤ－Ｐｒｏｌｏｇ的基础上，设计并实现了一个模块化Ｐｒｏｌｏｇ系统。它同时引入了模块和执行环境的概念，并提供了对这些概念的直接支持，使Ｐｒｏｌｏｇ更适于知识的表示和操作。本文主要研究了Ｐｒｏｌｏｇ模块系统的概念和理论，描述了系统的组织结构，并结合两种实现模块机制的方法介绍了本文的主要实现技术，最后给出了我们引入的模块操作原语。     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

The muse approach to Or-parallel prolog

Muse (Multi-sequential Prolog engines) is a simple and efficient approach to Or-parallel execution of Prolog programs. It is based on having several sequential Prolog engines, each with its local address space, and some shared memory space. It is currently implemented on a 7-processors machine with local/shared memory constructed at SICS, a 16-processors Sequent Symmetry, a 96-processors BBN Butterfly I, and a 45-processors BBN Butterfly II. The sequential SICStus Prolog system has been adapted to Or-parallel implementation. Extra overhead associated with this adaptation is very low in comparison with the other approaches. The speed-up factor is very close to the number of processors in the system for a large class of problems.The goal of this paper is to present the Muse execution model, some of its implementation issues, a variant of Prolog suitable for multiprocessor implementations, and some experimental results obtained from two different multiprocessor systems.     

A logical approach to program analysis

This paper describesMicroScope, a framework for developing analysis tools for Lisp programs. MicroScope uses a knowledge-intensive approach for program representation and analysis. The analysis tools share a common object oriented program database, and a common Prolog inference engine. The use of Prolog and a declarative representation for programs permits sharing of information, and provides high bandwidth communication between diverse analysis tools. It also supports program specification and debugging activities in the same framework. Extensions to Prolog to support analysis are described, and two tools, theCritic and theExpector, are presented.This work supported in part by Hewlett-Packard Company, the National Science foundation Under Grant Number MCS81-21750 and the Defense Advanced Research Projects Agency under contract number DAAK11-84-K-0017.     

The design, implementation, and performance evaluation of BERMUDA

We describe the design and implementation of BERMUDA, which is a loosely coupled system interfacing Prolog to the Britton-Lee Intelligent Database Machine (IDM-500). BERMUDA allows multiple concurrent Prolog processes, possibly running on different machines, to share a database. In addition, it preserves the semantics of Prolog programs and makes the use of the database system transparent to the user. We discuss several architectural issues faced by such systems and the approach adopted for each one in BERMUDA. We also present the performance results of a variety of experiments with the system. These include single-user benchmarks of BERMUDA against stand-alone Prolog and stand-alone IDM, detailed profiling of the costs of the modules of BERMUDA that shows the overhead imposed by the interface, and multiuser benchmarks of BERMUDA that show how the system behaves under heavier load. These experiments demonstrate the effectiveness of loosely coupled systems in general and of BERMUDA specifically. They also help in the identification of some aspects of the design and implementation of BERMUDA that could be improved     

Frame-based system for image interpretation

This paper describes a frame-based computer vision system named FABIUS implemented in Prolog. Advantages of using frames for computer vision are that they are modular and understandable; structural, decomposable objects can be described by part frame hierarchies, and specialization frame hierarchies enable property inheritance and flexible, efficient object classification. Image processing operations, written in C, are triggered as demons when specific slots in a frame are accessed. Prolog provides the problem solving facilities of backtracking and pattern matching. The system is shown to be well suited to rapid development of applications and alternative interpretation strategies, and its operation is illustrated when applied to the task of identifying vehicles in cluttered real-world scenes.     

基于抽象解释的Prolog程序验证技术研究

作为一种通用的语义近似理论,抽象解释已广泛应用于各类程序的形式化验证中.现有基于抽象解释的逻辑程序验证技术未涉及与程序点相关联的程序性质的验证,设计能够描述此类性质的逻辑程序具体语义和抽象语义是构造相应验证工具的关键.本文给出了一种基于抽象解释的Prolog程序验证方法,该方法采用了具有路径信息的Prolog语义及其抽象作为语义基础,因而可用于验证与程序点相关联的程序特性.本文例子表明了该验证方法的有效性.     

Andorra-I compilation

Andorra-I is an experimental parallel Prolog system which transparently exploits both dependent and-parallelism and or-parallelism. One of the main components of Andorra-I is its preprocessor. In order to obtain efficient execution of programs in Andorra-I, the preprocessor includes a compiler for Andorra-I. The compiler includes a determinacy analyser and a clause compiler, and generates code for a specialised abstract machine. In this paper we discuss the main issues in the Andorra-I compiler, presenting its abstract instruction set and describing the algorithms used in its implementation.     

Record manipulation in prolog

Prolog is a relatively new programming language that has proved excellent for symbolic computation. However, Prolog was not specifically designed for industrial scale work and it lacks some standard features that are useful for reading, maintaining and debugging large programs. In particular, Prolog has no record mechanism, and programs often require major changes when data structures are modified. The record is a standard data abstraction concept that improves the robustness of programs. The main advantage in using records is that data structures can be modified and extended with minimal repercussion to program code. Furthermore, the use of significant names to access data fields means that the intent of code is generally clearer. We present a set of primitive operators that support a readable and robust programming style for the manipulation of record data structures in standard Prolog. The proposal covers both simple and imbricated record types and handles selective modification of records cleanly. We also treat property lists and records in a uniform way. These benefits are achieved with minimal overhead while retaining the traditional Prolog non-deterministic style.     

Declarative diagnosis of missing answers

This paper investigates algorithms for declarative diagnosis of missing answers in Prolog programs, especially programs which use coroutines. The logic of the problem is first presented, in the form of the simplest possible debugger. Next, we compare several previously published declarative debuggers based on Shapiro’s work. Examples showing incompleteness, incorrectness and equivalence of debuggers are given. Several enhancements to these debuggers are presented which can reduce the number and complexity of questions asked of the oracle, while still supporting coroutines. Although no debugger considered is best in all cases, the new algorithms are a practical contribution. Finally, we discuss diagnosis algorithms based more on Pereira’s work. These algorithms ask easier questions than Shapiro’s algorithms but rely on the standard left to right computation rule. We discuss possible ways to adapt these algorithms to handle coroutining. Completeness of debuggers is also discussed.     

Machine independent AND and OR parallel execution of logicprograms. II. Compiled execution

For pt.I. see ibid., p. 170-80. In pt.I, we presented a binding environment for the AND and OR parallel execution of logic programs. This environment was instrumental in rendering a compiler for the AND and OR parallel execution of logic programs machine independent. In this paper, we describe a compiler based on the Reduce-OR process model (ROPM) for the parallel execution of Prolog programs, and provide performance of the compiler on five parallel machines: the Encore Multimax, the Sequent Symmetry, the NCUBE 2, the Intel i860 hypercube and a network of Sun workstations. The compiler is part of a machine independent parallel Prolog development system built on top of a run time environment for parallel programming called the Chare kernel, and runs unchanged on these multiprocessors. In keeping with the objectives behind the ROPM, the compiler supports both on and independent AND parallelism in Prolog programs and is suitable for execution on both shared and nonshared memory machines. We discuss the performance of the Prolog compiler in some detail and describe how grain size can be used to deliver performance that is within 10% of the underlying sequential Prolog compiler on one processor, and scale linearly with increasing number of processors on problems exhibiting sufficient parallelism. The loose coupling between parallel and sequential components makes it possible to use the best available sequential compiler as the sequential component of our compiler     

密码通讯模块设计的实现原则与要求

密码系统的模块化设计是当前军队信息化建设中的重要环节。在对国内外密码系统模块化设计应用进行研究分析的基础上,从分析密码系统一般模型着手,提出了密码系统模块化设计过程中应着重注意的几个方面,对各种密码系统模块化研究与设计工作有着一定的指导意义。     

A calculus for the construction of modular prolog programs

We present a module language for PROLOG based on the theory of modularity underlying the Standard ML module system. The language supports the construction of hierarchically structured programs from parametrized components and provides a form of structural data abstraction. A formal semantics is given for the system which translates modular programs into conventional programs     

Debugging Prolog Using Annotations

We present an annotation language well-suited for rendering aspects of Prolog execution. Our annotations are special Prolog goals that act as executable comments, performing debugging at run-time. No restrictions are placed upon the object language, the concern being verification of (full) Standard Prolog programs. Here we discuss the merits of the annotations for Prolog debugging. All the examples are actual runs of our system, Nope.     

ScaffCC: Scalable compilation and analysis of quantum programs

We present ScaffCC, a scalable compilation and analysis framework based on LLVM (Lattner and Adve, 2004), which can be used for compiling quantum computing applications at the logical level. Drawing upon mature compiler technologies, we discuss similarities and differences between compilation of classical and quantum programs, and adapt our methods to optimizing the compilation time and output for the quantum case. Our work also integrates a reversible-logic synthesis tool in the compiler to facilitate coding of quantum circuits. Lastly, we present some useful quantum program analysis scenarios and discuss their implications, specifically with an elaborate discussion of timing analysis for critical path estimation. Our work focuses on bridging the gap between high-level quantum algorithm specifications and low-level physical implementations, while providing good scalability to larger and more interesting problems.     

Implementing Constructive Intensional Negation

Although negation is an active area of research in logic programming, sound and complete implementations are still absent from actual Prolog systems. One of the most promising techniques in the literature is intensional negation (IN), which follows a transformational approach: for each predicate p in a program its negative counterpart intneg(p) is generated. However, implementations of IN have not been included in Prolog environments due, in part, to the lack of details and explicit techniques, such as the treatment of universally quantified goals. In this paper, we describe a variant of IN, which we have called constructive intensional negation (CIN). Unlike earlier proposals, CIN does not resort to a dedicated resolution strategy when dealing with universally quantified formulae, which has been instrumental in having an effective implementation. Therefore, pure SLD resolution is used, what enables the reuse of existing Prolog implementation technology. Among the contributions of this work we can mention not only a full implementation being tested for its integration in the Ciao Prolog system but also some formal results ensuring soundness and completeness with their associated proofs.

调用模式和正确调用模式语义在Prolog程序测试中的应用

将基于调用模式语义和正确调用模式语义的程序分析技术应用于Prolog程序的CPM测试。通过调用模式分析获得内部过程被调用和成功调用的条件,利用前者删除不满足调用条件的测试帧,或当删除条件不满足时利用该条件更新测试规格中过程属性的划分准则;利用后者预测CPM测试的结果。该方法可较好地保持程序测试的质量,改善Prolog程序的CPM测试过程。     

On computability by logic programs

The problem of computational completeness of Horn clause logic programs is revisited. The standard results on representability of all computable predicates by Horn clause logic programs are not related to the real universe on which logic programs operate. SLD-resolution, which is the main mechanism to execute logic programs, may give answer substitutions with variables. As the main result we prove that computability by Horn clause logic programs is equivalent to standard computability over the Herbrand universe with variables. The semantics we use isS-semantics introduced by Falaschi et al. [3]. As an application of the main result we prove the existence of a metainterpreter for a sublanguage of real Prolog, written in the language of Horn clauses with the S-semantics. We also show that the traditional semantics of Prolog do not reflect its computational behavior from the viewpoint of recursion theory.This article is a revised version of [13]. The work was essentially done during author's visit to ECRC.     

Modular strategies for recursive game graphs

Many problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global) pushdown games is known to be EXPTIME-complete, we show reachability in modular games to be NP-complete. We present a fixed-point computation algorithm for solving modular games such that in the worst case the number of iterations is exponential in the total number of returned values from the modules. If the strategy within a module does not depend on the global history, but can remember the history of the past invocations of this module, that is, if memory is local but persistent, we show that reachability becomes undecidable.