How to get the terms of a compund term (predicate: simplfy)?

Following Bratko's "PROLOG: Programming for Artificial
Intelligence" I found an exercise:

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 the 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


I thought to myself, well, all I need to do is to walk along
the expression, atom by atom and if it is a number put it
in a NumList, if not and if it is not the addition symbol +
then put it in a list SymList. Then sum all the numbers
in NumList, store it in Num, do a simplification on SymList
(which is another problem in itsefl) and then concatenate as
[SymList | Num]. This will be the desired simplified form.

Well, the complete solution looked a little bit difficult
to code in Prolog so I tried as a warm-up exercise, let
my initial *simplify* procedure (predicate?) just walk
along the compouned expression structure and tell me
if the atom I'm looking at is number or a symbol. So
I tried this one:

simplify([],[]).

simplify(Expression, E) :-
Expression =.. [Head | Tail],
number(Head), !,
write('number')
;
Head \== +,
write('symbol'),
L =.. Tail,
simplify(L, E).

However I was not successful, looks like I'm having
trouble using the cuts as if ... then ... structures.
I've run the debugger and got the following output:

[debug]  ?- simplify(1+2+3, E).
Call: (7) simplify(1+2+3, _G280) ?
Call: (8) 1+2+3=..[_G341|_G342] ?
Exit: (8) 1+2+3=..[+, 1+2, 3] ?
Call: (8) number(+) ?
Fail: (8) number(+) ?
Call: (8) _L205\== + ?
Exit: (8) _L205\== + ?
Call: (8) write(symbol) ?
symbol
Exit: (8) write(symbol) ?
Call: (8) _L207=.._L206 ?
ERROR: Arguments are not sufficiently instantiated
Exception: (8) _L207=.._L206 ?
Exception: (7) simplify(1+2+3, _G280) ?


Head doesn't seem to remember its value after
the cut, I think that is the problem but I don't
know how to solve this.

Any suggestions?

Maybe some of the Prolog masters here would say that
I don't need that warm-up exercise, I must directly
code the solution itself but I find to convert "if
X is that then put it in that list, otherwise put it
in the other list" a little bit difficult, that's why
I started this way.

Hope some exprerienced people can enlighten me.

Regards,

--
Emre Sevinc

eMBA Software Developer         Actively engaged in:
http:www.bilgi.edu.tr           http://ileriseviye.org
http://www.bilgi.edu.tr         http://fazlamesai.net
Cognitive Science Student       http://cazci.com
http://www.cogsci.boun.edu.tr

Emre Sevinc wrote:

> I thought to myself, well, all I need to do is to walk along
> the expression, atom by atom and if it is a number put it
> in a NumList, if not and if it is not the addition symbol +
> then put it in a list SymList.

This sounds perfectly rational - continue from here, instead of trying
to attack the main problem again. What about the conversation we just
had - you want to describe a list, remember DCGs? Here is one solution:

% define valid symbols

symbol(a).
symbol(b).
symbol(c).

allnumbers(Expr) -->
{ Expr = A+B },
allnumbers(A),
allnumbers(B).
allnumbers(Expr) -->
{ number(Expr) },
[Expr].
allnumbers(Expr) -->
{ symbol(Expr) },
[].

?- phrase(allnumbers(1+2+3+a+b+2),Xs).

Xs = [1, 2, 3, 2] ;


Try to come up with different solutions, for example, using =../2 like
you already tried. Just make sure to not forget the most basic things
only because you now know that !/0 exists.

Best regards,
Markus.

Markus Triska <triska@gmx.at> writes:

> Emre Sevinc wrote:
> 
>
> This sounds perfectly rational - continue from here, instead of trying
> to attack the main problem again. What about the conversation we just
> had - you want to describe a list, remember DCGs? Here is one solution:
>
> % define valid symbols
>
> symbol(a).
> symbol(b).
> symbol(c).
>
> allnumbers(Expr) -->
> 	{ Expr = A+B },
> 	allnumbers(A),
> 	allnumbers(B).
> allnumbers(Expr) -->
> 	{ number(Expr) },
> 	[Expr].
> allnumbers(Expr) -->
> 	{ symbol(Expr) },
> 	[].
>
> ?- phrase(allnumbers(1+2+3+a+b+2),Xs).
>
> Xs = [1, 2, 3, 2] ;
>
>
> Try to come up with different solutions, for example, using =../2 like
> you already tried. Just make sure to not forget the most basic things
> only because you now know that !/0 exists.

