PROLOG: Intelligent Logic Programming in AI (Part I)

What is PROLOG?

Prolog was invented in the early seventies at the University of Marseille. Prolog stands for PROgramming in LOGic. It is a logic language that is particularly used by programs that use non-numeric objects. For this reason it is a frequently used language in Artificial Intelligence where manipulation of symbols is a common task. Prolog differs from the most common programmings languages because it is declarativre language. Traditional programming languages are said to be procedural. This means that the programmer specify how to solve a problem. In declarative languages the programmers only give the problem and the language find himself how to solve the problem.

What is the difference between PROLOG and the languages you have studied ever?

You will see that Prolog is quite different from other programming languages you have studied. First, Prolog has no types. In fact, the basic logic programming environment has no literal values as such. Identifiers starting with lower-case letters denote data values (almost like values in an enumerated type) while all other identifiers denote variables. Though the basic elements of Prolog are typeless, most implementations have been enhanced to include character and integer values and operations. Also, Prolog has mechanisms built in for describing tuples and lists.

             Remember that all programming languages have both declarative (definitional) and imperative (computational) components. Prolog is referred to as a declarative language because all program statements are definitional. In particular, a Prolog program consists of facts and rules which serve to define relations (in the mathematical sense) on sets of values. The imperative component of Prolog is its execution engine based on unification and resolution, a mechanism for recursively extracting sets of data values implicit in the facts and rules of a program. In this section you will be briefly introduced to each of these terms.

What are Facts, Rules and Predicates?

Facts and Rules

Everything in Prolog is defined in terms of two constructs: the fact and the rule. A fact is a Prolog statement consisting simply of an identifier followed by an n-tuple of constants. The identifier is interpreted as the name of a (mathematical) relation and the fact states that the specified n-tuple is in the relation. In Prolog a relation identifier is referred to as a predicate; when a tuple of values is in a relation we say the tuple satisfies the predicate.

More complicated facts consist of a relation and the items that this refers to. These items are called arguments. Facts can have arbitrary number of arguments from zero upwards. A general model is shown below:

   

 relation(<argument1>,<argument2>,....,<argumentN> ).

The arguments can be any legal Prolog term. The basic Prolog terms are an integer, an atom, a variable or a structure. Various Prolog implementations enhance this basic list with other data types, such as floating point numbers, or strings. Exemple:

    

likes(john,mary).

In the above fact john and mary are two atomes. Atoms are usally made from letters and digits with lowercase characters. The underscore (_) can also be used to separe 2 words but is not allowed as the first charactere. Atoms can also be legally made from symbols.

Consider the following sentence: 'All men are mortal'.  We can express this thing in Prolog by:

     mortal(X) :- human(X)

The clause can be read as 'X is mortal if X is human'.
To continue with this example, let us define the fact that Socrate is a human. Our program will be:

    

mortal(X) :- human(X).

    

human(socrate).

Now if we ask to prolog :

    

?- mortal(socrate).

Prolog will respond :

   

 Yes

SWI PROLOG Environment:

The version of Prolog that we will use is called SWI-Prolog, developed at the Swedish Institute of Computer Science. The SWI-Prolog environment is an interactive system, much like the Hugs functional programming environment.

After SWI-Prolog has been installed on a Windows system, the following important new things are available to the user:

• A folder (called directory in the remainder of this document) called pl containing the executables, libraries, etc. of the system. No files are installed outside this directory.
• A program swipl-win.exe, providing a window for interaction with Prolog. The program swipl.exe is a version of SWI-Prolog that runs in a DOS-box.
• The file-extension .pl is associated with the program swipl-win.exe. Opening a .pl file will cause swipl-win.exe to start, change directory to the directory in which the file-to-open resides and load this file.

How to write and run programs in SWI-Prolog:

1. Go to \program files\pl\bin

2. Open a new Notepad file

3. Write the prolog code there

4. Save the file using .pl extension

5. The file will be saved as a prolog file

6. By double clicking execute the file

Pointers and References

