Denotational and operational semantics for prolog

The semantics of PROLOG programs is usually given in terms of the model theory of first-order logic. However, this does not adequately characterizethe computational behavior of PROLOG programs. PROLOG implementations typically use a sequential evaluation strategy based on the textual order of clauses and literals in a program, as well as nonlogical features like cut. In this work we develop a denotational semantics that captures thecomputational behavior of PROLOG. We present a semantics for “cut-free” PROLOG, which is then extended to PROLOG with cut. For each case we develop a congruence proof that relates the semantics to a standard operational interpreter. As an application of our denotational semantics, we show the correctness of some standard “folk” theorems regarding transformations on PROLOG programs.     

运用PROLOG语言表示和处理分子结构

本文描述了用第五代计算机程序设计语言－ＰＲＯＬＯＧ表示和处理分子结构的方法，提出了按照环系和功能团对分子结构进行归约的方法，并且设计了由母核与分子片段组合产生分子结构的ＰＲＯＬＯＧ程序。     

Login: a logic programming language with built-in inheritance

An elaboration of the PROLOG language is described in which the notion of first-order term is replaced by a more general one. This extended form of terms allows the integration of inheritance—an IS-A taxonomy—directly into the unification process rather than indirectly through the resolution-based inference mechanism of PROLOG. This results in more efficient computations and enhanced language expressiveness. The language thus obtained, called LOGIN, subsumes PROLOG, in the sense that conventional PROLOG programs are equally well executed by LOGIN.     

Implementing parallel algorithms in concurrent prolog: The Maxflow experience

This paper reports on the experience of implementing Shiloach and Vishkin's parallel Maxflow algorithm [7] in Concurrent PROLOG. The major difficulties in this endeavor were understanding the algorithm, which is intricate, and adapting it to the computational model of Concurrent PROLOG. In spite of the difficulties, we were able to produce a Concurrent PROLOG program that implements the algorithm and achieves the expected complexity bounds. The lack of destructive assignment in the logic program's computation model prevents PROLOG from being an efficient implementation language for many sequential algorithms. Our main conclusion is that, in concurrent algorithms, message passing is a powerful substitute for destructive assignment. It is therefore possible to write efficient Concurrent PROLOG implementations of concurrent algorithms.     

Teachers encounter PROLOG

Abstract A major problem in introducing computing into schools is how to teach teachers programming and give them confidence to write programs which they can use in their class-rooms. The Exeter Project, originally into PROLOG and History teaching, has experimented with a new user-friendly front-end to PROLOG , called MITSI (Man In The Street Interface), and has written teacher oriented documentation for the existing front-end, SIMPLE . This article analyses teacher's responses to the Project's two latest programming courses, and suggests that PROLOG programming, using appropriate front-ends, might be a particularly successful medium for Humanities teachers.     

A tabu search with an oscillation strategy for the discriminant analysis problem

This article proposes a tabu search approach to solve a mathematical programming formulation of the linear classification problem, which consists of determining an hyperplane that separates two groups of points as well as possible in ?^m. The tabu search approach proposed is based on a non-standard formulation using linear system infeasibility. The search space is the set of bases defined on the matrix that describes the linear system. The moves are performed by pivoting on a specified row and column. On real machine learning databases, our approach compares favorably with implementations based on parametric programming and irreducible infeasible constraint sets. Additional computational results for randomly generated instances confirm that our method provides a suitable alternative to the mixed integer programming formulation that is solved by a commercial code when the number of attributes m increases.     

An operational formal definition of PROLOG: a specification method and its application

We present in this paper a logic programming specification language and its application to the formal specification of PROLOG dialects (Marseille-Edinburgh like dialect or parallel logic programs). In particular it is used in the standardization work of PROLOG. The specification language is based on normal clauses (definite clauses with possibly negative literals in the body) whose semantics is the set of the (generalized) proof-trees. We restrict the specification language to stratified programs and ground proof-trees such that its semantics fits with most of the usual known semantics in logic programming. The specification language is fully declarative in the sense that it is written in a pure logical stule. It is relatively easy to deduce an executable specification from a specification written in such a language. Part of the specification are the associated comments and a methodology has been developed to write these. Without the comments a formal specification cannot be understood; they are partly formal and serve only to help to understand the axioms. They are a natural language form of formal statements relative to the correctness and the completeness of the axioms with regards to some intended meaning. We show in this paper how this specification language can be used to specify dialects of PROLOG. The presented example is just a sample of PROLOG but fully developed here. The specification language has already been used for real dialects as PARLOG and standard PROLOG. This specification method is also interesting because it illustrates the power of logic programming to make specifications. It seems to us that logic programming is generally considered as “impure” executable specification. Our purpose is to show that logic programming may also be used as a perhaps low level but full specification language.     

