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

I think you're getting an infinite unification, which eventually runs  
out of storage. Sometimes gprolog can report these problems gracefully.

Lindsey Spratt
http://homepage.mac.com/lspratt

On Apr 8, 2006, at 11:14 AM, Francisco Lobo wrote:

>
> 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.
>
>
>
> _______________________________________________
> Users-prolog mailing list
> [email protected]
> http://lists.gnu.org/mailman/listinfo/users-prolog
>