Sorting & Knowledge database in prolog

Introduction

All data in Prolog are represented by Prolog terms. Every term is either a variable or a compound term , where variables start with an uppercase letter or with an underscore .If there was a single underscore then it means an “anonymous variable” and also can be read as "any term". All data in Prolog can be represented in this way.if a term has no variables then it is called ground. Also a compound term is called partially instantiated if one of its sub-terms is a variable .Prolog language is dynamically typed and gives us freedom for representing data.

Bubble sort in prolog

The simple bubble sort algorithm is made up of two main loops, first traversing the list, if each pair of elements are not in order then swap them (inner loop).

Then repeat step one on the result until the list is completely sorted (outer loop).

The inner loop can be expressed like this:

% the first step of a bubble-sort on a list

sort_bubble([], []).

sort_bubble([X], [X]).

sort_bubble([X0,X1|Xs], [X0|Rem]) :-

    X0 =< X1, !,

    sort_bubble([X1|Xs], Rem).

sort_bubble([X0,X1|Xs], [X1|Rem]) :-

    sort_bubble([X0|Xs], Rem).

sort_bubble/2  takes a list, and recursively swaps consecutive elements in the list if they don't satisfy the =< test.  Then the Outer loop predicate calls the inner loop is, bubble_sort/2, as shown :

% recursively performing a bubble sort on the list 

bubble_sort(L, SL) :-

    sort_bubble(L, L0),

    (sorted_order(L0) ->

        SL = L0

    ;   bubble_sort(L0, SL)

    ).

This predicate takes the input list and recursively applies sort_bubble/2 until the predicate sorted_order/1 succeeds on the result,which is when the list is eventually sorted. The sorted_order can be defined as :

% checks the list if is sorted ascendingly 

sorted_order([]).

sorted_order([_]) :- !.

sorted_order([X0,X1|R]) :-

    X0 =< X1,

    sorted_order([X1|R]).

Then , the predicate takes the list and checks that each pair of consecutive elements are in sorted order.

Merge sort

The merge sort in prolog looks as follows:

% First the empty list must be returned as it is

mergesort([], []).

% same as single element lists

mergesort([X], [X]).

% and now for the catch-all:

mergesort([X|Xs], S) :-

    length(Xs, Len),

    0 < Len,

    half_split([X|Xs], Ys, Zs),

    mergesort(Ys, SY),

    mergesort(Zs, SZ),

    merge(SY, SZ, S).

Let's start with merge, which takes two sorted lists then produces a new sorted list which contains all elements in them. Using recursion and pattern matching to implement merge.

% First two cases: merging any list Xs with empty list which yields Xs

merge([], Xs, Xs).

merge(Xs, [], Xs).

% Other cases: the @=< predicate compares terms by the "standard order"

merge(Xs, Ys, S) :-

    Xs = [X|Xs0],

    Ys = [Y|Ys0],

    (X @=< Y ->

        S = [X|S0],

        merge(Xs0, Ys, S0)

    ;

        S = [Y|S0],

        merge(Xs, Ys0, S0)

    ).

Then we define half_split, which splits a list into two lists of probably equal size. we need the length of a list, which we do not get as input , so we need to compute that. We use a predicate split_at to actually split the list after computing the length.

half_split(Xs, Ys, Zs) :-

    length(Xs, Len),

    Half is Len // 2,    % // rounding down

    split_at(Xs, Half, Ys, Zs).

  split_at:

% divides List Xs into a list Ys of length N, and a list Zs contains the part which is after the first N.

split_at(Xs, N, Ys, Zs) :-

    length(Ys, N),

    append(Ys, Zs, Xs).

The list Xs, split after its first N elements into Ys and Zs, means that Ys has length N and Ys and Zs can be appended to retrieve Xs."

Facts database

Knowledge Base is simply a collection of facts. Facts are used to state things that are true of some situation of interest. For example, we can say that Bella plays guitar and a party is taking place and sophie, Bella, and mary are women , using these facts in Prolog: 

   woman(sophie).

   woman(Bella).

   woman(mary).

   playsGuitar(Bella).

   party.

We can use this database by posing queries. Which means asking questions about the information We can ask Prolog whether sophie is a woman by posing the query:

   ?-  woman(sophie).

The answer is yes

for the obvious reason that this is a fact recorded in the database. Similarly, we can ask whether Bella plays guitar by asking

   ?-  playsAirGuitar(Bella).

The answer is yes, because this is one of the facts in KB1. However, suppose we ask   

?-  playsGuitar(vincent).

The answer is no. Because this query is about Vincent that it has no information about

Facts and rules database 

Here is our second knowledge database:

There are two facts in, listens2Music(sophie) and happy(mary) . The last three items it contains are rules.

   happy(mary).

   listens2Music(sophie).

   listens2Music(mary):-  happy(mary).

   playsGuitar(sophie):-  listens2Music(sophie).

   playsGuitar(mary):-  listens2Music(mary).

Rules state information that is conditionally true of a certain situation of interest. The first rule says that Mary listens to music if she is happy, and the last rule says that Mary plays guitar if she listens to music.This step is called modus ponens.

Suppose we ask whether sophie plays air guitar:

   ?-  playsGuitar(sophie).

Prolog will respond yes. Although it can’t find playsGuitar(sophie) as a fact, it can find the rule

   playsGuitar(sophie):-  listens2Music(sophie).

This knowledge database also contains the fact listens2Music(sophie) . Therefore Prolog can deduce that it playsGuitar(Sophie) .

Suppose we ask:

   ?-  playsAirGuitar(mary).

The answer is yes. first of all, by using the fact happy(mary) and the rule listens2Music(mary):-  happy(mary). Prolog can deduce the new fact listens2Music(mary) . This fact is not recorded in the knowledge base , it is only implicitly present . So Prolog can use it just like a recorded fact. from this fact and the rule

   playsAirGuitar(mary):-  listens2Music(mary).

it can deduce playsAirGuitar(mary) , which is what we asked it.

Conclusion 

Therefore Prolog can be given the premises as facts, and if you ask it about the conclusion, it will respond "yes" . If you like you can make the predicate names shorter or longer, of course you could. Concerning sort algorithms, there are many advanced built-in ways in prolog such as sort() functions and others.

Resources 

Adam Lally; Paul Fodor (31 March 2011). "Natural Language Processing With Prolog in the IBM Watson System". Association for Logic Programming. 

Felty, Amy. "A logic programming approach to implementing higher-order term rewriting." Extensions of Logic Programming (1992): 135-161

Clocksin, William F.; Mellish, Christopher S. (2003). Programming in Prolog. Berlin ; New York: Springer-Verlag

SWI-Prolog development