various Prolog and Visual Prolog problems.
Author Message
various Prolog and Visual Prolog problems.

Hi All,
I've run into a few minor prolog hitches, 3 specific to Visual
Prolog (which are last), and one that I assume is more general. Any help
would be very welcome.
Thanks,
Martin.

1) Unification produces infinite lists.
test(X,X).
?- test([a,b,c|X],X).

In my naivety, I thought that this would fail, as no list is equal to
itself when you prepend three terms on it. I had not been planning for
the deviousness of prolog, which swiftly replied -
X = [a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a, ...(etc)

Now, while I'm sure this is a highly important behaviour in some
problems, it's one that puts a brick wall in front of me using some
ideas that looked to be pretty neat. Is there any way of changing test
to not accept this type of unification?

2) Visual Prolog - arbitrarily nested lists?
I can't find any way of representing arbitrary depth lists in Visual
prolog. I can do normal lists -
RefSym = reference Symbol
L_Sym = reference RefSym*
and lists of lists -
L_L_Sym = reference L_Sym*
but I can't see an obvious way to make a predicate accept
[[a],[a,b],[[a],b,c,d]], or likewise, as an input.

An unrelated problem is that I can't find out how to (or if it's even
possible) overload operators such as "-", for difference lists and other
structures.

4) Visual Prolog - why is the compiler complaining about ?
I was attempting to define append to take as many flow patterns as
possible, while still keeping it declared as an efficient "procedure"
style call. All was fine initially - I was able to mix "procedure" and
"determ" quite happilly. I then attempted to add the (o,o,i) flow
pattern (to solve questions of the form "what lists append together to
create [a,b,c,d]?").
To do this I created the code below. Sadly, Visual Prolog was having
nothing of it, and told me that "This flow pattern does not exist -
append2(o,i,i)". No - it doesn't - but it doesn't need to - the
free(X),free(Y),bound(Z) guard should ensure that append2 is only
evaluated for (o,o,i). I tried widening the accepted flow patterns for
append2 (to (*,*,i) before the compiler was happy), but then the
compiler smugly pointed out that append was a nondeterm predicate, so I
couldn't use it (in that manner) in append. :(

Help!

---------- CODE -----------
domains
RefSym = reference Symbol
L_Sym = reference RefSym*

predicates
determ append(L_Sym,L_Sym,L_Sym) - procedure(i,i,o), (o,i,i), (i,o,i),
(i,i,i), (i,o,o), nondeterm(o,o,i).

nondeterm append2(L_Sym,L_Sym,L_Sym)-(o,o,i)  %added later%, (o,i,i),
(i,o,i), (i,i,i)

clauses
append(X,Y,Z) :- free(X),free(Y),bound(Z),!,append2(X,Y,Z).
append([],L,L) :- !.
append([X|Y],T,[X|Z]) :- !, append(Y,T,Z).

append2([],L,L).
append2([X|Y],T,[X|Z]) :- append2(Y,T,Z).
--------------------------

Thu, 26 Sep 2002 03:00:00 GMT
various Prolog and Visual Prolog problems.
Perhaps this will help with the append/3 problem:

/********************************************************************

APPEND/3

(i,i,o) - append(List1,List2,List3)
True if List 3 is the result of appending List2 to List1.
Eg. append([1,2,3],[4,5,6],L) => L=[1,2,3,4,5,6]

(i,o,i) - append(List1,List2,List3)
True if List2 is the result av removing List1 from List 3.
Eg. append([1,2,3],L,[1,2,3,4,5,6]) => L=[4,5,6]

(o,i,i) - append(List1,List2,List3)
True if List1 is the result av removing List2 from List 3.
Eg. append(L,[4,5,6],[1,2,3,4,5,6]) => L=[1,2,3]

(o,[i|o],i) - append(List1,[E|List2],List3)
True if List3 can be split into 2 parts at, but excluding, element E.
Eg. append(L1,[4|L2],[1,2,3,4,5,6]) => L1=[1,2,3], L2=[5,6]

(o,[o|i],i) - append(List1,[X|List2],List3)
True if List3 can be split into 2 parts, List1 and the element X,
which precedes List2.
Eg. append(L,[X|[4,5,6]],[1,2,3,4,5,6]) => L=[1,2], X=3

********************************************************************/

DOMAINS
ilist = INTEGER*

PREDICATES
append(ilist,ilist,ilist)
- DETERM (i,i,o)(i,o,i)(o,i,i)(o,[i|o],i)(o,[o|i],i)

CLAUSES
append([],List,List):- !.
append([H|L1],L2,[H|L3]):-
append(L1,L2,L3).

GOAL
append([1,2,3],[4,5,6],L1),            % (i,i,o)
append([1,2,3],L2,[1,2,3,4,5,6]),      % (i,o,i)
append(L3,[4,5,6],[1,2,3,4,5,6]),      % (o,i,i)
append(L4,[4|L5],[1,2,3,4,5,6]),       % (o,[i|o],i)
append(L6,[X|[4,5,6]],[1,2,3,4,5,6]).  % (o,[o|i],i)

/* OUTPUT:
L1=[1,2,3,4,5,6], L2=[4,5,6], L3=[1,2,3], L4=[1,2,3], L5=[5,6], L6=[1,2], X=3
1 Solution
*/

Daniel

Quote:
> Hi All,
>     I've run into a few minor prolog hitches, 3 specific to Visual
> Prolog (which are last), and one that I assume is more general. Any help
> would be very welcome.
> Thanks,
> Martin.

> 1) Unification produces infinite lists.
> test(X,X).
> ?- test([a,b,c|X],X).

