CODEWITHSUNDEEP
prolog
user3704197
user3704197

Reputation:

ERROR: Unhandled exception: Out of local stack - Prolog

I was trying to write a simple version of length/3 in Prolog.

If you look at the standard implementation of length/2 it is something as below:

length([], 0).
length([Head|Tail], N) :-
    length(Tail, N1),
    N is 1+N1.

While my code uses almost the same idea but I get the error "out of local stack", and I think it happens because of deep recursion. I couldn't figure why. And my code:

mylength(_, [], 0).
mylength([H1|T1], [H1copy|T1copy], N) :-
    mylength([H1|T1], [T1copy], N1),
    N is N1 + 1.

Upvotes: 3

Views: 370

Answers (1)

user502187
user502187

Reputation:

Your predicate mylength/3 has the following problem. I assume that you want to run it with the mode mylength(+,-,-). It is then the case that the first argument is not decending.

The problem is the second clause, where the first argument [H1|T1] in the head is passed unchanged to the first argument of the same predicate in the body, contrary to what happens in length/2. Resulting in infinite recursion, since the given second argument [T1copy] does not match the first clause.

The infinite recursion can lead to a memory exhaust, since for example each invocation will generate a new variable for H1copy. The particular error message depends on the Prolog system.

Bye

P.S.: That there might be something wrong is aleady seen when consulting the predicate. One gets a singleton warning for H1copy.

But for example in the newest SWI-Prolog version, the out of local stack error will take some time, since SWI-Prolog does carbage collection. After ^C and g I see:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.16)
Copyright (c) 1990-2014 University of Amsterdam, VU Amsterdam

Action (h for help) ? goals

[552,959] mylength([1, 2, 3], [[]], _G40)
[552,958] mylength('<garbage_collected>', '<garbage_collected>', _G40)
[552,957] mylength('<garbage_collected>', '<garbage_collected>', _G40)
[552,956] mylength('<garbage_collected>', '<garbage_collected>', _G40)
[552,955] mylength('<garbage_collected>', '<garbage_collected>', _G40)

I guess the above means that at the current moment where I have interrupted the Prolog interpreter the call stack had already a depth of 552959, i.e. half a million!

After running for several minutes, I get the following error message in SWI-Prolog: ERROR: Out of local stack.

Upvotes: 1

Related Questions