Are reference and pointers same?

No.

I have seen this confusion crumbling up among the student from the first day. So better clear out this confusion at thevery beginning.

Pointers and reference both hold the address of other variables. Up to this they look similar, but their syntax and further consequences are totally different. Just consider the following pieces of code

Code 1                                         Code 2

int i;                                             int i;

int *p = &i;                                 int &r = i ;

Here in code 1 we have declared and defined one integer pointer p which points to variable i, that is now , p holds the address of i.

In code 2, we have declared and defined one integer reference r which points to variable i, that is now, r holds the address of i. This is completely same as that of p.

So where is the difference?

The first difference can be found just by looking at the code. Their syntaxes!

Secondly the difference will come up when they would be used differently to assign a value (suppose 10) to i.

If you are using a pointer, you can do it like *p = 10; but if you are using a reference, you can do it like r = 10.  Just be careful to understand that when you are using pointers, the address must be dereferenced using the *, whereas, when you are using references, the address is dereferenced without using any operators at all.

This notion leaves a huge effect as consequences. As the address of the variable is dereferenced by * operator, while using a pointer, you are free to do any arithmetic operations on it. That is you can increment the pointer p to point to the next address just by doing p++. But, this is not possible using references.  So a pointer can point to many different elements during its lifetime; where as a reference can refer to only one element during its life time.

Does C language support references?

No. The concept of reference has been added to C++, not in C. So if you run the following code, C compiler will object then and there.

#include<stdio.h>

#include<conio.h>

int main(void)

{

    int i;

    int &r = i;

    r = 10;

    printf("\n Value of i assigned with reference r = %d",i);

    getch();

    return 0;

}

But if you are using any C++ compiler, this code will work fine as expected.

If there is no concept of reference in C language, then how come there exists C function call by reference?

Strictly speaking, there is no concept of function call by reference in C language. C only supports function call by value. Though in some books ( I will not name any one) it is written that C supports function call by reference or the simulation of  function call by reference can be achieved through pointers, I will strongly say that C language neither directly supports function call by reference, nor provides any other mechanism to simulate the same effect.

I know you are at your toes to argue that what about calling a C function with address of a variable and receiving it with a pointer? The change made to that variable within the function has a global effect. How this cannot be treated as an example of function call by reference?

You probably argue with a code like following

#include<stdio.h>

#include<conio.h>

void foo(int* p)

{

     *p = 5;

      printf("\n Inside foo() the value of the variable: %d",*p);

}

int main(void)

{

    int i = 10;

    printf("\n before calling  foo() the value of the variable: %d",i);

    foo(&i);

    printf("\n after calling  foo() the value of the variable: %d",i);

    getch();

    return 0;

}      

  Your code will show the result as 

Your points are well taken. But the thing is what you are showing is not at all calling a function by reference. It just the function call by value! Here you are essentially copying the value of address of your variable i and calling the function foo with that copy. Now eventually in this case, the value that is being passed contains the address of another variable. Within the function, you are accepting this value with a pointer and changing the 

value of the content addressed by that pointer. So it is nothing but a function call by value only.

Please note that to change the value of the content addressed by a pointer, you are to use *, no way could it be thought of as a reference.

Now let me give you one example of true function call by reference

#include<stdio.h>

#include<conio.h>

void foo (int& r1)

{

     r1 = 5;

     printf("\n Inside foo() the value of the variable: %d", r1);

}

int main(void)

{

    int i = 10;

    int &r = i;

    printf("\n before calling  foo() the value of the variable: %d",i);

    foo(r);

    printf("\n after calling  foo() the value of the variable: %d",i);

    getch();

    return 0;

}

Will this run with your C compiler? No.

Note:: I have used DevC++ as the coding platform

Elementary Discussion About State Space Search (Part II)

Example problem: 8 puzzle

In the 8-puzzle problem we have a 3×3 square board and 8 numbered tiles. The board has one blank position. Bocks can be slid to adjacent blank positions. We can alternatively and equivalently look upon this as the movement of the blank position up, down, left or right. The objective of this puzzle is to move the tiles starting from an initial position and arrive at a given goal configuration.

