Logical programming is the general term for the use of logic as the language for programming. It is more general that the more restricted term Logic programming which applies to the use of a restricted form of backward chaining logic in programming.

History

Logic programming can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a theorem-prover is used as the problem-solver. According to this paradigm, the problem-solving task is split between declarative knowledge expressed in classical mathematical logic and a theorem-prover, which is responsible for solving problems efficiently. McCarthy's original advice taker proposal was based on forward chaining. Allen Newell and Herbert Simon incorporated backward chaining as well. The epitome of this paradigm was uniform proof procedure resolution theorem provers [Robinson 1965]. According to this paradigm, it was considered "cheating" to incorporate procedures.

This paradigm gave rise to a number of implementations, such as those by Fisher Black (1964), James Slagle (1965) and Cordell Green (1969), which were question-answering systems in the spirit of McCarthy's advice-taker. Foster and Elcock's Absys (1969), on the other hand, was one of the first languages to be explicitly developed as an assertional programming language.

Procedural Embedding of Knowledge

An alternative paradigm developed at MIT under the leadership of Seymour Papert and Marvin Minsky based on the procedural embedding of knowledge. Allen Newell and Herbert Simon had pioneered in development of the list structure for programming languages. The Lisp programming language represented a great advance with recursive procedures and automatic garbage collection. However, the procedural paradigm operated at a low level of abstraction by comparison with logic.

Planner

Carl Hewitt [Hewitt 1969] developed Planner as a hybrid between the procedural and logical paradigms in that it featured a procedural interpretation of logical sentences in that an implication of the form (P implies Q) can be procedurally interpreted in the following ways:

Forward chaining (antecedently):

If assert P, assert Q

If assert not Q, assert not P

Backward chaining (consequently)

If goal Q, goal P

If goal not P, goal not Q

In this respect, the development of Planner was influence by natural deductive logical systems (especially the one by Frederic Fitch [1952]).

The most influential implementation of Planner was the subset of Planner, called Micro-Planner, implemented by Gerry Sussman, Eugene Charniak and Terry Winograd. It was used to implement Winograd's natural-language understanding program SHRDLU, which was a landmark at that time. At Edinburgh, Julian Davies implemented Popler which provided almost all of the features of Planner [Davies 1973].

From Planner there developed the programming languages QA-4, Conniver, QLISP, and the concurrent language Ether used in an implementation of the Scientific Community Metaphor.

Logical Programming is not universal

Kowalski developed the thesis that “computation could be subsumed by deduction” [Kowalski 1988] which he states was first proposed by Hayes [1973] in the form “Computation = controlled deduction.” [Kowalski 1979]. The Hayes-Kowalski thesis that Logic Programming is universal was valuable in that it motivated further research to characterize exactly which computations could be performed by Logic Programming.

Carl Hewitt et. al. [Hewitt 1985; Hewitt and Agha 1991; Hewitt 2006b] argued that mathematical models of concurrency did not determine particular concurrent computations as follows: The Actor model makes use of arbitration for determining which message is next in the arrival order of an Actor that is sent multiple messages concurrently. For example Arbiters can be used in the implementation of the arrival order of messages sent to an Actor which are subject to indeterminacy in their arrival order. Since arrival orders are in general indeterminate, they cannot be deduced from prior information by mathematical logic alone.

It is important to be clear about the basis for the published claim about the limitation of mathematical logic. It was not that individual Actors could not in general be implemented in mathematical logic. The claim is that because of the indeterminacy of the physical basis of communication in the Actor model, that no kind of deductive mathematical logic can deduce future computational steps.

References

John McCarthy. Programs with common sense Symposium on Mechanization of Thought Processes. National Physical Laboratory. Teddington, England. 1958.
Fisher Black. A deductive question answering system Harvard University. Thesis. 1964.
John Alan Robinson, “A Machine-Oriented Logic Based on the Resolution Principle.” CACM. 1965.
James Slagle. Experiments with a Deductive Question-Answering Program CACM. December, 1965.
Ole-Johan Dahl and Kristen Nygaard. Class and subclass declarations IFIP TC2 Conference on Simulation Programming Languages. May 1967.
Cordell Green. Application of Theorem Proving to Problem Solving IJCAI 1969.
Carl Hewitt. Planner: A Language for Proving Theorems in Robots IJCAI 1969.
Gerry Sussman and Terry Winograd. Micro-planner Reference Manual AI Memo No, 203, MIT Project MAC, July 1970.
Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
Bruce Anderson. Documentation for LIB PICO-PLANNER School of Artificial Intelligence, Edinburgh University. 1972
Bruce Baumgart. Micro-Planner Alternate Reference Manual Stanford AI Lab Operating Note No. 67, April 1972.
Julian Davies. Popler 1.6 Reference Manual University of Edinburgh, TPU Report No. 1, May 1973.
Jeff Rulifson, Jan Derksen, and Richard Waldinger. QA4, A Procedural Calculus for Intuitive Reasoning SRI AI Center Technical Note 73, November 1973.
Robert Kowalski and Donald and Kuehner, Linear Resolution with Selection Function Artificial Intelligence, Vol. 2, 1971, pp. 227-60.
Robert Kowalski Predicate Logic as a Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973. Also in Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, pp. 569-574.
Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259A. January 1974.
Earl Sacerdoti, et al. QLISP: A Language for the Interactive Development of Complex Systems AFIPS National Computer Conference. 1976.
Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
Bill Kornfeld. The Use of Parallelism to Implement a Heuristic Search IJCAI 1981.
Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
Bill Kornfeld. Combinatorially Implosive Algorithms CACM. 1982
Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985.
Robert Kowalski. The Limitations of Logic Proceedings of the 1986 ACM fourteenth annual conference on Computer science.
Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
Robert Kowalski. The Early Years of Logic Programming CACM. January 1988.
Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys. September 1989.
Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
Shunichi Uchida and Kazuhiro Fuchi Proceedings of the FGCS Project Evaluation Workshop Institute for New Generation Computer Technology (ICOT). 1992.
Carl Hewitt. The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.
J. W. Lloyd. Foundations of Logic Programming (2nd edition). Springer-Verlag 1987.
Jean-Marc Andreoli and Remo Pareschi. Linear Objects: Logical Processes with Built-In Inheritance, Proceeding of the Seventh International Conference on Logic Programming, Jerusalem, May 1990.
Joshua Hodas and Dale Miller. Logic Programming in a Fragment of Intuitionistic Linear Logic, Information and Computation, 1994, 110(2), 327-365.
Naoki Kobayashi and Akinori Yonezawa. Asynchronous communication model based on linear logic, Formal Aspects of Computing, 1994, 279-294.
Dale Miller. Forum: A Multiple-Conclusion Specification Language, Theoretical Computer Science, 1996, 165 (1), 201--232.
Dale Miller. Overview of linear logic programming, in Linear Logic in Computer Science, edited by Thomas Ehrhard, Jean-Yves Girard, Paul Ruet, and Phil Scott. Cambridge University Press. London Mathematical Society Lecture Note, Volume 316.
J.M. Foster and E.W. Elcock. ABSYS 1: An Incremental Compiler for Assertions: an Introduction , Machine Intelligence 4, Edinburgh U Press, 1969, pp. 423-429
Pat Hayes. Computation and Deduction In Proceedings of the 2nd MFCS Symposium. Czechoslovak Academy of Sciences, 1973, pp. 105-118.
Carl Hewitt (2006b) What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006.
Robert Kowalski. The Logical Way to be Artificially Intelligent CLIMA VI. Springer Verlag. 2006.