Parallel programming with logic languages: A survey

Formal properties of logic languages are largely studied; however, their impact on the practice of software design and programming is currently minimal. In this paper we survey some interesting representatives of the family of logic languages aiming at comparing the different capabilities they offer for designing and programming parallel systems. The logic languages Prolog, Aurora, Flat Concurrent Prolog, Parlog, GHC, and DeltaProlog were chosen, because a suitable set of relevant examples has been published, mostly by the language designers themselves. A number of sample programs is used to expose and compare the languages with respect to their object oriented programming capabilities for multiprocess coordination, interprocess communication, and resource management. Special attention is devoted also to metaprogramming as well, seen as a useful technique for specifying and building the operating environments of the languages themselves. The paper ends with a discussion on positive and negative features found comparing these languages, and indicates some guidelines to be followed in the design of new logic languages.     

If Prolog is the Answer, What is the Question? or What it Takes to Support AI Programming Paradigms

Knowledge programming, which makes use of the explicit representation and interpretation of knowledge to create intelligent programs, requires specialized languages and tools to help programmers. Prolog, an implementation of a logic programing language, provides some of these tools; it and other languages have been argued to be the "best" way to do such knowledge programming. This paper raises questions which suggest that any single paradigm of programming (e.g., logic programming or object-oriented programming) benefits by being integrated in a single environment with other paradigms of programming. Integration of these paradigms with each other, and within a flexible, user-friendly computing environment is also necessary. Such an environment must provide source level debugging and monitoring facilities, analysis and performance tuning tools, and an extended set of user communication programs.     

QD-Janus: A sequential implementation of Janus in Prolog

Janus is a language designed for distributed constraint programming. This paper describes QD-Janus, a sequential implementation of Janus in Prolog. The compiler uses a number of novel analyses and optimizations to improve the performance of the system. The choice of Prolog as the target language for a compiler, although unusual, is motivated by the following: (i) the semantic gap between Janus and Prolog is much smaller than that between Janus and, say, C or machine language—this simplifies the compilation process significantly, and makes it possible to develop a system with reasonable performance fairly quickly; (ii) recent progress in Prolog implementation techniques, and the development of Prolog systems whose speeds are comparable to those of imperative languages, indicates that the translation to Prolog need not entail a significant performance loss compared to native code compilers; and (iii) compilation to Prolog can benefit immediately from a significant body of work on, and implementations of, parallel Prolog systems. Our experience indicates that translation of logic programming languages to Prolog, accompanied by the development of good program analysis and optimization tools, is an effective way to quickly develop flexible and portable implementations with good performance and low cost.     

Prolog/Rex-a way to extend Prolog for better knowledgerepresentation

Prolog/Rex represents a powerful amalgamation of the latest techniques for knowledge representation and processing, rich in semantic features that ease the difficult task of encoding heterogeneous knowledge of real-world applications. The Prolog/Rex concept mechanism lets a user represent domain entities in terms of their structural and behavioral properties, including multiple inheritance, arbitrary user-defined relations among entities, annotated values (demons), incomplete knowledge, etc. A flexible rule language helps the knowledge engineer capture human expertise and provide flexible control of the reasoning process. Additional Prolog/Rex strength that cannot be found in any other hybrid language made on top of Prolog is language level support for keeping many potentially contradictory solutions to a problem, allowing possible solutions and their implications to be automatically generated and completely explored before they are committed. The same mechanism is used to model time-states, which are useful in planning and scheduling applications of Prolog/Rex     

Critical factors in the evolution of logic programming and Prolog

Logic programming has received much critical attention over the past two decades from both a language perspective and as a methodology for practical problem solving. This paper presents a historical foundation of the approach and examines the development of Prolog since its first implementation. An analysis of the use of Prolog in commercial, research and teaching environments shows that there is an established base of users and that, after a period of rapid growth, the language currently enjoys continuing activity. The key to its success so far is due to its continuing evolution by including features that were not seen as being within the original concept as a pure logic language. Significant features which have contributed to the success of Prolog include integration with other languages, object oriented extensions, constraint representation, parallel execution as well as improved speed and robustness. Applications databases are analysed with respect to type of application, system status, type of developer, hardware platform, country of origin and the Prolog implementation used. Factors contributing to the success of Prolog are identified and likely future developments are explored.     

Icola — Incremental Constraint-Based Graphics for Visualization

