Wednesday, February 25, 2009

Adventures in Prolog - Simplify Sum (2)

The last post showed how to compute simple addition expressions. To provide a more structured approach to the problem at hand, I decided to write a small Prolog program that actually recognizes such addition expressions. This program basically represents a Prolog conversion of the grammar underlying such addition expressions. Because Prolog notation and grammer are so close, I will not comment on the following Prolog clauses.

addition_expression(A) :- sum_term(A).
addition_expression(A) :-
A = X + Y,
addition_expression(X),
sum_term(Y).

sum_term(X) :- number(X).
sum_term(X) :- atom(X).
sum_term(X) :- prod_term(X).

prod_term(X) :- X = A * B, number(A), atom(B).
prod_term(X) :- X = A * B, atom(A), number(B).

Sunday, February 22, 2009

Adventures in Prolog - Simplify Sum (1)

Today's post is concerned with (the first part of) an example task from the book "Prolog Programming For Artificial Intelligence" - it is a about the simplification of additive terms using Prolog's facilities to reason about the type of some symbol.

For example, Prolog offers the following (and more) built-in predicates:
  • number/1 - is the argumet passed, a number, e.g. number(1) returns true
  • atom/1 - is the passed argument an atom, e.g. atom(x) returns true
  • compound/1 - is the passed argument a compound term, e.g. compound(X+Y) returns true

Now, that we know how to inspect the type of some Prolog symbol, we may take a look onto today's task. Given some summation, the task is to simplify this summation, using some predicate called simplify_sum or simp_sum (for short).

For example:

  • 1 +2 +3 = 6
  • 1 +a = a +1
  • a + b + 1 + c = a+ b +c + 1
  • a + 1 +2 + b = a + b + 3

So in short, the summation should be ordered with atoms first and aggregated numbers last. The original task by Bratko is concerned with the aggration of atoms as well, such as x +x = 2*x, but I will keep this for the next post.

So based on the above statement of the problem, we must consider some elementary cases, such as:

  • number + atom = atom + number
  • number + number = number
  • atom1 + atom2 = atom1 + atom2
  • atom + number = atom + number

These cases will act as the recursion anchor in our simp_sum clauses. Based on this reduction to the simplest form of the problem (please note, that we do not consider a case where only one atom or one number is passed to simp_sum), we identify more advanced incarnations of the problem.

We must consider the following:

  • some compound term + number
  • some compound term + atom

cases as well. The reason for compound term occuring only on the left-hand side is the associativity of the + operator. For example. 3 + 4 + 5 is (3 + 4) + 5 and consuequently we have 3+ 4 +5 = compound + number where compound = number + number.

Putting together all this information we might come up with the following ...

simp_sum(X + Y, R) :- number(X), number(Y), R is X + Y.
simp_sum(X + Y, X + Y) :- atom(X), number(Y).
simp_sum(X + Y, Y + X) :- atom(Y), number(X).
simp_sum(X + Y, X + Y) :- atom(X), atom(Y), X \== Y.


%Result of simpsum is not compound
simp_sum(X + Y, Z) :-
simp_sum(X, X0), number(X0), number(Y), Z is X0 + Y.
simp_sum(X + Y, Y + X0) :-
simp_sum(X, X0), number(X0), atom(Y).


%Result of simpsum is compound
simp_sum(X + Y, A + Y0) :-
simp_sum(X, X0),
number(Y), X0 = A + B,
number(B), simp_sum(B+Y, Y0).

simp_sum(X + Y, A + B + Y) :-
simp_sum(X, X0), number(Y), X0 = A + B, atom(B).

simp_sum(X + Y, A + Y + B) :-
simp_sum(X, X0), atom(Y), X0 = A + B, number(B).

simp_sum(X + Y, A + B + Y) :-
simp_sum(X, X0), atom(Y), X0 = A + B, atom(B).

When Prolog is asked:

simp_sum(1 + b + 2 + c + a + 4 + d + 39 + e+ f + 122, X).

It answers correctly:

X = b+c+a+d+e+f+168 .

Thursday, February 19, 2009

Adventures in Prolog - Computations with lists II

As mentioned in my last post, this post is concerned with building some abstraction when computing with lists. For this, I will abstract the the addList and mulList prodecures into one more general processList procedure. processList will iterate over a list and process it according to some user-defined function. Users of F# might recognize this from F#'s map function offered by a list object.

At first we define the processList function. processList takes 4 input parameters - a list, a processing function some identity element and the result. processList processes some input list according to the provided processing function. The identity Identity element is used to process the empty list. The result of this operation is placed into the variable Res
.

%processList/4
processList([], F, Identity, Identity) :- functor(_, F, 3).
processList([HT], F, Identity, Res) :-
functor(_, F, 2),
processList(T, F, Identity, L1),
apply(F, [H, L1, Res]).

The functor procedure checks whether the user supplied processing function F is indeed a function accepting 3 Variables (F/3). processList is similar to mulList or addList, in that it uses the recursive definition of a list to process each list element. apply is used to call the user-supplied procedure F with submitted input variables.

