Declarative programming with Prolog

Declarative programming is a programming paradigm where you specify what the program needs to accomplish rather than how to accomplish as opposed with imperative programming. That is in simpler terms, imperative programs specify the sequence of steps/commands to be followed by the computer system where as declarative programs describe the logic of the program without specifying the control flow.

Declarative programming is widely used in logic programming and Prolog is a popular language inspired by many logic programming researches. Below are some example functions written using Prolog.

Reversing a List

Consider a function to reverse a given list of items. If this is to be implemented using imperative programming, we need to specify the compiler each step to be happened. But with Prolog, we just need to say what we want.

reverse_list([],[]).
reverse_list([H|T],X) :- reverse_list(T,A), append(A,[H],X).

A Prolog procedures consists clauses and clauses can be either facts or rules. Facts are of the form

     head.

Rules are of the form,

     head :- t1,t2,…..,tk. (where k>=1)

So in our procedure to reverse the list, first clause is a fact which specifies that reverse of an empty list is an empty list.  Second clause is a rule that specifies what is true about the result if it is not an empty list. The rule says reverse of the list [H|T] is X if X is the list obtained via appending H to the end of a list A, where A is the reverse of T.  Here, [H|T] is the list notation in Prolog where H is the head element  and T is the tail of the list.

If this is to be done in an imperative language, we may have to either traverse the given list until end or start traversing the list from end (if the language provide that functionality) and add each element to another list one by one.

Also, note that this works for any data item, numbers or strings or whatever, implicitly.

Below is an example invocation of the above procedure. 

[1] 69 ?- reverse_list([1,2,3,4],X).
X = [4, 3, 2, 1].

[1] 70 ?- reverse_list(['cat','bird','dog','lion'],X).
X = [lion, dog, bird, cat].

Delete first occurrence of an item in a list

Below is the Prolog procedure to delete the first occurrence of an item in a list.

delete_first(H,[H|T],T).
delete_first(X,[H|T],[H|Y]) :- X\==H,delete_first(X,T,Y).

In the above procedure, first clause is a fact which specifies that if the element we want to delete is the head of the list, result is simply the tail of the list. Second clause is a rule that specifies  if item X is removed from the list [H|T] result is [H|Y], if X is not equal to H and Y is the resultant list when X is deleted from tail of the list [H|T].

?- delete_first(2,[1,2,3,4,5],X).
X = [1, 3, 4, 5] .


?- delete_first('cat',['dog','lion','cat','bird','tiger'],X).
X = [dog, lion, bird, tiger] .

Split a list into two lists that contain positive and negative numbers

Below is the Prolog procedure to split a list into two lists based on the sign. 

split([],[],[]).
split([H|T],[H|P],N) :- H>0,split(T,P,N),!.
split([H|T],P,[H|N]) :- H<0, split(T,P,N).

First fact says that splitting an empty list to two positive and negative lists results two empty lists.  Second clause is a rule which indicate that a list having head H and tail T is split into a positive list [H|P] and negative list N if H > 0 and P,N are the positive and negative lists of tail T. Third clause is the same rule when head is negative.

?- split([1,2,-1,4,7,-2,-4,8,-9],P,N).
P = [1, 2, 4, 7, 8],
N = [-1, -2, -4, -9].

From all the above examples we can clearly see how declarative programs differs from the programs we write in languages like Java, C, C++ etc. Declarative and imperative programming has distinguished application domains. Even though it looks like declarative programming involves less coding, it is not applicable for all the domains as it can be used only for very specific purposes. 

Solving coin denomination problem using Greedy Approach

Suppose we have coins of the following denominations : 100, 50, 25, 10, 5, 2, 1. Our task is to devise an algorithm for paying a given amount to a customer using the smallest possible number of coins.  For example the minimum possible number of coins to pay 289/- would be 7.

 i.e 2x100+1x50+1x25+1x10+2x2

Greedy approach

Naive way of doing this is to follow a greedy approach. That is by choosing the largest possible coin at every step, without worrying whether this will lead to a sound decision at the end. Thus choosing the largest coin denomination is the greedy choice.   

My Java implementation for this looks like below.

    

