By Chris Murdock and Drew Vartanian
What is Prolog?
Prolog is a high level, logic based computer programming language, who's strength comes from its ability to define rules, and use those rules to answer queries.
Prolog Tutorial - http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html
- A website containing links to tutorial pages on different aspects of the language. Provides a table of contents for quickly finding a topic of interest.
Helpful Prolog Solutions: Prolog Cookbook
- A very helpful webpage with solutions to common programming issues in terms of prolog. (ex: indexing a list)
Textbook Resource - Programming in Prolog
- This text is one that I found last summer (08') when I was intending to take an AI course in Oz. It has very straightforward wording and is does a good job describing at least the basic structure the prolog language. Recommended as a good starting point. (I have a copy in possession).
Wikipedia Page: Wikipedia: Prolog
- Prolog's wikipedia page has quite a bitof useful information on the language with some information relating to ideas that we have discussed in class.
The basic concept of prolog is to set rules for the interpreter to follow. When a user queries the code, the interpreter will search through the rules and identify if the query "succeeds" or is satisfied by the rules. Variables come in when generalizing. Scoping is interesting in Prolog since the same variables can be used in every rule. This is allowed because a variable only lasts from the beginning of a given rule to the stopping point at the end (the "."). A user can also query using the same variables that are in the code and they will "share" values while the interpreter is searching through rules. In fact a variable will not be instantiated until there is a clear and concise verification that a query has been matched/determined.
Prolog syntax consists of any number of "terms" which can be a constant, variable or structure. A constant can be either a lowercase word, or a number, but not a combination of the two (the "" can be used within a constant to make it's identity more clear). However, those rules do not apply if you put the atom in single quotes ''. Variables are any word that begins with an Uppercase letter or "". Variables are used when we are unable or unwilling to instantiate some object in our code at the time the code is written (we will look into this further in our examples). The third type of term is a structure. Structures are like a more detailed fact that describes the components of an components of an object. Structures allow for more convenience, giving the programmer the ability to group together similar items. Below we examine some simple examples representing a family tree, which is often used to demonstrate the basics of Prolog.
Example 1. Our first example shows some simple declarations of facts. A fact consists of a name and then the components describing the fact. Above, we see male(drew). The english translation of this would be "drew is male". It is being stated that drew is male. We also state that dave, same and john are male, and that jen, katie and ann are female. All terms in this example are atoms (or constants). If we were to query male(dave). it would be like asking the interpreter if dave is male, to which the response would be true or yes. We could also query male(X). where X is a variable which the interpreter will try to unify with any defined facts. In this case the response would be true, X = dave. The user would then have the option of ending the query with "return (enter)" or continue searching for more results with ";" (continuing with ";" would next return dave, followed by sam, and then john).
Example 2. This second example starts to define relationships using slightly more complicated facts. We now define the fact sibling(drew,dave). The english translation being "drew is the sibling of dave". Now it is important to understand that this does not entail that "dave is the sibling of drew", even though that would be the case in reality, Prolog does not know that and will not make that connection. Prolog only sees a name which describes a fact defined by the programmer.
Example 3. With our third example, we begin to approach rules. In most programming languages, rule would be viewed as conditionals since the ":-" is loosely translated as "if". Here we have son(X,Y):-parent(Y,X), male(X). Translation being "X is the son of Y if Y is the parent of X and X is male". We have also begun to use variables in order to make the rules more versatile. Since we are using variables, we can now query son(drew,ann). which will return true since by the definition of our "son" rule, and the facts we have defined above, drew is in fact the son of ann. Similar queries can be made with the rules for brother, sister, and daughter. If the interpreter fails to unify the query with the defined rules and facts, the response will be "false".
Example 4. The comments in the code describe the use of a structure.
Binary Search Example
Prolog syntax is based on rules, and is ussually used to answer querries. Becuase of this, there is already a method for searching lists. Normally, if you wanted to search a list to see if it conatined a value, you would use the member function, with the first paramater as the value, and the second paramater as the list, shown below:
Even though it does not make sense in prolog, we created a binary search for a numbered list. In order to do this, we had to define rules in order to find the value at the middle index in the list, and some rules to react to the value and restart the search for a new middle index. The program finds the value at a given index by recursively removing the head (first value) of the list and decreasing the index, until all the values in front of the list are eliminated. Because of this process, we needed to define the List as a constant in the first binary rule (the rule that we will be calling. The arrows represent "if" statements, with the condition before the arrow, the "then" clause right after the arrow, and the "else" clause after the semi-colon. It is an extremely inefficient binary search, and due to Prolog's nature, it usually makes more sense to just ask if the value is a member.
A more realistic approach would be to use a random access data structure. Prolog does not include any standard functionality to support this, however such behavior can be created with the help of additional libraries. SICStus Prolog provides a random number generator which could be a first step in producing a random access data structure involving the list structure supported by Prolog.
The initial state of prolog is just the simple rule or fact definition. For example, the most basic prolog program would consist of a name (or predicate) and some component which it was descibing.
male(drew). (drew is male)
For any prolog program, you must have at least a fact such as this for the interpreter to relate a query.
Example 1. This is the mathematical description of the intitial state.
Description in Java
Example 2. This is the Java code representation of Prolog's intitial state.
Assignment is really a word used in more traditional languages to describe how variables are declared or "assigned" to their values. Since Prolog does not deal with such processes in the same way, we instead describe how rules and facts are defined or related to their predicate. The process of unifying variables with values does not happen until the
Example 1. The mathematical description of the assignment state in prolog.
Description in Java
Example 2. The Java code implementation of Prolog's assignment state.
Prolog's conditional state is more a description of how it defines rules (which in practice are all conditionals). You can however, create control flow by defining several rules of the same predicate.
Example 1. This is code showing control flow usage of the conditional statement in Prolog.
Example 2. This is the mathematical description of the conditional statement in Prolog.
Description in Java
Example 3. This is the Java code implementation of Prolog's conditional statement.
File I/O and Exception/Error Handling
When interacting with the terminal (GNU or SWI), I/O in prolog is treated as in the code below:
The code allows us to ask from a terminal what happened in a specific year. Although the input output already exists naturally with quries (input when writing a query, and output when a queriy is answered), the read and write functions allow for interactive I/O.
When interacting with a file, I/O in prolog is treated as in the code below:
The calendar rule will open a file, read the information, see if each line is the year of an event, and write that date and event to another file. When reading from the file below:
calendar creates the file below:
Exception handling in prolog is done with the catch function. We use it below to make sure we can open the requested file. The first parameter of catch is the Goal, or what we want to execute (comparable to a try in C or Java). The second parameter is what exception we want to catch. By using a variable (E), it will catch any exception. The third parameter for catch is an executable (rule) that will be run in the event of an exception. Since there is no distinction between exceptions and errors in prolog, there is no separate error handling.
You can also add a throw to the goal method for a user-defined exception. In the case below, our program will try to subtract two numbers from each other:
If the inputs are integers, which is checked in the checkInt rule, then it will work fine. If they are not integers, then a user defined error, "notInt" will be thrown. The catch predicate will catch the error, setting the second parameter to the error name, and then calling error_process with the specific error. If this error is "notInt", which it should be if any error, then it will ask for integer inputs, and retry to subtraction. If, for some reason, some other error comes up, and this applies to any part of the process rule, It will print out "Unknown Error:", display the error information, and stop running subtraction.
A list of standard Prolog errors are below:
The details of each error can be seen at http://pauillac.inria.fr/~deransar/prolog/exceptions.html
Functions and Memory Management
Syntax of a function definition
Functions are not defined the same way as in functional languages. They instead are defined using rules, and conditional statements. When a rule is queried, prolog will run through all the queries in its conditional statement. If all the queries in the conditional statements return true, then the rule will be returned true, as seen in the file I/O example below:
Calendar acts like a function, where it goes through and queries all the rules in the conditional statement (after the ':-'). It even calls another function like rule, process. Process has parameters, and even presents a certain type of overloading feature, by querying different rules depending on the parameters, If Data equals 'end_of_file', then the first process is queried, and if not the second process is queried). While it may look like the process' fail should cause calendar to fail, the failures are absorbed by the repeat loop until the process is queried will 'end_of_file'. Rules can also contain variables that are set in the conditional statement, producing a return like feature, like F below:
Syntax of a function call
A function is called just like any other rule, with a query. If there are parameters for the functions, they will be atoms within the rule definition. A atom can also be set to a variable and act as a return value.
Use of functions in expressions
Prolog functions do not have actual return values. They can create return like capabilities by setting atoms in the rule, but since they do not have return values, they cannot be used in expressions.
Use of functions labels as l-values
Functions in prolog are more of a concept than an object or method. They are made up of rules and the consequences of those rules. Because of this, values cannot be set to a function. Variables cannot have the same name as the rules that define the functions, since variables begin with upper case letters, where as rules begin with lower case letters. Constants, on the other hand, can have the same name as rules, as seen in the valid rule below:
While there is no distinction in syntax between the two, since rules, and thus functions, cannot be used in expressions or assignments, prolog will be able to tell which the program is referencing.
Side Effects of Functions
Prolog is in thoery suppose to be a delcarative language (i.e. one that defines relationships between facts and rules and than answers queries relating those facts and rules with the aid of a logic engine.) Using side effects in Prolog, takes prolog out of the world of strict logic. In fact, using side effects in some cases will make debugging nearly impossible.
Semantics of a function call
Prolog does not have functions as defined by traditional languages. However, Prolog is able to achieve function like behavior through it's conditional statements. When a conditional with many processes is defined in Prolog script, the interpreter will try to query each of those conditions, creating what can be considered function like behavior. Due to the lack of a traditional function definition, the semantics of a function call can be considered the same as the semantics of the conditional state.
In Prolog, there is no standard memory management capability on the user side. On the compiler side, there is constant memory management going on, and there are many conversations going on about how to make it more efficient. While this has little to no effect on the code, it makes a large difference in the execution and optimization of the system. The memory architecture used when creating this memory management is not definitive, but in 1983, the Warren Abstract Machine (WAM) was introduced and is now more or less used as the standard architecture. The GNU and SWI compilers are both based on the WAM. One paper that seems to be a standard reference on the WAM and its memory management capabilities is Understanding Memory Management in Prolog Systems available at SpringerLink.
Here are some haikus for your enjoyment:
Facts Rule Haiku
The following haiku is about one of the most basic ideas behind prolog.
The following haiku will actually preform subtraction on the two inputs and then prints the result.
note: the "-" is named "minus."
From the subtraction haiku above, we also created an addition haiku.
While the told call doesn't really do anything, it does make the break between the second line and the third line a little smother, plus it sounds a little like Yoda. note: the "+" is read "plus."
The following haiku demonstrates exceptions, and is about baseball.
A little note, the "write" is actually read as "right", since third base is to the right of almost all the players on the field. It will also print "At Third!" if you query "ifYouPlayBaseball."