Node:Building and Dismantling Terms, Next:Conditionals and Disjunction, Previous:Last Call Optimization, Up:Writing Efficient Programs

Building and Dismantling Terms

The built-in predicate (=..)/2 is a clear way of building terms and taking them apart. However, it is almost never the most efficient way.

functor/3 and arg/3 are generally much more efficient, though less direct. The best blend of efficiency and clarity is to write a clearly-named predicate which implements the desired operation and to use functor/3 and arg/3 in that predicate.

Here is an actual example. The task is to reimplement the built-in predicate (==)/2. The first variant uses (=..)/2 (this symbol is pronounced "univ" for historical reasons). Some Prolog textbooks recommend code similar to this.

ident_univ(X, Y) :-
        var(X),                 % If X is a variable,
        !,
        var(Y),                 % so must Y be, and
        samevar(X, Y).          % they must be the same.
ident_univ(X, Y) :-             % If X is not a variable,
        nonvar(Y),              % neither may Y be;
        X =.. [F|L],            % they must have the
        Y =.. [F|M],            % same function symbol F
        ident_list(L, M).       % and identical arguments

ident_list([], []).
ident_list([H1|T1], [H2|T2]) :-
        ident_univ(H1, H2),
        ident_list(T1, T2).

samevar(29, Y) :-               % If binding X to 29
        var(Y),                 % leaves Y unbound,
        !,                      % they were not the same
        fail.                   % variable.
samevar(_, _).                  % Otherwise they were.

This code performs the function intended; however, every time it touches a non-variable term of arity N, it constructs a list with N+1 elements, and if the two terms are identical, these lists are reclaimed only when backtracked over or garbage-collected.

Better code uses functor/3 and arg/3.

ident_farg(X, Y) :-
        (   var(X) ->           % If X is a variable,
                var(Y),         % so must Y be, and
                samevar(X, Y)   % they must be the same;
        ;   nonvar(Y),          % otherwise Y must be nonvar
            functor(X, F, N),   % The principal functors of X
            functor(Y, F, N),   % and Y must be identical,
            ident_farg(N, X, Y) % including the last N args.
        ).

ident_farg(0, _, _) :- !.
ident_farg(N, X, Y) :-          % The last N arguments are
        arg(N, X, Xn),          % identical
        arg(N, Y, Yn),          % if the Nth arguments
        ident_farg(Xn, Yn),     % are identical,
        M is N-1,               % and the last N-1 arguments
        ident_farg(M, X, Y).    % are also identical.

This approach to walking through terms using functor/3 and arg/3 avoids the construction of useless lists.

The pattern shown in the example, in which a predicate of arity K calls an auxiliary predicate of the same name of arity K+1 (the additional argument denoting the number of items remaining to process), is very common. It is not necessary to use the same name for this auxiliary predicate, but this convention is generally less prone to confusion.

In order to simply find out the principal function symbol of a term, use

| ?- the_term_is(Term),
|    functor(Term, FunctionSymbol, _).

The use of (=..)/2, as in

| ?- the_term_is(Term),
|    Term =.. [FunctionSymbol|_].

(=..)/2 should not be used to locate a particular argument of some term. For example, instead of

Term =.. [_F,_,ArgTwo|_]

you should write

arg(2, Term, ArgTwo)

It is generally easier to get the explicit number 2 right than to write the correct number of anonymous variables in the call to (=..)/2. Other people reading the program will find the call to arg/3 a much clearer expression of the program's intent. The program will also be more efficient. Even if several arguments of a term must be located, it is clearer and more efficient to write

arg(1, Term, First),
arg(3, Term, Third),
arg(4, Term, Fourth)

than to write

Term =.. [_,First,_,Third,Fourth|_]

Finally, (=..)/2 should not be used when the functor of the term to be operated on is known (that is, when both the function symbol and the arity are known). For example, to make a new term with the same function symbol and first arguments as another term, but one additional argument, the obvious solution might seem to be to write something like the following:

add_date(OldItem, Date, NewItem) :-
        OldItem =.. [item,Type,Ship,Serial],
        NewItem =.. [item,Type,Ship,Serial,Date].

However, this could be expressed more clearly and more efficiently as

add_date(OldItem, Date, NewItem) :-
        OldItem = item(Type,Ship,Serial),
        NewItem = item(Type,Ship,Serial,Date).

or even

add_date(item(Type,Ship,Serial),
         Date,
         item(Type,Ship,Serial,Date)
        ).