> In my naivety, I thought that this would fail, as no list is equal to
> itself when you prepend three terms on it. I had not been planning for
> the deviousness of prolog, which swiftly replied -
> X = [a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a, ...(etc)

> Now, while I'm sure this is a highly important behaviour in some
> problems, it's one that puts a brick wall in front of me using some
> ideas that looked to be pretty neat. Is there any way of changing test
> to not accept this type of unification?

> 2) Visual Prolog - arbitrarily nested lists?
> I can't find any way of representing arbitrary depth lists in Visual
> prolog. I can do normal lists -
> RefSym = reference Symbol
> L_Sym = reference RefSym*
> and lists of lists -
> L_L_Sym = reference L_Sym*
> but I can't see an obvious way to make a predicate accept
> [[a],[a,b],[[a],b,c,d]], or likewise, as an input.

> 3) Visual Prolog - overloading operators.
> An unrelated problem is that I can't find out how to (or if it's even
> possible) overload operators such as "-", for difference lists and other
> structures.

> 4) Visual Prolog - why is the compiler complaining about ?
> I was attempting to define append to take as many flow patterns as
> possible, while still keeping it declared as an efficient "procedure"
> style call. All was fine initially - I was able to mix "procedure" and
> "determ" quite happilly. I then attempted to add the (o,o,i) flow
> pattern (to solve questions of the form "what lists append together to
> create [a,b,c,d]?").
> To do this I created the code below. Sadly, Visual Prolog was having
> nothing of it, and told me that "This flow pattern does not exist -
> append2(o,i,i)". No - it doesn't - but it doesn't need to - the
> free(X),free(Y),bound(Z) guard should ensure that append2 is only
> evaluated for (o,o,i). I tried widening the accepted flow patterns for
> append2 (to (*,*,i) before the compiler was happy), but then the
> compiler smugly pointed out that append was a nondeterm predicate, so I
> couldn't use it (in that manner) in append. :(

> Help!

> ---------- CODE -----------
> domains
>   RefSym = reference Symbol
>   L_Sym = reference RefSym*

> predicates
>   determ append(L_Sym,L_Sym,L_Sym) - procedure(i,i,o), (o,i,i), (i,o,i),
> (i,i,i), (i,o,o), nondeterm(o,o,i).

>   nondeterm append2(L_Sym,L_Sym,L_Sym)-(o,o,i)  %added later%, (o,i,i),
> (i,o,i), (i,i,i)

> clauses
>   append(X,Y,Z) :- free(X),free(Y),bound(Z),!,append2(X,Y,Z).
>   append([],L,L) :- !.
>   append([X|Y],T,[X|Z]) :- !, append(Y,T,Z).

>   append2([],L,L).
>   append2([X|Y],T,[X|Z]) :- append2(Y,T,Z).
> --------------------------

Fri, 27 Sep 2002 03:00:00 GMT
various Prolog and Visual Prolog problems.
You'll lose some efficiency when you make the append/3 predicate
non-deterministic:

PREDICATES
append(ilist,ilist,ilist)
- NONDETERM (i,i,o)(i,o,i)(o,i,i)(o,[i|o],i)(o,[o|i],i)(o,o,i)

CLAUSES
append([],List,List).
append([H|L1],L2,[H|L3]):-
append(L1,L2,L3).

GOAL
append(L7,L8,[1,2,3,4,5,6]).  % (o,o,i)

/* OUTPUT:
L7=[], L8=[1,2,3,4,5,6]
L7=[1], L8=[2,3,4,5,6]
L7=[1,2], L8=[3,4,5,6]
L7=[1,2,3], L8=[4,5,6]
L7=[1,2,3,4], L8=[5,6]
L7=[1,2,3,4,5], L8=[6]
L7=[1,2,3,4,5,6], L8=[]
7 Solutions
*/

Note that the goals in my prior message work too!

You'll need to turn off the "nondeterm predicate" preference if you
want to avoid the compiler warning.

Daniel

Fri, 27 Sep 2002 03:00:00 GMT
various Prolog and Visual Prolog problems.

Quote:

>Hi All,
>    I've run into a few minor prolog hitches, 3 specific to Visual
>Prolog (which are last), and one that I assume is more general. Any help
>would be very welcome.
>Thanks,
>Martin.

>1) Unification produces infinite lists.
>test(X,X).
>?- test([a,b,c|X],X).

