(a) nth/3 segfault; (b) fail-fast implementation of nth/3

[Francisco Lobo]

Hi,

While doing my prolog coursework, using a generate & test technique, I 
have noticed the following two issues.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
(A) Please consider these failed gprolog sessions:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
GNU Prolog 1.2.19
By Daniel Diaz
Copyright (C) 1999-2005 Daniel Diaz
| ?- trace.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- nth(_, X, X).
      1    1  Call: nth(_16,_17,_17) ?
      1    1  Exit: 
nth(1,[[[[[[[[[...]|_50]|_50]|_50]|_50]|_50]|_50]|_50]|_50],[[[[[[[[[...]|_50]|_50]|_50]|_50]|_50]|_50]|_50]|_50]) 
?
Segmentation fault
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
GNU Prolog 1.2.19
By Daniel Diaz
Copyright (C) 1999-2005 Daniel Diaz
| ?- [user].
compiling user for byte code...

head(X, [X|_]).

user compiled, 3 lines read - 275 bytes written, 3105 ms

yes
| ?- trace.
The debugger will first creep -- showing everything (trace)

(4 ms) yes
{trace}
| ?- head(X, X).
      1    1  Call: head(_16,_16) ?
      1    1  Exit: 
head([[[[[[[[[...]|_48]|_48]|_48]|_48]|_48]|_48]|_48]|_48],[[[[[[[[[...]|_48]|_48]|_48]|_48]|_48]|_48]|_48]|_48]) 
?
Segmentation fault
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
GNU Prolog 1.2.19
By Daniel Diaz
Copyright (C) 1999-2005 Daniel Diaz
| ?- [user].
compiling user for byte code...

head(X, [X|_]).

user compiled, 3 lines read - 274 bytes written, 10173 ms

yes
| ?- trace.
The debugger will first creep -- showing everything (trace)

(4 ms) yes
{trace}
| ?- head(X, Y), head(Y, X).
      1    1  Call: head(_16,_17) ?
      1    1  Exit: head(_16,[_16|_64]) ?
      2    1  Call: head([_16|_64],_16) ?
      2    1  Exit: 
head([[[[[[[[[...]|_88]|_64]|_88]|_64]|_88]|_64]|_88]|_64],[[[[[[[[[...]|_64]|_88]|_64]|_88]|_64]|_88]|_64]|_88]) 
?
Segmentation fault
%_______________________________________________________________________________

The segfault of the built-in nth/3 is the same issue as those of the 
test clause head/2: a clause that is also found in many other list 
processing functions.

These goals remind me of Russell's paradox, and I would expect gprolog 
to answer 'no'.

But given the segfault, I wonder if there is some problem with my 
compilation of gprolog? (which was done on a slackware-current system.)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
(B) Please consider the following gprolog session:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
GNU Prolog 1.2.19
By Daniel Diaz
Copyright (C) 1999-2005 Daniel Diaz
| ?- [user].
compiling user for byte code...

nth1_A(1, [X|_], X) :- !.
nth1_A(N, [_|T], X) :- N1 is N - 1, nth1_A(N1, T, X).

nth1_B(1, [H|_], X) :- !, X = H.
nth1_B(N, [_|T], X) :- N1 is N - 1, nth1_B(N1, T, X).

user compiled, 7 lines read - 1384 bytes written, 26460 ms

(4 ms) yes
| ?- trace.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- nth1_A(1, [0,1], 1).
      1    1  Call: nth1_A(1,[0,1],1) ?
      2    2  Call: _87 is 1-1 ?
      2    2  Exit: 0 is 1-1 ?
      3    2  Call: nth1_A(0,[1],1) ?
      4    3  Call: _140 is 0-1 ?
      4    3  Exit: -1 is 0-1 ?
      5    3  Call: nth1_A(-1,[],1) ?
      5    3  Fail: nth1_A(-1,[],1) ?
      3    2  Fail: nth1_A(0,[1],1) ?
      1    1  Fail: nth1_A(1,[0,1],1) ?

no
{trace}
| ?- nth1_B(1, [0,1], 1).
      1    1  Call: nth1_B(1,[0,1],1) ?
      1    1  Fail: nth1_B(1,[0,1],1) ?

no
{trace}
| ?-

%_______________________________________________________________________________

This shows that the current definition of the nth/3 built-in predicate
when N is given (viz. nth1_A), will try to satisfy (possibly many) goals
that will never succeed.

I suggest that having the cut precede the unification test (viz. nth1_B) 
is an improved implementation, which would in all other cases behave as 
expected due to the condition on N.

I trust this information is useful, thus I have generated a patch
for the relevant source file.
%--------8<------------------8<------------------8<------------------8<---------
diff -Naur gprolog-1.2.19/src/BipsPl/list.pl
gprolog-1.2.19-nth/src/BipsPl/list.pl
--- gprolog-1.2.19/src/BipsPl/list.pl   2005-06-13 16:40:11.000000000 +0100
+++ gprolog-1.2.19-nth/src/BipsPl/list.pl       2006-04-07
06:25:08.000000000 +0100
@@ -180,8 +180,9 @@
        '$nth2'(L, X, 1, N).


-'$nth1'(1, [X|_], X) :-
-       !.
+'$nth1'(1, [H|_], X) :-
+       !,
+       X = H.

 '$nth1'(N, [_|T], X) :-
        N1 is N - 1,
%--------8<------------------8<------------------8<------------------8<---------


Regards,
Francisco.