Bug report

[P M Hill]

Dear GNU developer,

I have found the following problem in GNU Prolog.
(Running Linux 2.4.2 and using GNU Prolog 1.2.11.)

The bug is as follows: if the variable occurs before a choice point and
is then bound to a non-variable by a predicate defined in an interface
(to C++) after the choice point, then its binding is not undone on
backtracking.

More precisely, the bug occurs if: a variable is referred to before a
choice point; there is a choice point; after the choice point, an
C++ interface predicate binds the variable to a non-variable term; the
procedure is then forced to backtrack by ensuring the first branch of
the choice point fails.

The program below has three tests. The first (test1) shows the bug.
The other two (test2, test3) have no problem and by comparing them
with test1 help indicate what features are needed to reproduce the
bug.

The tests test1 and test2 use ppl_new_Polyhedron_from_dimension/3. This is
a predicate defined in the interface to the PPL (the Parma Polyhedra
Library) which is written in C++.  This predicate binds a variable P to a
handle to the vector space with the specified number of dimensions (0) and
topology (c).  Before calling this predicate, P should be free.  After a
call to this predicate, P should be bound to a term of the form
$address(N,M), where N and M are numbers.

The other PPL predicates (ppl_initilize/0, ppl_finalize/0,
ppl_delete_Polyhedron/1) used in the tests are relevant for using the
PPL but are not directly related to the problem being reported.

To run the tests you need both this little program and the PPL.
Note that the PPL with documentation is available at
   http://www.cs.unipr.it/ppl/
I am hoping that, even if you do not download and install the PPL, you
may be able to find the cause of the bug from the description here
which seems to be due to the interraction between using the interface
and backtracking.  Also, if it helps, I can perform for you any
further tests you suggest.

------------------------------------------------------------------

% The program gnu_bug.pl to show a bug in GNU Prolog 1.2.11

/*
The first test shows that if the variable occurs before the choice
point and is then bound to a handle for a polyhedron after the choice
point, then its binding is not undone on backtracking.

The second test shows that if the variable does not occur before the
choice point, then the binding is undone ok.

The third test shows that if it does not use
the ppl interface, then the binding is undone ok.
*/

test1 :-
  nl, write('test1 has the 1st occurrence of P before the choice point'),
nl,
  ppl_initialize,
  nl, write('Before the choice point:'),
  write(' N = '), write(N), write(' P = '), write(P), nl,
  nl, write('After the choice point:'),
  try(N),
  write(' N = '), write(N), write(' P = '), write(P),
  ppl_new_Polyhedron_from_dimension(c, 0, P),
  cleanup(P),
  N=2,
  nl,
  ppl_delete_Polyhedron(P),
  !,
  ppl_finalize.

test2 :-
  nl, write('test2 has the 1st occurrence of P after the choice point'),
nl,
  ppl_initialize,
%%  nl, write('Before the choice point:'),
%%  write(' N = '), write(N), write(' P = '), write(P), nl,
  nl, write('After the choice point:'),
  try(N),
  write(' N = '), write(N), write(' P = '), write(P),
  ppl_new_Polyhedron_from_dimension(c, 0, P),
  cleanup(P),
  N=2,
  nl,
  ppl_delete_Polyhedron(P),
  !,
  ppl_finalize.

test3 :-
  nl, write('test3 has the same structure as test1 without the PPL
interface'), nl,
  ppl_initialize,
  nl, write('Before the choice point:'),
  write(' N = '), write(N), write(' P = '), write(P), nl,
  nl, write('After the choice point:'),
  try(N),
  write(' N = '), write(N), write(' P = '), write(P),
  P = 99,
  N=2,
  nl,
  !,
  ppl_finalize.

try(1).
try(2).

% To prevent leaks:
cleanup(_Polyhedron).
cleanup(Polyhedron) :-
  ppl_delete_Polyhedron(Polyhedron),
  fail.

---------------------------------------------------------------------------

   Below I provide the output from the tests using GNU Prolog, and,
   for comparison, the output from the same tests using SWI Prolog.


$ /bin/sh /.../libtool --mode=execute -dlopen  /.../libppl.la ./ppl_gprolog
GNU Prolog 1.2.11
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- [gnu_bug].
compiling /.../gnu_bug.pl for byte code...
/.../gnu_bug.pl compiled, 58 lines
read
- 4931 bytes written, 424 ms

yes
| ?- test1.

test1 has the 1st occurrence of P before the choice point

Before the choice point: N = _273 P = _274

After the choice point: N = 1 P = _274 N = 2 P = $address(32008,2093)

yes
| ?- test2.

test2 has the 1st occurrence of P after the choice point

After the choice point: N = 1 P = _273 N = 2 P = _273

yes
| ?- test3.

test3 has the same structure as test1 without the PPL interface

Before the choice point: N = _273 P = _274

After the choice point: N = 1 P = _274 N = 2 P = _274

yes
| ?- halt.
$ cd ../SWI
$ /bin/sh /.../libtool --mode=execute -dlopen /.../src/libppl.la ./ppl_pl
Welcome to SWI-Prolog (Version 5.0.2)
Copyright (c) 1990-2002 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- [gnu_bug].
% gnu_bug compiled 0.00 sec, 3,080 bytes

Yes
?- test1.

test1 has the 1st occurrence of P before the choice point

Before the choice point: N = _L154 P = _L155

After the choice point: N = 1 P = _L155 N = 2 P = _L155

Yes
?- test2.

test2 has the 1st occurrence of P after the choice point

After the choice point: N = 1 P = _L155 N = 2 P = _L155

Yes
?- test3.

test3 has the same structure as test1 without the PPL interface

Before the choice point: N = _L154 P = _L155

After the choice point: N = 1 P = _L155 N = 2 P = _L155

Yes
?- halt.
$
*/

Best regards,
  Patricia Hill