The 15-puzzle problems is similar to the 8-puzzle. It has a 4×4 square board and 15 numbered tiles

The state space representation for this problem is summarized below:

States: A state is a description of each of the eight tiles in each location that it can occupy.

Operators/Action: The blank moves left, right, up or down

Goal Test: The current state matches a certain state (e.g. one of the ones shown on previous slide)

Path Cost: Each move of the blank costs 1

A small portion of the state space of 8-puzzle is shown below. Note that we do not need to generate all the states before the search begins. The states can be generated when required.

 



tic-tac-toe

Another example we will consider now is the game of tic-tac-toe. This is a game that involves two players who play alternately. Player one puts a X in an empty position. Player 2 places an O in an unoccupied position. The player who can first get three of his symbols in the same row, column or diagonal wins. A portion of the state space of tic-tac-toe is depicted below.

8 queens’ problem

The problem is to place 8 queens on a chessboard so that no two queens are in the same row, column or diagonal

The picture below on the left shows a solution of the 8-queens problem. The picture on the right is not a correct solution, because some of the queens are attacking each other.

How do we formulate this in terms of a state space search problem? The problem formulation involves deciding the representation of the states, selecting the initial state representation, the description of the operators, and the successor states. We will now show that we can formulate the search problem in several different ways for this problem.

N queens problem formulation 1

            • States: Any arrangement of 0 to 8 queens on the board

            • Initial state: 0 queens on the board

            • Successor function: Add a queen in any square

            • Goal test: 8 queens on the board, none are attacked

The initial state has 64 successors. Each of the states at the next level have 63 successors, and so on. We can restrict the search tree somewhat by considering only those successors where no queen is attacking each other. To do that we have to check the new queen against all existing queens on the board. The solutions are found at a depth of 8.

N queens problem formulation 2

            • States: Any arrangement of 8 queens on the board

            • Initial state: All queens are at column 1

            • Successor function: Change the position of any one queen

            • Goal test: 8 queens on the board, none are attacked

If we consider moving the queen at column 1, it may move to any of the seven remaining columns.

N queens problem formulation 3

            • States: Any arrangement of k queens in the first k rows such that none are attacked

            • Initial state: 0 queens on the board

            • Successor function: Add a queen to the (k+1)th row so that none are attacked.

            • Goal test : 8 queens on the board, none are attacked

Now here is the end of the discussion about State Space Search and some of its implementations. Feel free to query about the topic.

 

Source:http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT%20Kharagpur/Artificial%20intelligence/New_index1.html







Tutorial on Dynamic Programming - Concluding Part

This is the concluding part of the series of tutorials on Dynamic Programming. In this part we will see and assimilate one example where the problem of Matrix Chain Multiplication will be solved with Dynamic Programming Principle

What is this Matrix Chain Multiplication Problem?

Suppose we have a sequence or chain A₁, A₂, …, A_n of n matrices to be multiplied. That is, we want to compute the product A₁A₂…A_n. Now there are many possible ways (parenthesizations) to compute the product.

Let us consider the chain A₁, A₂, A₃, A₄ of 4 matrices. Now to compute the product A₁A₂A₃A_4, there are 5 possible ways as described below:

(A₁(A₂(A₃A₄))), (A₁((A₂A₃)A₄)), ((A₁A₂)(A₃A₄)), ((A₁(A₂A₃))A₄), (((A₁A₂)A₃)A₄)

Each of these options may lead to the different number of scalar multiplications, and we have to select the best one (option resulting fewer number of Scalar Multiplications)

Hence the problem statement looks something like:  “Parenthesize the product A₁A₂…A_n such that the total number of scalar multiplications is minimized”

Please remember that the objective of Matrix Chain Multiplication is not to do the multiplication physically, rather the objective is to fix the way of that multiplication ordering so that the number of scalar multiplication gets minimized.

Give me one real example

