Prolog is a logic programming language that has its origins in artificial intelligence , automated theorem proving and computational linguistics .
71-700: Prolog has its roots in first-order logic , a formal logic , and 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 , and automated planning , as well as its original intended field of use, natural language processing . Prolog
142-400: A domain of discourse that specifies the range of the quantifiers. The result is that each term is assigned an object that it represents, each predicate is assigned a property of objects, and each sentence is assigned a truth value. In this way, an interpretation provides semantic meaning to the terms, predicates, and formulas of the language. The study of the interpretations of formal languages
213-421: A concise meta-circular evaluator (also called meta-interpreter ) for pure Prolog code: 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
284-453: A definite truth value. Quantifiers can be applied to variables in a formula. The variable x in the previous formula can be universally quantified, for instance, with the first-order sentence "For every x , if x is a philosopher, then x is a scholar". The universal quantifier "for every" in this sentence expresses the idea that the claim "if x is a philosopher, then x is a scholar" holds for all choices of x . The negation of
355-540: A few straightforward rewriting rules, resulting in ordinary Prolog clauses. Most notably, the rewriting equips the predicate with two additional arguments, which can be used to implicitly thread state around, analogous to monads in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to difference lists. Prolog is a homoiconic language and provides many facilities for reflective programming (reflection). Its implicit execution strategy makes it possible to write
426-418: A fixed, infinite set of non-logical symbols for all purposes: When the arity of a predicate symbol or function symbol is clear from context, the superscript n is often omitted. In this traditional approach, there is only one language of first-order logic. This approach is still common, especially in philosophically oriented books. A more recent practice is to use different non-logical symbols according to
497-406: A formula such as Phil( x ) is true must depend on what x represents. But the sentence ∃ x Phil( x ) will be either true or false in a given interpretation. In mathematics, the language of ordered abelian groups has one constant symbol 0, one unary function symbol −, one binary function symbol +, and one binary relation symbol ≤. Then: The axioms for ordered abelian groups can be expressed as
568-427: A given query in a list. This can be used for list comprehension . For example, perfect numbers equal the sum of their proper divisors: 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: When P is a predicate that for all X , P(X,Y) unifies Y with
639-416: A history of first-order logic and how it came to dominate formal logic, see José Ferreirós (2001). While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates and quantification . A predicate evaluates to true or false for an entity or entities in the domain of discourse . Consider the two sentences " Socrates is a philosopher" and " Plato
710-429: 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
781-422: A mathematical function In economics, a factor of production , a resource employed to produce goods and services Advice (opinion) Impute (disambiguation) Output (disambiguation) Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title Input . If an internal link led you here, you may wish to change the link to point directly to
SECTION 10
#1732772359324852-527: A semi-colon ; . There are guidelines on good programming practice to improve code efficiency, readability and maintainability. Here follow some example programs written in Prolog. Example of a basic query in a couple of popular Prolog dialects: This comparison shows the prompt ("?-" vs "| ?-") and resolution status ("true." vs "yes", "false." vs "no") can differ from one Prolog implementation to another. Any computation can be expressed declaratively as
923-583: A sequence of state transitions. As an example, an optimizing compiler with three optimization passes could be implemented as a relation between an initial program and its optimized form: or equivalently using DCG notation: The quicksort sorting algorithm, relating a list to its sorted version: A design pattern is a general reusable solution to a commonly occurring problem in software design . Some design patterns in Prolog are skeletons, techniques, cliches, program schemata, logic description schemata, and higher-order programming . A higher-order predicate
994-482: A set of sentences in the language. For example, the axiom stating that the group is commutative is usually written ( ∀ x ) ( ∀ y ) [ x + y = y + x ] . {\displaystyle (\forall x)(\forall y)[x+y=y+x].} An interpretation of a first-order language assigns a denotation to each non-logical symbol (predicate symbol, function symbol, or constant symbol) in that language. It also determines
1065-410: A single symbol on the left side), except that the set of symbols may be allowed to be infinite and there may be many start symbols, for example the variables in the case of terms . The set of terms is inductively defined by the following rules: Only expressions which can be obtained by finitely many applications of rules 1 and 2 are terms. For example, no expression involving a predicate symbol
1136-560: 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 . For programming in the large , Prolog provides a module system , which is in the ISO Standard. However, while most Prolog systems support structuring the code into modules, virtually no implementation adheres to
1207-399: A single variable. In general, predicates can take several variables. In the first-order sentence "Socrates is the teacher of Plato", the predicate "is the teacher of" takes two variables. An interpretation (or model) of a first-order formula specifies what each predicate means, and the entities that can instantiate the variables. These entities form the domain of discourse or universe, which
1278-429: A ternary predicate symbol. However, ∀ x x → {\displaystyle \forall x\,x\rightarrow } is not a formula, although it is a string of symbols from the alphabet. The role of the parentheses in the definition is to ensure that any formula can only be obtained in one way—by following the inductive definition (i.e., there is a unique parse tree for each formula). This property
1349-410: Is Polish notation , in which one writes → {\displaystyle \rightarrow } , ∧ {\displaystyle \wedge } and so on in front of their arguments rather than between them. This convention is advantageous in that it allows all punctuation symbols to be discarded. As such, Polish notation is compact and elegant, but rarely used in practice because it
1420-402: Is a Turing-complete, general-purpose programming language, which is well-suited for intelligent knowledge-processing applications. In Prolog, program logic is expressed in terms of relations, and a computation is initiated by running a query over these relations. Relations and queries are constructed using Prolog's single data type, the term . Relations are defined by clauses . Given a query,
1491-452: Is a philosopher" alone does not have a definite truth value of true or false, and is akin to a sentence fragment. Relationships between predicates can be stated using logical connectives . For example, the first-order formula "if x is a philosopher, then x is a scholar", is a conditional statement with " x is a philosopher" as its hypothesis, and " x is a scholar" as its conclusion, which again needs specification of x in order to have
SECTION 20
#17327723593241562-416: Is a philosopher". In propositional logic , these sentences themselves are viewed as the individuals of study, and might be denoted, for example, by variables such as p and q . They are not viewed as an application of a predicate, such as isPhil {\displaystyle {\text{isPhil}}} , to any particular objects in the domain of discourse, instead viewing them as purely an utterance which
1633-458: Is a predicate that takes one or more other predicates as arguments. Although support for higher-order programming takes Prolog outside the domain of first-order logic, which does not allow quantification over predicates, ISO Prolog now has some built-in higher-order predicates such as call/1 , call/2 , call/3 , findall/3 , setof/3 , and bagof/3 . Furthermore, since arbitrary Prolog goals can be constructed and evaluated at run-time, it
1704-426: Is a set of predicates. For example, the following Prolog program, which defines some family relations, has four predicates: 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
1775-416: Is a term. The set of formulas (also called well-formed formulas or WFFs ) is inductively defined by the following rules: Only expressions which can be obtained by finitely many applications of rules 1–5 are formulas. The formulas obtained from the first two rules are said to be atomic formulas . For example: is a formula, if f is a unary function symbol, P a unary predicate symbol, and Q
1846-417: Is always true. Given the above fact, one can ask: is socrates a human? what things are humans? Clauses with bodies are called rules . An example of a rule is: If we add that rule and ask what things are mortals? 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
1917-469: Is bound in φ if all occurrences of x in φ are bound. Intuitively, a variable symbol is free in a formula if at no point is it quantified: in ∀ y P ( x , y ) , the sole occurrence of variable x is free while that of y is bound. The free and bound variable occurrences in a formula are defined inductively as follows. For example, in ∀ x ∀ y ( P ( x ) → Q ( x , f ( x ), z )) , x and y occur only bound, z occurs only free, and w
1988-525: Is called formal semantics . What follows is a description of the standard or Tarskian semantics for first-order logic. (It is also possible to define game semantics for first-order logic , but aside from requiring the axiom of choice , game semantics agree with Tarskian semantics for first-order logic, so game semantics will not be elaborated herein.) Input [REDACTED] Look up input in Wiktionary,
2059-403: Is called chronological backtracking . For example, given the family relation program defined above, the following query will be evaluated to true: 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.,
2130-444: Is easy to write higher-order predicates like maplist/2 , which applies an arbitrary predicate to each member of a given list, and sublist/3 , which filters elements that satisfy a given predicate, also allowing for currying . To convert solutions from temporal representation (answer substitutions on backtracking) to spatial representation (terms), Prolog has various all-solutions predicates that collect all answer substitutions of
2201-407: Is either true or false. However, in first-order logic, these two sentences may be framed as statements that a certain individual or non-logical object has a property. In this example, both sentences happen to have the common form isPhil ( x ) {\displaystyle {\text{isPhil}}(x)} for some individual x {\displaystyle x} , in the first sentence
Prolog - Misplaced Pages Continue
2272-400: 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: enumerates all valid answers on backtracking. Notice that with
2343-424: Is hard for humans to read. In Polish notation, the formula: becomes "∀x∀y→Pfx¬→ PxQfyxz". In a formula, a variable may occur free or bound (or both). One formalization of this notion is due to Quine, first the concept of a variable occurrence is defined, then whether a variable occurrence is free or bound, then whether a variable symbol overall is free or bound. In order to distinguish different occurrences of
2414-412: Is known as unique readability of formulas. There are many conventions for where parentheses are used in formulas. For example, some authors use colons or full stops instead of parentheses, or change the places in which parentheses are inserted. Each author's particular definition must be accompanied by a proof of unique readability. For convenience, conventions have been developed about the precedence of
2485-488: Is neither because it does not occur in the formula. Free and bound variables of a formula need not be disjoint sets: in the formula P ( x ) → ∀ x Q ( x ) , the first occurrence of x , as argument of P , is free while the second one, as argument of Q , is bound. A formula in first-order logic with no free variable occurrences is called a first-order sentence . These are the formulas that will have well-defined truth values under an interpretation. For example, whether
2556-564: 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: First-order logic First-order logic —also called predicate logic , predicate calculus , quantificational logic —is a collection of formal systems used in mathematics , philosophy , linguistics , and computer science . First-order logic uses quantified variables over non-logical objects, and allows
2627-448: 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). Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a resolution refutation of the negated query. The resolution method used by Prolog is called SLD resolution . If the negated query can be refuted, it follows that
2698-712: Is sometimes understood in a more formal sense as just a set of sentences in first-order logic. The term "first-order" distinguishes first-order logic from higher-order logic , in which there are predicates having predicates or functions as arguments, or in which quantification over predicates, functions, or both, are permitted. In first-order theories, predicates are often associated with sets. In interpreted higher-order theories, predicates may be interpreted as sets of sets. There are many deductive systems for first-order logic which are both sound , i.e. all provable statements are true in all models; and complete , i.e. all statements which are true in all models are provable. Although
2769-632: Is studied in the foundations of mathematics . Peano arithmetic and Zermelo–Fraenkel set theory are axiomatizations of number theory and set theory , respectively, into first-order logic. No first-order theory, however, has the strength to uniquely describe a structure with an infinite domain, such as the natural numbers or the real line . Axiom systems that do fully describe these two structures, i.e. categorical axiom systems, can be obtained in stronger logics such as second-order logic . The foundations of first-order logic were developed independently by Gottlob Frege and Charles Sanders Peirce . For
2840-447: Is the term . Terms are either atoms , numbers , variables or compound terms . Special cases of compound terms: Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses . Two types of Horn clauses are used to define Prolog programs: rules and facts. A rule is of the form and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called
2911-425: Is the case of Logtalk . GNU Prolog initially diverted from ISO modules, opting instead for Contextual Logic Programming , in which unit (module) loading and unloading can be made dynamically. Ciao designed a strict module system that, while being basically compatible with the de-facto standard used by other Prolog systems, is amenable to precise static analysis, supports term hiding, and facilitates programming in
Prolog - Misplaced Pages Continue
2982-428: Is the foundation of first-order logic. A theory about a topic, such as set theory, a theory for groups, or a formal theory of arithmetic , is usually a first-order logic together with a specified domain of discourse (over which the quantified variables range), finitely many functions from that domain to itself, finitely many predicates defined on that domain, and a set of axioms believed to hold about them. "Theory"
3053-610: Is usually required to be a nonempty set. For example, consider the sentence "There exists x such that x is a philosopher." This sentence is seen as being true in an interpretation such that the domain of discourse consists of all human beings, and that the predicate "is a philosopher" is understood as "was the author of the Republic ." It is true, as witnessed by Plato in that text. There are two key parts of first-order logic. The syntax determines which finite sequences of symbols are well-formed expressions in first-order logic, while
3124-459: The Löwenheim–Skolem theorem . Though signatures might in some cases imply how non-logical symbols are to be interpreted, interpretation of the non-logical symbols in the signature is separate (and not necessarily fixed). Signatures concern syntax rather than semantics. In this approach, every non-logical symbol is of one of the following types: The traditional approach can be recovered in
3195-419: The logical consequence relation is only semidecidable , much progress has been made in automated theorem proving in first-order logic. First-order logic also satisfies several metalogical theorems that make it amenable to analysis in proof theory , such as the Löwenheim–Skolem theorem and the compactness theorem . First-order logic is the standard for the formalization of mathematics into axioms , and
3266-513: The semantics determines the meanings behind these expressions. Unlike natural languages, such as English, the language of first-order logic is completely formal, so that it can be mechanically determined whether a given expression is well formed . There are two key types of well-formed expressions: terms , which intuitively represent objects, and formulas , which intuitively express statements that can be true or false. The terms and formulas of first-order logic are strings of symbols , where all
3337-404: The truth value of certain special predicates may have some deliberate side effect , such as printing a value to the screen. Because of this, the programmer is permitted to use some amount of conventional imperative programming when the logical paradigm is inconvenient. It has a purely logical subset, called "pure Prolog", as well as a number of extralogical features. Prolog's single data type
3408-589: The Prolog engine attempts to find a resolution refutation of the negated query. If the negated query can be refuted, i.e., an instantiation for all free variables is found that makes the union of clauses and the singleton set consisting of the negated query false, it follows that the original query, with the found instantiation applied, is a logical consequence of the program. This makes Prolog (and other logic programming languages) particularly useful for database, symbolic mathematics , and language parsing applications. Because Prolog allows impure predicates , checking
3479-500: The application one has in mind. Therefore, it has become necessary to name the set of all non-logical symbols used in a particular application. This choice is made via a signature . Typical signatures in mathematics are {1, ×} or just {×} for groups , or {0, 1, +, ×, <} for ordered fields . There are no restrictions on the number of non-logical symbols. The signature can be empty , finite, or infinite, even uncountable . Uncountable signatures occur for example in modern proofs of
3550-428: The code as stated above, the query ?- sibling(sally, sally). also succeeds. One would insert additional goals to describe the relevant restrictions, if desired. The built-in Prolog predicate \+/1 provides negation as failure , which allows for non-monotonic reasoning. The goal \+ illegal(X) in the rule is evaluated as follows: Prolog attempts to prove illegal(X) . If a proof for that goal can be found,
3621-407: 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
SECTION 50
#17327723593243692-768: The free dictionary. Input may refer to: Computing [ edit ] Input (computer science) , the act of entering data into a computer or data processing system Information , any data entered into a computer or data processing system Input device Input method Input port (disambiguation) Input/output (I/O), in computing Other [ edit ] Input (talk show) Input (typeface) International Public Television Screening Conference (INPUT), an international public television organization Input (online magazine) , an online technology and culture magazine owned by Bustle Digital Group See also [ edit ] All pages with titles containing Input Independent variable in
3763-476: The identical symbol x , each occurrence of a variable symbol x in a formula φ is identified with the initial substring of φ up to the point at which said instance of the symbol x appears. Then, an occurrence of x is said to be bound if that occurrence of x lies within the scope of at least one of either ∃ x {\displaystyle \exists x} or ∀ x {\displaystyle \forall x} . Finally, x
3834-482: The interpretation at hand. Logical symbols are a set of characters that vary by author, but usually include the following: Not all of these symbols are required in first-order logic. Either one of the quantifiers along with negation, conjunction (or disjunction), variables, brackets, and equality suffices. Other logical symbols include the following: Non-logical symbols represent predicates (relations), functions and constants. It used to be standard practice to use
3905-435: The large. XSB takes a different approach and offers an atom-based module system. The latter two Prolog systems allow controlling the visibility of terms in addition to that of predicates. There is a special notation called definite clause grammars (DCGs). A rule defined via -->/2 instead of :-/2 is expanded by the preprocessor ( expand_term/2 , a facility analogous to macros in other languages) according to
3976-415: 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
4047-419: The logical operators, to avoid the need to write parentheses in some cases. These rules are similar to the order of operations in arithmetic. A common convention is: Moreover, extra punctuation not required by the definition may be inserted—to make formulas easier to read. Thus the formula: might be written as: In some fields, it is common to use infix notation for binary relations and functions, instead of
4118-419: The logical symbol ∧ {\displaystyle \land } always represents "and"; it is never interpreted as "or", which is represented by the logical symbol ∨ {\displaystyle \lor } . However, a non-logical predicate symbol such as Phil( x ) could be interpreted to mean " x is a philosopher", " x is a man named Philip", or any other unary predicate depending on
4189-406: The modern approach, by simply specifying the "custom" signature to consist of the traditional sequences of non-logical symbols. The formation rules define the terms and formulas of first-order logic. When terms and formulas are represented as strings of symbols, these rules can be used to write a formal grammar for terms and formulas. These rules are generally context-free (each production has
4260-526: The modules part of the ISO standard. Instead, most Prolog systems have decided to support as de-facto module standard the Quintus / SICStus module system. However, further convenience predicates concerning modules are provided by some implementations only and often have subtle differences in their semantics. Some systems chose to implement module concepts as source-to-source compilation into base ISO Prolog, as
4331-399: 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
SECTION 60
#17327723593244402-442: The prefix notation defined above. For example, in arithmetic, one typically writes "2 + 2 = 4" instead of "=(+(2,2),4)". It is common to regard formulas in infix notation as abbreviations for the corresponding formulas in prefix notation, cf. also term structure vs. representation . The definitions above use infix notation for binary connectives such as → {\displaystyle \to } . A less common convention
4473-447: The proof procedure is complete. In particular, the query ?- legal(X). now cannot be used to enumerate all things that are legal. In Prolog, loading code is referred to as consulting . Prolog can be used interactively by entering queries at the Prolog prompt ?- . If there is no solution, Prolog writes no . If a solution exists then it is printed. If there are multiple solutions to the query, then these can be requested by entering
4544-418: The query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded. Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, one difference being that multiple clause heads can match a given call. In that case,
4615-403: 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: which is equivalent to the rule: The built-in predicate true/0
4686-415: The sentence "For every x , if x is a philosopher, then x is a scholar" is logically equivalent to the sentence "There exists x such that x is a philosopher and x is not a scholar". The existential quantifier "there exists" expresses the idea that the claim " x is a philosopher and x is not a scholar" holds for some choice of x . The predicates "is a philosopher" and "is a scholar" each take
4757-430: The symbols together form the alphabet of the language. As with all formal languages , the nature of the symbols themselves is outside the scope of formal logic; they are often regarded simply as letters and punctuation symbols. It is common to divide the symbols of the alphabet into logical symbols , which always have the same meaning, and non-logical symbols , whose meaning varies by interpretation. For example,
4828-406: The system creates a choice-point, unifies the goal with the clause head of the first alternative, and continues with the goals of that first alternative. If any goal fails in the course of executing the program, all variable bindings that were made since the most recent choice-point was created are undone, and execution continues with the next alternative of that choice-point. This execution strategy
4899-411: The system. For example, the predicate write/1 displays a term on the screen. Iterative algorithms can be implemented by means of recursive predicates. Consider the parent_child/2 predicate defined in the family relation program above. The following Prolog program defines the ancestor relation: 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
4970-458: The use of sentences that contain variables. Rather than propositions such as "all men are mortal", in first-order logic one can have expressions in the form "for all x , if x is a man, then x is mortal"; where "for all x" is a quantifier, x is a variable, and "... is a man " and "... is mortal " are predicates. This distinguishes it from propositional logic , which does not use quantifiers or relations ; in this sense, propositional logic
5041-417: The value of the variable x is "Socrates", and in the second sentence it is "Plato". Due to the ability to speak about non-logical individuals along with the original logical connectives, first-order logic includes propositional logic. The truth of a formula such as " x is a philosopher" depends on which object is denoted by x and on the interpretation of the predicate "is a philosopher". Consequently, " x
#323676