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.