1:     Stack find(int amount){      
2:      // initially we considering the largest available coin      
3:      int largestSelectedCoin = coins.length-1;     
4:      Stack stack = new Stack(); // to track coins being selected      
5:      // loop until the amount exists  
6:      while(amount>0){        
7:      // if the amount is greater than or equals to the largest coin under consideration, we can make a denomination using the largest coin        
8:      if(coins[largestSelectedCoin]<=amount){        
9:        // how many of the largest coin under consideration can use at maximum   
10:        int numberOfSelectedCoins = (int) Math.floor(amount/coins[largestSelectedCoin]);        
11:        // remainder to be changed  
12:        int remainder = amount%coins[largestSelectedCoin];        
13:        // push the coins to stack  
14:        for(int i=0;i<numberOfSelectedCoins;i++){  
15:          stack.push(coins[largestSelectedCoin]);          
16:        }        
17:        // adjust the amount to remainder  
18:        amount =remainder;        
19:        //let the largest coin under consideration to be the next lowest coin  
20:        largestSelectedCoin--;        
21:      }else{  
22:        // if the value of largest coin under consideration is greater than the amount go for the next available largest coin  
23:        largestSelectedCoin--;  
24:      }  
25:      }      
26:      return stack;      
27:    }  

Above method takes the amount to be checked and find the coin denomination to resolve that amount and put the output sequence of the coins to a stack. In order to test the code I wrote a simple console application which take the amount from the user and out put the sequence of coins that result the minimum number of coins. Here I’m assuming that the coin denomination is stored in an array named coins.

1:   public static void main(String[] args) {  
2:       System.out.println("Available coin denomination : ");  
3:       for(int i = 0 ; i < coins.length;i++){  
4:            System.out.print(coins[i] + ", ");  
5:       }      
6:     System.out.println("\nEnter the amount to be changed : ");  
7:     Scanner scanner = new Scanner(System.in);  
8:     int amount =scanner.nextInt();  
9:     CoinDenominator coinDenominator = new CoinDenominator();  
10:     Stack stack= coinDenominator.find(amount);  
11:     System.out.println("Number of coins = " + stack.size());  
12:     Iterator i= stack.iterator();  
13:     System.out.println("change for " + amount+" : ");  
14:     while(i.hasNext()){       
15:       System.out.println("  " + i.next());       
16:     }  
17:    }  

Execution of this program for the coin denomination {1, 2 , 5, 10, 25, 50, 100} gave the below result.

However it is noteworthy that the greedy approach is solving this coin denomination problem only for certain coin denominations. For example an attempt to use a greedy approach under the coin denomination of {1,5,12}would yield an incorrect result as below. 

Hence we can conclude that the Greedy approach is not giving the optimal solution for all sort of coin denominations. 

Searching a pattern in a serial stream on the fly using KMP

This work is based on an assignment I did for my postgrad studies. What I’m going to do here is to look for an efficient way to search an identified pattern on the fly in a binary serial stream so far received. Suppose the message T[1 ...n] is being transferred serially, in the order T[1],T[2],.... and what I’m interested is  checking if the text seen so far contains a pattern P, where P has length m.

That is every time when the next letter of the text T is transmitted, it is necessary to check if the text seen so far contains P.

To implement this I used KMP string matching algorithm. I slightly modified KMP algorithm to cater the online streaming of text. That is, in order to solve the given problem; algorithm needs to be executed while generating the input. Hence, there is no possibility of seeing the future values of text. So the algorithm was modified to consider the last received text character instead of the full text. Below are the important code

segments which was used to implement this.  

Computation of the prefix function was done as below

   
 1.      private int[] calculatePrefixFunction(char[] pattern) {  
   
 2.      pi = new int[pattern.length];  
 3.      int m = pattern.length;  
 4.      pi[0] = 0;  
 5.      int k = 0;  
   
 6.      for (int q = 1; q < m; q++) {  
   
 7.        while (k > 0 && pattern[k] != pattern[q]) {  
 8.          k = pi[k-1];  
 9.        }  
   
 10.       if (pattern[k] == pattern[q]) {  
 11.         k++;  
 12.       }  
   
 13.       pi[q] = k;  
   
 14.      }  
   
 15.      return pi;  
 16.      }  
   

Then the text matching can be done using a KMP implementation as shown below. Here the input to the function is the latest character received so far as opposed to the original KMP algorithm, which takes the entire text as the input.

   
 1.      public int match(char text)  
 2.      {  
 3.      int m = pattern.length;  
 4.      i++;  
   
 5.      while (q > 0 && pattern[q] != text) {  
 6.       q = pi[q-1];  
 7.      }  
   
 8.      if (pattern[q] == text) {  
 9.       q++;  
 10.     }  
   
 11.      if (q == m) {  
 12.       shift = i - m + 1;  
 13.       q = pi[q - 1];  
 14.      }  
   
 15.      return shift;  
 16.      }  
   

Complexity Analysis: 

Computation of the prefix function

