Q&A on relations as sets, quotation, mapping over set elements

Tom Gruber <gruber@HPP.Stanford.EDU>
Message-id: <199406022159.OAA28025@HPP.Stanford.EDU>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 2 Jun 1994 14:59:04 -0800
To: ontolingua@HPP.Stanford.EDU
From: Tom Gruber <gruber@HPP.Stanford.EDU>
Subject: Q&A on relations as sets, quotation, mapping over set elements
Is are some questions and answers on a representation problem that involves
several advanced KIF topics: relations as sets, quotation, mapping over set

Excerpt quoted with permission.

>1. It seems that in Ontolingua version 4 the distinction between class
>and set has been removed. Is that true?

No.  See the definition of CLASS in the frame ontology.
A class is a unary relation.  The definition of RELATION from
KIF-RELATIONS ontology says that a relation is a set of tuples.
So a class is a set of tuples of length one.  Of course, there
is a homomorphism from set operations to class operations: member
corresponds to instance-of and subset corresponds to subclass-of.

>If so, does that also mean
>that, for instance, an expression such as
>    (instance-of (?x ?y) some-relation)
>(where, as you guessed, some-relation is some relation previously
>defined as the Cartesian product of two sets) is a valid expression?

First, the expression "(?x ?y)" is not a legal term in KIF.
See the KIF BNF.  A term must be an atom or begin with a function
constant.  To denote the two-element tuple containing the items
A and B, one would write "(listof A B)".
Second, the simple way to say that a relation R holds on objects A and B is
with the HOLDS predicate.  So in your example, you could write
   (holds some-relation ?x ?y)
if some-relation was a variable, which is what I expect.  If it were a
constant, then (some-relation ?x ?y) would do.

>2. In one of your own examples of extensional definition, you give a
>list of the object-terms that make up the set after "setof" without
>lisp-quotes. In the previous Ontolingua version (the one we examined
>at Staford when I was there), the person who made it has used
>lisp-quotes there but I think he was wrong. Am I right?

SETOF is a function that denotes the set of its arguments.
QUOTE is an operator that denotes the symbol or list expression
that is quoted.  For example, the Beatles could be represented like this:
  (= the-beatles (setof john paul ringo george))
the set of the names of the beatles is
  (setof 'john 'paul 'ringo 'george)

>3. In my ontology, certain concepts are defined as sets of ordered
>pairs of which the second member is always a fraction. It is required
>that the sum of those fractions for any such concept be one. But I
>haven't been able to find an expression that takes each element of a
>set in turn, making sure that each element is taken only once, and
>performs some operation on them like keeping track of a running
>total. I would be helped if there was a way to turn a set into a
>list. (Prolog does that easily: its sets are lists anyway.) If that is
>possible I could, for each concept, determine the range of the
>relation involved, turn the range-set into a list, and submit the list
>to the addition-function. Is that at all possible in KIF/Ontolingua?

Note that there can't be a _function_ from sets to lists, since a list is
an ordered bag with duplication, so there are many lists whose elements are
the members of a set.  However, here's a definition for a _relation_ that maps
sets to lists.

(define-relation list-from-set (?set ?list)
  :iff-def (exists (@elements)
              (and (= ?set (setof @elements))
                   (= ?list (listof @elements)))))

If you want to add up the elements of a list L, use this:

 (apply + L)        ;; APPLY is from kif-relations

If you want to produce a list of the second elements of each element of a
list L, do this:

 (define-function second-element (?list)
    := (first (rest ?list)))

 (map second-element L)     ; MAP is also from kif-relations

But if the thing you're operating on is a relation, not some arbitrary list
or set, then you can use the frame ontology vocabulary.  For instance, the
function EXACT-RANGE (from frame-ontology) returns the class whose elements
are the second elements of the tuples of R, and the function ALL-INSTANCES
(also from frame-ontology) is the function from a class to the set of its

So if you want to count up the fractions in the second element of each
tuple in a binary relation R,

(define-function range-cardinality (?R) :-> ?n
  := (apply + (all-instances (exact-range ?R))))

>And if it is, I will certainly run into trouble when translating it to
>some target language.

Yes, because of APPLY and the @ operator, which isn't portable.  Still,
that's a pragmatic issue and one could imagine working around it by
extending the translators.  The main point is to formalize the