By itself processList does not do much, it is merely the skeleton to enable abstract computation on lists. To make use of it, we have to define some processing function F.
As mentioned, I want to use processList to abstract addList and mulList. For this, let's define two ternary relations add and mul. add is used to realize addList and mul is given to realize mulList. Their definition is straightforward and presented in the following.

%test ops
add(X, 0, X).
add(0, _, 0).
add(X, Y, Z) :- Z is X + Y.

mul(_, 0, 0).
mul(0, _, 0).
mul(X, 1, X).
mul(1, X, X).
mul(X, Y, Z) :- Z is X*Y.

Given the above definitions, we may ask Prolog now:
?- processList([1, 2, 3, 4, 5], add, 0, R).
, which yields:
R = 15

Clearly, add and mul are simple examples but more powerful processing functions can be implemented and passed to processList.

Wednesday, February 18, 2009

Adventures in Prolog - Computations with lists

My last post was concerned with basic computations in Prolog using the powerful technique - recursion. Today's post is concerned with recursion as well, but this time recursion is applied to Prolog's main data structure - the list.

A list in Prolog is a recursive data structure itself. Why? Because a list can be built by remembering the following ...

1. the empty list [] is a list
2. a list can be built by appending any list T to an item H, which yields [HT]

Using this definition we can see that the list [1, 2, 3, 4] is indeed a list with H = 1 and T = [2, 3, 4]. Consequently, a list cannot only be built from points 1. and 2. but also decomposed according to 1. and 2. Therefore 1. and 2. form the underlying principle when computing with lists in Prolog.

Now that we have covered the basic principle underlying a list. I will present two operations on lists - the addition of elements of a list (sumList) and the multiplication of elements of a list (mulList).

Both operations make use of the presented recursive structure of a list. The needed recursion anchor is the processing of the empty list. This maps to the identity operation in addition and multiplication. Identity in addition is performed using the zero element thus - a + 0 = 0 + a = a. Identity in multiplication is done by multiplying with the one element thus a * 1 = 1 * a = a.

Employing both identities, the definition of sumList and mulList become straightforward. A list is peeled down until it is stripped to the empty list, in this case the identity operation is performed. While peeling the list each element is either added or multiplied with the result obtained by performing the operation on the remaining unpeeled list (the list's tail T).

%sumList/2 sum list elements%
sumList([], 0).
sumList([HT], L) :-
sumList(T, L1),
L is H + L1.

%mul list elements%
mulList([], 1).
mulList([HT], L) :-
mulList(T, L1),
L is H * L1.

In my next post, I will cover the abstraction from special computations on lists to defining a general operation on a list, which executes a special function on each list item. This is similar to F#'s list-map function.

Sunday, February 15, 2009

Adventures in Prolog - Simple computations

This time I present a way to calculate the ith power of some integer j (i is also an integer number). Clearly, this is nothing too sophisticated but it will be helpful for some other program, I want to show later on.

Power is implemented as a simple ternary relation, which uses recursion. The base cases for power are of course the 0th and 1st power of some integer number. All other powers will be dependant on this anchor. The ith power of j means that j is multiplied with itself i times. For instance, the 3rd power of 2 is eigth, which is 2 * 2 * 2 = 8. This is used to implement the recursive core of power, which is ith power of j is the j * (i-1)th power of j.

After the basic power relation, power10 and power2 show how to use existing relations to implement some simple abstractions.


%power/3
power(X, 0, 1).
power(X, 1, X).
power(X, Y, Z) :-
Y1 is Y - 1,
power(X, Y1, Z1),
Z is X * Z1.

%power10/2
power10(P, R) :- power(10, P, R).
%power2/2
power2(P, R) :- power(2, P, R).

Adventures in Prolog - Fibonacci

As I have played around with Prolog lately, I wanted to share some enriching moments with my new favourite pet. We start of with the famous Fibonnaci numbers and their computation in Prolog. To spice things up, I used the dynamic clause, which enables one to add clauses to an existing database.


:- dynamic(fib/2).
fib(0, 1).
fib(1, 1).
fib(F, X) :-
F1 is F-1,
F2 is F-2,
fib(F1, X1),
fib(F2, X2),
X is X1 + X2,
asserta(fib(F, X)).


So what does this listing do? Clearly, it computes the ith value of the Fibonacci sequence using recoursion. Therefore, the recoursion anchor - 1st and 0th value - of the sequence is established first. After that the definition of the sequence is given in its known form.
By making the predicate fib/2 dynamic, we can add facts to the list of clauses covering fib/2. Dynamic has to be executed upon loading the fib database. That is why we write :- dynamic(fib/2). .
Now new knowledge about the Fibonnaci values can be added to the database. This is what is done later one with the asserta statement - asserta adds new clauses at the beginning of the database (assertz at the end). The value of the computation of the jth Fibonacci sequence value (fib(J, X)) is added as a fact to the database, thereby speeding up future computations of the same Fibonacci sequence value.