Logic Programming and the Andorra Kernel Language
Skip this bit, if you already know something about logic programming. The introduction is intended for those who don't know anything about the subject.
Logic Programming is not, as you might expect, a very low-level
part of computer science, working with gates.
Logic Programming is rather an attempt to use predicate logic as
the basis of a programming language, leading to some very high
Logic programming languages tend to be declarative programming languages, as opposed to the more traditional imperative programming languages, such as C or Pascal.
In a declarative language, you concentrate on the relationships between the parts of the problem, rather than on the exact sequence of steps required to solve the problem. An example of a well-known declarative language is SQL; SQL queries are translated by the database engine into various lookup strategies, where the presence of indexes and the sizes of various tables and views are taken into account. All this detail doesn't matter too much to the programmer1, who is only interested in the result of the query, rather than the exact steps taken to retrieve the result.
Imperative languages, in contrast to their declarative brethren, expect the programmer to provide an exact description of the steps required to solve some problem.
In a logic programming language, what is declared is the logical
relationship between various entities.
After that, if you supply some sort of query, the logic programming
language can deduce the results of the query by tracing its path
through the relationship.
Sue is-parent-of Bill. Sue is-parent-of James. Sue is-parent-of Edith. Fred is-parent-of Bill. Fred is-parent-of James. Authur is-parent-of Edith. Mary is-parent-of Kylie. Mary is-parent-of Jason. Mary is-parent-of Matilda. James is-parent-of Kylie. James is-parent-of Jason. James is-parent-of Matilda. Edith is-parent-of David. William is-parent-of David. X is-ancestor-of Y if X is-parent-of Y X is-ancestor-of Y if there is some Z such that X is-parent-of Z and Z is-ancestor-of Y
This example contains two relationships: is-parent-of and is-ancestor-of. These relationships are called predicates.
The simpler predicate is is-parent-of. All the statements which make up is-parent-of are simple facts and can be easily interpreted. We can easily ask "Is James the parent of Matilda?" and, since James is-parent-of Matilda is present in the above list, the question will be answered with a "true". If we ask "Is James the parent of David?" then, since James is-parent-of David is not in the list, we will be answered with a "false"2.
is-ancestor-of is a more complex predicate, since
it expresses the is-ancestor-of relationship as a pair of rules.
Logically, the first relationship can be read as "Someone
is the ancestor of somebody else if they are that person's parent."
This is the simplest expression of what it means to be sombody's ancestor.
The second part of the is-ancestor-of relationship is more complex.
This part can be read as "Somebody is the ancestor of somebody else if
there is another person who is the child of the first person, and
this third person is the ancestor of the second person."
If this is a little confusing, try this example:
my grandmother is my ancestor, because she is the parent
of my father and my father is my ancestor, because he is my parent.
There are four ways in which we may want to use the above example:
Logic Programming Resources
Here is a list of useful URLs concerned with logic programming:
PrologProlog (Programming in Logic) is the first logic programming language and still the most common. Prolog now has a large number of commercial and free implementations.
The arguments to predicates are constructed from terms..
The most primitive form of term is a constant which is represented
by a word with a lower-case initial letter, eg.
The next most primitive form of term is a variable.
Variables are represented by words beginning with an upper-case letter,
or an underscore, eg.
Complex terms are built from function symbols, consisting
of a named function and some arguments in brackets, eg.
Lists are used extensively in Prolog
and have a special syntax.
A list is represented by
Predicates are defined by either stating facts, eg.
Queries in Prolog are expressed as
?- Goal1, ..., Goaln.
The ancestor example, written in Prolog would look like:
parent(sue, bill). parent(sue, james). parent(sue, edith). parent(fred, bill). parent(fred, james). parent(arthur, edith). parent(mary, kylie). parent(mary, jason). parent(mary, matilda). parent(james, kylie). parent(james, jason). parent(james, matilda). parent(edith, david). parent(william, david). ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
An example query would be
Another example query would be
When Prolog is searching for an answer to a query, it
starts by choosing one of the goals that it has, to see if it
can find an answer to that goal.
Eg. if the query were
Once Prolog has chosen a goal, it starts to try and
match the clauses of the goal, top-to-bottom until it finds one
In the above example,
The Prolog search rule now tries the
The first clause of
The program now tries the next clause of ancestor, which leads
to two further goals,
After another round of backtracking,
The Prolog search strategy, therefore, always picks the leftmost, innermost goal to try next and always tries clauses in top to bottom order. This strategy is called a depth-first search strategy, as it always searches down the possible goals, rather than across them. The depth-first strategy is very simple and efficient to implement, but can lead to some very odd infinite loops. For example:
p(a) :- p(Z). q(b). ?- p(X), q(X)
In ordinary use of Prolog, you are interested in any possible answer that can be computed. Occasionally, however, you want just a few answers, and then wish to cut away any further answers. This process is normally referred to as pruning.
In Prolog the cut operator, written as a
An example of the use of cut is where you have a series of alternatives, with a default at the end. If you encounter an alternative, then you want to ignore the default. As an example, the following table works out whether a foreign exchange deal is a spot deal or not5:
dealType(Date, Today, cad, _Currency2, spot) :- addDays(Today, 1, Date), !. dealType(Date, Today, _Currency1, cad, spot) :- addDays(Today, 1, Date), !. dealType(Date, Today, _Currency1, _Currency2, spot) :- addDays(Today, 2, Date), !. dealType(_Date, _Today, _Currency1, _Currency2, outright).
addDays(date(Day, Month, Year), Days, Date) :- plus(Day, Days, Day1), normalizeDate(date(Day1, Month, Year), Date). normalizeDate(date(Day, Month, Year), Date) :- Day =< 0, !, nextMonthYear(Month1, Year1, Month, Year), daysInMonth(Month1, Year1, DIM), plus(Day, DIM, Day1), normalizeDate(date(Day1, Month1, Year1), Date). normalizeDate(date(Day, Month, Year), Date) :- daysInMonth(Month, Year, DIM), Day > DIM, !, nextMonthYear(Month, Year, Month1, Year1), plus(Day1, DIM, Day), normalizeDate(date(Day1, Month1, Year1), Date). normalizeDate(Date, Date). daysInMonth(jan, _Year, 31). daysInMonth(feb, Year, 29) :- isLeapYear(Year), !. daysInMonth(feb, Year, 28). daysInMonth(mar, _Year, 31). daysInMonth(apr, _Year, 30). daysInMonth(may, _Year, 31). daysInMonth(jun, _Year, 30). daysInMonth(jul, _Year, 31). daysInMonth(aug, _Year, 31). daysInMonth(sep, _Year, 30). daysInMonth(oct, _Year, 31). daysInMonth(nov, _Year, 30). daysInMonth(dec, _Year, 31). nextMonthYear(jan, Year, feb, Year). nextMonthYear(feb, Year, mar, Year). nextMonthYear(mar, Year, apr, Year). nextMonthYear(apr, Year, may, Year). nextMonthYear(may, Year, jun, Year). nextMonthYear(jun, Year, jul, Year). nextMonthYear(jul, Year, aug, Year). nextMonthYear(aug, Year, sep, Year). nextMonthYear(sep, Year, oct, Year). nextMonthYear(oct, Year, nov, Year). nextMonthYear(nov, Year, dec, Year). nextMonthYear(dec, Year, jan, NewYear) :- plus(Year, 1, NewYear). leapYear(Year) :- Year \\ 400 =:= 0, !. leapYear(Year) :- Year \\ 4 =:= 0, Year \\ 100 =\= 0.
In this example,
Cut damages the idea of directionless programming7.
For example, the query
Here is a list of handy URLs for getting various Prolog resources:
Agents Kernel Language
Prolog's search strategy can be very inefficient. Very often, many fruitless search branches are explored which could be ignored if more information from later in the query were made available. As an example, consider the following program and query:
number(0). number(s(X)) :- number(X). ?- number(X), X = s(s(s(0))).
With a normal Prolog search strategy, the program would
The easiest goals in a query to execute are those with only one possible clause to execute. These goals are called determinate goals, in contrast to nondeterminate where several branches may have to be tried. Determinate goals represent "no regrets" goals; they have to be executed sometime, so the program should execute them as soon as possible and see if they bind enough variables to make another goal determinate.
The Andorra Principle essentially says "Do the
determinate bits first".
The Agents Kernel Language, or AKL is a
Prolog-like language designed to take advantage
of the Andorra principle.
The AKL syntax is similar to Prolog-syntax, but somewhat more complex to allow the AKL to decide how much of a goal to try to see whether it is determinate or not.
The AKL is a guarded language.
Clauses are written as
All clauses in a predicate must have the same guard operator.
If no guard operator is specified, then a guard and guard operator
Queries follow the Prolog model.
The ancestor example, written in AKL would look like:
parent(sue, bill). parent(sue, james). parent(sue, edith). parent(fred, bill). parent(fred, james). parent(arthur, edith). parent(mary, kylie). parent(mary, jason). parent(mary, matilda). parent(james, kylie). parent(james, jason). parent(james, matilda). parent(edith, david). parent(william, david). ancestor(X, Y) :- parent(X, Y) ? true. ancestor(X, Y) :- parent(X, Z) ? ancestor(Z, Y).
An AKL program essentially acts like a Prolog program, except that the leftmost, depthmost goal is not always selected. Preference is given to any goal where the AKL can detect determinism.
When a goal is selected, all the guards in each clause in the predicate are all tried. With a bit of luck, all the guards except one will fail and the goal can be determinatly promoted. A determinately promoted goal first allows its guard to complete, and then sets about executing the body of the clause.
If there are two or more possible clauses when the guards complete, then the goal suspends until further bindings cause enough guards to fail. Any variable bindings made by the guards are treated as speculative; they apply to the guard, but do not leak into the surrounding computation. Part of promotion is the promotion of speculative bindings into real bindings.
Clauses (and predicates) with conditional or commit guards must have quiet guards before the operators are allowed to prune. Quiet guards have no speculative bindings; either the guard doesn't care about the state of a variable, or the variable has been really bound. Quietness makes sure that pruning operators don't get activated by an over-enthusiastic guard. For example:
p(X) :- X = a | true. p(X) :- X = b | true. q(X) :- true ? X = b. ?- p(X), q(X).
In the example above, if quietness were not required, then
each guard in
At some point, most AKL programs won't be able to
find a determinate goal9.
At this point, the AKL program must fall back
on the Prolog-style search.
Since the an AKL program has usually tried
many goals in the program, there is a wider variety of possible choices.
The AKL picks a goal which is wait-guarded
and then promotes the first clause, leaving the remaining clauses
Hopefully, this nondeterminate promotion will cause
something else to be determinate and start the ball rolling again.
The AKL chooses a goal to execute from a set of determinate goals. Since the order of execution of these goals does not matter, the AKL allows both concurrent programming and parallelism.
In concurrent programming, although each goal is evaluated one at a time, the system is free to switch between goals as it sees fit. This kind of behaviour is similar to a multitasking operating system, and concurrent systems allow logic programs to be viewed as a set of threads, all acting in concert.
Concurrent programming gives the appearance of parallelism, without actually having a parallel set of systems. In true parallelism, several determinate goals can be evaluated at once.
Stream and-parallelism views individual predicates as independent, communicating processes. The processes communicate by incrementally filling out a list; as one process binds the head of a list, another process can commit to a single clause and process the list element. As an example, the following program and query sums up a series of numbers:
numbers(0, X) :- true -> X = . numbers(N, X) :- true -> X = [N | X1], plus(N1, 1, N), numbers(N1, X1). sum(, S, T) :- true ? T = S. sum([N | N1], S, T) :- true ? plus(S, N, S1), sum(N1, S1, T). sum(N, T) :- sum(N, 0, T). ?- numbers(5, X), sum(X, T).
Here are some links to various AKL resources:
24-Mar-2004 Doug Palmer