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

Author

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

Emre Sevinc

2004-12-25, 3:57 pm

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

Markus Triska

2004-12-25, 3:57 pm

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.

Emre Sevinc

2004-12-25, 9:01 pm

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

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

Markus Triska

2004-12-25, 9:01 pm

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.

Emre Sevinc

2004-12-25, 9:01 pm

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

Emre Sevinc

2004-12-25, 9:01 pm

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

tmp123

2004-12-26, 8:55 am

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

Emre Sevinc

2004-12-26, 3:56 pm

"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

tmp123

2004-12-26, 3:56 pm

Your analisis of the problem is OK.
To solve the problem, just is missing some prolog mechanicals.

In addition, remember prolog is nicer if you split the problem in
basical concepts.

In particular:

The input is, by example, "1+x+y+3".

OK, it is a list of characters, and from this point of view we need
parsers, grammars, ... . However implement a parser has big cost.
Analizing the input with "write_canonical", we see the input in a new
way:

+( 1, +(x, +(y,3)))

That is different: a tree. Prolog likes trees. Atoms and integers as
tokens, + as relation.

In your previous post, in a good analisis, you have found that if you
obtain a list with the atoms, and a number with the addition of
integers, you have the problem solved:

analisis(1+x+y+3,ATOMS,SUM).
must answer ATOMS=[x,y] and SUM=4.

Question: Can we do something starting by:

analisis(X+Y,ATOMS,SUM) :- !, ...
analisis(X,ATOMS,SUM) :- number(X), !, ..
analisis(X,ATOMS,SUM) :- atom(X), !, ...

Kind regards.

PS: Thanks for your information about cognitive sciences. I'm reading
the links you provide.

tmp123

2004-12-26, 3:56 pm

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

]]

tmp123

2004-12-26, 3:56 pm

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

Emre Sevinc

2004-12-27, 8:56 pm

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

> Emre Sevinc wrote:
>
> Sugestion, try:
>
> ... :-
> Expression =.. [Head | Tail],
> ( % <=add
> bla, bla, !, ...
> ;
> blo blo
> ). % <=add
>
> Take care where the '(' ')' are.

Hey, why didn't anybody tell me that I
can do grouping of expressions using
parantheses before! :) I was dying for it.

Well, at least my Bratko book didn't tell it
to me (or did I miss it, I don't know).

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

Certainly I appreciate the existence of this
kind of stuff in Prolog! :)

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

2004-12-27, 8:56 pm

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

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

Thanks for the suggestions, indeed. It seems like even a "simple"
algebraic simplification problem is not that simple stuff, I mean
when you consider someone who's just learning and making similar
mistakes again and again in Prolog. :)

The problem in itself is a beautiful one and I'll keep on
trying to find a solution but now...

.... *please, please, please, if you know some URLs that contain
some working examples of Cased-Based Reasoning in Prolog*
just give me the addresses, I need to hurry up for a project
all I could find was abstract tutorials with abstract diagrams
or some short articles from proceedings or some stuff done
in a proprietary envrionment which is not Prolog. I need
some sample code as a starting point and apply it to some
case bases and play with some of the parameters and compare
the results.

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

Bart Demoen

2004-12-27, 8:56 pm

tmp123 wrote:
>
>
> 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.

Pardon my French, but the assert/retract and flag and nb_setval
suggestions are complete crap.

Most often, suggestions hinting at using these side-effect predicates
are crap. These predicates are useful (and |>sometimes<| necessary) when
you need to save information over backtracking, and very very rarely a
good alternative to passing information as an argument.
In all other cases, one should avoid them like the plague.

Since the OP is after constructing terms like 3*a anyway, why not
just use a list like [3*a, 2*b, ...] (the suggestion with the inc has
the di

vantage that one needs to traverse that list once more to
construct these, but at least it is reasonable)

BTW, a list is not an array.

I can post a complete solution if the OP is interested, but only if he
states the complete problem one final time - I do not want to chase the
specification, neither start from a vague one.

Cheers

Bart Demoen

Emre Sevinc

2004-12-27, 8:56 pm

Bart Demoen <bmd@cs.kuleuven.ac.be> writes:

> tmp123 wrote:
>
> Pardon my French, but the assert/retract and flag and nb_setval
> suggestions are complete crap.

Hmm, another thing to note down.

But for example when you are interacting with user
or gathering new information in some other way, aren't
assert/retract useful? I'm just speculating...

> Most often, suggestions hinting at using these side-effect predicates
> are crap. These predicates are useful (and |>sometimes<| necessary) when
> you need to save information over backtracking, and very very rarely a
> good alternative to passing information as an argument.
> In all other cases, one should avoid them like the plague.
>
> Since the OP is after constructing terms like 3*a anyway, why not
> just use a list like [3*a, 2*b, ...] (the suggestion with the inc has
> the di

vantage that one needs to traverse that list once more to
> construct these, but at least it is reasonable)

