AI Cologne

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

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: [English] New Mexico State University: Building and Programming Robots http://www.cs.nmsu.edu/~tson/classes/fall03-579/schedule.htm [German] University of Potsdam: Programmieren in Prolog http://www.cs.uni-potsdam.de/wv/03SS/aktuell.html#SECTION00051000000000000000 [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/...

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.

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

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

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

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: the gcd of two numbers x and y is equal to the gcd of x - y and y for y the gcd of some number and 0 is the number 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 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 proble...

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: We traverse the list element by element until we reach the last element, i.e. the empty list. 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).

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

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.

Here is a link to the Prolog directory of CMU's AI group: http://www.cs.cmu.edu/Groups/AI/lang/prolog/

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

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: The (German and English) alphabet contains only 26 elementary characters (variable symbols) 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...

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

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

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

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

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

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

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

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.

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

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

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

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

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

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