Visualization is valuable in monitoring and debugging programs. The goal of the Wand research project at the University of Saskatchewan is to provide both a framework and tools for rapid development of visualization aids for logic programming languages. The ICOLA (Incremental Constraint-based Object Layout Algorithm) system is the newest graphics facility within Wand. ICOLA positions graphical objects according to object declarations and constraints specifying relative positional relationships among the objects. Three important features of ICOLA are that it is capable of creating reasonable pictures from highly under-constrained specifications, it uses an incremental constraint solution algorithm and hence generates those pictures efficiently, and it supports incremental (i.e. progressive) insertions and deletions of objects and constraints. The ability of the incremental algorithm to support such deletions is particularly noteworthy. This paper describes: PDI, the language supported by ICOLA; the incremental constraint solution algorithm itself; a successful implementation in Prolog and C; and results of a performance evaluation of the implementation.     

Focal structures and information types in Prolog

Several studies have suggested that the mental structures of programmers of procedural languages have a close relationship with a model of structural knowledge related to functional information known as programming Plans. It also has been claimed that experienced programmers organize this representation in a hierarchical structure where some elements of Plans are focal or central to them. However, it is not clear that this is the case for other types of programming languages, especially for those which are significantly different from the procedural paradigm.The study reported in this paper investigates whether these claims are true for Prolog, a language which has important differences to procedural languages. Prolog does not have obvious syntactic cues to mark blocks of code (begin/end, repeat/until, etc). Also, its powerful primitives (unification and backtracking) and the extensive use of recursion might influence how programmers comprehend Prolog code in a significant way.The findings of the study suggest that Plans and functional information are important for Prolog programmers, but that there is also at least another model of structural knowledge valid for this language. This model of structural knowledge, Prolog schemas, is related to data structure information and it seems that a hierarchical organisation that highlights the relevance of some of its elements as focal is valid for Prolog. These results support the view that comprehension involves the detection of varying aspects of the code and that each of the structures related to these aspects might have their own organization and hierarchical relations.     

Programming in concurrent logic languages

The authors survey concurrent logic languages, which expand Prolog by dropping its built-in sequential search order. These languages make parallelism easy by avoiding the low-level constructs that result from a too direct translation of machine hardware into programmer's language     

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.     

The languages FCP(:) and FCP(:,?)

The language FCP(:,?) is the outcome of attempts to integrate the best of several flat concurrent logic programming languages, including Flat GHC, FCP (↓, |) and Flat Concurrent Prolog, in a single consistent framework. FCP(:) is a subset of FCP(:, ?), which is a variant of FPP(↓, |) and employs concepts of the concurrent constraint framework of cc(↓, |). FCP(:, ?) is a language which is strong enough to accommodate all useful concurrent logic programming techniques, including those which rely on atomic test unification and read-only variables, yet incorporates the weaker languages mentioned as subsets. This allows the programmer to remain within a simple subset of the language such as Flat GHC when the full power of atomic unification or read-only variables is not needed.     

Linear objects: Logical processes with built-in inheritance

We present a new framework for amalgamating two successful programming paradigms: logic programming and object-oriented programming. From the former, we keep the delarative reading of programs. From the latter, we select two crucial notions: (i) the ability for objects to dynamically change their internal state during the computation; (ii) the structured representation of knowledge, generally obtained via inheritance graphs among classes of objects. We start with the approach, introduced in concurrent logic programming languages, which identifies objects with proof processes and object states with arguments occurring in the goal of a given process. This provides a clean, side-effect free account of the dynamic behavior of objects in terms of the search tree—the only dynamic entity in logic programming languages. We integrate this view of objects with an extension of logic programming, which we call Linear Objects, based on the possibility of having multiple literals in the head of a program clause. This contains within itself the basis for a flexible form of inheritance, and maintains the constructive property of Prolog of returning definite answer substitutions as output of the proof of non-ground goals. The theoretical background for Linear Objects is Linear Logic, a logic recently introduced to provide a theoretical basis for the study of concurrency. We also show that Linear Objects can be considered as constructive restriction of full Classical Logic. We illustrate the expressive power of Linear Objects compared to Prolog by several examples from the object-oriented domain, but we also show that it can be used to provide elegant solutions for problems arising in the standard style of logic programming.     

Efficient Interval Linear Equality Solving in Constraint Logic Programming

Existing interval constraint logic programming languages, such as BNR Prolog, work under the framework of interval narrowing and are deficient in solving systems of linear constraints over real numbers, which constitute an important class of problems in engineering and other applications. In this paper, we suggest to separate linear equality constraint solving from inequality and non-linear constraint solving. The implementation of an efficient interval linear constraint solver, which is based on the preconditioned interval Gauss-Seidel method, is proposed. We show how the solver can be adapted to incremental execution and incorporated into a constraint logic programming language already equipped with a non-linear solver based on interval narrowing. The two solvers share common interval variables, interact and cooperate in a round-robin fashion during computation, resulting in an efficient interval constraint arithmetic language CIAL. The CIAL prototypes, based on CLP(R), are constructed and compared favorably against several major interval constraint logic programming languages.     