Interesting approach. It seems that "phrase" is a part of Definite Clause
Grammars. Is this part of Prolog standard? The only DCG related chapter in m
y
Bratko book is related to natural language processing. I'm surprised
to see it is used in other parts of Prolog programming. Is this a usual
approach?

I'm trying to understand your examples. Looks like *phrase* handles
a lot of things.

To my surprise I tried to extend your example by writing a very
similar *allsymbols* predicate:

allsymbols(Expr) -->
{ Symbol = A+B },
allsymbols(A),
allsymbols(B).

allsymbols(Expr) -->
{ symbol(Expr) },
[Expr].

allsymbols(Expr) -->
{ number(Expr) },
[].


However when I tried to run it to

?- phrase(allsymbols(1 + 2 + a + b + 2),Xs).
ERROR: Out of local stack

And I didn't understand why this happened. What did I do wrong?

Thanks again for DCG examples, I think I must learn that
well, too. It seems to make the task of dividing lists to
sublists based on some criterion easier. But maybe the best
thing would be to have a general predicate, something like
"categorize this list into N different lists based on the
results of my categorization function". I've seen
sublist(+Pred, +List1, ?List2) in SWI manual and I'll check
it out but I don't know how flexible it is.

I also still wonder if it will take too much
to code the examples above without relying on DCGs.

Regards,

--
Emre Sevinc

eMBA Software Developer         Actively engaged in:
http:www.bilgi.edu.tr           http://ileriseviye.org
http://www.bilgi.edu.tr         http://fazlamesai.net
Cognitive Science Student       http://cazci.com
http://www.cogsci.boun.edu.tr

Emre Sevinc wrote:

> Interesting approach. It seems that "phrase" is a part of Definite Clause
> Grammars. Is this part of Prolog standard? The only DCG related chapter in
 my
> Bratko book is related to natural language processing. I'm surprised
> to see it is used in other parts of Prolog programming. Is this a usual
> approach?

DCGs are no feature "sui generis", they are only disguised conventional
predicates. You can readily transform a DCG into predicate notation
using extremely simple transform rules (search for "list difference" or
"list differences", it's mainly a matter of adding 2 additional
arguments to every DCG clause). That's what phrase/2 is doing for you
automatically. Due to these "missing" arguments, DCGs are often more
readable.

>
>   allsymbols(Expr) -->
>         { Symbol = A+B },

Expr?

>
> I also still wonder if it will take too much
> to code the examples above without relying on DCGs.
>

It takes roughly the same amount. What follows is the expanded code
(that's what phrase/2 would do for you):

allnumbers(Expr,Xs,Ys) :-
Expr = A+B,
allnumbers(A,Xs,Xs1),
allnumbers(B,Xs1,Ys).
allnumbers(Expr,[Expr|Xs],Xs) :-
number(Expr).
allnumbers(Expr,Ys,Ys) :-
symbol(Expr).

You have to think in terms of 2 lists now - the list that is currently
being processed, and the rest ("difference") that is passed through.
Successful "parse" would leave no rest:

?- allnumbers(1+2+a+b+3+c,Xs,[]).

Xs = [1, 2, 3] ;


Best regards,
Markus.

Markus Triska <triska@gmx.at> writes:

> "list difference" or "list differences", it's mainly a matter of
> adding 2 additional arguments to every DCG clause). That's what
> phrase/2 is doing for you automatically. Due to these "missing"
> arguments, DCGs are often more readable.
> 
>
> Expr?

Ooops!

It must be:

allsymbols(Expr) -->
{ Expr = A+B },
allsymbols(A),
allsymbols(B).

allsymbols(Expr) -->
{ symbol(Expr) },
[Expr].

allsymbols(Expr) -->
{ number(Expr) },
[].

And now it works fine:

?- phrase(allnumbers(a+b+1+c+2), NumList).

NumList = [1, 2]

Yes
?- phrase(allsymbols(a+b+1+c+2), SymList).

SymList = [a, b, c]

Yes
?-


