Prolog

Prolog++ is an object-oriented toolkit for the Prolog logic programming language. It allows classes and class hierarchies to be created within Prolog programs. Prolog++ was developed by LPA and first released in 1989 for MS-DOS PCs. Support for other platforms was added, and a second version was released in 1995. A book entitled 'Prolog++ The Power of Object-Oriented and Logic Programming' by Chris Moss was published by Addison-Wesley in 1994. Currently, Prolog++ is available as an add-on to LPA Prolog for Windows. Three other approaches to object-oriented Prolog include PDC Visual Prolog (once known as Borland Turbo Prolog), SICStus Prolog and the almost implementation-neutral Logtalk framework.

Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics. Prolog has its roots in first-order logic, a formal logic. Unlike many other programming languages, Prolog is intended primarily as a declarative programming language: the program is a set of facts and rules, which define relations. A computation is initiated by running a query over the program. Prolog was one of the first logic programming languages and remains the most popular such language today, with several free and commercial implementations available. The language has been used for theorem proving, expert systems, term rewriting, type systems, automated planning, and question answering as well as its original intended field of use, natural language processing. Prolog is a Turing-complete, general-purpose programming language, which is well-suited for intelligent knowledge-processing applications. Head :- Body. and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called the rule's goals. The built-in logical operator ,/2 (meaning an arity 2 operator with name , ) denotes conjunction of goals, and ;/2 denotes disjunction. Conjunctions and disjunctions can only appear in the body, not in the head of a rule. Clauses with empty bodies are called facts. An example of a fact is: human(socrates). which is equivalent to the rule: human(socrates) :- true. The built-in predicate true/0 is always true. Given the above fact, one can ask: is socrates a human? ?- human(socrates). Yes what things are humans? ?- human(X). X = socrates Clauses with bodies are called rules. An example of a rule is: mortal(X) :- human(X). If we add that rule and ask what things are mortals? ?- mortal(X). X = socrates A predicate (or procedure definition) is a collection of clauses whose heads have the same name and arity. We use the notation name/arity to refer to predicates. A logic program is a set of predicates. For example, the following Prolog program, which defines some family relations, has four predicates: mother_child(trude, sally). father_child(tom, sally). father_child(tom, erica). father_child(mike, tom). sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y), not(X = Y). parent_child(X, Y) :- father_child(X, Y). parent_child(X, Y) :- mother_child(X, Y). Predicate father_child/2 has three clauses, all of which are facts, and predicate parent_child/2 has two clauses, both are rules. Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example, length/2 can be used to determine the length of a list ( length(List, L) , given a list List ), and to generate a list skeleton of a given length ( length(X, 5) ), and to generate both list skeletons and their lengths together ( length(X, L) ). Similarly, append/3 can be used both to append two lists ( append(ListA, ListB, X) given lists ListA and ListB ), and to split a given list into parts ( append(X, Y, List) , given a list List ). For this reason, a comparatively small set of library predicates suffices for many Prolog programs. As a general purpose language, Prolog also provides various built-in predicates to perform routine activities like input/output, using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and are only useful for the side-effects they exhibit on the system. For example, the predicate write/1 displays a term on the screen. Consider the parent_child/2 predicate defined in the family relation program above. The following Prolog program defines the ancestor relation: ancestor(X, Y) :- parent_child(X, Y). ancestor(X, Y) :- parent_child(X, Z), ancestor(Z, Y). It expresses that X is an ancestor of Y if X is parent of Y or X is parent of an ancestor of Y. It is recursive because it is defined in terms of itself (there is a call to predicate ancestor/2 in the body of the second clause). ?- sibling(sally, erica). Yes This is obtained as follows: Initially, the only matching clause-head for the query sibling(sally, erica) is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction (parent_child(Z, sally), parent_child(Z, erica)) . The next goal to be proved is the leftmost one of this conjunction, i.e., parent_child(Z, sally) . Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is father_child(Z, sally) . This goal can be proved using the fact father_child(tom, sally) , so the binding Z = tom is generated, and the next goal to be proved is the second part of the above conjunction: parent_child(tom, erica) . Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like: ?- father_child(Father, Child). enumerates all valid answers on backtracking. Notice that with the code as stated above, the query ?- sibling(sally, sally). also succeeds. One would insert additional goals to describe the relevant restrictions, if desired. legal(X) :- \+ illegal(X). is evaluated as follows: Prolog attempts to prove illegal(X) . If a proof for that goal can be found, the original goal (i.e., \+ illegal(X) ) fails. If no proof can be found, the original goal succeeds. Therefore, the \+/1 prefix operator is called the "not provable" operator, since the query ?- \+ Goal. succeeds if Goal is not provable. This kind of negation is sound if its argument is "ground" (i.e. contains no variables). Soundness is lost if the argument contains variables and the proof procedure is complete. In particular, the query ?- legal(X). now cannot be used to enumerate all things that are legal. program_optimized(Prog0, Prog) :- optimization_pass_1(Prog0, Prog1), optimization_pass_2(Prog1, Prog2), optimization_pass_3(Prog2, Prog). or equivalently using DCG notation: program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3. partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :- ( X @ Smalls = [X|Rest], partition(Xs, Pivot, Rest, Bigs) ; Bigs = [X|Rest], partition(Xs, Pivot, Smalls, Rest) ). quicksort([]) --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger). perfect(N) :- between(1, inf, N), U is N // 2, findall(D, (between(1,U,D), N mod D =:= 0), Ds), sumlist(Ds, N). This can be used to enumerate perfect numbers, and to check if a number is perfect. As another example, the predicate maplist applies a predicate P to all corresponding positions in a pair of lists: maplist(_, [], []). maplist(P, [X|Xs], [Y|Ys]) :- call(P, X, Y), maplist(P, Xs, Ys). When P is a predicate that for all X , P(X,Y) unifies Y with a single unique value, maplist(P, Xs, Ys) is equivalent to applying the map function in functional programming as Ys = map(Function, Xs) . Higher-order programming style in Prolog was pioneered in HiLog and λProlog. solve(true). solve((Subgoal1,Subgoal2)) :- solve(Subgoal1), solve(Subgoal2). solve(Head) :- clause(Head, Body), solve(Body). where true represents an empty conjunction, and clause(Head, Body) unifies with clauses in the database of the form Head :- Body . Since Prolog programs are themselves sequences of Prolog terms ( :-/2 is an infix operator) that are easily read and inspected using built-in mechanisms (like read/1 ), it is possible to write customized interpreters that augment Prolog with domain-specific features. For example, Sterling and Shapiro present a meta-interpreter that performs reasoning with uncertainty, reproduced here with slight modifications: solve(true, 1) :- !. solve((Subgoal1,Subgoal2), Certainty) :- !, solve(Subgoal1, Certainty1), solve(Subgoal2, Certainty2), Certainty is min(Certainty1, Certainty2). solve(Goal, 1) :- builtin(Goal), !, Goal. solve(Head, Certainty) :- clause_cf(Head, Body, Certainty1), solve(Body, Certainty2), Certainty is Certainty1 * Certainty2. This interpreter uses a table of built-in Prolog predicates of the form builtin(A is B). builtin(read(X)). % etc. and clauses represented as clause_cf(Head, Body, Certainty) . Given those, it can be called as solve(Goal, Certainty) to execute Goal and obtain a measure of certainty about the result. turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :- symbol(Rs0, Sym, RsRest), once(rule(Q0, Sym, Q1, NewSym, Action)), action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), perform(Q1, Ls1, Ls, Rs1, Rs). symbol([], b, []). symbol([Sym|Rs], Sym, Rs). action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). left([], [], Rs0, [b|Rs0]). left([L|Ls], Ls, Rs, [L|Rs]). A simple example Turing machine is specified by the facts: rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay). This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result: ?- turing([1,1,1], Ts). Ts = [1, 1, 1, 1] ; This illustrates how any computation can be expressed declaratively as a sequence of state transitions, implemented in Prolog as a relation between successive states of interest. ===Related languages=== The Gödel language is a strongly typed implementation of concurrent constraint logic programming. It is built on SICStus Prolog. Visual Prolog, formerly named PDC Prolog and Turbo Prolog, is a strongly typed object-oriented dialect of Prolog, which is very different from standard Prolog. As Turbo Prolog, it was marketed by Borland, but is now developed and marketed by the Danish firm Prolog Development Center (PDC) that originally produced it. Datalog is a subset of Prolog. It is limited to relationships that may be stratified and does not allow compound terms. In contrast to Prolog, Datalog is not Turing-complete. Mercury is an offshoot of Prolog geared toward software engineering in the large with a static, polymorphic type system, as well as a mode and determinism system. GraphTalk is a proprietary implementation of Warren's Abstract Machine, with additional object-oriented properties. In some ways Prolog is a subset of Planner. The ideas in Planner were later further developed in the Scientific Community Metaphor. AgentSpeak is a variant of Prolog for programming agent behavior in multi-agent systems. Erlang began life with a Prolog-based implementation and maintains much of Prolog's unification-based syntax. Pilog is a declarative language built on top of PicoLisp, that has the semantics of Prolog, but uses the syntax of Lisp. λProlog is an extension of core Prolog that features polymorphic typing, modular programming, and higher-order programming, including direct support for terms with variable-binding operators through so-called λ-tree syntax and higher-order pattern unification. ==External links==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1290048768 under CC BY-SA 4.0; modifications have been made.