P-Prolog: A parallel logic language based on exclusive relation

This paper presents a parallel logic programming language named P-Prolog which is being developed as a logic programming language featuring both and- and or-parallelism. Compared with the other parallel logic programming languages, syntactic constructs such as read-only annotation,⁶⁾ mode declaration²⁾ and communication constraints⁷⁾ are not used in P-Prolog. A new concept introduced in P-Prolog is the exclusive relation of guarded Horn clauses. Advances included in P-prolog. are:

1. The synchronization mechanism can determine the direction of data flow dynamically.
2. Guarded Horn clauses can be interpreted as eitherdon’t care nondeterminism ordon’t know non-determinism.

A prototype interpreter of P-Prolog has been implemented in C-Prolog. We are now implementing a P-Prolog interpreter in the C language.     

Basic constructs of the SIM operating system

The basic constructs of SIMPOS (Sequential Inference Machine Programming and Operating System) are explained. SIMPOS is an operating system for a super-personal computer (SIM), based on logic programming language (a modified Prolog, called KL0). Our design principle is simplicity both in concept and structure. The entire system will be constructed using these basic constructs.     

A prological definition of HASL a purely functional language with unification based conditional binding expressions

We present a definition in Prolog of a new purely funtional (applicative) language HASL (HArvey’s StaticLanguage). HASL is a descendant of Turner’s SASL and differs from the latter in several significant points: it includes Abramson’s unification based conditional binding constructs; it restricts each clause in a definition of a HASL function to have the same arity, thereby complicating somewhat the compilation of clauses to combinators, but simplifying considerably the HASL reduction machine; and it includes the single element domain {fail} as a component of the domain of HASL data structures. It is intended to use HASL to express the functional dependencies in a translator writing system based on denotational semantics, and to study the feasibility of using HASL as a functional sublanguage of Prolog or some other logic programming language. Regarding this latter application we suggest that since a reduction mechanism exists for HASL, it may be easier to combine it with a logic programming language than it was for Robinson and Siebert to combine LISP and LOGIC into LOGLISP: in that case a fairly complex mechanism had to be invented to reduce uninterpreted LOGIC terms to LISP values. The definition is divided into four parts. The first part defines the lexical structure of the language by means of a simple Definite Clause Grammar which relates character strings to “token” strings. The second part defines the syntactic structure of the language by means of a more complex Definite Clause Grammar and relates token strings to a parse tree. The third part is semantic in nature and translates the parse tree definitions and expressions to a variable-free string of combinators and global names. The fourth part of the definition consists of a set of Prolog predicates which specifies how strings of combinators and global names are reduced to “values”, ie., integers, truth values, characters, lists, functions, fail, and has an operational flavour: one can think of this fourth part as the definition of a normal order reduction machine.     

A knowledge assimilation method for logic databases

In this paper we consider a deductive question-answering system for relational databases as a logic database system, and propose a knowledge assimilation method suitable for such a system. The concept of knowledge assimilation for deductive logic is constructed in an implementable form based on the notion of amalgamating object language and metalanguage. This concept calls for checks to be conducted on four subconcepts, provability, contradiction, redundancy, independency, and their corresponding internal database updates. We have implemented this logic database knowledge assimilation program in PROLOG, a logic programming language, and have found PROLOG suitable for knowledge assimilation implementation.     

Composing recursive logic programs withClausal join

A family of methods for composing logic programs from simpler components is presented. Specifically, simple pairs of programs operating on lists, trees and other recursive structures are composed to generate a single program with composite functionality. The methods are based onclausal join, a specific sequence of unfold/fold transformations for deriving a new clause from a given pair of clauses and a join specification.Procedural join composes a new procedure from two given procedures by applyingclausal join to all pairs of their clauses.1-1 Join composes a new procedure from closely related procedures by applyingclausal join to corresponding pairs only.Meta join is a modification of1-1 join for composing meta-interpreters. The transformations are straightforward to implement in Prolog, as is demonstrated in the paper.     

A logic programming language based on the Andorra model

The Andorra model is a parallel execution model of logic programs which exploits the dependent and-parallelism and or-parallelism inherent in logic programming. We present a flat subset of a language based on the Andorra model, henceforth called Andorra Prolog, that is intended to subsume both Prolog and the committed choice languages. Flat Andorra, in addition todon’t know anddon’t care nondeterminism, supports control of or-parallel split, synchronisation on variables, and selection of clauses. We show the operational semantics of the language, and its applicability in the domain of committed choice languages. As an examples of the expressiveness of the language, we describe a method for communication between objects by time-stamped messages, which is suitable for expressing distributed discrete event simulation applications. This method depends critically on the ability to expressdon’t know nondeterminism and thus cannot easily be expressed in a committed choice language.     

The programming language GCLA — A definitional approach to logic programming

We present a logic programming language, GCLA^*** (Generalized horn Clause LAnguage), that is based on a generalization of Prolog. This generalization is unusual in that it takes a quite different view of the meaning of a logic program—a “definitional” view rather than the traditional logical view. GCLA has a number of noteworthy properties, for instance hypothetical and non-monotonic reasoning. This makes implementation of reasoning in knowledge-based systems more direct in GCLA than in Prolog. GCLA is also general enough to incorporate functional programming as a special case. GCLA and its syntax and semantics are described. The use of various language constructs are illustrated with several examples.     

Design and simulation of a sequential Prolog machine

