3 ms·

Thanks for the link. I dug a bit into the site, and failed to fully grok the "why" behind even the first example. From https://www.metalevel.at/prolog/facets#de

by pacala 8y ago

Thanks for the link. I dug a bit into the site, and failed to fully grok the "why" behind even the first example. From https://www.metalevel.at/prolog/facets#declarative https://www.metalevel.at/prolog/facets#declarative: list_length([], 0). list_length([_|Ls], N) :- N #> 0, N #= N0 + 1, list_length(Ls, N0). All makes sense, except for the subclause "N #> 0". Why is this necessary, is there any way to generate a negative N?!

pacala 8y ago
I ran the program through swish, https://swish.swi-prolog.org/p/aNiMdQgL.pl https://swish.swi-prolog.org/p/aNiMdQgL.pl. Turns out that the version without N #> 0 enters a nontermination loop when asked to produce the 2nd result for list_length2(X, 3) and fails with "Stack limit (0.2Gb) exceeded". Presumably because it unifies the first clause for the 1st result, then for 2nd result it unifies the second clause to enter negative N domain, and it's all downhill from there. Somewhat scary that one has to run programs forwards and backwards to ensure there are no hidden corner cases, but perhaps it becomes second nature for more experienced Prolog coders.
RichardLake 8y ago
Yes, just ask for one. Consider list_length(A, -1) this is asking if any list A has a length of -1. If the guard is not there the second rule is valid, and a infinite recursion can result.
zephyrfalcon 8y ago
A bit further on it says: > For example, given a specific length, we can ask whether there are lists of that length: ?- list_length(Ls, 3). Ls = [_G1007, _G1087, _G1167] ; false. In the current situation, if you ask for `list_length(Ls, -1)`, this will fail, obviously because there are no lists with length -1. But if you remove the `N #> 0` clause, the code will happily try to find such a list, by checking for lists with length -2, -3, ... ad infinitum. Another way to look at this is that if you have a list `[_|Ls]` with length N, its length must be an integer greater than 0.

by pacala 8y ago

pacala 8y ago

I ran the program through swish, https://swish.swi-prolog.org/p/aNiMdQgL.pl https://swish.swi-prolog.org/p/aNiMdQgL.pl. Turns out that the version without N #> 0 enters a nontermination loop when asked to produce the 2nd result for list_length2(X, 3) and fails with "Stack limit (0.2Gb) exceeded". Presumably because it unifies the first clause for the 1st result, then for 2nd result it unifies the second clause to enter negative N domain, and it's all downhill from there. Somewhat scary that one has to run programs forwards and backwards to ensure there are no hidden corner cases, but perhaps it becomes second nature for more experienced Prolog coders.

RichardLake 8y ago

Yes, just ask for one. Consider list_length(A, -1) this is asking if any list A has a length of -1. If the guard is not there the second rule is valid, and a infinite recursion can result.

zephyrfalcon 8y ago

A bit further on it says: > For example, given a specific length, we can ask whether there are lists of that length: ?- list_length(Ls, 3). Ls = [_G1007, _G1087, _G1167] ; false. In the current situation, if you ask for `list_length(Ls, -1)`, this will fail, obviously because there are no lists with length -1. But if you remove the `N #> 0` clause, the code will happily try to find such a list, by checking for lists with length -2, -3, ... ad infinitum. Another way to look at this is that if you have a list `[_|Ls]` with length N, its length must be an integer greater than 0.