I tried to do a similar thing without using DCG
but I was not successful:

flatten_expression([], []).

flatten_expression([Head | Tail], L) :-
compound(Head),
flatten_expression(Head, L), !
;
flatten_expression(Tail, L).

flatten_expression(Expression, List):-
Expression =.. [Head | Tail],
flatten_expression(Tail, List1).


> It takes roughly the same amount. What follows is the expanded code
> (that's what phrase/2 would do for you):
>
> allnumbers(Expr,Xs,Ys) :-
> 	Expr = A+B,
> 	allnumbers(A,Xs,Xs1),
> 	allnumbers(B,Xs1,Ys).
> allnumbers(Expr,[Expr|Xs],Xs) :-
> 	number(Expr).
> allnumbers(Expr,Ys,Ys) :-
> 	symbol(Expr).
>
> You have to think in terms of 2 lists now - the list that is currently
> being processed, and the rest ("difference") that is passed
> through. Successful "parse" would leave no rest:
>
> ?- allnumbers(1+2+a+b+3+c,Xs,[]).
>
> Xs = [1, 2, 3] ;

DCG style seems to be quite handy, your other version seems
more difficult to understand compared to DCG version. However
I think it is a good example to understand those transformations
and using extra lists as accumulators.

Now I'll try to finish simplify predicate using the
tools I've learned.

Thanks for spending time.

Cheers,

--
Emre Sevinc

eMBA Software Developer         Actively engaged in:
http:www.bilgi.edu.tr           http://ileriseviye.org
http://www.bilgi.edu.tr         http://fazlamesai.net
Cognitive Science Student       http://cazci.com
http://www.cogsci.boun.edu.tr

Markus Triska <triska@gmx.at> writes:


> allnumbers(Expr,Xs,Ys) :-
> 	Expr = A+B,
> 	allnumbers(A,Xs,Xs1),
> 	allnumbers(B,Xs1,Ys).
> allnumbers(Expr,[Expr|Xs],Xs) :-
> 	number(Expr).
> allnumbers(Expr,Ys,Ys) :-
> 	symbol(Expr).
>
> You have to think in terms of 2 lists now - the list that is currently
> being processed, and the rest ("difference") that is passed
> through. Successful "parse" would leave no rest:
>
> ?- allnumbers(1+2+a+b+3+c,Xs,[]).
>
> Xs = [1, 2, 3] ;

With your help, I'm one step closer to the final
solution. I've tried that:

simplify([], []).

simplify(Expr, L) :-
phrase(allnumbers(Expr), NumList),
phrase(allsymbols(Expr), SymList),
sumlist(NumList, SumOfNumList),
flatten([SymList | SumOfNumList], L).


?- simplify(1+2+a+b+3+a, E).

E = [a, b, a, 6]

Yes


Now I need to handle the SymList. I think
first it must be ordered alphabetically, after
that I have to start processing list and unless
the symbol is changed, increment a counter and
when symbol changes create a term like Counter*Symbol
and put it in a list and continue the process adding
these lists to a new SimplifiedSymbolList. Sounds easy
English but I don't if I'll be convert this to Prolog! :)

(Well, I assumed all the operations to be +
and now I wonder how I must modify the above code
to handle things like 1 - 2 - 3 + a - b + 99  ... etc.).

Regards,

--
Emre Sevinc

eMBA Software Developer         Actively engaged in:
http:www.bilgi.edu.tr           http://ileriseviye.org
http://www.bilgi.edu.tr         http://fazlamesai.net
Cognitive Science Student       http://cazci.com
http://www.cogsci.boun.edu.tr

Emre Sevinc wrote:
> Following Bratko's "PROLOG: Programming for Artificial
> Intelligence" I found an exercise:

I insert some sugestions, I hope they useful:

>
>   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 the 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
>
>
> I thought to myself, well, all I need to do is to walk along
> the expression, atom by atom and if it is a number put it
> in a NumList, if not and if it is not the addition symbol +
> then put it in a list SymList. Then sum all the numbers
> in NumList, store it in Num, do a simplification on SymList
> (which is another problem in itsefl) and then concatenate as
> [SymList | Num]. This will be the desired simplified form.
>
> Well, the complete solution looked a little bit difficult
> to code in Prolog so I tried as a warm-up exercise, let
> my initial *simplify* procedure (predicate?) just walk
> along the compouned expression structure and tell me
> if the atom I'm looking at is number or a symbol. So
> I tried this one:
>
>   simplify([],[]).
>
>   simplify(Expression, E) :-
>         Expression =.. [Head | Tail],
>         number(Head), !,
>         write('number')
>         ;
>         Head \== +,
>         write('symbol'),
>         L =.. Tail,
>         simplify(L, E).
>

