{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# An Introduction to Prolog\n", "\n", "Prolog stands for programming in logic. Prolog programs are specified as relations and rules around the relations defined by programming in logic. The programs can be queried to determine the veracity of facts or to infer new facts using the rules. The specification of the facts and rules will be illustrated using the STAR WARS family tree as per the end of episode 8 at the end of this post (obtained from google images). Please review the family tree before proceeding with the post. Two popular interpreters are `gprolog, swipl`.\n", "\n", "\n", "The family tree will be specified in Prolog as a set of individuals and relationships between pairs of individuals. Basic facts that we encode are whether the individual (specified by the name) is a male or a female, and the child-of relationship between a pair of individuals. \n", "\n", "Following unary and binary relations will be used.\n", "\n", "+ `male(X)/female(X)/neuter(X)`, encodes the gender of `X`.\n", "+ `child(X,Y)`, encodes that `X` is a child of `Y`.\n", "\n", "The fact `the_force` is neuter in gender is stated as `neuter(the_force)`. Note the use of lower-case letters. The basic units (called atoms) all being with lower-case letters. The basic facts about the family tree as below. The basic facts from the tree are encoded as below." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "\n", "neuter(the_force).\n", "male(cliegg_lars).\n", "male(owen_lars).\n", "female(shmi_skywalker). \n", "male(anakin_skywalker).\n", "male(ruwee_naberrie).\n", "female(jobal_naberrie).\n", "female(padme_amidala).\n", "male(luke_skywalker).\n", "female(leia_organa).\n", "male(han_solo).\n", "male(kylo_ren).\n", "female(rey).\n", "\n", "child(anakin_skywalker, the_force).\n", "child(anakin_skywalker, shmi_skywalker).\n", "child(luke_skywalker, anakin_skywalker).\n", "child(luke_skywalker, padme_amidala)\n", "child(leia_organa, anakin_skywalker).\n", "child(leia_organa, padme_amidala).\n", "child(owen_lars, cleigg_lars). \n", "child(padme_amidala, ruwee_naberrie).\n", "child(padme_amidala, jobal_naberrie).\n", "child(kylo_ren, leia_organa).\n", "child(kylo_ren, han_solo)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Given the database of related facts above, we already are in a position to query it. To know the children, we can ask `child(X, han_solo)`. Prolog will evaluate the query below (queries are always prefixed with `?-`) to find all `X` such that `X` is a child of `han_solo;`." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ERROR: Caused by: ' child(X, han_solo)'. Returned: 'error(existence_error(procedure, /(child, 2)), context(/(pyrun, 2), _192))'." ] } ], "source": [ "?- child(X, han_solo)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Both the children of `anakin_skywalker` can be queried using the query `?- child(X, anakin_skywalker)`" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ERROR: Caused by: ' child(X, anakin_skywalker)'. Returned: 'error(existence_error(procedure, /(child, 2)), context(/(pyrun, 2), _440))'." ] } ], "source": [ "?- child(X, anakin_skywalker)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "We can also query the parents of `kylo_ren` using the query `child(kylo_ren, X).`\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ERROR: Caused by: ' child(kylo_ren, X)'. Returned: 'error(existence_error(procedure, /(child, 2)), context(/(pyrun, 2), _634))'." ] } ], "source": [ "?-child(kylo_ren, X)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The current facts in the prolog database do not support the fan theory that `rey` is a child of `leia` and `luke`. The query `child(rey, X)` fails to returns any parent of `rey`." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ERROR: Caused by: ' child(rey, X)'. Returned: 'error(existence_error(procedure, /(child, 2)), context(/(pyrun, 2), _804))'." ] } ], "source": [ "?- child(rey, X)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "So far, we have seen that we can use Prolog as a relational database and query for the existence of relations. Prolog can return all possible answers. Specialized versions of Prolog do exist for such data processing (see datalog).\n", "\n", "The statements above are called `facts` and `queries`. It is also possible to describe `rules` of inference in Prolog. A rule is written `q :- q`, it means `if p then q`. Rules can be logically consistent but may not have any utility in computational reasoning. A rule `p :- p` (which says `if p then p`) is correct, but it does not help us derive a proof that `p` is true. The part before `:-` is called the `head` and the part after `:-` is called the `body` of the rule. Body of a rule can have multiple conditions (combined using `and/or`). Rule `p :- a , b ; c` means `if (c or (a && b)) then p`. `,` represents the `&&` and `;` represent the `||`. \n", "\n", "Let's assume that `X` is a father of `Y` if `X` is a parent of `Y` and `X` is male or `X` is neuter. This knowledge can be described using the following rules. The body of the two rules can also be combined using the `;` operator. Now we can ask Prolog, who is the father of `anakin`?\n", "\n", "Similarly we can write a rule `mother(X,Y) :- female(X), child(Y,x)` to determine if `X` is mother of `Y`. \n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ERROR: Caused by: ' father(X,anakin_skywalker)'. Returned: 'error(existence_error(procedure, /(male, 1)), context(/(father, 2), _1046))'." ] } ], "source": [ "father(X,Y) :- male(X), child(Y,X).\n", "father(X,Y) :- neuter(X), child(Y,X).\n", "\n", "?-father(X,anakin_skywalker)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Let us try to understand the way Prolog searches for answers. We can turn the `trace` on and see the order in which Prolog tries the rules and the clauses in the body. \n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "true.\n", "ERROR: Caused by: ' father(X, anakin_skywalker)'. Returned: 'error(existence_error(procedure, /(male, 1)), context(/(father, 2), _1300))'." ] } ], "source": [ "?- trace.\n", "?- father(X, anakin_skywalker)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Prolog has to find an `X` such that either the body of the first rule is true or the body of the second rule is true. The choice for `X` is again determined by the facts starting with `male`. The clauses (parts of the body) that are proved to find `X` form the proof-tree. The proof tree for the query `father(X, anakin_skywalker)` is \n", " \n", "~~~~~ \n", " father(X,anakin_skywalker) \n", " |\n", " |\n", " -----------------------------------\n", " | |\n", " male(X) child(anakin_skywalker,X)\n", "\n", "~~~~~\n", "\n", "This tree is a simplified representation of the process followed by Prolog. The choices in the tree are evaluated from top-down left to right. This ordering is determined by order of the facts in the program. The facts (and the rules) are tried in the order they are listed in the file. If `X=clieg_lars` then Prolog goes on to check the second part of the body, whether `cleig is the father of anakin?` using the rule `child(anakin_skywalker, cleig_lars)`. The tree of choices for 'X' evaluated by Prolog is shown below\n", "\n", "![](images/starwars.jpg)\n", "\n", "The actual process used by Prolog (SLD-resolution) can be observed by using the `trace` command. The complete trace for the query (in SWI-prolog) is shown below. Spend some time on understanding the trace below. This will significantly help you understand how Prolog searches for solutions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```` \n", " [trace] ?- father(X, anakin_skywalker).\n", " Call: (8) father(_5874, anakin_skywalker) ? creep\n", " Call: (9) male(_5874) ? creep\n", " Exit: (9) male(cliegg_lars) ? creep\n", " Call: (9) child(anakin_skywalker, cliegg_lars) ? creep\n", " Fail: (9) child(anakin_skywalker, cliegg_lars) ? creep\n", " Redo: (9) male(_5874) ? creep\n", " Exit: (9) male(owen_lars) ? creep\n", " Call: (9) child(anakin_skywalker, owen_lars) ? creep\n", " Fail: (9) child(anakin_skywalker, owen_lars) ? creep\n", " Redo: (9) male(_5874) ? creep\n", " Exit: (9) male(anakin_skywalker) ? creep\n", " Call: (9) child(anakin_skywalker, anakin_skywalker) ? creep\n", " Fail: (9) child(anakin_skywalker, anakin_skywalker) ? creep\n", " Redo: (9) male(_5874) ? creep\n", " Exit: (9) male(ruwee_naberrie) ? creep\n", " Call: (9) child(anakin_skywalker, ruwee_naberrie) ? creep\n", " Fail: (9) child(anakin_skywalker, ruwee_naberrie) ? creep\n", " Redo: (9) male(_5874) ? creep\n", " Exit: (9) male(luke_skywalker) ? creep\n", " Call: (9) child(anakin_skywalker, luke_skywalker) ? creep\n", " Fail: (9) child(anakin_skywalker, luke_skywalker) ? creep\n", " Redo: (9) male(_5874) ? creep\n", " Exit: (9) male(han_solo) ? creep\n", " Call: (9) child(anakin_skywalker, han_solo) ? creep\n", " Fail: (9) child(anakin_skywalker, han_solo) ? creep\n", " Redo: (9) male(_5874) ? creep\n", " Exit: (9) male(kylo_ren) ? creep\n", " Call: (9) child(anakin_skywalker, kylo_ren) ? creep\n", " Fail: (9) child(anakin_skywalker, kylo_ren) ? creep\n", " Redo: (8) father(_5874, anakin_skywalker) ? creep\n", " Call: (9) neuter(_5874) ? creep\n", " Exit: (9) neuter(the_force) ? creep\n", " Call: (9) child(anakin_skywalker, the_force) ? creep\n", " Exit: (9) child(anakin_skywalker, the_force) ? creep\n", " Exit: (8) father(the_force, anakin_skywalker) ? creep\n", "X = the_force.\n", "````" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Prolog uses depth-first search and matching of terms (unification, `=` operator) to determine the next goal to be tried. This process is slow and may not terminate. We will look at unification later. Consider the following program, `X = f(X).` \n", "\n", "> Is this a legitimate program? What do you think prolog would? To find the value of `X` prolog needs to use `f(X)`. So,\n", "\n", "~~~~\n", "X if f(X)\n", "X if f(f(X))\n", "X if f(f(f(X)))\n", "~~~~\n", "\n", "`gprolog` sees this cyclic dependency readily and bars the specification of the program. However, `SWI-prolog` sees it only at the time of execution. Therefore it allows the program to be defined. There will be more on unification later.\n", "\n", "For any free variable `Z` SWI-prolog says (see https://en.wikipedia.com/wiki/42_(number)) when the query `?-Z.` is evaluated. \n", "\n", "> % ... 1,000,000 ............ 10,000,000 years later\n", ">\n", "> %\n", ">\n", "> % >> 42 << (last release gives the question)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Let us finish with a brief introduction to recursive rules. A rule is called recursive if the head of the rules also appears in the body. This ability is the same as the recursive definition of the functions in traditional imperative programming, so one has to be careful about the specification of the base case. The base cases are themselves specified by rules. Thus, the base cases are typically defined earlier than the recursive definition.\n", "\n", "See the following recursive definitions of the ancestor relation `anc(X,Y)`.\n", "\n", "+ Base Case: `X is an ancestor of Y if Y is a child of X.'\n", "+ Recursive Definition `X is an ancestor of Y if X has a child Z and Z is an ancestor of Y`\n", "\n", "An equivalent form in prolog is the two rules. Now, we can query the fact base for all the ancestors of `kylo_ren`." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ERROR: Caused by: ' anc(X, kylo_ren)'. Returned: 'error(existence_error(procedure, /(child, 2)), context(/(anc, 2), _1488))'." ] } ], "source": [ "anc(X,Y) :- child(Y,X).\n", "anc(X,Y) :- child(Z,X), anc(Z,Y).\n", "\n", "?- anc(X, kylo_ren)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "> If the rules were specified as below, then the left recursion in the rule (head) would cause the stack to overflow. The recursion will not terminate.\n", ">\n", "> ~~~~\n", "> anc1(X,Y) :- anc1(Z,Y), child(Z,X).\n", "> anc1(X,Y) :- child(Y,X).\n", "> ~~~~\n", ">\n", ">\n", "> The program specifying `anc1` does not terminate, however, it is \"logically equivalent\" to the program for `anc`. Thus, the prolog program has two meanings, i) the \"logical\" meaning, and ii) a \"computational\" meaning. Logical meaning can be thought of as the intended meaning, and computational meaning is the result that is obtained after the program is executed. These are known as declarative and the procedural meaning of the program respectively. So, two programs can have the same declarative meaning but different procedural meanings. Moreover, the declarative meaning of a program might not be the same as the procedural meaning of the program." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise:\n", "\n", " + Write down the four different variants of the ancestor rules.\n", " + Trace the query `anc(X, kylo_ren)`, draw the proof tree. Explain.\n", " + Modify the fact base above to capture the training relationships (master-student). Your model should capture the light and the dark side.\n", " + For `X, a Jedi Y is a Jedi-ancestor, if Y trained X, or Y trained some Z, and Z is a Jedi-ancestor of X`. Write a set of rules to identify Jedi-ancestors.\n", " + Using your rules (and the new fact base), write a query to determine all those individual who has some Jedi ancestor from the dark side and well as some from the light side.\n", " \n", " ### Additional Resources:\n", " \n", "+ You may use the online interpreter at https://swish.swi-prolog.org/\n", "+ Reading: Read the book by Ivan Bratko.\n", "+ The source code is available at http://www.cs.uleth.ca/~gaur/code/starwars.txt.\n", "+ The jupyter notebook is available at http://www.cs.uleth.ca/~gaur/code/prolog-lecture.ipynb. You will need to install the SWI-prolog kernel (google for instructions).\n", "### Star Wars Family Tree, as per the end of episode 8\n", "\n", "![](http://www.cs.uleth.ca/~gaur/images/starwars-tree.jpg)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SWI-Prolog", "language": "", "name": "jswipl" }, "language_info": { "mimetype": "text/plain", "name": "swipl" } }, "nbformat": 4, "nbformat_minor": 4 }