Techniques of integrating Datalog with PROLOG

Since extending DATALOG to a general-purpose programming language seems very difficult,many projects have embedded a DATALOG-based query laguage into a procedural host language,such as CORAL,Glue-Nail,etc.Although DATALOG can be consideed as function-free PROLOG,they are very different in many aspects.For instance,DATALOG is declarative while PROLOG isn‘t,DATALOG takes “a-set-at-a-time” mode of evaluation but PROLOG takes “a-tuple-at-a-time”one,DATALOG is only a query language whereas PROLOG is a general-purpose programming language.It is thought that integrating DATALOG with PROLOG may take their advantages.KBASEP is such a language.It uses KBASE as the query language and PROLOG as its procedural host language,where KBASE is a ne extemsion of DATALOG with negation and function.This paper introduces the integration techniques used in KBASE-P system.     

A cost-optimal parallel algorithm for the 0–1 knapsack problem and its performance on multicore CPU and GPU implementations

The 0–1 knapsack problem has been extensively studied in the past years due to its immediate applications in industry and financial management, such as cargo loading, stock cutting, and budget control. Many algorithms have been proposed to solve this problem, most of which are heuristic, as the problem is well-known to be NP-hard. Only a few optimal algorithms have been designed to solve this problem but with high time complexity. This paper proposes the cost-optimal parallel algorithm (COPA) on an EREW PRAM model with shared memory to solve this problem. COPA is scalable and yields optimal solutions consuming less computational time. Furthermore, this paper implements COPA on two scenarios – multicore CPU based architectures using Open MP and GPU based configurations using CUDA. A series of experiments are conducted to examine the performance of COPA under two different test platforms. The experimental results show that COPA could reduce a significant amount of execution time. Our approach achieves the speedups of up to 10.26 on multicore CPU implementations and 17.53 on GPU implementations when the sequential dynamic programming algorithm for KP01 is considered as a baseline. Importantly, GPU implementations outstand themselves in the experimental results.     

SC-PROLOG解释系统中的约束逻辑程序设计方法

约束逻辑程序设计（ＣＬＰ）方法是提高ＰＲＯＬＯＧ语言效率的一种崭新方法，本文针对ＳＣ┐ＰＲＯＬＯＧ解释系统的实现介绍其相应设计思想，从域变量含义入手，提出了域及约束的存储方法以及约束机制的实现算法，是对逻辑设计方法研究的一点体会     

Programming Environment for Phase-Reconfigurable Parallel Programming on SuperNode

This paper presents a programming environment called C_—NET that we have developed for the reconfigurable SuperNode multiprocessor. It shows how one can take advantage of the environment to implement phase-reconfigurable programs. In the first stage a computing model is designed in relation with the capabilities of the hardware. Next, the entire programming environment is built upon this model. It is organized around a kernel language which has been extended in three separate directions so as to provide three specialized languages: PPL (phase programming language) for the development of phase-reconfigurable programs, GCL (graph-construction language) for the construction of processor graphs on which the phases are to be executed, and CPL (component programming language) for coding the software components that are to be executed on the processors within the phases. The second part of the paper provides an illustration of C_—NET. First, two implementations of the conjugate gradient algorithm within C_—NET are carried out: a phase-reconfigurable implementation and a fixed-topology one. Both have been developed on a 32-node machine. Next, a time model is built for both implementations. The time estimates yielded by the models are checked against time measurements issued from program runs. The time models are proved valid and are subsequently used for extrapolation purposes. The speed-up that could be achieved by executing the conjugate gradient algorithm on larger machines (up to 1024) is discussed ultimately.     

Data Parallel Algorithmic Skeletons with Accelerator Support