a) in SWI exist a clause called "write_canonical". Is is very practical
to show the real format of one expressions, because filters all infix
expressions. By example, typing:

?-  write_canonical(1+x)
+(1,x)

b) A clause can have any kind of term as input. Thus, not only it is
posible write things like:
foo(1) :- ...
foo([H|Q]) :- ...
foo(n(X,Y)) :- ...

but also
foo(+(X,Y)) :- ...
foo(X+Y) :- ...                <= interesting for your problem?

> However I was not successful, looks like I'm having
> trouble using the cuts as if ... then ... structures.
> I've run the debugger and got the following output:
>
>   [debug]  ?- simplify(1+2+3, E).
>      Call: (7) simplify(1+2+3, _G280) ?
>      Call: (8) 1+2+3=..[_G341|_G342] ?
>      Exit: (8) 1+2+3=..[+, 1+2, 3] ?
>      Call: (8) number(+) ?
>      Fail: (8) number(+) ?
>      Call: (8) _L205\== + ?
>      Exit: (8) _L205\== + ?
>      Call: (8) write(symbol) ?
>   symbol
>      Exit: (8) write(symbol) ?
>      Call: (8) _L207=.._L206 ?
>   ERROR: Arguments are not sufficiently instantiated
>     Exception: (8) _L207=.._L206 ?
>     Exception: (7) simplify(1+2+3, _G280) ?
>
>
> Head doesn't seem to remember its value after
> the cut, I think that is the problem but I don't
> know how to solve this.
>
> Any suggestions?
>

! problem or ; problem?

?- write_canonical(
( Expression =.. [Head | Tail],
number(Head), !,
write('number')
;
Head \== +,
write('symbol'),
L =.. Tail,
simplify(L, E) ).



;(,(=..(_G1440, '.'(_G1437, _G1438)), ,(number(_G1437), ,(!,
write(number)))), ,(\==(_G1437, +), ,(write(symbol), ,(=..(_G1461,
_G1438), simplify(_G1461, _G1465)))))

Expression = _G1440
Head = _G1437
Tail = _G1438
L = _G1461
E = _G1465

; is at the start. Is that what you expected?


> Maybe some of the Prolog masters here would say that
> I don't need that warm-up exercise, I must directly
> code the solution itself but I find to convert "if
> X is that then put it in that list, otherwise put it
> in the other list" a little bit difficult, that's why
> I started this way.
>
> Hope some exprerienced people can enlighten me.

Maybe. In the while, I hope that a simple programmer can help ;-)

>
> Regards,
>
> --
> Emre Sevinc
>
> eMBA Software Developer         Actively engaged in:
> http:www.bilgi.edu.tr           http://ileriseviye.org
> http://www.bilgi.edu.tr         http://fazlamesai.net
> Cognitive Science Student       http://cazci.com
> http://www.cogsci.boun.edu.tr

"tmp123" <tmp123@menta.net> writes:

> Emre Sevinc wrote: 
>
> I insert some sugestions, I hope they useful:
> 
> a) in SWI exist a clause called "write_canonical". Is is very practical
> to show the real format of one expressions, because filters all infix
> expressions. By example, typing:
>
> ?-  write_canonical(1+x)
> +(1,x)
>
> b) A clause can have any kind of term as input. Thus, not only it is
> posible write things like:
> foo(1) :- ...
> foo([H|Q]) :- ...
> foo(n(X,Y)) :- ...
>
> but also
> foo(+(X,Y)) :- ...
> foo(X+Y) :- ...                <= interesting for your problem?


As far as I can see the problem is a little bit more
complex than I assumed it to be at the beginning ;-)

The things I've done until now just splits the original
expression into two lists and then recombining the lists
but losing the operations, so it simply is not the solution
to the simplification problem.

