Can you do this?
Author Message
Can you do this?

Quote:

> Hi, anybody.

> I think this is not too difficult for you, but I have spent two hours
> and got no idea:-(

> for any expression which includes just "+", "(" and ")" and some atomics
> something like
>         a+((b+c)+d)+e
> how can I take all "+", "(" and ")" out and leave a list like
>         [a,b,c,d,e]
> ???

> I believe this problem is similar to
>         [a,[[b,c],d],e]  ->   [a,b,c,d,e]
> or even esier. I remember the code for the second problem has been poblished
> long time ago....I didn't copy it.

> Thnak you in advance for your hint, code or any help.

get_nodes(T1+T2,Nodes):- !,
get_nodes(T1,Nodes1),
get_nodes(T2,Nodes2),
append(Nodes1,Nodes2,Nodes).
get_nodes(T,[T]).

The above gives you this:

?- get_nodes( (a+a) + b + (c) + p*q , N).
N = [a, a, b, c, p * q]

Notice that you can DISPLAY a term in prefix notation:
:-display((a+a) + b + (c) + p*q).
+(+(+(+(a,a),b),c),*(p,q))

H.

Mon, 06 Apr 1998 03:00:00 GMT
Can you do this?

> for any expression which includes just "+", "(" and ")" and some atomics
> something like
>         a+((b+c)+d)+e
> how can I take all "+", "(" and ")" out and leave a list like
>         [a,b,c,d,e]

get_nodes(T1+T2,Nodes):- !,
get_nodes(T1,Nodes1),
get_nodes(T2,Nodes2),
append(Nodes1,Nodes2,Nodes).
get_nodes(T,[T]).

The above gives you this:

?- get_nodes( (a+a) + b + (c) + p*q , N).
N = [a, a, b, c, p * q]

Notice that you can DISPLAY a term in prefix notation:
:-display((a+a) + b + (c) + p*q).
+(+(+(+(a,a),b),c),*(p,q))

Not bad, but there's no need for append/3.  Use DCGs, to change this
from O(N*2) to O(N) ("green" cuts would increase the efficiency, but
not the correctness):

get_nodes(X+Y) --> get_nodes(X), get_nodes(Y).
get_nodes(X-Y) --> get_nodes(X), get_nodes(Y).
get_nodes( +Y) -->               get_nodes(Y).
get_nodes(X*Y) --> get_nodes(X), get_nodes(Y).
get_nodes(X/Y) --> get_nodes(X), get_nodes(Y).
get_nodes(X)   --> {atomic(X)}, [X].

get_nodes(Expr, List) :- phrase(get_nodes(Expr), List).

:-      Expr = a+((b+c)+d)*e,
get_nodes(Expr, List),
write((Expr -> List)), nl.

Incidentally, something similar will flatten a list:

flatten([]) --> [].
flatten([X|Y]) --> flatten(X), flatten(Y).
flatten(X) --> {atomic(X), X \== []}, [X].

flatten(List, Flattened) :- phrase(flatten(List), Flattened).

-------

--

ExperNet                        phone: +1.415.949.8691
Systems Architect               fax:   +1.415.949.1395

Mon, 06 Apr 1998 03:00:00 GMT
Can you do this?

Quote:

> for any expression which includes just "+", "(" and ")" and some atomics
> something like
>    a+((b+c)+d)+e
> how can I take all "+", "(" and ")" out and leave a list like
>    [a,b,c,d,e]
> ???

Hi,

Since posted above question, I have got a lot of useful help from a few
people. I would like to say think you again.

Almost all people (include the ones who helped by giving me very good
hints) thought the question is homework:-) No, not at all! All my Prolog
profs are in this newsgroup. My question is the first step toward to
a big simplifier (if I can finish it).

At the moment, what I can do is something like:
simplify(2*a-(a*5-4+(6*b+4)-2*a*b), NewExpression).
NewExpression = -3 * a + ( -6 * b + 2 * ( a * b )).
In the result, all "(" and ")" are useless and look not very nice.
Any one can help me delete them?

Cheers.

Lin

Tue, 07 Apr 1998 03:00:00 GMT
Can you do this?

