Prolog using Examples – Part 1

Prolog is a programming language which works around relations not functions.
Prolog is homoiconic due the structure of its clauses and database that provide it the ability to represent itself.
Note: A language is homoiconic when the language is self-defined. This means that if we run on the interpreter a copy of itself, it should work. Another behaviour of an homoiconic language is to lets the programmer to create, change, and run the code on the fly.
Prolog is not fully reflective, but close, Prolog seems like reflective language because  a program that can resolve a problem by itself by just using relationships, facts, rules, structures, and a database. A fully reflective language should be able to create relationships, rules, structures, and database by itself as needed to find a solution.

In Prolog, facts are clauses with an empty body, eg:

is_mother_of(Maria, Matias). /* Maria is_mother_of Matias */

Rules are clauses with a head and body (head():- body), eg:

/* A Person is_parent_of the Child if (Smile the Person is_mother_of the Child */
is_parent_of(Person, Child) :- is_mother_of(Person, Child).

Predicate are clauses using the same head with different bodies, eg:

/* A Person is_parent_of the Child if (Smile the Person is_mother_of the Child */
is_parent_of(Person, Child) :- is_mother_of(Person, Child).
/* A Person is_parent_of the Child if (Smile the Person is_father_of the Child */
is_parent_of(Person, Child) :- is_father_of(Person, Child).

Note: Every code written before ‘?-‘ are facts and rules. Code written following ‘?-‘ are queries, and all code after ‘?-‘ are the results that prolog returns. eg:

is_mother_of(Marina, Marcos).   /* This is a fact */
is_parent_of(Person, Child) :- is_mother_of(Person, Child). /* This is a rule */
?- is_parent_of(Marina, Marcos). /* This is a query */
True /* This is a result. note that this comment will not show up */
?- is_parent_of(Marina, Lucia). /* This is a query */
False

Lets talk about unification.

/* A unified with B if and only if A and B are the same */
?- =(A, B).
A = B.

/* This is the same as =(A, B) */
?- A = B.
A = B.

Note that A = 1 + 2 will not give you 3 but A = 1 + 2 which means you are unifying A with 1 + 2.
If you to obtain a mathemarical result you should use the following code, eg:

?- A is 1 + 2.
A = 3.

The follows are some examples of unification:

/* a is a constant (also known as an atom) */
/* Since constants can unify with themselves then this is true */
?- a = a.
True

/* a and b are constants, but b is not the same as a, when trying to unify a with b, this will give you false */
?- a = b.
False

/* In case you are unifying facts with constants */
?- foo(a, b) = foo(a, b).
True.

/* This case fails since in both facts, at least one of the constants are nor the same */
?- foo(a, b) = foo(a, c).
False.

?- foo(a, b) = foo(b, a).
False.

Unification can also being use to unify a constant with a variable (Variables start with capital letter), eg:

?- A = a.
A = a.

/* In this case for example we can unify A with c and B with d */
?- foo(A, B) = foo(c, d).
A = c,
B = d.

Note that in Prolog, a variable cannot be modified after

You may have notice the comma after A = c. In Prolog, ‘,’ have the same meaning as AND, while a new line or ‘;’ means OR.

Example:

/* Lets say that prolog provide us with an answer */
?- foo(a, X) = foo(a, b).
X = b; /* <- if we add this semicolon ';' instead of a newline to ask another answer (OR) */
False  /* We get a false because there is no other case */

/* Person is_parent_of Child if Person is_mother_of Child OR Person is_father_of Child */
is_parent_of(Person, Child) :- is_mother_of(Person, Child).
is_parent_of(Person, Child) :- is_father_of(Person, Child).

/* Person is_mother_of Child if Person is_parent_of Child AND Person is_female */
is_mother_of(Person, Child) :- is_parent_of(Person, Child), is_female(Person).

/* Another example of AND and unification */
/* A is unified with B AND A is unified with constant z AND B is unified with Y */
?- A = B, A = z, B = Y.
A = z, /* A was unified with z */
B = z, /* Since A = B and A = z then B = z */
Y = z. /* Since B = A = z then Y = z */

Explicit versus Implicit:

Explicit:

relationship(Z, Z).
is_related(X, Y):-
    relationship(X, b),
    relationship(a, Y).
?- check(First, Second).
First = b,
Second = a.

Implicit:

relationship(Z, Z).
?- is_related(relationship(First, b), relationship(a, Second)).
First = a,
Second = b.