Hardware accelerators such as GPUs or Intel Xeon Phi comprise hundreds or thousands of cores on a single chip and promise to deliver high performance. They are widely used to boost the performance of highly parallel applications. However, because of their diverging architectures programmers are facing diverging programming paradigms. Programmers also have to deal with low-level concepts of parallel programming that make it a cumbersome task. In order to assist programmers in developing parallel applications Algorithmic Skeletons have been proposed. They encapsulate well-defined, frequently recurring parallel programming patterns, thereby shielding programmers from low-level aspects of parallel programming. The main contribution of this paper is a comparison of two skeleton library implementations, one in C++ and one in Java, in terms of library design and programmability. Besides, on the basis of four benchmark applications we evaluate the performance of the presented implementations on two test systems, a GPU cluster and a Xeon Phi system. The two implementations achieve comparable performance with a slight advantage for the C++ implementation. Xeon Phi performance ranges between CPU and GPU performance.     

USING META-PROGRAMMING,CONSTRAINT LOGIC PROGRAMMING AND APPROXIMATE REASONING FOR EXPERT SYSTEMS DESIGN

Abstract

This paper presents an enhancement of the CARESS system—A Constraint Approximative Reasoning System Support—introduced in (Popescu and Roventa, 1994). CARESS is an experimental system with primarily two objectives:

(1)knowledge representation and manipulation techniques and to implement them in PROLOG III, and

(2) to develop a knowledge programming environment for building expert systems. We discuss here the use of meta-programming, constraint logic programming and approximate reasoning for the design of expert systems

It has already been proven that meta-programming and logic programming are powerful techniques for expert system design. Fuzzy logic can be used to model one kind of uncertainty. Constraint logic programming is useful for dealing with the constraints given by operations using fuzzy sets.     

Experiments in the Parallel Computation of 3D Convex Hulls

Two parallel implementations of a 3D convex hull algorithm are reported. The paper considers a MIMD distributed memory architecture and the implementations are carried out on the Meiko Computing Surface using T800 transputers and the programming languages Occam and C. The first method uses a simple parallel geometric decomposition strategy and produces encouraging results. With the second approach a parallel generic Divide-and-Conquer kernel is incorporated. This is an example of the algorithmic skeleton approach to parallel programming and involves run-time, dynamic allocation of work to processors. The resulting performances for both methods are measured and compared.     

Content and representation effects with reasoning tasks in PROLOG form

Abstract

Two experiments were carried out to examine human reasoning performance in the context of the logic programming language PROLOG. Two factors, ‘content’ (familiar versus unfamiliar) and ‘representation’ (diagrammatic versus PROLOG-like list) were investigated. Subjects answered questions about hierarchical relationships in each condition. A significant interaction was obtained in both experiments, subjects making fewer errors in the familiar-diagram and unfamiliar-list conditions than in the familiar-list and unfamiliar-diagram conditions.

It is hypothesized that a lower percentage of correct responses was given in familiar-list and unfamiliar–diagram conditions because the representation of information prevented successful use of an appropriate reasoning strategy. Working memory limitations provide a basis for understanding constraints on reasoning strategies for solving task questions. These strategies may involve either a serial or a spatial solution process. One strategy may require a larger working memory load than another, depending on the representation and content of the task information. Implications for PROLOG programming instruction are discussed.     

On the impact of serializing contention management on STM performance

Transactional memory (TM) is an emerging concurrent programming abstraction. Numerous software-based transactional memory (STM) implementations have been developed in recent years. STM implementations must guarantee transaction atomicity and isolation. In order to ensure progress, an STM implementation must resolve transaction collisions by consulting a contention manager (CM).     

A Comparison of Implicitly Parallel Multithreaded and Data-Parallel Implementations of an Ocean Model

Two parallel implementations of a state-of-the-art ocean model are described and analyzed: one is written in the implicitly parallel language Id for the Monsoon multithreaded dataflow architecture, and the other in data-parallel CM Fortran for the CM-5. The multithreaded programming model is inherently more expressive than the data-parallel model but is not especially adapted to regular data structures common to many scientific codes. One goal of this study is to understand what, if any, are the performance penalties of multithreaded execution when implementing a program that is well suited for data-parallel execution. To avoid technology and machine configuration issues, the two implementations are compared in terms of overhead cycles perrequiredfloating point operation. When flows in complex geometries typical of ocean basins are simulated, the data-parallel model only remains efficient if redundant computations are performed over land. The generality of the Id programming model, however, allows one to easily and transparently implement a parallel code that computes only in the ocean. When ocean basins with complex and irregular geometry are simulated the normalized performance on Monsoon is comparable with that of the CM-5. For more regular geometries that map well to the computational domain, the data-parallel approach proves to be a better match. We conclude by examining the extent to which clusters of mainstream symmetric multiprocessor (SMP) systems offer a scientific computing environment which can capitalize on and combine the strengths of the two paradigms.