Quote:

>> for any expression which includes just "+", "(" and ")" and some atomics
>> something like
>>        a+((b+c)+d)+e
>> how can I take all "+", "(" and ")" out and leave a list like
>>        [a,b,c,d,e]

> Since posted above question, I have got a lot of useful help from a few
> people. I would like to say think you again.

> Almost all people (include the ones who helped by giving me very good
> hints) thought the question is homework:-) No, not at all! All my Prolog
> profs are in this newsgroup. My question is the first step toward to
> a big simplifier (if I can finish it).

Hello, Thank you for the helps I have got again. At the moment, the simplifier
can do something like:
?- sim(2*((b+a)+c)/(c+(a+b))-1, Sim).
Sim = 1 ?
?- sim(a/(a/(b/a)*a)/b*a*a, Sim).
Sim = 1 ?
What I want to do and don't know how is something like:
?- sim((a*a+a*b-2*b*b)/(a+2*b), Sim).
Sim = a-b
Anybody can offer me hints?
Do you think the simplifier may be developed until as clever as a child of 15 ?

Thanks a lot.

Lin

Sat, 11 Apr 1998 03:00:00 GMT
Can you do this?

Quote:

>> flatten([]) --> [].
>> flatten([X|Y]) --> flatten(X), flatten(Y).
>> flatten(X) --> {atomic(X), X \== []}, [X].

>> flatten(List, Flattened) :- phrase(flatten(List), Flattened).

>What are the reasons for/against using phrase/2 as above (assuming
>standard token list expansion), instead of:

>flatten(List, Flattened) :- flatten(List, Flattened, []).

The reason against it is that is just what you said - it assumes
the standard token list expansion.

Using phrase/2 can be considered a higher-level, more declarative notion.
Instead of requiring preprocessing, phrase/2 could be implemented
as a simple meta-interpreter:

phrase(Phrase, Tokens) :-
dcg_parse(Phrase, Tokens, []).

dcg_parse([], Tokens, Tokens).
dcg_parse([X|Xs], [X|Ys], Zs) :-
dcg_parse(Xs, Ys, Zs).
dcg_parse({Goal}, Tokens, Tokens) :- Goal.
dcg_parse((A, B), Tokens0, Tokens) :-
dcg_parse(A, Tokens0, Tokens1),
dcg_parse(B, Tokens0, Tokens1).
dcg_parse((A ; B), Tokens0, Tokens) :-
dcg_parse(A, Tokens0, Tokens)
;
dcg_parse(B, Tokens0, Tokens).
dcg_parse(DCG_Body, Tokens0, Tokens).

This is a very elegant way of specifying the semantics of DCGs.  (Or at
least it is until you start trying to deal with quantifiers, negation,
if-then-else, and cut - that's the trouble with meta-programming
in Prolog!)  It gives DCGs a simple and very direct declarative
semantics.  This is better than the more indirect translation semantics
which is required if you want to assume that DCGs are implemented using the
standard DCG expansion.

Of course, without partial evaluation this is a lot less efficient
than the way DCGs are typically implemented via expand_term.

