Logtalk - Hello World

According to the SWI-Prolog Mailing List, ...

Logtalk is an object-oriented logic programming language that can use most
Prolog implementations as a back-end compiler. As a multi-paradigm language, it includes support for both prototypes and classes, protocols (interfaces), component-based programming through category-based composition, event-driven programming, and high-level multi-threading programming.

For this, it seems worth trying Logtalk in order to lift Prolog programming to a different level (more contained). As usually, the first program show-casing some programming language is the famous "hello world" program. Unlike, other programming languages the Prolog version of "hello world" is a family relation.

Since this post is merely to maintain flow, I will present a "hello world" in Logtalk. Logtalk helps decomposing program logic by offering the well known concept of object and interface (including visibility of object members).

Behold .. the magic "hello world":

:- object(first_program).
  :- public(main/1).

  hello_world(Text) :- write(Text), nl.

  main(Text) :-
    hello_world(Text).

:- end_object.

As can be guessed, the program is quite simple. An object called first program is declared,
offering a publicly visible method called main. main passes one argument, i.e. some text to print, to the famous hello_world procedure. hello_world calls Prolog's write function to write the passed text on some line, adding a newline at the end of the text.

After consulting the program, one may call main using

first_program::main('Hello World').

Prolog – Mindstorms (I)

The last friday, I received my Lego Mindstorms NXT 2.0 – THANKS! Unfortunately, I lack the necessary power supply in form of 6AA batteries. Clearly, I went to my favorite retailer – Amazon – and ordered a couple of rechargeable ones (including the recharger).

Since my mind is somehow attached to Prolog, I asked myself would it be possible to do the mind-storming in Prolog … so I fired up the information retrieval engine of the day … and hit:

1. [English] New Mexico State University: Building and Programming Robots
   http://www.cs.nmsu.edu/~tson/classes/fall03-579/schedule.htm
2. [German] University of Potsdam: Programmieren in Prolog
   http://www.cs.uni-potsdam.de/wv/03SS/aktuell.html#SECTION00051000000000000000
3. [German] Toni Gläser: LEGOLOG - Lego Mindstorms und ein Golog-Planer Eine Einführung und ein Überblick über das Konzept und die
   Programmierung sowie die Implementation von Aufgaben für
   den Roboter
   http://www.kbs.uni-hannover.de/~brase/Paper/studienarbeit_Prolog.pdf
4. [English] Fermé and Gaspar: RCX+PROLOG
   A platform to use Lego Mindstorms™ Robots in
   Artificial Intelligence courses
   http://dme.uma.pt/ferme/Papers/Ferme-Gaspar07.pdf
5. [English] University of Toronto: Cognitive Robotics
   http://www.cs.toronto.edu/cogrobo/main/systems/index.html
6. [English] Nalepa: Prototype Prolog API for Mindstorms NXT
   http://www.springerlink.com/content/9r47108w18835742/

Clearly, I will inspect some of these resources soon to see what’s in the Lego Prolog toolbox. Until then happy robot-building.

Adventures In Prolog - General Reading (2)

Since I have not posted anything for while, I thought I keep the flow running, by pointing to Boehm's "Document Analysis Experiment" - applied NLP using Prolog.

Taken from the Overview section:

The main purpose of this document analysis program is to count the number of useful words in the document in various ways, and to use NLP to (hopefully)
improve the analysis.

You may find his project useful and interesting - so happy reading.

Adventures In Prolog - ProjectEuler20

Continuing with the Euler Quest, a simple and straight-forward solution to Project Euler's problem 20 is presented.

The problem statement reads:

Find the sum of the digits in the number 100!

Where ! denotes the faculty operator.

One (simple) way to solve the problem goes as follows:

Firstly, calculate the value of 100!. Secondly, convert the value into a list of digits. Thirdly, sum each digit. Lastly, output the cumulative result.

A translation of this solution may read like:

euler_20_1(F, Out) :-
  fac(F, Fac),
  string_to_list(Fac, CList),
  euler_20_1_t(CList, 0, Out), !.

euler_20_1_t([], Current, Current).

euler_20_1_t([X|Y], Current, Out) :-
  number_chars(N, [X]),
  NewCurrent is Current + N,
  euler_20_1_t(Y, NewCurrent, Out).

The fac predicate computes the faculty of some positive integer number. string_to_list is a built-in predicate converting a string into its character list representation and number chars converts between ascii character code and number. Building only on these relatively few predicates the code should be straight-forward.

Please note, that this solution is not the most efficient, in fact it may not work for very large numbers. To reduce the complexity of the faculty operation, we might additional knowledge like:

multiplying a number n by a multiply of 10 (n mod 10 = 0), does not change the value of the sum of the digits of the result. For example

3*4*10 = 120 but sum_digit(3*4*10) = sum_digit(3*4*100) = sum_digit(3*4) = 3

Now building on such knowledge, one might cut all numbers that multiplied together yield a multiply of 10 from the faculty operation. This approach will be covered in a future post.

