Next: Conditionals and Disjunction, Previous: Last Call Optimization, Up: Writing Efficient Programs [Contents][Index]
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 that 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, then 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|_].
is wasteful, and should generally be avoided. The same remark applies if the arity of a term is desired.
(=..)/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) ).