how does variable calculating the value in prolog's functor?

Question

The trace processing of the functor 'flatten2' with input list: "[4, [3, [2, [1,[ ] ] ] ] ]" (Screenshot of the tracing process)

The above is the screenshot of me calling functor flatten2 with input list "[4, [3, [2, [1,[ ] ] ] ] ]", and a variable 'X'.

The below is the function that I was tracing, stolen from this question: Flatten a list in Prolog.

So my essential question is that during the recursion, what happens to the variable X and its value? Why is the 'X' showed as '_295' in the "call 1", how does prolog grammar calculating this value?

flatten2([], []) :- !.
flatten2([L|Ls], FlatL) :-
    !,
    flatten2(L, NewL),
    flatten2(Ls, NewLs),
    append(NewL, NewLs, FlatL).
flatten2(L, [L]).

`_295` isn't a value. It's the internal name for the variable `X`. Since Prolog often recurses then each call defines a new `X` so Prolog creates a new variable for each call. — Enigmativity, Oct 12 '20 at 06:12

David Tonhofer · Accepted Answer · 2020-10-11T08:25:03.630

X is just a local name for "globally visible stuff" that is held in the "term store".

X designates (or names or denotes) either:

Concrete content: A term, which a generally tree. The variable is called "bound" or "instantiated". The leaves of the tree are either concrete content (atoms, numbers etc.) or cells with no content (see below). The inner nodes are called compound terms. If X designates a term, then the query nonvar(X) succeeds. When X is printed, it "disappears": The content is printed instead.
A cell with no content (I like to call this a "hole"), which is meant to be take up a term eventually. In that case the variable is called "unbound" or "uninstantiated". If X is such an unbound variable, i.e. if it designates a hole, then the query var(X) succeeds. When X is printed, its name is printed.

Confusingly (and I should add, rather sloppily), a "variable name" is commonly also called a "term". That's a Prolog tripmine, these two concepts should be held apart but they are not.

If you write your Prolog clause, you will use nice variable names.

flatten2(L, [L]).

Remember these variables names have no particular significance and they are local to the clause.

When Prolog runs, it has to pull new variable names that are distinct from any other names "out of the hat". These fresh variable names look like _295. Different implementations have different conventions here.

An example where new variable names have to be created to describe a list that contains a member foo somewhere (on at least one place). List templates of increasing length are generated. At each place of the list except the place holding foo (a concrete term), there is a "cell without content"/"hole". To express this, a random new variable name distinct from any other variable name is generated and printed. The variable name is probably directly derived from the hole address.

?- member(foo,L).
L = [foo|_23302] ;
L = [_23300, foo|_24038] ;
L = [_23300, _24036, foo|_24774] ;
L = [_23300, _24036, _24772, foo|_25510] ;
L = [_23300, _24036, _24772, _25508, foo|_26246] ;
L = [_23300, _24036, _24772, _25508, _26244, foo|_26982]

how does variable calculating the value in prolog's functor?

1 Answers1