Segmentation fault with constraints involving many terms.

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Segmentation fault with constraints involving many terms.

Thierry Martinez-3
Hi!

The following program leads to a segmentation fault, possibly after
having printed ”here” (and more precisely, when telling the constraint
Sum #> 0), with all versions of GNU Prolog at least since 1.4.1. The
length of the sum leading to the error may vary depending on the
architecture.

:- initialization(test).

test :-
   test_sum_n(162),
   print(here),
   nl,
   test_sum_n(163).

test_sum_n(N) :-
   length(VarList, N),
   build_sum(VarList, Sum),
   Sum #> 0.

build_sum([], 0).
build_sum([A], A) :- !.
build_sum([H1, H2 | T], S + H1):-
   build_sum([H2 | T], S).

Changing build_sum by introducing intermediate FD variables solves the problem.

build_sum([], 0).
build_sum([A], A) :- !.
build_sum([H1, H2 | T], Sum):-
   Sum #= S + H1,
   build_sum([H2 | T], S).

--
Thierry.

_______________________________________________
Bug-prolog mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-prolog
Reply | Threaded
Open this post in threaded view
|

Re: Segmentation fault with constraints involving many terms.

Daniel Diaz-3
Hi,

this is due to a process stack overflow. The expressions (arguments) of #> are subject to a normalization, handled by a recursive C function. Depending on how arguments are given (left or right associated) the function can recurs too much.
For instance if you change S + H1 by H1 + S no overflow occurs. I have modified a bit the function to accept simple cases (so your initial code works):


Also in the git (branch master):

git clone <a href="git://git.code.sf.net/p/gprolog/code">git://git.code.sf.net/p/gprolog/code gprolog-code

A remark about your build_sum/2 predicate:

build_sum([], 0).

build_sum([A], A) :- !.

build_sum([H1, H2 | T], S + H1):-
build_sum([H2 | T], S).


It is not take advantage of Prolog indexing (a choice-point is created of clause 2 and 3). This is simple and enough:

build_sum([], 0).

build_sum([H|T], S + H):-
build_sum(T, S).

If you wan to avoid the 0+ in case the list is not empty, you can use:

build_sum([], 0).

build_sum([H|T], S):-
build_sum(T, H, S).


build_sum([], X, X).

build_sum([H|T], S, S1):-
build_sum(T, S + H, S1).

This version takes advantage of Prolog indexing too.

Finally it is very heap consuming to create the sum as a Prolog term and then to pass it to #>. It is preferable to create the constraints #= step by step with intermediate FD variables (as in your last example).

To come back to process stack size: I have been asked several times about how to set process stack size. Depending on the OS it is possible to increase this limit (e.g. under unix-liko OS using ulimit -s SIZE). 

To know its size:

$ ulimit -s
8192

For instance under linux it is possible to set:

$ ulimit -s 65535

or even
 
$ ulimit -s unlimited

Mac OS X does not seem to accept unlimited (test OS X Lion = Darwin Kernel Version 12.2.1). But it accepts:
$ ulimit -s 65532
(why not 65536 ? I don't know).

Under windows it is possible to set the size of the stack for an executable at link time.


Daniel


Le 6 mars 2013 à 16:25, Thierry Martinez <[hidden email]> a écrit :

Hi!

The following program leads to a segmentation fault, possibly after
having printed ”here” (and more precisely, when telling the constraint
Sum #> 0), with all versions of GNU Prolog at least since 1.4.1. The
length of the sum leading to the error may vary depending on the
architecture.

:- initialization(test).

test :-
  test_sum_n(162),
  print(here),
  nl,
  test_sum_n(163).

test_sum_n(N) :-
  length(VarList, N),
  build_sum(VarList, Sum),
  Sum #> 0.

build_sum([], 0).
build_sum([A], A) :- !.
build_sum([H1, H2 | T], S + H1):-
  build_sum([H2 | T], S).

Changing build_sum by introducing intermediate FD variables solves the problem.

build_sum([], 0).
build_sum([A], A) :- !.
build_sum([H1, H2 | T], Sum):-
  Sum #= S + H1,
  build_sum([H2 | T], S).

--
Thierry.


--
Ce message a été vérifié par MailScanner pour des virus ou des polluriels et rien de suspect n'a été trouvé.
_______________________________________________
Bug-prolog mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/bug-prolog