3

When I apply this query:

? length(P, _).

P = [] ? ;

P = [_] ? ;

P = [_,_] ? ;

P = [_,_,_] ? ;

P = [_,_,_,_] ?

I have that result. How does this works?

lurker
  • 56,987
  • 9
  • 69
  • 103
John Sall
  • 1,027
  • 1
  • 12
  • 25
  • 2
    Because since you have not specify any length Prolog tries every possible length and generates the corresponding list, as you can see it starts with length 0 where you get `P = []`, then length 1 where you get `P = [_]` etc... – coder Nov 09 '18 at 15:17
  • Related question: [What is redo in Prolog when you trace?](https://stackoverflow.com/q/53214129/1243762) – Guy Coder Nov 09 '18 at 15:30
  • 1
    Of interest: [List Length in Prolog](https://stackoverflow.com/a/19230900/1243762) – Guy Coder Nov 09 '18 at 15:36
  • 1
    Prolog seeks to find instances of your variables that result in a success of the predicate (note: it's a *predicate*, not a *function*). When you query, `length(P, _)` you are asking Prolog what instances of `P` will give me *any length*. Prolog responds with lists, `P`, that first have length 0, then length 1, etc. You didn't limit the length (it's variable), so you get "infinite" number results. Also, since you provided an anonymous variable for length `_`, it doesn't provide you specific results for the length value, either. Compare your result with `length(P, N).` and see what you get. – lurker Nov 09 '18 at 16:02

1 Answers1

3

Through choice points. As soon as a predicate has more than one clause, roughly a choice point is created:

length([], 0).
length([_|L], M) :- length(L, N), M is N+1.

These choice points then give different derivations by the Prolog interpreter. Here is a derivation screenshot in Tau Prolog sandbox:

enter image description here

Hold on, I guess I need to raise an issue, this derivation screenshot shows a little bit too much. Synthetic (=)/2 and control (,)/2.