U-Reddy%UTAH-20@sri-unix.UUCP (11/03/83)
From: Uday Reddy <U-Reddy@UTAH-20>
Ref: Abbott, Purity, Prolog Digest, 1, 40, (20 Oct 83)
Richard, Reply to My Critics, Prolog Digest, 1, 44, ( 1 Nov 83)
The above references discussed the purity of =.. (UNIV). My position
is that =.. is not pure in either first-order or higher-order logic,
in the sense that it is "referentially opaque".
In the terminology of logicians, a "name" is used in a referentially
transparent way if its meaning is independent of the context in which
it appears. In particular, a name that is "used" (to denote some
semantic object) cannot be "mentioned" (to denote the name itself),
in order to preserve referential transparency.
In the context of programming, name means any syntactic object:
identifier, expression, term, clause, program, pointer or what have
you. We use these syntactic objects to denote semantic objects,
like, values, functions, and relations. As long as they are used
to denote semantic objects, their syntactic structure cannot be
"referenced" in the program. Classic cases of violations of this
principle are the use of variables in imperative languages and QUOTE
and EVAL of LISP.
Prolog has several features that violate referential transparency.
Some of them are var, functor, arg, univ and call. To see why,
consider the simple example
1 + 2 =.. [+, 1, 2]
Since 1+2 denotes a semantic object (the integer 3) its syntactic
structure should be transparent to the program. But using =.. allows
the program to look at its syntactic structure. 2+1 denotes the
semantic object as 1+2. But, replacing 1+2 by 2+1 in the above
literal does not preserve its truthful-ness.
Features like =.. can, however, be used in a referentially
transparent way. When a program manipulates syntactic objects without
using them to denote semantic objects, using these features is
perfectly acceptable. Examples of such programs are compilers and
theorem provers. It is an interesting exercise to design languages
which allow these features to be used only in a referentially
transparent way.
Arguments of the kind "all programs with a feature X can be
transformed into first-order programs; so programs with feature X
are first-order" used by Richard should be treated with scepticism.
Transformations do not preserve first-order-ness or any such property
of programs. All languages can be transformed into Turing machines.
It does not mean, of course, that all languages have the same
properties as those of Turing machines.
Once referential transparency is lost, there is really no point of
talking about the "order" of the language. univ and call (like eval
and quote of LISP) can be used to convert programs into data and data
into programs and anything is possible. Here is a definition of map
(a higher order relation) using univ and call.
map([],[],P).
map([A|X],[B|Y],P) :- Goal =.. [P,A,B], call(Goal), map(X,Y,P).
Whether you choose to call Prolog first-order or higher-order is your
choice. For me, it is neither.
-- Uday Reddy