Ok. But before I show you one real example, let us revisit the algorithm which multiplies two matrices. It goes like following:

Input: Matrices A_p×q and B_q×r (with dimensions p×q and q×r)

Result: Matrix C_p×r resulting from the product A·B

MATRIX-MULTIPLY(A_p×q , B_q×r)

1.            for i ← 1 to p

2.                                            for j ← 1 to r

3.                                                            C[i, j] ← 0

4.                                                            for k ← 1 to q

5.                                                                            C[i, j] ← C[i, j] + A[i, k] · B[k, j]

6.            return C

In the above algorithm, scalar multiplication in line 5 dominates time to compute C Number of scalar multiplications = pqr

Now on the basis of above algorithm what if we try to multiply three matrices A_10´100, B_100´5, and C_5´50?

There are 2 ways to parenthesize

–        ((AB)C) = D_10´5 · C_5´50

•          AB Þ 10·100·5=5,000 scalar multiplications

•          DC Þ 10·5·50 =2,500 scalar multiplications

•          Total number of scalar multiplications 7,500

–        (A(BC)) = A_10´100 · E_100´50

•          BC Þ 100·5·50=25,000 scalar multiplications

•          AE Þ 10·100·50 =50,000 scalar multiplications

•          Total number of scalar multiplications 75,000

It is evident that the first option will result the fewer number of scalar multiplication and it is the best one for computational easiness.

Hope now you understand what I mean.

How do you know that this problem could be solved through Dynamic Programming?

See, there are some clear evidences that this problem is perfect fit to be solved through Dynamic Programming.

In connection to the Matrix Chain Multiplication, the optimal solution to the problem contains within it the optimal solution to subproblems. That is why we can say that this problem will better be solved by Dynamic Programming. Now the question is how we came to a conclusion that the principle of optimality holds true in this case?

Looking back to the problem, we are given with a chain A₁, A₂, …, A_n of n matrices, where for i=1, 2, …, n, matrix A_i has dimension p_i-1´p_i. We need to search for optimal solution of  parenthesization in order  to minimize the scalar computation.

Hence to find the structure of the optimal solution –

§       

       Let us use the notation A_i..j for the matrix that results from the product A_i A_i+1 … A_j

§    

        Let us admit that an optimal parenthesization of the product A₁A₂…A_n splits the product between A_k and A_k+1 for some integer k where1 ≤ k < n

§     

            So we have to compute matrices A_1..k and A_k+1..n  first; then multiply them to get the final matrix A_1..n

The Key observation here is the parenthesizations of the subchains A₁A₂…A_k and A_k+1A_k+2…A_n must also be optimal if the parenthesization of the chain A₁A₂…A_n is optimal.

Hence Dynamic Programming Principle could effectively be used for Matrix Chain Multiplication problem.

What is the Dynamic Programming approach particularly for this problem?

Let m[i, j] be the minimum number of scalar multiplications necessary to compute A_i..j . So minimum cost to compute A_1..n is m[1, n]

Suppose the optimal parenthesization of A_i..j splits the product between A_k and A_k+1 for some integer k where i ≤ k < j. Hence A_i..j = (A_i A_i+1…A_k)·(A_k+1A_k+2…A_j)= A_i..k · A_k+1..j

We get Cost of computing A_i..j = cost of computing A_i..k + cost of computing A_k+1..j + cost of multiplying A_i..k and A_k+1..j

Now Cost of multiplying A_i..k and A_k+1..j is p_i-1p_k p_j

So evidently m[i, j ] = m[i, k] + m[k+1, j ] + p_i-1p_k p_j   for i ≤ k < j and m[i, i ] = 0 for i=1,2,…,n

But optimal parenthesization occurs at one value of k among all possible i ≤ k < j, so check all these and select the best one.

So the optimal substructure relation is like following:

m[i, j ] =  0                                                                              if i=j

               min {m[i, k] + m[k+1, j ] + p_i-1p_k p_j }                      if i<j

             i ≤ k< j