Well, yes, I need that kind of a list, but of course I also need
to store the operations.

> BTW, a list is not an array.

Because I cannot reach an element directly using an index?

> I can post a complete solution if the OP is interested, but only if he
> states the complete problem one final time - I do not want to chase the
> specification, neither start from a vague one.

Don't know what OP refers to but my simplification problem
was that:

given an algebraic expression like:

a + b + c - a + 1 + a - d + b + 13 - d

produce:

a + 2*b + c - 2*d + 14

So that the symbols are grouped together, operations
are applied on them, they are put at the beginning of
the new expression and the numbers are grouped together,
operations (addition, subtraction) are applied, the
resulting number is put at the end of the expression to
have the resulting simplified algebraic expression:

simplify(a + b + c - a + 1 + a - d + b + 13 - d, E).

E = a + 2*b + c - 2*d + 14

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

Bart Demoen

2004-12-28, 3:56 am

Emre Sevinc wrote:
> Bart Demoen <bmd@cs.kuleuven.ac.be> writes:
> But for example when you are interacting with user
> or gathering new information in some other way, aren't
> assert/retract useful? I'm just speculating...

(Every program is gathering (computing) new information ...)

The issue is not what sort of things is the program doing (interaction
with the user), but the structure of the program you are writing: if at
some point you must save information over backtracking, you can
contemplate using assert/retract. For instance when you have a generator
(by backtracking) of solutions, and you want the best solution. Then it
could be reasonable to use assert, as in

:- dynamic solution/1.

best_solution(Best) :-
generate(NewSol),
(solution(PrevSol) ->
(better(NewSol,PrevSol) ->
retract(solution(PrevSol)),
assert(solution(NewSol))
;
true
)
;
assert(solution(NewSol))
),
fail.
best_solution(Best) :-
retract(solution(Best)).

That should give an idea of what it is (untested code !).

But even that is more elegantly done with findall:

best_solution(Best) :-
findall(Sol,generate(Sol),AllSol),
pick_best(AllSol,Best).

The only di

vantage is that findall will make a list of all the
solutions, which might bite you if there are very many or each of them
is huge.

>
> Because I cannot reach an element directly using an index?

No. Because you cannot have access to every element (by an index or
other means) in constant time.

> Don't know what OP refers to but my simplification problem
> was that:

(OP = Original Poster - you in this case)

> given an algebraic expression like:
>
> a + b + c - a + 1 + a - d + b + 13 - d
>
> produce:
>
> a + 2*b + c - 2*d + 14

How much can we induce from that ?
Should the output be sorted in the part that has the symbols,
or is

-2*d+c+a+2*b+14

also ok ?

Should the expression be "flat", or can it contain
brackets like in

a + (b + c) + d

Can the input contain things like 2*d ?

Any other operators besides + - * ?
Is the unary - possible ? (for instance in -a + 3)
Are brackets in the input allowed ?

Why not give us a BNF of the input and we can work from that.

Cheers

Bart Demoen

Emre Sevinc

2004-12-28, 3:59 pm

Bart Demoen <bmd@cs.kuleuven.ac.be> writes:

>
>
> How much can we induce from that ?
> Should the output be sorted in the part that has the symbols,
> or is
>
> -2*d+c+a+2*b+14
>
> also ok ?

It's ok. Symbols (plain lowercase single letters) do not have to
appear in alphabetical order

> Should the expression be "flat", or can it contain
> brackets like in
>
> a + (b + c) + d

If that makes it easier to code, yes the resulting
expression can contain brackets.

> Can the input contain things like 2*d ?

No. Just numbers, single letter symbols and addition,
subtraction operations on them.

> Any other operators besides + - * ?

The input is allowed to contain only plus or minus
sign.

The output can contain plus, minus or multiplication
sign ('*', in this case).

> Is the unary - possible ? (for instance in -a + 3)

No, it is not permitted.

> Are brackets in the input allowed ?

No, the input expression will not contain any brackets,
paranthesis, no kind of grouping, plain simple symbols,
numbers, no unary operators, no multiplication in the
input expression.

> Why not give us a BNF of the input and we can work from that.

Something like that?

<Expr> ::= <Expr> <Op> <Expr>
<Expr> ::= <Symbol> | <Number>
<Symbol> ::= "a" | "b" | "c" | "d"
<Number> ::= 0 .. 9
<Op> ::= "+" | "-"

(I don't know I've used BNF notation correct, excuse me
if I have done some stupid mistakes above :)

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

Bart Demoen

2004-12-29, 3:58 pm

I have made two versions of symplify: one in Prolog and one in CHR.
Both work under SWI Prolog 5.4.4

Together, they were a bit too long to post, so I have put them at

http://www.cs.kuleuven.ac.be/~bmd/Prolog/

Cheers

Bart Demoen

tmp123

2004-12-30, 8:57 am

Sponsored Links