>In my naivety, I thought that this would fail, as no list is equal to
>itself when you prepend three terms on it. I had not been planning for
>the deviousness of prolog, which swiftly replied -
>X = [a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a, ...(etc)

>Now, while I'm sure this is a highly important behaviour in some
>problems, it's one that puts a brick wall in front of me using some
>ideas that looked to be pretty neat. Is there any way of changing test
>to not accept this type of unification?

The ISO Prolog standard says that any unification which might produce
infinite lists leads to undefined behaviour.  It defines a predicate
unify_with_occurs_check/2 which you can use to get the behaviour that
you want.

Visual Prolog is quite different to standard Prolog;
I don't know if it has anything similar to unify_with_occurs_check/2.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"

Fri, 27 Sep 2002 03:00:00 GMT
various Prolog and Visual Prolog problems.

[snipped]

Quote:

> You'll need to turn off the "nondeterm predicate" preference if you
> want to avoid the compiler warning.

To be fair to PDC, you can avoid the warning if you place the
NONDETERM mode qualifier before the predicate name in the predicate
declaration. Maybe some day PDC will improve the compiler, such that
it recognizes the mode qualifier wherever it occurs in the predicate
declaration.

BTW, the cut in the first clause of append/3 is what makes the
predicate deterministic; placing the NONDETERM mode qualifier in the
declaration (see your code) is, therefore, superfluous.

To improve efficiency in the append/3 predicate, you should declare
2 versions: DETERM append/3 and NONDETERM nd_append/3, both with
appropriate flow patterns for the actual application.

Daniel

Fri, 27 Sep 2002 03:00:00 GMT
various Prolog and Visual Prolog problems.

Quote:

> To improve efficiency in the append/3 predicate, you should declare
> 2 versions: DETERM append/3 and NONDETERM nd_append/3, both with
> appropriate flow patterns for the actual application.

That's what I was afraid of - It's a shame you can't overload predicate
names to get round this.
I suppose it isn't major, and may even be good - in code using it(append)
I'll have to know whether I'm using append in a deterministic or
nondeterministic manner.
Thanks,
Martin.

Sat, 28 Sep 2002 03:00:00 GMT
various Prolog and Visual Prolog problems.

Quote:

> > To improve efficiency in the append/3 predicate, you should declare
> > 2 versions: DETERM append/3 and NONDETERM nd_append/3, both with
> > appropriate flow patterns for the actual application.

> That's what I was afraid of - It's a shame you can't overload predicate
> names to get round this.
> I suppose it isn't major, and may even be good - in code using it(append)

The advantage of specifying modes and flow patterns in the
declarations is that it allows the compiler to optimize the generated
machine code. If you don't specify modes and flow patterns, the
chances are that inefficient code will be generated to cater for
situations that might occur when the program is run. Generally, one
can say that for each mode and flow pattern a block of code is
generated, so it really doesn't matter if you instead write different
predicates for the different modes. That's the theory, anyway.

The Visual Prolog compiler does a good job, but it doesn't hurt to
give it some help by declaring modes and flow patterns. Such
declarations also provide some self-documentation of the program.

Quote:
> I'll have to know whether I'm using append in a deterministic or
> nondeterministic manner.

Isn't that good? Programming is about writing code to solve a number
of predefined goals (program objectives). Often you will program
procedurally and determinately but sometimes you will choose to
program declaratively and non-determinately and rely on Prolog's
built-in backtracking mechanism to find an appropriate solution to a
specific goal. IMO, if you're going to craft together a good program,
you NEED to know in which mode you are going to use predicates.
You'll also need to know how to "tame" Prolog's built-in backtracking
mechanism, which isn't by throwing in lots of cuts "just in case...".

Quote:
> Thanks,

You're welcome.

Daniel

Sun, 29 Sep 2002 03:00:00 GMT

 Page 1 of 1 [ 7 post ]

Relevant Pages