Re: Prolog Programming for AI, problem 7.1

Lash Rambo 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 occurrences, and tally the constants. At the end, stitch the contents of the hash together with the tally. That's maybe 5 lines of Perl code.
....

So, is there a simple, clever solution to this problem in Prolog?

I don't see anything particularly helpful about using the predefined
'+' operator as a separator, nor in thinking i.t.o. arithmetic
expressions, so please allow me to rephrase the question as follows:

Write a procedure 'simplify' to symbolically simplify lists of numbers
and symbols (lower-case letters). Let the procedure rearrange the
lists so that all the symbols precede the numbers in alphabetical order
and add up the 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]

etc,

If I further assume the given list is simply a sorted list of atoms and
integers, I am left with the problem of combining successive sequences of like elements, which can be expressed in Prolog as follows:


simplify([],[]).

simplify([X],[X]).

simplify([X,Y|L1],L0) :-
( integer(X), integer(Y) -> Z is X + Y, simplify([Z|L1],L0) ;
( integer(X), atom(Y) -> simplify([Y|L1],L2), L0 = [X|L2] ;
( atom(X), integer(Y) -> simplify([Y|L1],L2), L0 = [X|L2] ;
( X = N1*A ->
( A == Y ->
N2 is N1 + 1, simplify([N2*A|L1],L0) ;
simplify([Y|L1],L2), L0 = [X|L2] ) ;
( X = Y -> simplify([2*X|L1],L0) ; simplify([Y|L1],L2), L0 = [X|L2] ))))).

whereupon

?- simplify([a,a,b,c,c,c,d,e,f,f,f,f,g,1,2,2,3,3,3],Q).
Q = [2*a, b, 3*c, d, e, 4*f, g, 14] ;
No.

etc.

Simple? Yes. Clever? No.

OTOH, I don't know what "just read through the expression, use
a hash to map each symbol to its number of occurrences, and tally the
constants" or "stitch the contents of the hash together with the tally" means, but if all it entails is "maybe 5 lines of Perl code", I think the problem of explaining the primitives used in those 5 lines of Perl code to your boss might have to be considered in the balance.

And then, of course, there is the matter of the relative difficulty in proving the correctness of the answers that a given Perl program produces, as compared to the difficulty in proving the correctness of the answers that a given Prolog program produces.

--
billh

.

Relevant Pages