Prolog-X is an implemented portable interactive sequential Prolog system in which clauses are incrementally compiled for a virtual machine called the ZIP Machine. At present, the ZIP Machine is emulated by software, but it has been designed to permit easy implementation in microcode or hardware. Prolog-X running on the software-based emulator provides performance comparable with existing Prolog interpreters. To demonstrate its efficiency, compatibility, and comprehensiveness of implementation, Prolog-X has been used to compile and run several large applications programs. Several novel techniques are used in the implementation, particularly in the areas of the representation of therecordx database, the selection of clauses, and the compilation of arithmetic expressions.     

Knowledge information processing language: ShapeUp

A new logic programming language, ShapeUp, is developed. ShapeUp is an expanded Prolog system with string matching facilities. The language has been developed to give programmers a new computer programming environment, especially for knowledge information processing. This area includes natural language comprehension and intelligent text processing systems with better man-machine interfaces. For this kind of application, character string data play a principal part rather than conventional numerical data. In ShapeUp, string patterns are introduced as Prolog ‘terms’. Their matching process is performed inside the unification. Thus, a program is far simpler and easier to write and read in ShapeUp, than in conventional Prolog systems, and program size is extremely reduced.     

BUP: A Bottom-Up parser embedded in Prolog

A parser based on logic programming language (DCG) has very useful features; perspicuity, power, generality and so on. However, it does have some drawbacks in which it cannot deal with CFG with left recursive rules, for example. To overcome these drawbacks, a Bottom-Up parser embedded in Prolog (BUP) has been developed. In BUP, CFG rules are translated into Prolog clauses which work as a bottom-up left corner parser with top-down expectation. BUP is augmented by introducing a “link” relation to reduce the size of a search space. Furthermore, BUP can be revised to maintain partial parsing results to avoid computational duplication. A BUP translator and a BUP tracer which support the development of grammar rules are described.     

The Recursive Resolution method for Modal Logic

In this paper a syntactic proof procedure, Recursive Resolution (RR), will be introduced for a Modal Logic system S4. The RR is analogous to Robinson’s resolution method on predicate calculus. In Predicate Calculus, a well-formed-formula (wff) can be transformed to a set of normal forms (clauses) after a skolemization process where skolem functions are introduced. For any two normal forms, the resolution method tells how to find their resolvent if they are resolvable at all. Similarly, for modal logic S4, there is a preliminary step in RR to transform a wff into a set of normal forms (m-clauses) after a skolemization step of the possibility operator □. For any two normal forms (m-clauses), the RR method determines whether they are modal-resolvable. If so, their modal-resolvent(s) (MR) can be computed. Traditionally, we use the semantic tableau or related method to reason on modal logic which is a direct application of the semantic analysis of the concept of possible world. Computationally, these semantic proof procedures involve unnecessary backtracking and so cannot be efficiently implemented in a computer. RR is also justified by and devised according to the semantic analysis of possible worlds. But it avoids explicit construction of possible worlds or reducing modalities by quantified variables and can be implemented by some recursive functions.     

Virtual Machines and Real Implementations

What does it take to implement a computer? Answers to this question have often focused on what it takes for a physical system to implement an abstract machine. As Joslin (Minds Mach 16:29–41, 2006) observes, this approach neglects cases of software implementation—cases where one machine implements another by running a program. These cases, Joslin argues, highlight serious problems for mapping accounts of computer implementation—accounts that require a mapping between elements of a physical system and elements of an abstract machine. The source of these problems is the complexity introduced by common design features of ordinary computers, features that would be relevant to any real-world software implementation (e.g., virtual memory). While Joslin is focused on contemporary views, his discussion also suggests a counterexample to recent mapping accounts which hold that genuine implementation requires simple mappings (Millhouse in Br J Philos Sci, 2017.  https://doi.org/10.1093/bjps/axx046; Wallace in The emergent multiverse, Oxford University Press, Oxford, 2014). In this paper, I begin by clarifying the nature of software implementation and disentangling it from closely related phenomena like emulation and simulation. Next, I argue that Joslin overstates the degree of complexity involved in his target cases and that these cases may actually give us reasons to favor simplicity-based criteria over relevant alternatives. Finally, I propose a novel problem for simplicity-based criteria and suggest a tentative solution.     

A shortest augmenting path algorithm for dense and sparse linear assignment problems

We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is presented.     

Outline of the Personal Sequential Inference machine: PSI

PSI is a personal computer system being developed as a tool for providing researchers with an efficient programming environment. It directly supports logic programming language, KL0 (Fifth Generation Kernel Language, Version 0), with firmware and hardware. Its interpreter is implemented in the firmware and several hardware mechanisms are provided to attain almost the same level of performance as the DEC-10 Prolog on DEC2060. It also provides the user with a large memory space, 40 bits × 2 to 16 MW, which is essential for developing actual application programs like an expert system. To make efficient man-machine interaction possible, such input and output devices as bit-map display, pointing device and key-board are provided. A local area network is also being developed to build a distributed system.     

Bounded-wait merge in Shapiro’s Concurrent Prolog

InA Subset of Concurrent Prolog and Its Interpreter (1983), E. Y. Shapiro introduces the language Concurrent Prolog. In his presentation, the problem of guaranteeing bounded-waiting during a merge operation is used as a programming example. Solutions are proposed for binary and n-ary merges. The solutions are, however, completely dependent on specific operational characteristics of a Concurrent Prolog machine or interpreter. This paper presents an alternate approach in which the property of bounded-waiting is incorporated into the semantics of the programs, demonstrable given only the computational model of the language. The solution strategy is to utilize the familiar systems programming techniques of block-on-input and busy-wait. This approach requires that the language be augmented with a metalogical predicate analogous to thevar(_) predicate of Sequential Prolog. The resultant programs are interesting and illustrative examples of Concurrent Prolog as a programming language.