On a different side node, a Prolog implementation of the Porter stemming algorithm can be found here.

Adventures In Prolog - Euler7 and the Nth Prime

Building on our previous prime-related posts, today's post will cover a solution to Project Euler's 7th Problem, i.e. finding the 10001st prime. Now, the solution to this problem can be easily expressed in thought and then converted to some programming language …

Starting with the lowest and first prime – 2 - , we check each subsequent number j > i, for primality. Whenever we find a j such that j is prime, we increment a prime counter c by one and continue testing numbers k > j. This is done until c reaches the number 10001.

The Prolog code below is an expression of this idea, added with some prime numbers found during the process of finding the 10001st prime. This means, given the border of some prime interval, i.e. 100th prime = i and 200th prime = j, we may start looking for the 150th prime within the number interval [i,j], instead of starting at 2 and checking each number until the prime counter reaches 150. Also, we might have defined the euler_7 predicate to be dynamic, i.e. updatable, such that whenever we find some kth prime, it will be stored in the fact database.

%EULER7 the 10001 prime
euler_7(4409, 600) :- !.

euler_7(Out, Xth) :-
  Xth < 600, !,
  euler_7_t(2, 1, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 700, !,
  euler_7_t(4409, 600, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1000, !,
  euler_7_t(5279, 700, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1100, !,
  euler_7_t(7917, 1000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1200, !,
  euler_7_t(8831, 1100, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1500, !,
  euler_7_t(9733, 1200, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 2000, !,
  euler_7_t(12553, 1500, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 3000, !,
  euler_7_t(17389, 2000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 4000, !,
  euler_7_t(27449, 3000, Xth, Out).
  
euler_7(Out, Xth) :-
  Xth < 5000, !,
  euler_7_t(37813, 4000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 7000,
  euler_7_t(48611, 5000, Xth, Out), !.

euler_7(Out, Xth) :-
  Xth < 10001,
  euler_7_t(70657, 7000, Xth, Out), !.

euler_7(Out, Xth) :-
  euler_7_t(104743, 10001, Xth, Out), !.


euler_7_t(P, Xth, Xth, P) :-
  is_prime(P), !.
  
euler_7_t(NP, Xth, Xth, P) :-
  NewPrime is NP + 1,
  euler_7_t(NewPrime, Xth, Xth, P), !.

euler_7_t(X, Xth, Gth, Prime) :-
  is_prime(X),
  Y is X + 1,
  Yth is Xth + 1,
  euler_7_t(Y, Yth, Gth, Prime), !.

euler_7_t(X, Xth, Gth, Prime) :-
  Y is X + 1,
  euler_7_t(Y, Xth, Gth, Prime).
%EULER7 the 10001 prime

Adventures in Prolog - Some more Primes

Again, we are going to tackle some problems mentioned in the list of 99-Prolog problems. Today's post builds upon the gcd predicate defined last time to attack problems:

• P31 = is_prime


• P35 = prime_factors


• P36 = prime_factors_mult


• P39 = prime_list

Now, building on the previously defined gcd predicate, on may define a prime inductively:

• a prime is a number which is only (divisible by one and itself)


• the smallest prime is 2


• any number greater than 2 is either composite or prime

Building on this definition we may translate the smallest prime into a Prolog predicate quite easily. To determine the primeness/composibility of any number greater than 2, one may use the gcd predicate. Recalling that a prime p is a number which cannot be divided by any number in ]1, p[, the following predicate may be given:

is_prime(2) :- !.
is_prime(3) :- !.
is_prime(X) :-
  X >= 2,
  UpperBound is round(sqrt(X)) + 1,
  is_prime_t(X, 2, UpperBound), !.

is_prime_t(_, UpperBound, UpperBound).
is_prime_t(X, CurrentFactor, UpperBound) :-
  gcd(X, CurrentFactor, GCD),
  GCD = 1, !,
  NewFactor is CurrentFactor + 1,
  is_prime_t(X, NewFactor, UpperBound).

As can be seen above, two elementary cases (2 and 3) are given and any number not 2 or 3 is checked for primeness. Instead of checking composibility of a prime p for any number in ]1, p[, one may use any number in ]1, square_root(p)]. The reason why I used the rounded value of the square root + 1 is the case of checking 4 which would be determined as a prime because of:

is_prime_t(4, 2, 2).

Instead of the + 1, we might also a check on whether some number is even. Since we know that 2 is not only the smallest prime but also the only even prime number, such a check might greatly enhance the solution search.

Using this definition of is_prime, we might define the prime_list predicate quite easily. A prime list is generated from any number within some interval [a, b], which is prime. We might differentiate three cases (where the last is for convenience) in the definition of prime_list:

1. the interval is [a,b] where a=b


2. the interval is [a,b] where a<b


3. the interval is [a,b] where b<a

Case one results in a list containing one prime if a is itself a prime number. Case 3 will be mapped to case 2 where a and b are switched. This results in a possible prime_predicate as follows:

prime_list(X, X, [X]) :-
  is_prime(X), !.

prime_list(X, X, []) :- !.

prime_list(X, Y, L) :-
  X > Y,
  prime_list_t(Y, X, [], L), !.
 
prime_list(X, Y, L) :-
  prime_list_t(X, Y, [], L), !.
 
prime_list_t(X, X, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], OutPrimes);
  OutPrimes = CurrentPrimes.

prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], NewPrimes),
  Z is X + 1,
  prime_list_t(Z, Y, NewPrimes, OutPrimes).
 
prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  Z is X + 1,
  prime_list_t(Z, Y, CurrentPrimes, OutPrimes).

The last problem to cover is the prime factorization of some given number. This problem is handled by the two predicates prime_factors and prime_factors_mult. Where the first contains each (possibly duplicate) prime factor and prime_factors_mult delivers a power representation of the prime factors of some given number. The approach taken is quite simple, again the factorization of a prime number contains itself (and one which is not included). Also, any composite number can be represented uniquely by a product of prime factors. For example, 4 = 2 * 2 or 12 = 2 * 2 * 3. Now, provided this property of a natural number we may define our two predicates like this:

prime_factors(0, []) :- !.
prime_factors(1, []) :- !.
prime_factors(X, [X]) :- is_prime(X), !.
prime_factors(X, Out) :-
  prime_factors_t(X, 2, [], Out), !.
  
prime_factors_t(1, _, Out, Out).

prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  append(CurrentFactors, [GCD], NewFactors),
  Z is X / TestFactor,
  prime_factors_t(Z, TestFactor, NewFactors, Out).
  
prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  NewTestFactor is TestFactor + 1,
  prime_factors_t(X, NewTestFactor, CurrentFactors, Out).
  
prime_factors_mult(0, []) :- !.
prime_factors_mult(1, []) :- !.
prime_factors_mult(X, [X]) :- is_prime(X), !.
prime_factors_mult(X, Out) :-
  prime_factors_mult_t(X, 2, 0, [], Out), !.

prime_factors_mult_t(1, _, _, Out, Out).
prime_factors_mult_t(X, X, CurrentPower, CurrentFactors, Out) :-
  Power is CurrentPower + 1,
  append(CurrentFactors, [[X, Power]], Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  NewPower is Power + 1,
  Z is X / TestFactor,
  prime_factors_mult_t(Z, TestFactor, NewPower, CurrentFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power >= 1,
  append(CurrentFactors, [[TestFactor, Power]], NewFactors),
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, NewFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power = 0,
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, CurrentFactors, Out).

Essentially, prime_factors_mult performs the same steps as prime_factors. However, instead of creating a list for some prime factor right from the beginning, the power of that prime factor is accumulated and stored at last.

Happy, Prolog-ing and if you find any errors/typos please report them.

Adventures in Prolog - GCD and Coprime

Today's post follows the tradition of the my last post, i.e. it continues with another problem stated in the list of 99 Prolog problems. Today, we are going to have a look at problem 32 and 33.

Problem 32 concerns the implementation of a greatest common divisor predicate (gcd). In an earlier post, I implemented a gcd routine in Python. We are going to reuse this definition of gcd here, using a ternary predicate/relation.

The Prolog definition of gcd makes use of gcd's recursive definition, which are:

1. the gcd of two numbers x and y is equal to the gcd of x - y and y for y <>
2. the gcd of some number and 0 is the number
3. the gcd of some number and 1 is 1

Now, given the above properties (and some more) a possible gcd predicate might look like this:

gcd(A, 0, A) :- !. %includes gcd(0,0)
gcd(1, _, 1) :- !.
gcd(A, A, A) :- !.

gcd(A, B, GCD) :-
  A < B, !,
  X is B - A,
  gcd(X, A, GCD).

gcd(A, B, GCD) :-
  X is A - B,
  gcd(X, B, GCD).

Provided the above definition of gcd, the solution to problem P33 is given within the problem statement. For this, a predicate to determine coprimality may be defined as is:

coprime(X, X) :- fail.
coprime(X, Y) :- gcd(X, Y, 1).

Clearly, we could add more clause to avoid a computation of gcd when it is obviously not necessary. However this was omitted here.

Adventures In Prolog - Duplicate List Members

Today's post is about problem 14 from the list of 99 Prolog problems (see here):

(*) Duplicate the elements of a list.
Example:
?- dupli([a,b,c,c,d],X).
X = [a,a,b,b,c,c,c,c,d,d]

Since the problem is marked with one star, a solution should be within reach. Now, to duplicate each element of the list, we do the following:

1. We traverse the list element by element until we reach the last element, i.e. the empty list.


2. For each element (excluding the empty list), the element is added twice to a newly built output list.

Given the above solution statement, a possible translation to Prolog code might look like this:

dupli([], []).
dupli(L, O) :-  dupli_t(L, [], O).

dupli_t([], Current, Current).
dupli_t([H|T], CList, OutList) :-  
  append(CList, [H, H], IntermediateList),  
  dupli_t(T, IntermediateList, OutList).

Adventures in Prolog – A Simple Tokenizer

Today’s post is concerned with presenting a simple tokenizer that I have written during the last couple of weeks (not full-time off course). The tokenizer’s goal is to – off course – tokenize a provided sentence or input sequence of characters. For example, the following sentence:

“This is my world!”

Should be split up into individual descriptors/ tokens of the respective string part they cover, such as:

Word(This), Space(5), Word(is), Space(8), Word(my), Space(11), Word(world), EndOfSentence(!)

Now, given that the position of a space between characters can be computed by taking the length of the character sequence and adding one to it, we might not need to store the Space explicitly. Also, to avoid verbose representation of tokens we might shorten the name of individual tokens a bit. Since Prolog reserves upper case characters for variables, we might change the casing of tokens too. For example, the above token stream might be collapsed to:

w(This), w(is), w(my), w(world), eos(!)

Now, what difference does it make whether this is written with a capital t or not? Clearly, this is at the beginning of a sentence, but since we now that it is at the beginning of the sentence we might change casing here. Also transforming to lower case characters simplifies the implementation of the tokenizer somewhat, since we don’t need to deal with specific representations of a single character. For this, all characters will be transformed to lower case characters and the above sequence of tokens reduces too:

w(this), w(is), w(my), w(world), eos(!)

Adding a complement to the end of sentence indicator, i.e. beginning of sentence, marks each distinct sentence, such that the above token stream looks like:
bos(i), w(this), w(is), w(my), w(world), eos(!)
i in the bos() token identifies the ith sentence in a set of sentences. As you may see from the above example there are a few situations one wants to deal with in order to tokenize real-world sentences. For this, the tokenizer is spread across several Prolog files, each covering a separate aspect or token. Tokens covered are:

1. Words
   Description: A sequence of letters, possibly containing “-“ (bar), or “’” (apostrophe).
   Example: Hello, world, top-down, Mike’s, Andreas’, don’t
2. Simple Numbers (integer, float)
   Description: A sequence of digits, possibly containing a “.” (dot)
   Example: 1234, 12.343
3. Names, Quantities and Abbreviations
   Description: special words, stored in a name, quantity, abbreviation map
   Example: 5m (five meter), MS (Microsoft)
4. Unknown and unrecognized character streams
   Description: A sequence of arbitrary characters closed by a “ “ (space)
   Example: 34sd=+
   

Please note that in order to identify a sentence, a sentence must be properly terminated with one of the following: ‘.’ (Dot), ‘?’ (Question mark) or ‘!’ (Exclamation mark). Other types of (sub)sentence termination , such as the ‘-‘ (bar), ‘;’, (Semicolon), ‘,’ (comma) are handled as sentence fragment terminators. If you want to use the tokenizer, you may either tokenize a file containing sentences or a string. For this, you may use either of the following predicates:

• 
  tokenize_string(+InString, -OutTokenList)
  




• 
  tokenize_file(+InFile, -OutTokenList)
  

For example, you might ask:

3 ?- tokenize_string("this is my world!", X).
X = [[bos(0), w(this), w(is), w(my), w(world), eos(!)]].

Or you might ask:

tokenize_file(‘Path to file’, X).

The Prolog source code of the tokenizer can be found here. It is stored as a zip container. You will find the following inside the zip-file:

• Prolog source files (extension pl)


• Directory “Corpora” with two text files containing some text to test the tokenizer on.

Please note that I do not claim its robustness or coverage of 99% of the possible sentences. Also, performance has not been a major concern for me. For this you will not find the use of difference lists or optimized database access. This might be a future task as well. In fact, this is one of the many open points. However, in case that you do have found a bug, error or recommendation, please do contact me. Currently, I try to add features to the tokenizer and make it more stable. Also, documentation and code cleanup is a item on the to-do list.

Adventures in Prolog - LinkList (2)

Some time ago, I have done a small tokenizer, which I will present in one of the upcoming posts. However, this post is another link to some Prolog tutorials:

http://www.intranet.csupomona.edu/~jrfisher/www/prolog_tutorial/intro.html

All posted links and links that I will post in the future, will be collected on my Prolog link site at:

http://sites.google.com/site/bittermanpage/Home/prolog-links

This link will be available in the side bar as well.

Adventures in Prolog - LinkList

Here is a link to the Prolog directory of CMU's AI group:

http://www.cs.cmu.edu/Groups/AI/lang/prolog/

Adventures in Prolog - General Reading (1)

Today's post is merely the advertisement of a dissertation thesis that might be an interesting read:

Can Logic Programming Execute as Fast as Imperative Programming?
Peter Lodewijk Van Roy

ABSTRACT
The purpose of this dissertation is to provide constructive proof that the logic programming language Prolog can be implemented an order of magnitude more efficiently than the best previous systems, so that its speed approaches imperative languages such as C for a significant class of problems. The driving force in the design is to encode each occurrence of a general feature of Prolog as simply as possible. The resulting system, Aquarius Prolog, is about five times faster than Quintus Prolog, a high performance commercial system, on a set of representative programs. The design is based on the following ideas:

• Reduce instruction granularity. Use an execution model, the Berkeley Abstract Machine (BAM), that retains the good features of the Warren Abstract Machine (WAM), a standard execution model for Prolog, but is more easily optimized and closer to a real machine.
• Exploit determinism. Compile deterministic programs with efficient conditional branches. Most predicates written by human programmers are deterministic, yet previous systems often compile them in an inefficient manner by simulating conditional branching with backtracking.
• Specialize unification. Compile unification to the simplest possible code. Unification is a general pattern-matching operation that can do many things in the implementation: pass parameters, assign values to variables, allocate memory, and do conditional branching.
• Dataflow analysis. Derive type information by global dataflow analysis to support these ideas.

The thesis can be found here.

On that note I would like to mention a paper going for a similar direction, actually I found the thesis because of the paper.

Optimizing Prolog for Small Devices: A Case Study
M. Carro, J. Morales, Henk L. Muller, G. Puebla, M. Hermenegildo

Abstract
In this paper we present the design and implementation of a wearable application in Prolog. The application program is a “sound spatializer.” Given an audio signal and real time data from a head-mounted compass, a signal is generated for stereo headphones that will appear to come from a position in space. We describe high-level and low-level optimizations and transformations that have been applied in order to fit this application on the wearable device. The end application operates comfortably in real-time on a wearable computer, and has a memory foot print that remains constant over time enabling it to run on continuous audio streams. Comparison with a version hand-written in C shows that the C version is no more than 20-40% faster; a small price to pay for a high level description.

The paper can be found here.

The reason why posting these documents, is my thinking of maybe porting or reusing an existing Prolog implementation for the Nintendo DS. Unfortunately, I have not made great progress. But with some time, there may be something out there.

Adventures in Prolog - Simplify Sum (4)

Last post was concerned with implementing the simplification of an additive (compound) term. The proposed solution consists of three elementary steps (sorting, simplifying and reducing). Although the proposed solution is quite flexible, i.e. works on any atom not specifically a single character,
the sorting of characters decreases performance somewhat. For this, this post is concerned with a more targeted approach to the introduced problem.

Given an additive (compound) term containing numbers and (unitary) variable symbols (e.g., a, b, x, y, z), we wish to obtain a reduced form of this term, which simplifies the same variables and sums multiple numbers to one single number.

The following solution makes use of:

1. The (German and English) alphabet contains only 26 elementary characters (variable symbols)
2. Character symbols can be ordered according to their occurence within the alphabet.

Instead of operating on additive compound term, the proposed solution operates on a character array , i.e. array indexing individual variable characters. The following solution consists of two main steps:

1. Simplification of additive (compound) term
2. Computing a reduced printable form (string) of the simplified term.

Now, given the perimeters of the proposed approach, this is what it looks like:

map_index(a, 1).
map_index(b, 2).
map_index(c, 3).
map_index(d, 4).
map_index(e, 5).
map_index(f, 6).
map_index(g, 7).
map_index(h, 8).
map_index(i, 9).
map_index(j, 10).
map_index(k, 11).
map_index(l, 12).
map_index(m, 13).
map_index(n, 14).
map_index(o, 15).
map_index(p, 16).
map_index(q, 17).
map_index(r, 18).
map_index(s, 19).
map_index(t, 20).
map_index(u, 21).
map_index(v, 22).
map_index(w, 23).
map_index(x, 24).
map_index(y, 25).
map_index(z, 26).
map_index(V, 27) :- number(V).

map_index defines the array index of each variable symbol. index 27 is reserved as the computation cell for numbers.

increment(1, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A1, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- A1 is A + 1.
increment(2, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- B1 is B + 1.
increment(3, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- C1 is C + 1.
increment(4, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D1, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- D1 is D + 1.
increment(5, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E1, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- E1 is E + 1.
increment(6, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- F1 is F + 1.
increment(7, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- G1 is G + 1.
increment(8, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- H1 is H + 1.
increment(9, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- I1 is I + 1.
increment(10, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- J1 is J + 1.
increment(11, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- K1 is K + 1.
increment(12, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L1, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- L1 is L + 1.
increment(13, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- M1 is M + 1.
increment(14, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N1, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- N1 is N + 1.
increment(15, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O1, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- O1 is O + 1.
increment(16, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P1, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- P1 is P + 1.
increment(17, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q1, R, S, T, U, V, W, X, Y, Z, NN]) :- Q1 is Q + 1.
increment(18, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R1, S, T, U, V, W, X, Y, Z, NN]) :- R1 is R + 1.
increment(19, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S1, T, U, V, W, X, Y, Z, NN]) :- S1 is S + 1.
increment(20, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T1, U, V, W, X, Y, Z, NN]) :- T1 is T + 1.
increment(21, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U1, V, W, X, Y, Z, NN]) :- U1 is U + 1.
increment(22, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V1, W, X, Y, Z, NN]) :- V1 is V + 1.
increment(23, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W1, X, Y, Z, NN]) :- W1 is W + 1.
increment(24, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X1, Y, Z, NN]) :- X1 is X + 1.
increment(25, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y1, Z, NN]) :- Y1 is Y + 1.
increment(26, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z1, NN]) :- Z1 is Z + 1.

increment(27, Inc, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN1]) :- NN1 is NN + Inc.

increment uses an index and updates the respective variable or number cell. Note that, variables may only be
incremented by one, whereas numbers can be incremented by any other number (adding two numbers).

simplify(In) :-
simplify_a(In, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], OutMap),
print_simplified(OutMap), !.

simplify(_).

simplify_a(X, InMap, OutMap) :-
  atomic(X),
  map_index(X, I),
  print('Index: '), print(I), nl,
  increment(I, X, InMap, OutMap), !.

simplify_a(A + B, InMap, OutMap) :-
  atomic(A),
  atomic(B),
  map_index(A, I1),
  map_index(B, I2),
  increment(I1, A, InMap, TMap),
  increment(I2, B, TMap, OutMap), !.

simplify_a(A + B, InMap, OutMap) :-
  compound(A),
  atomic(B),
  map_index(B, I),
  increment(I, B, InMap, TMap),
  simplify_a(A, TMap, OutMap), !.

simplify_a(_, InMap, InMap).

simplify calls simplify_a, which is responsible for obtaining a simplified representation from some additive term.

print_simplified(In) :-
  print('Result:'), nl,
  str_simplified_t(In, 1, '', OutStr),
  print(OutStr), nl, !.

get_no(_, 0, '').
get_no(Char, 1, Char).
get_no(Char, X, X*Char).

str_simplified_t([0|Rest], Index, TStr, RStr) :-
  Index1 is Index + 1,
  str_simplified_t(Rest, Index1, TStr, RStr), !.

str_simplified_t([X, 0], 26, TStr, RStr) :-
  map_index(Char, 26),
  RStr = TStr + X*Char, !.

str_simplified_t([X, N], 26, TStr, RStr) :-
  map_index(Char, 26),
  get_no(Char, X, XStr),
  RStr = TStr + XStr + N, !.

str_simplified_t([X|R], 1, _, RStr) :-
  map_index(Char, Loop),
  get_no(Char, X, AStr),
  I1 is Loop + 1,
  str_simplified_t(R, I1, AStr, RStr), !.

str_simplified_t([X|R], Loop, TStr, RStr) :-
  map_index(Char, Loop),
  get_no(Char, X, XStr),
  AStr = TStr + XStr,
  I1 is Loop + 1,
  str_simplified_t(R, I1, AStr, RStr).

print_simplified calls str_simplified_t to compute the reduced string representing a simplified additive term of the initial additive term.

As one can see this solution is somewhat less complex and more performant than the previous solution. Most of the code is responsible for computing array indices or updating an array cell. For this, further (code length) optimizations may be identified. The array approach completely avoids the sort predicate thereby reducing run-time overhead. On the downside, this approach works with single characters instead of any atom.

Adventures in Prolog - Simplify Sum (3)

In an earlier installment the simplify_sum predicate was discussed. However it was not really a feature complete solution to the initially motivated problem. For this, this post is concerned with providing a newer version, which actually solves the following problem.

Given some additive formulae, such as:
1
a
1 + a
a + a
1 + a + 9 + b + a + b + c
we wish to obtain the following results:

1
1*a (or a)
1*a + 1 (or a + 1)
2*a
2*a + 2*b + 1*c + 10 (or 2*a + 2*b + c + 10)

The proposed solution will consist of three parts:

1.
order all parts of an additive equation according to letters and numbers.
place letters in order of the alphabet and summarize numbers, such that at most one number is present.

2.
summarize all variables. this leads to the transformation of x into 1*x

3.
reduce all variables from 1*x to x.

Translating the above sequence of steps into a Prolog program, leads to the following definition of the simplify_sum predicate:

simplify_sum(In, Final) :-
  sort_sum(In, SortedOut),
  simplify(SortedOut, Result),
  strip_sum(Result, Final), !.

A first naive implementation of sort_sum, checks whether some parameter is an atom or a number and arranges the output accordingly. The high level predicate sort_sum makes use of the acutal predicate called sort_sum_t. sort_sum_t implements a bubble sort approach to arrange numbers and atoms. If two numbers are encountered they are reduced to their sum.Elementary cases are only one number, one atom, two atoms, two numbers and atom and number. Compound cases split the input argument into simpler forms until input is elementary.

%sort_sum_t
sort_sum_t(X + Y, X + Y) :-
  atom(X),
  number(Y), !.

sort_sum_t(X + Y, X + Y) :-
  atom(X),
  atom(Y),
  char_code(X, CX),
  char_code(Y, CY),
  CX =< CY, !.

sort_sum_t(X + Y, Y + X) :-
  atom(X),
  atom(Y), !.

sort_sum_t(X + Y, Y + X) :-
  number(X),
  atom(Y), !.

sort_sum_t(X + Y, Res) :-
  number(X),
  number(Y),
  Res is X + Y, !.

%compounds
sort_sum_t(C + X, Res) :-
  sort_sum_t(C, R1),
  number(R1),
  number(X),
  Res is X + R1, !.

sort_sum_t(C + X, X + R1) :-
  sort_sum_t(C, R1),
  number(R1),
  atom(X), !.

sort_sum_t(C + X, A + Res) :-
  sort_sum_t(C, A + B),
  number(B),
  number(X),
  Res is B + X, !.

sort_sum_t(C + X, A + B + X) :-
  sort_sum_t(C, A + B),
  atom(B),
  number(X), !.

sort_sum_t(C + X, Res + B) :-
  sort_sum_t(C, A + B),
  number(B),
  atom(X),
  sort_sum_t(A + X, Res), !.

sort_sum_t(C + X, Res + B) :-
  sort_sum_t(C, A + B),
  atom(B),
  atom(X),
  char_code(B, CB),
  char_code(X, CX),
  CX =< CB,
  sort_sum_t(A + X, Res), !.

sort_sum_t(C + X, A + B + X) :-
  sort_sum_t(C, A + B),
  atom(B),
  atom(X), !.

sort_sum(X, X) :- atom(X), !.
sort_sum(X, X) :- number(X), !.

sort_sum(In, Out) :- sort_sum_t(In, Out), !.

sort_sum(_, _).

Now that an input additive term is sorted according to variables and numbers, it may be processed. This processing, i.e. summing equal atoms and numbers is handled by the simplify predicate, which in turn calls simplify_t to summarize some additive input term. special cases correspond to those identified for the sort_sum predicate. However, simplify_t can make use of the following: (1) there is only one number in the input term, which is at the right most position and (2) an atom follows another atom which is either equal to itself (only having higher quantity) or is a smaller atom.

simplify_t(X, 1*X) :- atom(X), !.

simplify_t(A*X, A*X) :-
  atom(X),
  number(A), !.

simplify_t(X*A, A*X) :-
  atom(X),
  number(A), !.

simplify_t(X, X) :- number(X), !.

simplify_t(X + Y, 1*X + Y) :-
  atom(X),
  number(Y), !.

simplify_t(X + Y, 1*X + 1*Y) :-
  atom(X),
  atom(Y),
  X \= Y, !.

simplify_t(X + X, 2*X) :- atom(X), !.

simplify_t(X + I*X, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(X + X*I, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(I*X + X, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(X*I + Y, I*X + Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(I*X + Y, I*X + Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(X + Y*I, X + I*Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(X + I*Y, X + I*Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(A*X + B*X, C*X) :-
  atom(X),
  number(A),
  number(B),
  C is A + B, !.

simplify_t(X + Y, X + Y) :-
  atom(X),
  atom(Y), !.

simplify_t(A*X + B*Y, U + V) :-
  simplify_t(A*X, U),
  simplify_t(B*Y, V), !.

%compounds
simplify_t(C + X, R + X) :-
  number(X),
  simplify_t(C, R), !.

simplify_t(A + B, R*X) :-
  simplify_t(A, M*X),
  simplify_t(B, N*X),
  atom(X),
  R is M + N, !.

simplify_t(A + B, M*X + N*Y) :-
  simplify_t(A, M*X),
  simplify_t(B, N*Y),
  atom(X),
  atom(Y),
  X \= Y, !.

simplify_t(A + B, M + R*X) :-
  simplify_t(A, M + N*X),
  simplify_t(B, S*X),
  atom(X),
  R is N + S, !.

simplify_t(A + B, M + N + SX) :-
  simplify_t(A, M + N),
  simplify_t(B, SX), !.

simplify(In, Out) :- simplify_t(In, Out), !.

simplify(_, _).

Now that an additive term is transformed to its reduced form, the only thing left is to remove any unnecessary 1. That is reduce each 1*x to x. Again the compound case is reduced to atomic cases, which are 1*x = x, n*x = n*x, number = number.

strip_sum(X, X) :- number(X), !.

strip_sum(1*X, X) :- atom(X), !.

strip_sum(N*X, N*X) :-
  atom(X),
  number(N), !.

strip_sum(A + B, A1 + B1) :-
  strip_sum(A, A1),
  strip_sum(B, B1), !.

running the following example:

simplify_sum(a + b + c + d + a + c + 70 + a+ a + 50, X).
X = 4*a+b+2*c+d+120.

shows the correct working of simplify_sum.

As mentioned sort_sum makes use of a bubble sort approach, which clearly is less than optimal. For this, the next post is concerned with using a different sort_sum approach to speed simplify_sum up.

Adventures in Prolog - Computations with lists VII

Again, as I am quite busy these days, I will present some not recent predicates, just to keep the flow going. Quite recently, I have seen the world of depth, breadth and intelligent search in Prolog. For this, I am working on an implementation of the 8-queens problem. Unfortunately, this is nothing to show off at the moment. But probably in 2 weeks or so, I will be able to show present it here and demonstrate how elegantly one may solve problems using Prolog.

Today's post is about the detection of a palindrome using Prolog. A palindrome is defined as some word that can be read from start to end or end to start and it will not change. For example, the word ANNA is a palindrome.

Now, using the idea that a palindromic word is a word that can be read back and forth and does not change, we come with the following ...

Let X be some word. If X is the empty word then it is a palindrome. If X is not the empty word then let Y be the reverse of X. If Y equals X, X is a palindromic word. Instead of focussing on words, we focus on lists.

%palin/1 X is a palindrome
palin([]).
palin(X) :- revList(X, Y), X = Y.

A more succinct version of the above would avoid the additional test of equality, i.e. lead to the following predicate:

palin(X) :- revList(X, X).

Which clearly is the the same, i.e. if reversing X leads to X, then clearly, X has to be palindromic. revList is a binary predicate that takes a list as input and outputs the reverse list.

Adventures in Prolog - Computations with lists VI

Today's post is merely to get the flow going and the blog updated. That is it is about the simple concatenation of two lists. Just like the append predicate appends some element at the end of a list, concatenate_list joins two lists by recursively reducing one list until it is the empty list.

%concatenate_list/3
concatenate_list([], List, List).
concatenate_list([H1¦T1], [H2¦T2], [H1¦T3]) :-
concatenate_list(T1, [H2¦T2], T3).

Adventures in Prolog - Link List I

Today's post is merely a compilation of interesting resources on Prolog.

Learn Prolog Now - An online (and paperback) book to learn Prolog

Aspect-Oriented Programming Prolog

Adventures in Prolog - another online book to learn Prolog

P99-Ninety-Nine Prolog Problems - a set of Prolog challenges organized into different degree of difficulty and domains

So happy reading and solving problems :D

Adventures in Prolog - computations with Lists V

Today's post presents a predicate defined for lists that is as simple as yesterdays rem_dups/2. flatten/2 is concerned with flattening an arbitrary list to a one-dimensional list/array.The idea behind flatten is pretty simple, i.e. if a list is non-flat we lower its dimensionality by taking theinner of that list and process it further until we reach a one-dimensional list.

%flatten/2
flatten([], []).
flatten([[]], []).
flatten([[HT]], X) :- flatten([HT], X).
flatten([[H]T], X) :- flatten([HT], X).
flatten([H[T]], X) :- flatten([HT], X).
flatten([HT], X) :-
flatten(T, Y),
append([H], Y, X).

Adventures in Prolog - computations with lists IV

Today's post is merely a modification to yesterdays post, i.e. the remove duplicate functions will be streamlined. rem_dups2/2 is a replication of rem_dups/2 with less dependencies, i.e. it does not use the remove/3 predicate thereby improving performance. A drawback is that rem_dups2 does not preserve order of list elements when producing output, i.e. the last occurence of a duplicate list element will be preserved in the output list.

rem_dups2([X[]], [X]).

rem_dups2([HT], X) :-
member(H, T),
!,
rem_dups2(T, X);
rem_dups2(T, Y),
append([H], Y, X).

Adventures in Prolog - Computations with lists III

This week's post is concerned with another operation on lists, i.e. how to compute a set given a list. This means that given a list containing any values, we wish to remove duplicates from this list to obtain a set containing unique members. The predicate rem_dups/2 does exactly this.

rem_dups([X[]], [X]).

rem_dups([HT], X) :-
member(H, T),
!,
remove(H, T, Y),
rem_dup([HY], X);
rem_dup(T, Y),
append([H], Y, X).

The problem forumulation basically says that if the head of a list is contained within the tail of the list it is a duplicate. Consequently, this duplicate (and any further duplicate of H) is removed from T. Since we want to retain H, we need to connect it with the list that does not contain any instance of H, i.e. X. This procedure is followed for all elements of the list. If a list element does not have a duplicate it is not removed from the list.

rem_dup makes use of auxiliary predicates like remove/3, append/3 and member/2. member/2 checks whether some X is element of some list L. remove/3 removes some X from list L1 yielding the result list L2. append/3 does the opposite it appends some X to an existing list L1 yielding L2.

Adventures in Prolog - Link

Since I am quite occupied these days, I will only post a link to some intellectual stimulus today.

If you follow this link you will be taken to "The First 10 Prolog Programming Contests". So indulge some brain food.

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).

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 .

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.

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.

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.