Prolog: Code Explanation about list and recursive wanted

Question

the following code works, but if need help to understand how it is working.

%Multiplication of List Elements, Lists have same length

listmulti([],[],[]).
listmulti([H1|B1],[H2|B2],[Result|Spare]) :-
   listmulti(B1,B2,Spare),
   Result is H1 * H2.

Everything is understandable, but not the Spare variables. Without it the code don't work.

I added my Prolog trace here, to see what happens.

trace,(listmulti([2,1],[3,5],Result)).
 Call:listmulti([2, 1], [3, 5], _5956)
 Call:listmulti([1], [5], _6268)
 Call:listmulti([], [], _6274)
 Exit:listmulti([], [], [])
 Call:_6272 is 1*5
 Exit:5 is 1*5
 Exit:listmulti([1], [5], [5])
 Call:_6266 is 2*3
 Exit:6 is 2*3
 Exit:listmulti([2, 1], [3, 5], [6, 5])
Result = [6, 5]

What are the _5956 and so on digits? Help variables from Prolog? What happens with the Spare variable, it is Empty all the time? Why i need the Spare variable? Why I can't write only [Result] so like this

listmulti([H1|B1],[H2|B2],[Result])

Thanks for your answers in advance and best greetings.

@lurker So i need [Result | Spare] cause this list has undefined much possible list elements? That Result is not the same as [Result], I know. But I cant not write easily: ``` listmulti([H1|B1],[H2|B2],Result). ``` or? — MvS
Yes, you could use a head/tail form for the result argument if it's useful for you to have a result in terms of a head and a tail. Not sure what you mean when you say you can't write listmulti([H1|B1],[H2|B2],Result) easily. Why would it be easier to write listmulti([H1|B1],[H2|B2],[Result | Spaere])? Are you referring to the query, or your predicate? — lurker
@lurker I need here a Head and Tail as result, I think not. Not for having a use of that. But without the Head and Tail construction, I get only a single list element back, as you mentioned. If I write only Result, without the [] then i also get only a single element back as result. Thats why i meant, I can't write it easily. I refer to the predicate. — MvS
Technically, _ is the only anonymous variable. I misspoke in my last comment. But other variables starting with _, such as _5956, may be an internally generated variable name. Or you can use _X for example if you want a named variable but don't care if it's singleton but _X used anywhere else in the same predicate is the same variable. Whereas _ in multiple places is considered different. — lurker

Isabelle Newbie Isabelle Newbie · Accepted Answer · 2020-07-03T21:58:14

Prolog communicates the results of computations by binding variables to terms. Variables can start out unbound, i.e., not bound to any value, and can become bound during a computation by unification.

To some extent you already know this. After all, when you write a query like

?- listmulti([2,1],[3,5],Result).

you do not specify a value for Result -- it is unbound. But when you run the query, Prolog will bind Result to a term and tell you what it is:

Result = [6, 5].

We can visualize this by printing the value of Result before and after it is bound by calling listmulti:

?- write('before the query, Result is: '), write(Result), nl,
|    listmulti([2,1], [3,5], Result),
|    write('after the query, Result is: '), write(Result), nl.
before the query, Result is: _G1699
after the query, Result is: [6,5]
Result = [6, 5].

In the beginning, Result is just some unbound variable, which is shown as _G1699 in this case. (Different variables have different numbers so you can distinguish them.) After the query is run, that same variable is now bound to the list [6, 5].

This is also what the tracer was telling you, although it takes some practice to read its output:

 Call:listmulti([1], [5], _6268)
 ...
 Exit:listmulti([1], [5], [5])

This is a pair of states just before and just after executing listmulti([1], [5], Spare). The current instance of Spare is unbound before the call and is bound to [5] afterwards, as listmulti computed the element-wise product of the lists [1] and [5].

Now consider the following version of your predicate:

listmulti([],[],[]).
listmulti([H1|B1], [H2|B2], AllResults) :-
   listmulti(B1,B2, ResultsForTheTailsOfTheLists),
   Result is H1 * H2,
   AllResults = [Result | ResultsForTheTailsOfTheLists].

When you call this with two lists of numbers in the first two arguments, operationally this will decompose those lists into their heads and tails, and compute the element-wise product of the tails. The result of this is a list of ResultsForTheTailsOfTheLists. The product of the heads is computed as Result. And then the results for the complete lists is just the list containing Result followed by all of the ResultsForTheTailsOfTheLists. Is this clearer?

The final twist is that in Prolog you can create lists and other data structures before you know what you will put in them. You can construct a list like this:

?- Head = a, Tail = [b, c], List = [Head | Tail].
Head = a,
Tail = [b, c],
List = [a, b, c].

but you can also construct the list first and only then bind its head and tail:

?- List = [Head | Tail], Head = a, Tail = [b, c].
List = [a, b, c],
Head = a,
Tail = [b, c].

And this is what is going on in your original definition: In the head, once you know that you are looking at two lists of numbers, you know that the result will be of the form [HeadResult | TailResults]. Having this term in the clause head builds it right away. Only later do you compute HeadResult and the TailResults through a recursive call. Overall this gives you a complete list.

Prolog: Code Explanation about list and recursive wanted

1 Answers