Prolog: A Programmer's Introduction
Prolog, short for Programmable Logic, is a declarative logic language which reasons about truth within a closed universe. The language dates back to the 1970s, originally intended to produce natural language procssors, however was expanded during the 1980s to provide expert systems. As a logic language, Prolog has a drastically different grammar and syntax; missing many of the control structures you would typically find in a mature structured languages. These are replaced with unification and backtracking.
There have been many successors to Prolog. From the more esoteric such as Mercury, to those sitting on the fringes of popularity such as Erlang. Mercury continued within the vien of declaritive inferrence langauges, evolving into a self hosting native compiler with an alternative I/O implementation. Erlang on the other hand retained the funky syntax style and chose a functional approach. Prolog is a grandfather of many langauges within the logcial paradigm.
Grab yourself a Prolog environment, and let us begin playing with Prolog's language features! I recommend SWI-Prolog, however there are several open source systems available. Many Prolog systems strive for compatibility, adhering to the ISO and Edinburgh standards. If you compile from source or use the Ubuntu packages you enter the interpreter using the command swi-prolog. This dumps features, versionining, and copyright information then provides a prompt ?- .
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.2.6-1-gf51d197) Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?-
Here we can enter the query a = a., which the interpreter will respond true.. on the next line. In Prolog the a is interpreted as a symbol, called an atom. The equality infix operator between the two atoms states we are unifying the two operands. Unifying a symbol with itself is considered true. Unifying two different atoms, such as a = b. will cause the interpreter to respond false. The period, or full-stop, is a postfix operator closing our statement. When the interpret reaches the full stop it evaluates our statement, responding that our statement is true.
Variables
Atoms within Prolog begin with a lowercase character. If you were to use a capital letter then Prolog would interpret the token as a variable. A variable initially exists as an ubound or unground value. When you unify a variable with a ground value the variable becomes bound to that value. Entering Variable = a. at the query prompt of the interpreter we get the response Variable = A.. Unification of two unbound variables results in the values of those variables being linked. Consider the following exchange made to the interpreter:
?- FirstVariable = SecondVariable, SecondVariable = unified_value. FirstVariable = unified_value, SecondVariable = unfied_value.
In Prolog the comma character is a built-in infix operator defined as a logical and operator. For this statement to succeed all clauses must also succeed, which easily occurs in the above. So what happens when we attempt to unify each variable to a different value?
?- FirstVariable = SecondVariable, FirstVariable = some_value, SecondVariable = unified_value. false.
The Prolog system informs us the system is unable to find a true solution for our hypothesis. This is because the third clause attempts to assign SecondVariable to a different value called unified_value. Behind the scenes when Prolog attempts to unify SecondVariable with the atom unified_value. The Prolog engine is aware that the value of SecondVariable is equivialnt to the value of FirstVariable, which has been bound to some_value. some_value is not equal to unified_value, so the statement fails. The Prolog engine then backtracks through the statements in an attempt to find an alternate solution. In a simple series of statements such as this there are no alternate solutions, so the statement fails to be evaluated as true.
To exit the interpreter type halt.. This will return you to your shell.
Backtracking
Considering a more complex example such as the following exchange. Press the semi-colon key after each response stanza.
?- member( FirstListElement, [this, is, a, fun, list] ), | member( SecondListElement, [this, fun, list] ), | FirstListElement = SecondListElement. FirstListElement = SecondListElement, SecondListElement = this ; FirstListElement = SecondListElement, SecondListElement = fun ; FirstListElement = SecondListElement, SecondListElement = list.
Each time you press the semi-colon you ask Prolog to find an additional solution. After all solutions have been exhausted then Prolog will return to the prompt. There are two constructs which haven’t been introduced yet. The square brackets denote an ordered list of elements separated by a comma. We also refer to the goal member/2. Goal member/2 is defined within the standard library and will unify the first parameter with a member of the list given as the second parameter. When Prolog attempts to resolve the variables, FirstListElement and SecondListElement are assigned the first value of their respective lists. Then Prolog attempts to unify the two variables. This succeeds and provides our first solution.
When we press the semicolon we are asking the Prolog interpreter to find an alternate solution. Prolog then backtracks to the last choice point encountered. Choice points are created when Prolog believes there may be alternate solutions provide by a given goal. In the above example the last choice point encountered was at member( SecondListElement, [this, fun, list] ). SecondListElement would then be unified with fun, which upon the next clause would fail as FirstListElement is still unified with the value. This will continue until all possible values member( SecondListElement, [this, fun, list] ), exhausting all alternatives at the choice point.
Prolog then moves to the previous choicepoint, which was with member( FirstListElement, [this, is, a, fun, list] ). From here we will again try all values for the first list, finding no matches for the atoms is or a within the second list. This appears to consume a great amount of computational power, however this is a rather naive implementation. In practice we would use a variable unified with the FirstListElement prior to the invocation of the second member/2 goal. This would allow all of the backtracking to occur within that goal, reducing computational time.
Defining your own goals
A Prolog engine works against a database of goals. Although you can create goals via the interpreter it is a cumbersome process. The easiest method to define your own goals is consult a file, which is done by invoking SWI Prolog with the s flag and providing the file name. For example swipl -s test.pl will load the file test.pl. Prolog files are typically saved with the .pl extension, however you may also encounter the .pro extension.
The remainder of this section utilizes code which builds upon itself. I have created a Github project with the contents of the completed files.
Prolog files have no special header required, however you will generally encounter a comment header with documentation and licensing of a given file. SWI Prolog supports two comments, the traditionalstyle % which denotes a comment until the end of the file or the C style /*..*/ multiline comments. Within more complex applications you will encounter module declarations, then goals. For our simple application we will use the implicit module user.
There are two types of goals. Facts which contain axiomatic truths within our closed universe, and rules which reason about the closed universe. As an example of applied Prolog, let us consider a fragment of a family tree. Consider the following facts regarding a segment of a family tree:
child( john, mary, george ). child( steve, mary, george ). child( jeff, john, ana ). child( brian, steve, isabella ).
Loading this file, or consulting in Prolog vernacular, allows us to find a person and their parents. Each fact contains a head, and a period. The head contains an atom for the name and the parameters enclosed within parenthesies. If we desired to use the correct case with the names we would need to enclose the atoms within single quotes. For this example we will keep it simple. Facts are great, however data gleaned from inference is the true power behind Prolog.
A rule in Prolog is defined with a head separated from the body by the :- operator and terminated by a period. The body follows the same rules and format given to the interpreter. The body is composed of a series of clauses separated by a conjunctive operator such as a comma. As an applied example let our application’s problem domain be determining the name of family relationships. The lowest hanging fruit is parentage, so let us define those rules first.
parent_of( Child, Parent ) :- child( Child, Parent, _ ). parent_of( Child, Parent ) :- child( Child, _, Parent ).
Terms beginning with an underscore are called anonymous variables and inform Prolog this may be any value. If we provided a named variable only used once in its place most engines would warn of a singleton variable. This sounds annoying, however this comes in handy to locate misspellings.
Our goal is to find the relationship between two people, so let us describe our solution goal. For our implementation we will place importance on the location of the person within the parameter list.
relationship( Child, Parent, parent ) :- parent_of( Child, Parent ). relationship( Parent, Child, child ) :- parent_of( Child, Parent ).
This is great, however we have not gained much over imperative programming. Let us define some additional relationships. Siblings by defintion can not the same person. In order to do so we must use the meta-predicate \+ or not/1 which is more expressive of the intent. When evaluated, the negation predicate will only succeed if the statement provided as a value fails.
sibling( Sibling1, Sibling2 ) :- parent_of( Sibling1, Parent ), parent_of( Sibling2, Parent ), not( Sibling1 = Sibling2 ) . relationship( Sibling1, Sibling2, sibling ) :- sibling( Sibling1, Sibling2 ).
Now the fun play time right? You can ask the Prolog interpreter to find all possible solutions for you using findall/3 predicate. The usage of findall/3 still feels rather strange to me still, however a very useful predicate. The first parameter contains variables you would like resolved, often referred to as a template or pattern. If we were interested in all people who are siblings then we would use a list of [P1, P2]. The second parameter is the goal we would like to find all solutions for. The third is a list results in the format given in the first parameter. For example findall( [P1,P2], relationship( P1, P2, sibling ), Result) will give the following response from the Prolog engine:
?- findall( [P1,P2], relationship( P1, P2, sibling ), R ). R = [[john, steve], [steve, john], [john, steve], [steve, john]].
Thank you for reading!
This is a living document, changing as I receive feedback from readers. I appreciate any feedback you have. Especially when you e-mail the feedback at meschbach@gmail.com!