To keep track of how to construct an optimal solution, we use a table s. s[i, j ] = value of k at which A_i A_i+1 … A_j is split for optimal parenthesization.

Wait a minute, I got almost everything except that p array what is it? Where did it come from?

The P array stores the dimensions of the matrices. Suppose we are to multiply 3 matrices of dimension 5* 10, 10* 3 and 3*8, in this case the length of p array will be (3+1) 4 and it will be like P[0] =  5, p[1] = 10, p[2] = 3 and p[3]=8.

So generalizing, if you have n matrices to be multiplied, take the length of p as n+1, then fill p[0] with row number of 1^st matrix, fill p[n] with column no of nth matrix, and for the intermediate indices go like following

P[1] = col no of 1^st matrix or row no of 2^nd matrix

P[2] = col no of 2^nd matrix or row no of 3^rd matrix

P[3] = col no of 3^rd matrix or row no of 4^th matrix

…….

P[n-1] = col no of (n-1)th matrix or row no of nth matrix.

Now I got it. Anyways, how is the algorithm?

Input: Array p[0…n] containing matrix dimensions and n

Result: Minimum-cost table m and split table s

MATRIX-CHAIN-ORDER(p[ ], n)

                for i ← 1 to n

                                m[i, i] ← 0

                for l ← 2 to n

                                for i ← 1 to n-l+1

                                                j  ← i+l-1

                                                m[i, j] ← ¥

                                                for k ← i to j-1

                                                                q ← m[i, k] + m[k+1, j] + p[i-1] p[k] p[j]

                                                                if  q < m[i, j]

                                                                                m[i, j] ← q

                                                                                s[i, j] ← k

return m and s

Can you please give me a C code for Matrix Chain Multiplication 

Here is the code. This code fills up the split table but never utilizes it to show the proper ordering of parenthesis. That part is left for you guys to explore.

This program takes the length of the chain of matrices, and the p array where the dimension of arrays are stored and computes the minimum number of scalar multiplications. 

There is no comment. Try to comment it by your own..this will give you the insights of the program

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<limits.h>

int compute(int*dimArray, int**splitTab, int start, int end)

{

    int iter, sTableEntry;

    int minimumCountOfScalarMultiplications = INT_MAX;

    int countOfScalarMultiplications;

    if(start == end)

             return 0;

    else

    {

        for(iter = start; iter < end; iter++)

        {

                    countOfScalarMultiplications = compute(dimArray, splitTab, start,iter)+ compute(dimArray, splitTab, iter+1, end)+(dimArray[start - 1]*dimArray[iter]*dimArray[end]);

                    if(countOfScalarMultiplications < minimumCountOfScalarMultiplications)

                    {

                                                    minimumCountOfScalarMultiplications = countOfScalarMultiplications;

                                                    sTableEntry = iter;

                    }

        } 

        splitTab[start][end] = sTableEntry;     

    }

    return minimumCountOfScalarMultiplications;

}

int main(void)

{

    int* processedInput;

    int lengthOfChain;

    int iter;

    int** splitTable;   

    printf("\n Enter the length of the chain::");

    scanf("%d", &lengthOfChain);

    processedInput = (int*)malloc(lengthOfChain+1*sizeof(int));

    splitTable = (int**)calloc(lengthOfChain + 1, sizeof(int*));

    for(iter = 0; iter<lengthOfChain; iter++)

             splitTable[iter] = (int*)calloc(lengthOfChain + 1 , sizeof(int));

    printf("\n Enter the dimension of the matrix = ");

    for(iter = 0; iter<=lengthOfChain; iter++)

        scanf("%d", &processedInput[iter]);

    printf("\n Your Input Is Registered Successfully.... Press any key to continue");

    getch();

    printf("\n The number of minimum scalar multiplication = %d", compute(processedInput,splitTable,1, lengthOfChain));

    getch();

    return 0;

}                 

Sample Input

Enter the length of the chain::6

Enter the dimension of the matrix =30 35 15 5 10 20 25

Sample Output

The number of minimum scalar multiplication = 15125