write_canonical looks like a nice function, but I guess
it is only for output, it doesn't create a list, am I wrong.

Anyway, the problem seems to be walk along the list and

if the current element is a number
then put it in the ResultingNum,
move on to next element and keep on iterating
if the current element is a + or -
get the next element
if it is a number then add (it to) or subtract it from
the ResultingNum variable,
storing the result in ResultingNum
if it is NOT a number then put it in a SymList
which have slots like Symbol, SymbolCounter
such that SymbolCounter is incremented or decremented
if the same symbol is encountered
if a different symbol is encountered then put
it in another slot and make its SymbolCounter 1.

Sort of a rough description in procedural style, but I just
can't imagine it in declarative style.
 
>
> ! problem or ; problem?
>
> ?- write_canonical(
> ( Expression =.. [Head | Tail],
> number(Head), !,
> write('number')
> ;
> Head \== +,
> write('symbol'),
> L =.. Tail,
> simplify(L, E) ).
>
>
>
> ;(,(=..(_G1440, '.'(_G1437, _G1438)), ,(number(_G1437), ,(!,
> write(number)))), ,(\==(_G1437, +), ,(write(symbol), ,(=..(_G1461,
> _G1438), simplify(_G1461, _G1465)))))
>
> Expression = _G1440
> Head = _G1437
> Tail = _G1438
> L = _G1461
> E = _G1465
>
> ; is at the start. Is that what you expected?


What I want to do in these kind of situations is that

first of all do: Expression =.. [Head | Tail]

and only after that

if bla bla Head is something bla bla ...
then bla bla...
otherwise do
bla bla Tail bla bla...

The problem is that the Prolog template I try
to use simply don't work that way, what I call
"first of all do:" part becomes a part of "if"
and worst of all if it is not satisfied it means
that Head and Tail variables is not instantiated and
this creates a problem in "otherwise do ..." part
because I assume that Head and Tail are initialized to some
value and then I check something and if it's ok
I do something with Head otherwise I do another thing
with Tail. But the Tail is not... you see? oh my! It just twists
my brain :)

 
>
> Maybe. In the while, I hope that a simple programmer can help ;-)

You certainly know much more than me ;-)
I finally tried something with DCGs but at the end
I've created a solution that does completely another
thing (I guess). :)



--
Emre Sevinc

eMBA Software Developer         Actively engaged in:
http:www.bilgi.edu.tr           http://ileriseviye.org
http://www.bilgi.edu.tr         http://fazlamesai.net
Cognitive Science Student       http://cazci.com
http://www.cogsci.boun.edu.tr

Emre Sevinc wrote:
>
> What I want to do in these kind of situations is that
>
>   first of all do: Expression =.. [Head | Tail]
>
> and only after that
>
>   if bla bla Head is something bla bla ...
>        then bla bla...
>   otherwise do
>       bla bla Tail bla bla...
>

Sugestion, try:

... :-
Expression =.. [Head | Tail],
(                             % <=add
bla, bla, !, ...
;
blo blo
).                            % <=add

Take care where the '(' ')' are.

[[ In other words:

?- write_canonical(( a,b;c,d )).

;( ,(a,b), ,(c,d) )   % "or" a,b with c,d

however,

?- write_canonical(( a,(b;c,d) )).
,( a, ;(b, ,(c,d)) ) % first a, after "or" b with c,d

]]

> Emre Sevinc wrote:
>          which have slots like Symbol, SymbolCounter
>         such that SymbolCounter is incremented or decremented
>         if the same symbol is encountered
>        if a different symbol is encountered then put
>           it in another slot and make its SymbolCounter 1.

This part is an interesting problem. It is necessary implement an
associative array, that associates to each atom (symbol) an integer
(the counter).

Some posibilities are:

- A list like [counter(a,3),counter(b,2),...]
- A list like [inc(inc(inc(a))),inc(inc(b)),..]
- Or use assert/retract.
- Or the "flag" clause of SWI-prolog, or nb_setval.

In all cases you will need a clause like:
 increment(SYMBOL,ORIGINAL_LIST,RESULT_LI
ST).

However, any of these options is very good. Could be another person has
better posibilities.

PS: As you can see, I've splitted my answer in 3, because I though they
are 3 different subjects.