cdsm@doc.ic.ac.uk (Chris Moss) (07/27/87)
We would like to encourage some discussion of standardization issues on the net. Terminology is always a contentious issue, and so appended here is a reprint of one of the BSI documents on terminology. Comments please! I suggest you post issues directly to the network, and to help the discussion, please (1) quote only as much of the definitions as are necessary to make your point (2) remember that definitions hang together. Check the ramifications of your point on other definitions. (3) be constructive, suggest replacements if possible. Sorry for the length of this posting. I'm going on holiday next week so won't respond immediately. Chris Moss. --------------------------------------------------------------------- THE TERMINOLOGY OF PROLOG BSI/IST/5/15 PS/135 Edited by N D North, National Physical Laboratory, Teddington, Middlesex, England NOTE - This is a working document and replaces PS/65/1. Features described in it may well be changed or even not appear in an eventual standard. Introduction This is the terminology to be adopted in standard Prolog. The format is modelled on that of ISO Standards Handbook 10, Data Processing - Vocabulary. Words and phrases that are defined in the glossary are printed in italics when they are used in definitions (in the printed version). Suggestions for additions and corrections are welcomed. Definitions argument A term which is associated with a literal or compound term. arity A non-negative integer associated with a functor or predicate. atom One of a set of unstructured objects whose only property is that equality of two elements can be determined. NOTE - Most Prologs give an atom some structure by introducing a built-in predicate which relates the atom to the sequence of symbols comprising its name. body A goal, distinguished by its context as part of a rule. bound A variable is bound with respect to a substitution unless the substitution maps the variable to itself. built-in predicate A procedure whose definition is part of the Prolog system. NOTE - A built-in predicate cannot be redefined. clause A clause is a fact or a rule compound term A functor of arity N together with a sequence of N arguments. constant An atom, a number, or a string. to consult To read in and store a program, executing any directives. database The set of procedures with respect to which resolution is performed. directive A goal given as input to the top level, interactively or in a program being consulted. Variable substitutions that are found while executing the directive are not output. empty list A distinguished atom. Variously written as "[]", (), <>, nil. fact A literal which is known to be true. There is implicit universal quantification over any variables in the fact. functor A functor symbol together with an arity. functor symbol An atom, associated with a functor. goal A literal, or a disjunction or conjunction of goals. ground A term is ground if it contains no uninstantiated variables. A term is ground with respect to a substitution if repeated application of the substitution yields a ground term. head (of a rule) A literal, distinguished by its context. head (of a list) The first argument of a non-empty list. instantiated A variable is instantiated with respect to a substitution if repeated application of the substitution yields a constant or a compound term. list Either the empty list or a non-empty list. list constructor A distinguished functor, of arity two, used for constructing lists. Usually written as '.' literal A predicate of arity N and a sequence of N arguments. most general unifier The unique minimal substitution which unifies a set of terms. non-empty list A compound term whose functor is the list constructor and which has two arguments, the second of which is a list. number An integer or floating point number. predicate A predicate symbol together with an an arity. predicate symbol An atom, associated with a predicate. procedure A sequence of clauses defining a predicate. The predicate symbol and arity of all facts and heads of rules in the procedure are those of the predicate being defined. program A sequence of clauses and directives. query A goal given as interactive input to the top level. Variable substitutions found while executing the query are output. resolution A method for finding a substitution which, when applied to a set of literals, makes their conjunction true with respect to a set of clauses. rule Syntactically a head and a body. Declaratively a statement that, if the body is true for some substitution, then the head is also true for that substitution. string A sequence of characters. NOTE - Strings are implemented as a separate data type. substitution A mapping from variables to terms. By extension a substitution acts on a term by acting on each variable in the term. tail The second argument of a non-empty list. term A constant, a compound term or a variable. to unify To find a substitution which, when repeatedly applied to a set of terms, makes them all identical. uninstantiated A variable is uninstantiated when it is not instantiated. variable An object which can represent any term. ** End of Terminology list
debray@arizona.edu (Saumya Debray) (07/30/87)
In article <505@ivax.doc.ic.ac.uk>, cdsm@doc.ic.ac.uk (Chris Moss) writes: > We would like to encourage some discussion of standardization issues > on the net. [...] This is the terminology to be adopted in standard Prolog. ---------- > argument A term which is associated with a literal or compound > term. "associated" seems rather vague here. E.g. I'd argue that if T2 is a subterm of T1, then T1 is associated with T2 just as much as T2 is associated with T1. I'd rather say something like "if p is an n-ary predicate symbol and L = p(t1, ..., tn) a literal, then the terms t1, ..., tn are the arguments to L; if f is an n-ary function symbol ..." ---------- > atom One of a set of unstructured objects whose only > property is that equality of two elements can be determined. Prolog's usage of the term "atom" has often bothered me, because standard texts on logic typically define an atom to be a literal p(t1,..., tn). I'd prefer to have Prolog's usage of "atom" replaced by "constant" (i.e. 0-ary function symbol). That would also do away with any need to explain what it means for an object to be "structured". (Of course, given established Prolog usage, I expect the atomic ambiguity will live on!) ---------- > built-in predicate A procedure whose definition is part of the > Prolog system. NOTE - A built-in predicate cannot be redefined. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ I have trouble with this one: surely this depends on the implementation? E.g. in SB-Prolog, most built-in predicates *can* be redefined. Also, what does it mean to be "part of the Prolog system"? Do libraries count? ---------- > goal A literal, or a disjunction or conjunction of goals. There should be some provision for negation. ---------- > substitution A mapping from variables to terms. By > extension a substitution acts on a term by acting on each > variable in the term. I like my substitutions idempotent, i.e. "fully dereferenced", but this might be a matter of taste. It does simplify things elsewhere, though: "repeated applications" of substitutions become unnecessary. ---------- -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: {allegra, cmcl2, ihnp4} !arizona!debray
harald@munnari.oz (Harald Sondergaard) (07/31/87)
Terminology is certainly an important issue and it is true that we could
need some clarification. The attempt by Chris Moss to start a discussion
is thus praiseworthy. In fact it is guaranteed to succeed since the draft
posted is sufficiently vague to create a heated debate.
It seems that the attempt is premature. If a group is working on this
under the auspices of BSI, one would expect that it would like to put off
a presentation of its work to a wider audience until the draft was found
reasonably well-balanced, coherent and finished.
A rationale and a statement of purpose would seem to be minimal
requirements for debaters. Who are the addressees of this standard? Prolog
novices? Researchers in programming languages? I would like to be more
constructive, but without a rationale it is a bit difficult. Following are
some more or less specific comments to the draft:
General
-------
Basically, much more precision is needed. As it stands, "Definitions" is
a grossly misleading heading. Also, well established term from logic
programming should be adopted. Lloyd's book by now serves more or less as
a standard, and it would be nice if there were to be no conflicts between
this book and the BSI draft [Lloyd 1984]. In particular, "atom" should be
given the meaning of "atomic formula". (Note that a second edition of
Lloyd's book is due to appear this year, and there are some changes in
terminology as compared to the first edition).
Substitutions
-------------
The idea of substitutions being mappings is fine, but note that this is
not in agreement with [Lloyd 1984]. In any case, the fact that substitutions
(apparently) are not assumed to be idempotent causes all kinds of problems.
For instance, is the continual "repeated application" of a substitution
supposed to terminate? Or does {x/f(x)} unify {x,f(x)} ("to unify")? On a
conceptual level, all substitutions generated by unification are idempotent
so why not use the fact to simplify definitions? (Admittedly the set of
idempotent substitutions is not closed under composition, but this never
causes problems for Prolog semantics). It is not stated what is meant by a
minimal substitution ("most general unifier"), and the reader may wonder
what a minimal mapping is. Indeed, if one allows for the lack of idem-
potence, there is no "unique minimal substitution" (under the ordering
we normally assume for substitutions). And in the general case, uniqueness
only holds modulo consistent renaming of variables.
The authors of course know this well, but they should keep in mind
that readers probably do not.
Issues of reference
-------------------
It is suggested that matters of syntax and of semantics are more carefully
distinguished. It is unclear what it means for a literal (a syntactic
entity) to be "known to be true" ("fact"). Or what it means to "define a
predicate" which is in turn explained as an atom and a natural number
("procedure"). Indeed, the notion of "truth" is never clarified. A good
device for emphasizing the difference between phrases in the language
and what they denote is the term "expression". For instance it would be
more natural to say that nil is a list expression that can denote any
empty list, rather than define lists to be purely syntactic objects.
Miscellaneous
-------------
In the definition of a ground term, "uninstantiated" should be dropped.
It is not clear what "top level" means. Is a "variable substitution"
anything but a substitution ("query")? To "consult" does not sound
natural for reading and storing.
[Lloyd 1984]
Lloyd, John W., Foundations of Logic Programming, Springer-Verlag 1984
Harald Sondergaard
University of Copenhagen