A garbage collection algorithm for shared memory parallel processors

This paper describes a technique for adapting the Morris sliding garbage collection algorithm to execute on parallel machines with shared memory. The algorithm is described within the framework of an implementation of the parallel logic language Parlog. However, the algorithm is a general one and can easily be adapted to parallel Prolog systems and to other languages. The performance of the algorithm executing a few simple Parlog benchmarks is analyzed. Finally, it is shown how the technique for parallelizing the sequential algorithm can be adapted for a semi-space copying algorithm.     

A pointer logic and certifying compiler

Proof-Carrying Code brings two big challenges to the research field of programming languages. One is to seek more expressive logics or type systems to specify or reason about the properties of low-level or high-level programs. The other is to study the technology of certifying compilation in which the compiler generates proofs for programs with annotations. This paper presents our progress in the above two aspects. A pointer logic was designed for PointerC (a C-like programming language) in our research. As an extension of Hoare logic, our pointer logic expresses the change of pointer information for each statement in its inference rules to support program verification. Meanwhile, based on the ideas from CAP (Certified Assembly Programming) and SCAP (Stack-based Certified Assembly Programming), a reasoning framework was built to verify the properties of object code in a Hoare style. And a certifying compiler prototype for PointerC was implemented based on this framework. The main contribution of this paper is the design of the pointer logic and the implementation of the certifying compiler prototype. In our certifying compiler, the source language contains rich pointer types and operations and also supports dynamic storage allocation and deallocation.     

Relating the implementation techniques of functional and functional logic languages

Functional logic languages are declarative programming languages that integrate the programming paradigms of functional and logic languages within a single framework. They are extensions of functional languages with principles derived from logic programmingNarrowing, the evaluation mechanism of functional logic languages, can be defined as a generalization ofreduction, the evaluation mechanism of purely functional languages. The unidirectional pattern matching, which is used for parameter passing in functional languages, is simply replaced by the bidirectionalunification known from logic programming languages. We show in this paper, how to extend a reduction machine, that has been designed for the evaluation of purely functional programs to a machine that performs narrowing. The necessary extensions concern the realization of unification and backtracking, for which we fall back upon the methods of Warren’s Prolog engine.²¹⁾ The narrowing machine embodies an optimized treatment of deterministic computations. A complete specification of the reduction and the narrowing machine and of the translation of a sample language into abstract machine code is given. Comparative results of a C-implementation of the reduction and the narrowing machine show that the time overhead of the more complex narrowing evaluation is, in general, less than 10% of the reduction evaluation.     

Logical English meets legal English for swaps and derivatives

In this paper, we present an informal introduction to Logical English (LE) and illustrate its use to standardise the legal wording of the Automatic Early Termination (AET) clauses of International Swaps and Derivatives Association (ISDA) Agreements. LE can be viewed both as an alternative to conventional legal English for expressing legal documents, and as an alternative to conventional computer languages for automating legal documents. LE is a controlled natural language (CNL), which is designed both to be computer-executable and to be readable by English speakers without special training. The basic form of LE is syntactic sugar for logic programs, in which all sentences have the same standard form, either as rules of the form conclusion if conditions or as unconditional sentences of the form conclusion. However, LE extends normal logic programming by introducing features that are present in other computer languages and other logics. These features include typed variables signalled by common nouns, and existentially quantified variables in the conclusions of sentences signalled by indefinite articles. Although LE translates naturally into a logic programming language such as Prolog or ASP, it can also serve as a neutral standard, which can be compiled into other lower-level computer languages.

     

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.     

混合知识表示法在基于实例设计中的应用研究

针对基于实例的设计（CBD）系统中的复杂知识类型,提出了混合知识表示法,综合运用逻辑、规则、框架、过程表示法的优点,通过面向对象技术加以实现,并给出了基于Visual Prolog5.0的编程方法的应用实例。     

Logicon: An integration of prolog into icon

This paper describes the coupling of logic programming with Icon, which is a programming language aimed at string processing. Icon and Prolog have many similarities and their integration is feasible and desirable because the weaknesses of one can be compensated for by the strengths of the other. In our case, a Prolog interpreter was written as an Icon procedure that can be linked and called by an Icon program. This interpreter deals with all Icon data types and can be called in the context of the goal-directed evaluation of Icon. We give an example showing the power of this symbiosis between these two languages where a Prolog call in Icon is a generator and an Icon call in a Prolog clause is a built-in predicate.