Prolog - How to create a list of sharing variables?

Author

How to create a list of sharing variables?

Wolfgang von Hansen

2006-09-12, 7:02 pm

Hi,

how can I create (a list of) sharing but uninstantiated variables that can
be used to express relationships? The background is this: I am a Prolog
newbie and try to get some experience by solving tasks from "The First 10
Prolog Programming Contests". Currently, I am working on "Crossword". I
already created a list of variables similar to that in the hints (p. 9)
but all refer to different places. There is no relationship between rows
and columns...

I could track the problem down to the simple case shown below. Basically,
the fields are contained in the Prolog database and are retrieved via
findall/3.

main :-
assert(field(_)),
findall(X, field(X), F1),
findall(Y, field(Y), F2),
write('Field 1: '), write(F1), nl,
write('Field 2: '), write(F2), nl.

Field 1: [_G364]
Field 2: [_G387]

The strange thing is, that two consecutive calls return different
variables. Why is it like this and what can I do about it?

Wolfgang

bart demoen

2006-09-12, 7:02 pm

On Tue, 12 Sep 2006 21:12:27 +0200, Wolfgang von Hansen wrote:

> Hi,
>
> how can I create (a list of) sharing but uninstantiated variables that can
> be used to express relationships?

share(L) :-
L = [X, Y],
X = Y.

would do.

> The background is this: I am a Prolog
> newbie and try to get some experience by solving tasks from "The First 10
> Prolog Programming Contests". Currently, I am working on "Crossword". I
> already created a list of variables similar to that in the hints (p. 9)
> but all refer to different places. There is no relationship between rows
> and columns...
>
> I could track the problem down to the simple case shown below. Basically,
> the fields are contained in the Prolog database and are retrieved via
> findall/3.
>
> main :-
> assert(field(_)),
> findall(X, field(X), F1),
> findall(Y, field(Y), F2),
> write('Field 1: '), write(F1), nl,
> write('Field 2: '), write(F2), nl.
>
> Field 1: [_G364]
> Field 2: [_G387]
[...]

There are several possible appropriate reactions to what you write. None
of them solve directly your problrm, and they might seem to be unrelated,
but you could pick up enough so that you arrive at following the hint and
solving the problem.

1) only two problems in the book benefit from using assert; in most
contests, it was actually forbidden explicitly to use assert; the reason
is that using assert drives you away from logic (which Prolog is only
an approximation to anyway, but assert makes it worse)

2) findall/3 has a copying semantics; you don't need to use assert for
showing that:

| ?- findall(Y,X=Y,L1), findall(Y,X=Y,L2).
L1 = [_A],
L2 = [_B] ?

If you want a sharing semantics, use bagof or setof - but believe me:
you pretty much never want bagof or setof: the sharing semantics is
quite difficult to understand and there are other pitfalls as well.

> The strange thing is, that two consecutive calls return different
> variables.

Even without findall, this can be true:

| ?- assert(f(_)), f(X), f(Y), write(X=Y).
_513=_550

I.e. also assert (and subsequent calling) has a copying semantics - we
actually rather say "variable renaming semantics", but it amounts to
non-sharing as far as variables is concerned. Try reading something about
resolution.

Now let me give a hint on how to implement the hint on page 9 of the book:

write a predicate with input a list of atom and a list of free (different)
variable - now make sure that the predicate makes the variables in the
second list the same (i.e. unifies them) if on the corresponding positions
in the atomlist, the atoms are the same - here are some sample queries
with answers:

?- makesame([a,b,a],[X,Y,Z]).
X = Z
yes

?- makesame([a,b,c,a,b],[A,B,C,D,E]).
A = D
B = E
yes

The exact output from the Prolog toplevel might be a bit different, but
you certainly get the gist of it.

Try to make makesame/2 first and get back to us.

Cheers

Bart Demoen

ps. the intro of the book also says:

Mind you: this book does not attempt to teach you how to program
in Prolog. For that, you will need to read one of the excellent books
on Prolog, or go through one of the on-line Prolog tutorials. You can
find them in the \texttt{comp.lang.prolog} FAQ\footnote{Currently at
\texttt{http://www.cs.kuleuven.be/\~{}remko/prolog/faq/}}.

really, it is worth first doing a tutorial !

Wolfgang von Hansen

2006-09-15, 7:00 pm

On Tue, 12 Sep 2006, bart demoen wrote:

> 1) only two problems in the book benefit from using assert; in most
> contests, it was actually forbidden explicitly to use assert; the reason
> is that using assert drives you away from logic (which Prolog is only
> an approximation to anyway, but assert makes it worse)

I guess you are right with this. After successfully solving the task I saw
that my approach was quite different from the given solution. I hadn't
stored the crossword in an array but as a number of facts field(X,Y,_). I
also had the idea to transpose rows and columns but did it by replacing
the facts with transposed ones...

> Now let me give a hint on how to implement the hint on page 9 of the book:

Thanks for your help. In fact, I got rid of the problem with the
non-sharing variables by storing all facts as objects in a list and using
member/2 to access them. BTW, I liked the predicate fill_in/2 from the
given solution. It is very elegant (even though not too quick).

This leads me to a different, but related question:

Given a general task, where the input consists of some objects (maybe of
more than one type) that shall be combined to create new objects (of a
different type). What would be the best way to represent the objects in a
Prolog program? Should I enter/assert them as facts or would it be better
to put them all into a single list?

Wolfgang

bart demoen

2006-09-23, 7:00 pm

On Fri, 15 Sep 2006 22:02:27 +0200, Wolfgang von Hansen wrote:

> This leads me to a different, but related question:
>
> Given a general task, where the input consists of some objects (maybe of
> more than one type) that shall be combined to create new objects (of a
> different type). What would be the best way to represent the objects in a
> Prolog program? Should I enter/assert them as facts or would it be better
> to put them all into a single list?

Often, the form of the input is not your choice, so you must be able
to comply to given facts, or to given lists with terms.

Often, when facts are given, you will feel the need to convert them to
lists of terms. For instance, let a graph be given by a set of arc/2 facts:

arc(a,b).
arc(b,c).
arc(a,d).

and then your program might need the list of tuples consisting of a node
and for that node the list of nodes connected directly to that node - as
in

[t(a,[b,d]), t(b,[c])]

so you need to convert between facts and terms.

Often, you will have a list like above, and feel the need to define a
fact-like predicate - you might the write:

arc(X,Y,AboveList) :-
member(f(X,LX),AboveList),
member(Y,LX).

which would behave like the facts which lead to the list ...

Just to say: there is no unique best way. Make sure you can go from one
to the other. Try to understand tradeoffs. Try to understand
which tradeoff is the best in your particular application.

Cheers

Bart Demoen

Sponsored Links