search

SWI-Prolog / swipl-devel

SWI-Prolog Main development repository
http://www.swi-prolog.org
Other
974 stars 175 forks source link

Segmentation fault #327

Open triska opened 6 years ago

triska commented 6 years ago

With SWI-Prolog 7.7.14, I get on OSX and also on Debian:

?- [user].
|: conjunction(A, G, (G,A)).
|: % user://1 compiled 0.00 sec, 1 clauses
true.

?- length(Ls, 100 000), maplist(=(true), Ls), foldl(conjunction, Ls, true, G), G.
Segmentation fault
JanWielemaker commented 6 years ago

Meta-calls are translated into temporary clauses and processing control structures (,/2) is done using a recursive C routine. This hits a C stack overflow. The best solution would be to get rid of this recursion in C, but that is a lot of work. Possibly we should implement some form of C stack overflow checking. Unfortunately that is all highly non-portable AFAIK.

XVilka commented 6 years ago

Maybe transforming C routine in tail-recursion form can help? Most of the modern C compilers can understand it and optimize properly.

JanWielemaker commented 6 years ago

The routine is already optimized for last argument processing. If you change to (swapped args)

conjunction(A, G, (A,G)).

it all works fine. As is though, the term is (((true,true),true),true). It shouldn't be too hard to fix this particular case, but the general case of control structures that are deeply nested is much harder. Conjunctions are easy, but the other control structures require state and fixup after the all arguments have been processed. The only way out is manage an explicit stack of the work to be done and the state and use an interative loop. That is surely possible, but makes the code a lot longer and harder to read. the other remaining case is write_term/2,3. All other C recursion has been removed long ago, sponsored by SecuritEase.

If you want the challenge, the function is compileBody() in pl-comp.c

JanWielemaker commented 4 years ago

This is still a relevant open issue. Reopening.