Using the potential method of amortized analysis it can be shown that the running time for computing the refix function is Q(m).We can associate a potential of k with the current state k of the algorithm where this potential has an initial value of 0 by line 5. Whenever line 8 is executed it reduces k since k <  pi[k-1]. However since pi[k] >= 0 for all k, k can never be negative. Line 11 increases k by at most one during each execution of the for loop. Since k <q  when entering to the for loop body and q is incremented during each loop of the body, k < q always remain true. That claims pi[q] < q as well by line 13. Since pi[k] < k we can pay for each execution of the while loop body on line 7 with the corresponding decrease in the potential function. Line 11 increases the potential function by at most 1 so that the amortized cost of the loop body on lines  7-13 is O(1). Since the number of outer loop iterations is Q(m) and since the final potential function is as greater as at least the initial potential function, the total actual worst case running time of calculatePrefixFunction is Q(m).

String matching

Using the potential method of amortized analysis it can be shown that the algorithm does a constant work (Q(1))) per each letter it receives. We can associate a potential of q with the current execution of the algorithm and this will have a potential of 0 initially. Since q < pi[q-1], each execution of line 6 reduces q. however since pi[q] >=0 for all q, q can never become negative. For each letter received line 9 increases q by at most one. However q < pi[q-1] remains true while the execution the algorithm for all the letters. Therefore we can pay for each execution of while loop at line 5 with the corresponding decrease in the potential function. Line 9 increases the potential function at most by one so that the amortized cost of the method body form lines 5-13 O(1). Hence for each letter received match function do a constant amount of work. 

Test Cases : 

Capturing pattern to be searched

Searching pattern and displaying the occurrence of the pattern

Finding the pattern in a reversed message

If the pattern is P and text is T, searching for an occurrence of P in T is equivalent to searching for an occurrence of reversed P in reversed T. So if the text is received in the reverse order we can find the occurrence of reversed pattern in the text. Hence, KMP algorithm implementation was changed to calculate the prefix function of reversed pattern.

Code segment which computes prefix function for the reversed pattern is as follows.

   
 1.      public KMPAlgorithm(char[] pattern) {  
 2.      // store the patter received in the reverse order  
 3.      this.pattern = new char[pattern.length];  
 4.      for(int i=pattern.length-1;i>=0;i--){  
 5.        this.pattern[pattern.length-1-i] = pattern[i];  
 6.      }  
 7.      this.calculatePrefixFunction(pattern);  
 8.      }  
   

Test Cases : 

Capturing pattern to be searched

Searching pattern and displaying the occurrence of the pattern

Why blogging is important for a researcher ?

As a start for this new blog series of mine, I thought of spending some time to think how blogging can be beneficial for a researcher. Time is gold : valuable and limited; hence, it is very important to spend each second doing something worthwhile. Blogging is something upon which you can spend a generous amount of time without a hesitation as it bears a positive Return on Investment. I compiled a list of reasons for why I think blogging is important for someone pursuing a research career. 

•         Expands the knowledge base.

The more you think, read, learn and experiment the more you can blog. Eventually it expands the knowledge base and help to gain expertise in many areas.

•       Increases the hunger to research

Blogging and researching go hand in hand and it has become a new paradigm in research communication. To compile quality blogs one needs to engage in more research. Hence, blogging is a good medium to enhance the research career, especially for beginners pursuing a research career.

•         Expands social connections

There are many bloggers out there in the blogosphere who blogs on a variety of things. When you start blogging and researching, it is obvious that you may drop in on good or debatable posts and comment on them. And the vice versa can be expected.  Hence, you can get connected with many people who are the expertise in areas of your interest.

•       Establishes your name in the globe and creates a space for your voice

When you blog stuff you are researching about, others who are researching the same area may pay a visit on your posts. The posts you have compiled can become useful to those who are searching on those research areas. This leads your name to be established among a wider audience.

Blog is a best way of conveying your genuine thoughts and perspectives for a wide audience around the globe.

•  Reduces stress and a means of spending leisure time effectively

Blogging is a gainful hobby to engage with in leisure time. As the thoughts stocked in the mind are poured in to a blog post, more relaxed and happy you can be.  

•  Polishes the writing skills

Writing skill is a major tool for a good researcher.  Blogging helps to polish this skill progressively.

These are not the only benefits and this is just a list of benefits that crossed my mind for the moment. Following is a good article I came across in the web where  Patrick Dunleavy and Chris Gilson  talks about how blogging can help academics .

Fiveminutes with Patrick Dunleavy and Chris Gilson: “Blogging is quite simply, oneof the most important things that an academic should be doing right now”.