[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
(a) nth/3 segfault; (b) fail-fast implementation of nth/3
From: |
Francisco Lobo |
Subject: |
(a) nth/3 segfault; (b) fail-fast implementation of nth/3 |
Date: |
Sat, 08 Apr 2006 16:14:39 +0100 |
User-agent: |
Thunderbird 1.5 (X11/20051201) |
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.
- (a) nth/3 segfault; (b) fail-fast implementation of nth/3,
Francisco Lobo <=