| Logic Programming |
Article Index for Logic |
Articles about Logic Programming |
Website Links For Logic |
Information AboutLogic Programming |
|
There are also concurrent logic programming languages (not based on backtracking) derived from Planner (''e.g.,'' Ether ) and derived from Prolog (see Shapiro {Link without Title} for a survey). BASIS IN MATHEMATICAL LOGIC The point of logic programming is to bring the style of Mathematical Logic to computer programming. Mathematicians and philosophers find logic a successful tool for developing bodies of theory. Many problems are naturally expressed as a theory. To say a problem needs solving is often equivalent to asking if a new hypothesis is consistent with an existing theory. Logic provides a way to prove whether the question is true or false. The process of constructing a proof is well-known, so logic is thought to be a reliable way to answer questions. Logical programming systems automate this process. Artificial Intelligence was an important influence on the development of logic programming. PROLOG Prolog was an early programming language that was billed by its designers as being based on mathematical logic. The basis for the claim that Prolog was that it used backward chaining from goal to subgoal (as in Planner ). Schematically, the process is: goal :- subgoal1, ..., subgoaln. which states that in order to prove goal, it is sufficient to prove subgoal1 through subgoaln. Limitations of Prolog as logic programming However, Prolog did not include the ''negation'' or '' Disjunction '' of mathematical logic because both individually and together they cause a lot of trouble for the Prolog interpreter. For example if negation were included, the following Prolog program ''not'' Q. Q :- P. would be unable to prove ''not'' P even though it follows by the rules of mathematical logic. This is an illustration of the fact that Prolog is unable to prove many of the logical consequences that follow from a declarative reading of its programs. However, certain dialects do implement Negation As Failure typically using the characters \+ or '''~'''. LIMITATIONS OF USING MATHEMATICAL LOGIC FOR PROGRAMMING John McCarthy proposed that mathematical logic be used as the foundation for the epistemology of computer systems. Under the leadership of Marvin Minsky and Seymour Papert a different approach based on procedural approaches developed at MIT. When Planner was developed, the question arose about the relationship between the two approaches. Robert Kowalski developed the thesis that “computation could be subsumed by deduction” and quoted with approval “Computation is controlled deduction.” which he attributed to Pat Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes, Carl Hewitt developed the thesis that logical deduction was incapable of carrying out concurrent computation in open systems. (See Indeterminacy In Computation .) The answer to the question about the relationship between the logical and procedural approaches is that the procedural approach has a different mathematical semantics (see Denotational Semantics ) from the semantics of mathematical logic (see Model Theory ). CONCURRENT LOGIC PROGRAMMING Keith Clark , Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog -like concurrent message passing systems using unification of shared variables and data structure streams for messages. Efforts were made to base these systems on mathematical logic, and they were used as the basis of the Japanese Fifth Generation Project (ICOT) . Like the Actor Model , the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy. This was the basis of an argument by Carl Hewitt and Gul Agha {Link without Title} claiming that the Prolog-like concurrent systems were neither deductive nor logical. HIGHER-ORDER LOGIC PROGRAMMING Several researchers have extended logic programming with Higher-order Programming features derived from Higher-order Logic , such as predicate variables. Such languages include the Prolog extensions HiLog and λProlog . APPLICATION DOMAINS
HISTORY Logic Programming is an idea that has been investigated in the context of artificial intelligence since at least the time of John McCarthy {Link without Title} which proposed :"programs to manipulate in a suitable formal language (most likely a part of the predicate calculus) common instrumental statements. The basic program will draw immediate conclusions from a list of premises. These conclusions will be either declarative or imperative sentences. When an imperative sentence is deduced the program takes a corresponding action.” McCarthy justified his proposal as follows :"'The main advantages we expect the ''advice taker'' to have is that its behavior will be improvable merely by making statements to it, telling it about its symbolic environment and what is wanted from it. To make these statements will require little if any knowledge of the program or the previous knowledge of the advice taker. One will be able to assume that the advice taker will have available to it a fairly wide class of immediate logical consequences of anything it is told and its previous knowledge. This property is expected to have much in common with what makes us describe certain humans as having common sense. We shall therefore say that ''a program has common sense if it automatically deduces for itself a sufficiently wide class of immediate consequences of anything it is told and what it already knows''." SEE ALSO
REFERENCES
EXTERNAL LINKS
|
|
|