But the nice thing about using phrase/2, at least in theory, is that
it leaves open the opportunity to plug in a smarter parsing tool
which could generate very efficient mostly non-backtracking parsers
using standard parser generator techniques.  In practice, I haven't
seen any such tools :-(.

Quote:
>In particular, are there any problems intermixing DCG and non-DCG clauses?
>For example, having a predicate whose three clause (heads) are:

>foo(A, B) :- ...
>foo --> ...
>foo(A, B) :- ...

>and, similarly, invoking this predicate by either goal:
>  foo(A, B)   or    phrase(foo, A, B)

There are no practical problems, provided you're willing to stick to
implementations that use the standard DCG expansion.

Sun, 12 Apr 1998 03:00:00 GMT
Can you do this?

Quote:
>/* OK then, yet another hint: */

>remove_parentheses(T1*(T2*T3),T):- !,
> remove_parentheses(T1*T2*T3,T).
>remove_parentheses(T1*T2,NT1*NT2):- !,
> remove_parentheses(T1,NT1),
> remove_parentheses(T2,NT2).

>remove_parentheses(T1+(T2+T3),T):- !,
> remove_parentheses(T1+T2+T3,T).
>remove_parentheses(T1+T2,NT1+NT2):- !,
> remove_parentheses(T1,NT1),
> remove_parentheses(T2,NT2).

>remove_parentheses(T,T).

Why do people persist in writing non-steadfast code using cut?

Consider the goal

?- remove_parentheses((1+(2+3))+4,(1+(2+3))+4).

Should this succeed?  With the definition of remove_parenthese above, does it?

Anyone who thinks code like the above is good code should read
Richard O'Keefe's book "The Craft of Prolog".

Can anyone think of a language construct in any language that is more
widely misused than Prolog's cut?

--
Fergus Henderson                WWW: http://www.cs.mu.oz.au/~fjh

Tue, 14 Apr 1998 03:00:00 GMT
Can you do this?

Quote:

> >/* OK then, yet another hint: */

> >remove_parentheses(T1*(T2*T3),T):- !,
> > remove_parentheses(T1*T2*T3,T).
> >remove_parentheses(T1*T2,NT1*NT2):- !,
> > remove_parentheses(T1,NT1),
> > remove_parentheses(T2,NT2).

> >remove_parentheses(T1+(T2+T3),T):- !,
> > remove_parentheses(T1+T2+T3,T).
> >remove_parentheses(T1+T2,NT1+NT2):- !,
> > remove_parentheses(T1,NT1),
> > remove_parentheses(T2,NT2).

> >remove_parentheses(T,T).

> Why do people persist in writing non-steadfast code using cut?

Because everybody makes mistakes once in a while,
in my case it is not structural (I hope 8-) ).

Quote:

> Consider the goal

>         ?- remove_parentheses((1+(2+3))+4,(1+(2+3))+4).

> Should this succeed?

NO, because left associativity is not exploited maximally in
the right-hand argument.

Quote:
>With the definition of remove_parenthese above, does it?

NO

And that is because the body of the clause

remove_parentheses(T1+(T2+T3),T):- !,
remove_parentheses(T1+T2+T3,T).

will fail, because 1+2+3 does not unify with 1+(2+3)

We BTW also get:
:-remove_parentheses(1+(2+3),1+A).
no

Quote:

> Anyone who thinks code like the above is good code should read
> Richard O'Keefe's book "The Craft of Prolog".

The definition above obeys O'Keefe's page 96 rule:
"Place a cut precisely as soon as you know that this is the right
clause to use, not later, and not sooner."

But applying the principle on page 97 of that book:
"Postpone output unifications until after cut"

I should have written:

remove_parentheses(T1*(T2*T3),T):- !,
remove_parentheses(T1*T2*T3,T).
remove_parentheses(T1*T2,T):- !,
remove_parentheses(T1,NT1),
remove_parentheses(T2,NT2),
T = NT1*NT2.

remove_parentheses(T1+(T2+T3),T):- !,
remove_parentheses(T1+T2+T3,T).
remove_parentheses(T1+T2,T):- !,
remove_parentheses(T1,NT1),
remove_parentheses(T2,NT2),
T = NT1+NT2.

remove_parentheses(T,T).

My definition just a quick and dirty HINT for the original poster
of the question, who himself changed my code in something
applying to O'Keefe's p. 97 principle.

ANYTHING ELSE?

Consider the goal

:-remove_parentheses( ((1+2)+3)+4, ((1+2)+3)+4 ).

> Should this succeed?
For all practical purposes: YES:
(Left associativity of + is not disturbed by the parentheses).

Quote:
> With the definition of remove_parentheses above, does it?

YES

To conclude:
THE CODE WAS STEADFAST, BUT TO PREVENT FALSE
ALARMS FROM ON-LOOKERS, IT SHOULD HAVE BEEN WRITTEN
IN A WAY TO NOT EVEN SUGGEST NON-STEADFASTNESS.

Also taking into account your DCG slip of the pen,
I think we both had an off-day. Agree?

Henk

Fri, 17 Apr 1998 03:00:00 GMT

 Page 1 of 1 [ 9 post ]

Relevant Pages