More examples of simple Facts and Rules:

Example 1: Lets do a modification of the game of Yahtzee (http://en.wikipedia.org/wiki/Yahtzee).
Yahtzee is played with 5 dices, and depending of the combination you can obtain: Chance, Three-Of-A-Kind, Four-Of-A-Kind, Full House, Small Straight, Large Straight, and Yahtzee.
We are going to do only the Yahtzee combination for this example and the user will input values from 1 to 6.

/* Establish the facts and rules */

/* Yahtzee: All five dices show the same face. */
yahtzee(A, A, A, A, A).
?- yahtzee(5,5,5,5,5).
True

?- yahtzee(5,4,5,4,5).
False

Example 2: Lets do some adding. This is a way that you can do adding by using successor(0)
as a numeral.

/* When 0 is the same as 0, then Y = 0 */
add(0, Y, Y).
/* */
add(successor(X), Y, successor(Z)) :- add(X, Y, Z).
/* Example of behavior when used in the wrong way */
?- add(A, B, C).
A = 0,
B = C;
A = successor(0),
C = successor(B);
A = successor(successor(0)),
C = successor(successor(B));
... /* This keeps on going if you use OR ';' */
/* Example of behavior when used in the wrong way */
?- add(A, 0, C).
A = 0,
C = 0;
A = successor(0),
C = successor(0);
A = successor(successor(0)),
C = successor(successor(0));
... /* This keeps on going if you use OR ';' */
/* Example of behavior when used in the wrong way */
?- add(0, B, C).
A = 0,
B = 0.
/* Example of behavior when used in the wrong way */
?- add(0, 1, C).
false.
/* Do 1 + 1 = 2: successor(0) + successor(0) = successor(successor(0)). */
?- add(successor(0), successor(0), X).
X = successor(successor(0)).
/* Do 2 + 1 = 3. */
/* successor(successor(0)) + successor(0) = successor(successor(successor(0))). */
?- add(successor(successor(0)), successor(0), X).
X = successor(successor(successor(0))).

Notice that a rule can behave different depending who you define your inputs and outputs.

Example:

/* Here we find that we are doing -1 + 1 = 0 */
?- add(successor(0), X, successor(0)).
X = 0.
/* Here we have 2 - 1 = 1 */
?- add(successor(0), X, successor(successor(0))).
X = successor(0).
/* While this give you X = 0, it would fail in a different case */
?- add(X, successor(0), successor(0)).
X = 0
/* Here this fails */
?- add(X, successor(successor(0)), successor(0)).
false.

In the next submittion we are going to see recursion in Prolog.

Share
Leave a comment

Prolog

(This document is in process, it will be continually updated until completion. Please be patience).

Right now, I am learning how to program in PROLOG (PROgramming in LOGic) in my course of programming languages at Binghamton University. I must confess that I find it to be very different to what I thought it would looks like.

Prolog was mainly used for artificial intelligence and computational linguistics (http://en.wikipedia.org/wiki/Prolog). I would really like to know if it is used outside of the academic environment. If anyone have any info about this let me know.

The following article at http://www.kuro5hin.org/story/2004/2/25/124713/784 written by tkatchev says that Prolog can be used for hacking. Even do I agree with tkatchev that is plausible, I would love to see an actual example. Some encryption braking, etc.  Also, I agree that the way it is presented could be more effective if applied to real life uses than IA.

At the bottom I will add a list of links related with this topic.

Prolog is a programming language that let the programmer write a declarative program instead of a procedural program. Just to make sure we are in the same page, a declarative program is when the programmer used “truth and logical deduction” (Barták). In declarative programming, the programmer must use a descriptive style that let know which are the relationship between the entities (Brna).
In a procedural program, the programmer indicate the machine what to do, step by step.

Prolog perform the execution of the program in an tree dept-first fashion or other way to call it: First Order Predicate Logic. Later I will go more in deep and clarify this.

Let start with installing the basics:

  1. Install a text editor. It seems that Emacs is the right editor for this
    1. http://bruda.ca/emacs-prolog/
    2. If you have Ubuntu, you can install the emacs editor for prolog. Just go to the Ubuntu Software Center. Type Prolog in the search box and install “Emacs major mode for editing Prolog code” [prolog-el]
  2. Install one of these prolog compiler:
    1. http://www.gnu.org/software/gprolog/
    2. http://www.swi-prolog.org/download/stable (recommended)

Prolog works using atoms, terms, variables, facts, rules, recursion, and queries between others. Little by little we will be introducing this concepts.

Lets analyse the following examples:

1. pens have inside ink

a. This should be written as:

have_inside(pens, ink).

b. Notice that pens and ink do not have the first letter in capital. Words that are start with capital letters are considerate logical variables.

Logical Variable: Pens

No logical variable: pens

c. A predicate cannot be a logical variable

Wrong: Have_inside(pens, ink).

Correct: have_inside(pens, ink).

d. pens and ink are called atoms (or constants).

e. This functor is a prefix called a relationship (or predicate).

f. This predicate have a arity (number of arguments) of 2.

i. A predicate with no arguments is a single proposition, a predicate with one argument is unary, with two arguments is binary, with three arguments is ternary, …

g. This is a clause therefore they must end with a period (.) and an space after or with a period(.) and a new line.

h. More examples:

i. pepe is bold:

bold(pepe).

ii. juan saw tim by the coffe shop:

saw(juan, tim, coffee_shop).

2. In the previous example, we named atoms (or constants) and logical variables

a. Examples of atoms:

countryA, –+–,  ‘Hello World’ (Notice that we are using a single tilde (”) not a double tilde (“”))

3. Difference between a goal and a unit clause

a. Goal:

miss(maria, jose)

b. Unit Clause:

miss(maria, jose).

What are the difference between both? The period at the end. A goal is called a unit while a clause is called a non-unit. More details about this later.

4. Multi Clause: We can have more than one clause with the same name for example:

square_root(1, 1).
square_root(4, 2).
square_root(9, 3).

In this case we are saying: the square root of 1 is 1 OR the square root of 4 is 2 OR the square root of 9 is 3.
Every time you use the period(.) and a newline, this is the equivalent of saying OR.

5. Rules: Rules are non-unit conditionals in Prolog. For example:

a. If tim have a job, then tim can pay his bills

can_pay_bills(tim) :-

have_job(tim).

i. :- is the equivalent of if

ii. This is a non-unit clause

b.Let say we want to use a rule with a variable:

i. if a number is divisible by 1 AND also the number is divisible by three then the number is odd

number_is_odd(X) :-

number_divisible_by_one(X),

number_divisible_by_three(X).

I. The comma (,) is the representation of the statement AND. If number_divisible_by_one is true AND number_divisible_by_three     is true, then number_is_odd is true.

ii. classes are cancel if the day is a holiday OR the professor is sick

cancel(classes) :-

day_is_holiday(classes).

cancel(classes) :-

proffesor_is_sick(classes).

iii. There is an special case in which two rules seems to be talking about the same variable but they are not:

number_is_divisible_by_two(X) :-

number_is_odd(X).

number_is_divisible_by_two(X) :-

number_is_odd(X).

I. In this case it says that a number is divisible by one is the number is odd or a number is divisible by three if the number is odd. Believed or not, we are not talking about the same variable. Why? Because “local variables cannot be overwritten with a new value” (Paul Brna). Example:

A. if we say that X = 1 and later we try to change this variable (X = 2) this will not work for Prolog

I will try to continue this topic in another posting.

Related Links:

  1. http://www.learnprolognow.org/
  2. http://kti.ms.mff.cuni.cz/~bartak/prolog/
  3. http://cs.union.edu/~striegnk/learn-prolog-now/html/
  4. http://www.swi-prolog.org/
  5. http://www.cse.unsw.edu.au/~billw/prologdict.html
  6. http://homepages.inf.ed.ac.uk/pbrna/prologbook/index.html
  7. http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/

Work Citied

Roman Barták, http://kti.mff.cuni.cz/~bartak/prolog/intro.html

Paul Brna, http://homepages.inf.ed.ac.uk/pbrna/prologbook/node11.html

Share
One Comment

Code Examples in C++

Here are some code examples written in C++
Even do they are written in C++, I would advice to compile them in Linux as I did. If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks
NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. I do not take responsibilities of how they are used.

Share
Leave a comment

Interesing Links for Source of Information

Share
Leave a comment

Algorithms Examples in ANSI C

Here are some examples of Algorithm written in ANSI C.
Even do they are written in ANSI C, I would advice to compile them in Linux as I did. If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.
NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. I do not take responsibilities of how they are used.

Share
Leave a comment