Concurrent logic programming

Last updated

Concurrent logic programming is a variant of logic programming in which programs are sets of guarded Horn clauses of the form:

Contents

H :- G1, …, Gn | B1, …, Bn.

The conjunction G1, … , Gn is called the guard of the clause, and | is the commitment operator.

Declaratively, guarded Horn clauses are read as ordinary logical implications:

H if G1 and … and Gn and B1 and … and Bn.

However, procedurally, when there are several clauses whose heads H match a given goal, then all of the clauses are executed in parallel, checking whether their guards G1, … , Gn hold. If the guards of more than one clause hold, then a committed choice is made to one of the clauses, and execution proceeds with the subgoals B1, …, Bn of the chosen clause. These subgoals can also be executed in parallel. Thus concurrent logic programming implements a form of "don't care nondeterminism", rather than "don't know nondeterminism".

History

The first concurrent logic programming language was the Relational Language of Keith L. Clark and Steve Gregory, which was an offshoot of IC-Prolog. Later versions of concurrent logic programming include Ehud Shapiro's Concurrent Prolog and Ueda's Guarded Horn Clause language.

The development of concurrent logic programming was given an impetus when Guarded Horn Clause was used to implement KL1, the systems programming language of the Japanese Fifth Generation Project (FGCS). The FGCS Project was a $400M initiative by Japan's Ministry of International Trade and Industry, begun in 1982, to use massively parallel computing/processing for artificial intelligence applications. The choice of concurrent logic programming as the “missing link” between the hardware and the applications was influenced by a visit to the FGCS Project in 1982 by Ehud Shapiro, who invented Concurrent Prolog.

See also

Related Research Articles

KL1, or Kernel Language 1 is an experimental and-parallel version of KL0 developed for the ICOT Fifth Generation Computer project. KL1 is an implementation of Flat GHC, making it a parallelised Prolog variant.

Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving and computational linguistics.

<span class="mw-page-title-main">Inductive logic programming</span>

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical rather than mathematical induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form that gives it useful properties for use in logic programming, formal specification, universal algebra and model theory. Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951.

The Fifth Generation Computer Systems was a 10-year initiative begun in 1982 by Japan's Ministry of International Trade and Industry (MITI) to create computers using massively parallel computing and logic programming. It aimed to create an "epoch-making computer" with supercomputer-like performance and to provide a platform for future developments in artificial intelligence. FGCS was ahead of its time, and its excessive ambitions led to commercial failure. However, on a theoretical level, the project spurred the development of concurrent logic programming.

The Guarded Command Language (GCL) is a programming language defined by Edsger Dijkstra for predicate transformer semantics in EWD472. It combines programming concepts in a compact way. It makes it easier to develop a program and its proof hand-in-hand, with the proof ideas leading the way; moreover, parts of a program can actually be calculated.

<span class="mw-page-title-main">Ehud Shapiro</span> Israeli computer scientist

Ehud Shapiro is an Israeli scientist, entrepreneur, artist, and political activist who is Professor of Computer Science and Biology at the Weizmann Institute of Science. With international reputation, he made contributions to many scientific disciplines, laying in each a long-term research agenda by asking a basic question and offering a first step towards answering it, including how to computerize the process of scientific discovery, by providing an algorithmic interpretation to Karl Popper's methodology of conjectures and refutations; how to automate program debugging, by algorithms for fault localization; how to unify parallel, distributed, and systems programming with a high-level logic-based programming language; how to use the metaverse as a foundation for social networking; how to devise molecular computers that can function as smart programmable drugs; how to uncover the human cell lineage tree, via single-cell genomics; how to support digital democracy, by devising an alternative architecture to the digital realm grassroots.

Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.

In computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. Unbounded nondeterminism became an important issue in the development of the denotational semantics of concurrency, and later became part of research into the theoretical concept of hypercomputation.

Indeterminacy in concurrent computation is concerned with the effects of indeterminacy in concurrent computation. Computation is an area in which indeterminacy is becoming increasingly important because of the massive increase in concurrency due to networking and the advent of many-core computer architectures. These computer systems make use of arbiters which gives rise to indeterminacy.

In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. This article reports on the later history of the Actor model in which major themes were investigation of the basic power of the model, study of issues of compositionality, development of architectures, and application to Open systems. It is the follow on article to Actor model middle history which reports on the initial implementations, initial applications, and development of the first proof theory and denotational model.

Concurrent constraint logic programming is a version of constraint logic programming aimed primarily at programming concurrent processes rather than solving constraint satisfaction problems. Goals in constraint logic programming are evaluated concurrently; a concurrent process is therefore programmed as the evaluation of a goal by the interpreter.

Keith Leonard Clark is an Emeritus Professor in the Department of Computing at Imperial College London, England.

Progol is an implementation of inductive logic programming that combines inverse entailment with general-to-specific search through a refinement graph.

B-Prolog was a high-performance implementation of the standard Prolog language with several extended features including matching clauses, action rules for event handling, finite-domain constraint solving, arrays and hash tables, declarative loops, and tabling. First released in 1994, B-Prolog is now a widely used CLP system. The constraint solver of B-Prolog was ranked top in two categories in the Second International Solvers Competition, and it also took the second place in P class in the second ASP solver competition and the second place overall in the third ASP solver competition. B-Prolog underpins the PRISM system, a logic-based probabilistic reasoning and learning system. B-Prolog is a commercial product, but it can be used for learning and non-profit research purposes free of charge. B-Prolog is not anymore actively developed, but it forms the basis for the Picat programming language.

SLD resolution is the basic inference rule used in logic programming. It is a refinement of resolution, which is both sound and refutation complete for Horn clauses.

In computer science, a rule-based system is a computer system in which domain-specific knowledge is represented in the form of rules and general-purpose reasoning is used to solve problems in the domain.

Parlog is a logic programming language designed for efficient utilization of parallel computer architectures. Its semantics is based on first order predicate logic. It expresses concurrency, interprocess communication, indeterminacy and synchronization within the declarative language framework.

References

    This page is based on this Wikipedia article
    Text is available under the CC BY-SA 4.0 license; additional terms may apply.
    Images, videos and audio are available under their respective licenses.