Thursday, July 19, 2012

Calling Prolog from Foreign Languages

When you define Prolog clauses for global predicates  as being of foreign language, those predicates may be called from foreign languages. They will have parameter access and entry and exit code, including register preservation, as for the language specified.
Example:predicate called from .pro in C language
/* Program hello_p.pro */
global predicates
char prohello_msg(string) - (i) language c
hello_c - language c
clauses
prohello_msg(S,C) :-
write(S," (press any key)"), readchar(C).
goal
prohello_msg("Hello from  Prolog"),
hello_c.

The global predicate prohello_msg is now accessible from C and can be called just like any other C function:

Wednesday, July 18, 2012

Multiset data structure implementation in java

Multiset  is a generalized version set structure.Similar to set, multiset only stores data values without  guarantee of any particular ordering of its contents. On the other hand, it allows storing of multiple items with the same value (ie. supports non-unique keys).

It can be implemented using list but for optimal result i.e O(1) hash table structure should be used. Otherwise it  takes O(n) steps, where n is number of distinct elements stored.

Source Code (JAVA)
01. /**
02.* Multiset implemented using two lists (list of values, list of occurrences)
03.* @author Pavel Micka
04.* @param <ENTITY> type parameter of the contained value
05.*/
06.public class Multiset<VALUE> {
07. 
08.private List<VALUE> values;
09.private List<Integer> occurences;
10. 

set data structure implementation in java

Set refers an abstract data structure used for storing data elements. Analogy with the mathematical term set, it does not guarantee any particular order of the stored elements and contains every value at most once (i.e. contains only unique values).
Similarly we can define multiset (bag) – a set, which may contain each value more than once. we can implement disjoint,union and difference of these set like in set theory of mathematics.

Source Code(JAVA)
/**
 * Set implemented as a list (using ArrayList)
 * @author Pavel Micka
 * @param <ENTITY> Type parameter of the contained value
 */
public class Set<ENTITY> {
    private List<ENTITY> list;
    /**
     * Constructor
     * @param initialCapacity initial capacity of the underlying ArrayList
     */
    public Set(int initialCapacity){
        list = new ArrayList<ENTITY>(initialCapacity);
    }

Prune and Search Alogrithm and implemetation in java

Prune and search is a method for finding an optimal value by iteratively dividing a search space into two parts – the promising one, which contains the optimal value and is recursively searched and the second part without optimal value, which is pruned (thrown away). This paradigm is very similar to well know divide and conquer algorithms.



* Prune and search
* @param array array to be searched in
* @param index order of the searched value (indexed starting at 0)
.* @param left first elemenent, which can be touched
* @param right first element, which cant be touched
* @return n-th largest value
*/
public static int pruneAndSearch(int[] array, int index, int left, int right) {
int boundary = left;
for (int i = left + 1; i < right; i++) {
if (array[i] > array[left]) {
 //place after the pivot every value, which is larger than the pivot
swap(array, i, ++boundary);
}
}

Interpolation Search implementation in java

The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.

The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. Interpolation search calculates a position p, where the value should be placed in accordance to the distribution of values a splits the array at p. If the array contains numbers 0, 1,\; 2, \cdots,\; 10 and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position (index 9) and immediately finds the value. The expected complexity of the interpolation search in O(\log(\log{n})).



/* Interpolation search
* @param array array with uniformly distributed values in ascending order
* @param value searched value
* @param from first index that might be touched
* @param to last index that might be touched
* @return index index of the searched value in the array, -1 if not found
*/
public static int interpolationSearch(int[] array, int value, int from, int to){
if(array[from] == value) return from;
else if(from == to || array[from] ==  array[to]) return -1; //not found
//probable position of the searched value
int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);
if(array[index] == value) return index;//found
//continue in the right part of the array
else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);
//continue in the left part of the array
else return interpolationSearch(array, value, from, index - 1);
}


Depth First Search Algorithm and implementation in c++

DFS is the basic tree search technique in which goal,data is searched by moving downward until a leaf,end node, is reached.Then it backtrack and repeat the moving down to leaf process.This process is repeated until the searching data is found.

Algorithm
An algorithm for the depth – first search is the same as that for breadth first search except in the ordering of the nodes.

  1. Place the starting node s on the top of the stack.
  2. If the stack is empty, return failure and stop.
  3. If the element on the stack is goal node g, return success and stop. Otherwise,
  4. Remove and expand the first element , and place the children at the top of the stack.
  5. Return to step 2.
     
    #include <iostream>
    #include <ctime>
    #include <malloc.h>
    using namespace std;
    struct node{
        int info;
        struct node *next;
    };
     

Breadth-First Search Algorithm and implementation in c++

BFS is most useful searching technique in database.In this technique,form the tree of data, corresponding child nodes of current state node is selected first during the searching process.Then in next step the childrens' of these selected child nodes will be searched.In this way exploring all nodes at a given depth before proceeding to the next level this searching method is implemented.
Algorithm
BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search. The BFS algorithm proceeds as follows.

  1. Place the starting node s on the queue.
  2. If the queue is empty, return failure and stop.
  3. If the first element on the queue is a goal node g, return success and stop Otherwise,
  4. Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
  5. Return to step 2.
    Source Code 
    #include <iostream>
    #include <ctime>
    using namespace std;
    struct node {
        int info;
        node *next;
    };

Tuesday, July 17, 2012

Monkey- Banana Problem in Prolog

Monkey-Banana Problem is the famous problem in AI. Where there is a room containing a monkey, a chair, and bananas that have been hung from the center of the ceiling of the room; out of reach from monkey. If the monkey is cleaver enough, he can reach the bananas by placing the chair directly below the bananas and climbing on the top of the chair.
Now the problem is to use FOPL to represent this monkey-banana problem and prove that monkey can reach the bananas.
The program is given below. Before running the program, think carefully what are the essential objects of the problem and how should them be arranged in predicate logic. 

PREDICATES
in_room(symbol)
dexterous(symbol)
tall(symbol)
can_move(symbol,symbol,symbol)
can_reach(symbol,symbol)
get_on(symbol,symbol)
can_climb(symbol,symbol)
close(symbol,symbol)
under(symbol,symbol)
can_climb(symbol,symbol)