Hacker News Reader

Comment by pacala | Hacker News Reader

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:

    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?!

View on HN

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.

I ran the program through swish, 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.

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.

Reply on news.ycombinator.com