Prolog Programming for AI, problem 7.1

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.

For Prolog, the best I could come up with was scanning the summation
expression, and for each constant: 1) if it's an integer, add it to the
running integer total, and 2) if it's an atom, delete all occurrences of
that atom in the expression, keeping count of the number of deletions,
and replace them with the new factor. E.g., if you had "3 + x + x",
you'd delete the two xs, leaving "3", and then you'd add the new factor
for the xs: "3 + 2*x". Fart around with ordering the integers, smooth
out the rough spots (what if it's all integers? what if it's all
atoms?), and you're looking at a couple dozen lines of junk. Plus, in
the end what you're left with is a ghastly, inefficient reformulation of
the elegant imperative solution.

Figuring there must be some clever solution to the problem using only
things the book has covered up to this point, I peeked at the solutions
in the back of the book. Sure enough, there was a clever solution--for a
completely different problem! It looks like originally the problem was
to write a partially reversible addition procedure. See, that would have
actually been fun. It'd take a couple minutes and I'd get to use the
type predicates, which was the point of the exercises.

I next did a quick Google Groups search on the problem. I found a thread
from a couple years ago, but all the solutions involved things that
haven't yet been covered in the book. The solutions were also much more
complex than the solutions for any problems up to this point in the book.
As such, I doubt they're what Bratko had in mind.

Finally, I found a simplification procedure tied in with a
differentiation procedure, but even it used more advanced stuff than has
been covered in the book so far.

So, is there a simple, clever solution to this problem in Prolog? I'm
thinking a dozen lines, max. No CFGs, no term decomposition (beyond
stuff like X+Y), no wacky 3rd party libraries, etc.
.

Relevant Pages

  • Re: removing duplicates from result - newbee
    ... >I am learning prolog using the prolog bookby Bratko. ... >Is it expected behavior to get the same result more ... If you want S to be non-empty, you can modify sublist/2 accordingly. ...
    (comp.lang.prolog)
  • removing duplicates from result - newbee
    ... I am learning prolog using the prolog bookby Bratko. ... Antony Sequeira ...
    (comp.lang.prolog)
  • Re: Rules and Recursion
    ... I'm very new to Prolog and have a question. ... confusing. ... Again, if X and Y are the same, you can simplify your code by using the ... Nick ...
    (comp.lang.prolog)
  • Re: An innovative approach to Monkey-Banana Problem?
    ... my teacher asked me to implement the ... mr bratko did it in "prolog - programming for artificial intelligence". ... thought of making the monkey climb down the box again. ...
    (comp.ai.philosophy)