Re: Prolog Programming for AI, problem 7.1

Lash Rambo <lr@xxxxxxxxxxxx> wrote:
I'm soldiering through "Prolog Programming for Artifical Intelligence" by
Bratko, but have run into a nasty exercise. It's 7.1, and reads:
"
Write a procedure 'simplify' to symbolically simplify summation
expressions with numbers and symbols (lower-case letters). Let the
procedure rearrange the expressions so that all the symbols precede
numbers. These are examples of its use:
?- simplify(1 + 1 + a, E).
E = a + 2
?- simplify(1 + a + 4 + 2 + b + c, E).
E = a + b + c + 7
?- simplify(3 + x + x, E).
E = 2*x + 3
"
The imperative solution sprung immediately to mind. You'd just read
through the expression, use a hash to map each symbol to its number of
[...]


Imperative solutions work fine in Prolog, too. :)
But it can also do things like run a "process" backwards and forwards
and just find something you know the look of, but don't really know how
to calculate.

In this problem you could operate on the expression in steps.

1) flatten out the expression into a list of terms.
I.e. (a+1)+(1+b-a) ==> [a,1,1,b,-a].

2) tag each item in the term-list with a value 0 == constant, X == name
of variable.
I.e. [a-a,0-1,0-1,b-b,a-(-a)].

3) use keysort to get like near like.

I.e. [0-1,0-1,a-a,a-(-a),b-b].

4) strip tags and combine like with like.
[2,0,b].

5) Peephole.
[2,b].

6. Convert back to sum-of-terms (e.g. by running same function used in 1, but
bckwards).
2+b.

(Any resemblance with C&M's "converting a predicate formula to normal form"
is -- of course -- purely non-coincidental.)

If you have the time, you could also write a meta-interpreter that
de-forrests the above into a highly efficient, but unreadable,
throw away program. (Something a bit harder to do in C. :)

.