Part II: CGs

Introduction

Part II is about writing knowledge bases in Prolog+CG.

The goal is to be able to write a simple knowledge base in Prolog+CG, using:

In order to meet this goal, we will cover a little bit of Prolog. This will be covered in a chapter by itself, after the main material on CGs. The main material will have lots of links to this chapter. Refer to it whenever you need to.

Part II will only cover enough Prolog to enable you to write knowledge bases. More advanced Prolog topics will be left for Part III.

Next

The first chapter looks at concept types and instances.


Concept types and instances

Brief review

In Module I, we learned about concept types and concept instances.

Here is a brief review.

Next

Next, we look at how to represent concept types and type-hierarchies in Prolog+CG.


Concept types and type-hierarchies in Prolog+CG

How to form a type hierarchy

In Prolog+CG, we form type hierarchies like this:

  1. Write a supertype,
  2. Write a ">" (greater-than sign, without the quotes),
  3. Write a comma-separated list of subtypes,
  4. Finish with a "." (period, without the quotes).
  5. Repeat steps 1. - 4. for all types in the hierarchy that have subtypes.

Schematic representation

This could also be represented schematically as:

Supertype > Subtype1, Subtype2, ..., SubtypeN.

Repeat this pattern for all types that have subtypes.

Next

What you have just seen is an example of a specification of syntax. Next, we look at what syntax is and why you must be aware of it.


Syntax

On the previous page, you saw an example of a specification of syntax. It specifies how to write a part of the Prolog+CG language. We repeat it here:

Supertype > Subtype1, Subtype2, ..., SubtypeN.

It's like a recipe

This is just like a recipe for a cake. It describes the syntax of Prolog+CG type hierarchies.

The meaning of syntax

"Syntax" comes from Greek, "syn" (which means "together") and "taxis" (which comes from "tasso", which means "I arrange"). So it means "together-arrangement".

The syntax of a programming language specifies how to put together certain parts of the language into larger wholes.

For example, the syntax you have just seen specifies how to build:

Why you must know

The computer is stupid and is not able to guess what you had in mind if you don't follow the syntax-rules. Therefore, it is picky about syntax.

You must be careful to get the details right when writing a type-hierarchy. For example:

The computer will help

But don't worry if you get it wrong. You will be told if something is wrong, so you can correct it.

The Prolog+CG program will complain with a "syntax error", which just means it wasn't able to understand what you wrote.

In such cases, try to figure out what is wrong, and correct it and try again. It's as simple as that.

Next

Next, we give an example of how to construct a type-hierarchy given the rule we've learned.


Example

Our rule

Recall the rule used for building a type-hierarchy:

Supertype > Subtype1, Subtype2, ..., SubtypeN.

Example

Below is a type-hierarchy in Prolog+CG.

Note how each line conforms to the recipe given above:

Entity > Physical, Abstract.
Physical > Object, Process, Property.
Object > Animate, Inanimate.
Animate > HumanBeing, Animal, Plant.
Property > Juvenile, Adult, Gender.
Gender > Male, Female.
HumanBeing > Man, Woman, Boy, Girl.
Adult > Man, Woman.
Juvenile > Boy, Girl.
Male > Man, Boy.
Female > Woman, Girl.

We now explain this example.

Explanation

The example starts at the top of the lattice with "Entity". This supertype is then declared to have two immediate subtypes:

The "Abstract" node is then never given any subtypes, and so remains a leaf node.

The "Physical" node is given three immediate subtypes:

These are then each given further subtypes, which may be given further subtypes, and so on down the lattice.


Multiple inheritance

Example

Consider the following example:

Adult > Woman, Man.
Young > Girl, Boy.
Female > Woman, Girl.
Male > Man, Boy.

Multiple inheritance

It will be noticed that "Woman" occurs in several places. This is allowed, so long as there is no circularity, i.e., so long as a type is not specified to be a subtype of itself, whether immediately or indirectly.


Universal and Absurd

Example

Consider again the following example:

Adult > Woman, Man.
Young > Girl, Boy.
Female > Woman, Girl.
Male > Man, Boy.

Built-in Absurd element

It will be noticed that there is no "Absurdity" element. This could be represented, but this is not normally done.

The reason it is not normally done is that Prolog+CG implicitly adds a built-in type called "Absurd" as a subtype of every leaf node.

Built-in Universal element

It will also be noticed that, in this example, there is no single common supertype, such as "Entity", to gather "Male", "Female", etc.

This is allowed, since Prolog+CG always implicitly adds the built-in supertype called "Universal" as the sole supertype of the top-most elements.

This is true even if you add a top-most element yourself, such as "Entity". In such cases, "Entity" will have a supertype, namely "Universal".

You can use Universal

You can let types be subtypes of Universal:

Universal > Male, Female, Young, Adult.
Adult > Woman, Man.
Young > Girl, Boy.
Female > Woman, Girl.
Male > Man, Boy.

The reason we don't do it in most of the examples is that "Entity" is the preferred terminology in this course, as it is in Sowa's book from 2000 (see the references).

Next

The names of types must follow certain rules. Next, we look at these.


Identifiers

Types must be identifiers

The name of the type must be an identifier. That is, it must follow certain rules.

Definition of identifier

An identifier, in Prolog+CG, is any sequence of:

The first two characters must be letters.

Examples

For example, the following are all identifiers:

These are all identifiers because they conform to the rule given above.

Anti-examples

However, the following are not identifiers:

Summary

Thus an identifier is a sequence of letters, digits, and underscores, where the first two characters are letters.

Next

Next, we give more hints and further rules for constructing type-hierarchies.


Further rules

Introduction

On this page, we give further rules about type-hierarchies.

To have only one subtype is allowed

It is allowed to have only one subtype in the list:

Animal > Unicorn.

It is allowed to have a supertype more than once

It is allowed to have the same supertype on the left of more than one list of subtypes.

For example, the following is allowed:

Entity > Physical, Abstract.
Entity > Independent, Relative, Mediating.
Entity > Continuant, Occurent.

Next

Next, we summarize this section.


Summary

General rules

In Prolog+CG, we represent supertypes and subtypes as follows:

supertype > subtype, subtype,
                     ..., subtype.

This rule is then repeated for each type that has subtypes.

Other rules

Next

Next, we look at how to make a catalog of individuals in Prolog+CG.


Concept type instances in Prolog+CG

Introduction

There is a fundamental difference between a type on the one hand, and instances of that type on the other.

For example, while "Animal" may be a type, "Odie" and "Garfield" are instances of that type.

Instances are members of the group of entities which the type names. The type is the name of the group.

Next

Next, we look at the rules for specifying a catalog of instances.


The rules

Two ways

In Prolog+CG, we have two ways of saying that a type has an instance:

Like types, instances must be identifiers.

How to write a catalog of individuals

A catalog of individuals for a given type is written like this:

Type = Instance1, Instance2, ..., InstanceN.

Here, a number of instances (on the right-hand side) are declared to be instances of a specific type (on the left-hand side).

This rule is then repeated for each type that has instances.

This is similar to type-hierarchies

Notice how this is similar to the recipe for type-hierarchies.

The differences include:

Next

Next, we give some examples.


Examples

Example

For example:

Entity > Animate.
Animate > HumanBeing, Animal.

HumanBeing = Peter, Paul, Mary.
Animal = Garfield, Odie, Eeek.

(This example can be found in the AAU directory as "Type-hierarchy2.plgCG".)

Explanation

First, we have a very small type-hierarchy (specified with ">"). This declares our types.

Then we have the catalog of instances:

Next

Next, we give some further rules.


Further rules

The list can have any length

Note that the list of instances can have any length, from one upwards. For example:

Animate > Unicorn, HumanBeing.

Unicorn = Gaudior.
HumanBeing = CharlesWallace, Meg, Sandy, ElZacho, Bezee, Kevin, 
             MrMortmain, Zylle, Maddox.

Each type may be listed more than once

Each type may appear on the left-hand side of an instance declaration more than once. For example, the following is allowed:

Entity > Animal.

Animal = Garfield.
Animal = Odie.

Next

Next, we summarize this section.


Summary

General rules

Here is how to write the instances of one type:

Type = Instance1, Instance2, ..., InstanceN.

This rule is repeated for each type that has instances.

Other rules

Next

Next, we have a quiz


CG syntax

Introduction

This chapter is about how to write conceptual graphs in the syntax provided by Prolog+CG.

  1. The first section deals with relations.
  2. The second deals briefly with arcs.
  3. Then, concepts are treated.
  4. After concepts, we describe how to write graphs that extend over multiple lines.
  5. Then we describe how to make coreferents in this syntax.
  6. And finally, there is a quiz.


Relations

Introduction

A relation looks like this in context:

  [ConceptType1]-Relation->[ConceptType2]

Note how the relation is simply an identifier or variable that stands between two concepts, connected by arcs.

No parentheses

In the syntax of Prolog+CG, we write a relation simply as an identifier or a variable between two arcs. There are no parentheses around the relation.

Note also how there is no arrow-head on the arc going to the relation, only on the one going from it.

Example

For example:

[Animal : Wolf]-AGNT->[Act : Eat]-PTNT->[Animal : Lamb]

Here, AGNT and PTNT are relations.

It is important to note that relations need not be all upper-case. The only requirement is that they conform to the syntax for identifiers (or variables).


Further rules

Only dyadic relations are allowed

Prolog+CG only allows dyadic relations. This means that one will have to find other ways of representing relations like PAST, which are normally monadic.

This is a restriction in Prolog+CG that cannot be circumvented. This is a choice made by Dr. Adil Kabbaj when he implemented Prolog+CG, to support only dyadic relations.

Any identifier will do

Any identifier will do as a relation. Prolog+CG assigns no implicit or explicit meanings to any relations.

No relation hierarchy

There is no relation hierarchy behind any of the relations you may choose to employ, nor can you build one within the framework of Prolog+CG. This is not a critical restriction, however.

Next

Next, we look at variables in connection with relations.


Variables

Introduction

Prolog+CG also allows variables to function as relations.

Variables are names we give to values. The cool thing about variables is that their value can change. This makes variables really useful.

Example

Entity > Animal, Act.
Animal = Wolf, Lamb.
Act = Persuade, Eat.

Act([Animal : Wolf]<-AGNT-[Act : Persuade]-RCPT->[Animal : Lamb]).
Act([Animal : Wolf]<-AGNT-[Act : Eat]-PTNT->[Animal : Lamb]).

WolfDoesToLamb(A,R) :- 
          Act([Animal : Wolf]<-AGNT-[Act : A]-R->[Animal : Lamb]).

This program is available in the AAU directory as Aesop1.plgCG.

Explanation

First, we have the usual type-hierarchy and catalog of instances.

Then we have two facts called "Act" which specify two CGs.

Lastly, we have a rule called "WolfDoesToLamb". It "calls" the "Act" facts with a special CG as the actual parameter.

The CG has two variables, called "A" and "R". The "R" variable is in the place of a relation, whereas the "A" parameter is in the place of a referent.

When calling the "Act" facts, these two variables are "bound" to the corresponding values in the CGs in the "Act" facts.

Usage

If we run the following query:

?- WolfDoesToLamb(A,R).

the answer is:

{A = Persuade, R = RCPT}
{A = Eat, R = PTNT}

As we see, the variables have been bound to the correct referents and relations in each CG.

Next

Next, we have a summary.


Summary

Summary

Relations are written as either identifiers or variables with no parentheses.

Only dyadic relations are allowed.

Any identifier will do as a relation.

Any variable will also do as a relation.

There is no relation hierarchy behind the scenes.

Next

Next, we look briefly at arcs.


Arcs

There is not much to say about arcs in Prolog+CG. There are only two possiblities:

[C1]-R->[C2]

and

[C2]<-R-[C1]

both have the same interpretation: C1 has an R which is a C2. Or, equivalently, C2 is an R of C1.

Note that:

Next

Next, we look at concepts in detail.


Concepts

Introduction

There are really only two points to remember about concepts, the latter of which consists of three parts:

  1. Concepts are enclosed in [square brackets]
  2. Concepts consist of:
    1. A concept type,
    2. An optional concept referent, and
    3. An optional descriptor.

Since concepts consist of a concept type, an optional concept referent, and an optional concept descriptor, we will look at each of these in turn.


Concept types

Introduction

All concepts must have a concept type, and this concept type should generally be specified in the type hierarchy in the program. Otherwise, the concept type will have no place in the type hierarchy, and consequently the type will not be very useful.

A concept type can also be a variable, in which case the Prolog engine must be able to infer the type for it to be useful.

Example

Entity > Animal, Act, Persuasion.

Animal = Wolf, Lamb.
Act = Say.

SpeechAct([Animal : Wolf]<-AGNT-[Act : Say]-THME->[Persuasion]).

This example is available in the AAU directory as Aesop2.plgCG.

Explanation

First, there is a short type hierarchy in which the types "Entity", "Animal", "Act" and "Persuasion" are defined.

Then, we have a catalog of instances in which the Wolf and Lamb are declared to be instances of Animal. "Say" is also declared to be an instance of Act.

Then we have a fact which is called "SpeechAct" and which encloses a conceptual graph. The fact is there in case we need to refer to the CG in a rule somewhere else in the program.

The CG uses the three types "Animal", "Act", and "Persuasion".


Referents

Concept referents

Concept referents are separated from the concept type by a colon:

[Type : Referent]

Concept referents can be one of three things:

  1. Identifiers
  2. Strings
  3. Variables
  4. Multi-referents (such as '*2')

In the following, we describe these.


Identifiers and strings

Identifiers

Identifiers can be predefined as instances in instantiation rules (with =), but need not be.

For example, the instances "See", "Run", and "Sleep" can all be defined to be instances of the type "Act":

Act = See, Run, Sleep.

To use one of these, simply write them in a concept after the colon:

[Act: See]

Strings

A referent can also be a string:

[Act: Say]-THME->[Utterance: "Romeo, Romeo, wherefore art thou Romeo?"]


Variables

Introduction

A concept referent can be is a variable.

A variable is a name we give to a value. The value may change. This makes variables really useful.

Example

Entity > Animal, Fable.

Animal = Wolf, Lamb.
Fable = Fable1.

fab([Animal : Wolf]<-THME-[Fable : Fable1]).
fab([Animal : Lamb]<-THME-[Fable : Fable1]).

AnimalInFable(F,A) :- fab([Animal : A]<-THME-[Fable : F]).

This example is available in the AAU directory as as Aesop3.plgCG.

Explanation

First, we have the usual type-hierarchy and catalog of instances.

Then we have two facts called "fab" which specify two CGs.

Lastly, we have a rule called "AnimalInFable". It "calls" the "fab" facts with a special CG as the actual parameter.

The CG has two variables, called "A" and "F". When calling the "fab" facts, these two variables are "bound" to the corresponding values in the CGs in the "fab" facts.

Note how the CG in the rule has the same form as the CGs in the "fab" facts. This makes it possible for the Prolog+CG system to match the CGs.

Usage

If we ask the following query:

?- AnimalInFable(F,A).

The answer is:

{F = Fable1, A = Wolf}
{F = Fable1, A = Lamb}

As we can see, the variable "F" has been "bound" to the value "Fable1" in both "fab" facts. This corresponds with the actual CGs, where the referent of the "Fable" concepts is "Fable1" in both cases.

Likewise, the variable "A" has been bound to the value "Wolf" in one, and "Lamb" in the other result set. This also corresponds to the actual CGs.


Multi-referents

Introduction

The final thing that a concept referent can be is a multi-referent. Multi-referents are used to specify that two or more concepts are really the same concept.

Syntax

The syntax of a multi-referent is:

* DIGIT

for example, "*1" or "*2" ... up to "*9".

Meaning

When we write the same multi-referent in two spatially separate concepts, we are thereby indicating that this really is the same concept.

Example

Entity > Animal, Act.

Act = Say.

// An animal is talking to itself
SpeechAct([Animal : *1]<-AGNT-[Act : Say]-RCPT->[Animal : *1]).

This example is available in the AAU directory as Aesop4.plgCG.

Explanation

The SpeechAct fact says that an animal is talking to itself. The referent of both [Animal] concepts is the multi-referent *1, so the concept is really the same concept internally in the machine. Graphically, this would look as follows:

Note how this is different from coreference:

It is the former, not the latter, we are representing with multi-referents.


Concept descriptors

Introduction

Concept descriptors are used to associate data with a concept.

This data can be any type of Prolog+CG data, but most often, we use CGs as concept descriptors. This enables us to write nested graphs.

Syntax

Concept descriptors are separated from the concept type and concept referent by an equals sign:

[Type = Descriptor]

or

[Type : Referent = Descriptor]

Example

Entity > Proposition, Animal, Act.

Animal = Wolf, Lamb.
Act = Persuade.

prop([Proposition =
        [Animal : Wolf]<-AGNT-[Act : Persuade]-RCPT->[Animal : Lamb]
     ]).

This example is available in the AAU directory as Aesop5.plgCG.

Explanation

Here, the subgraph

[Animal : Wolf]<-AGNT-[Act : Persuade]-RCPT->[Animal : Lamb]

is the descriptor of the concept Proposition.

You will often use CGs as descriptors of concepts with types such as Proposition, Utterance, Cause, Effect, If, Then, etc.


Summary

Syntax

Concepts are enclosed in square brackets and follow one of these general schemas:

[Type]
[Type : Referent]
[Type = Descriptor]
[Type : Referent = Descriptor]

Types

The type can be any identifier, and should generally be included in the type hierarchy to be most useful. The type can also be a variable, in which case the Prolog system must be able to infer the type.

Referents

Referents can be either:

  1. Identifiers,
  2. Strings
  3. Variables, or
  4. Multi-referents.

Multi-referents look like this: "*1", "*2", ..., "*9" and are used to say that a concept is really the same as another concept even though it is placed somewhere else textually. Multi-referents are different from coreference links. (We will get back to coreferents later).

Concept descriptors

Concept descriptors associate data with a concept. They can be any kind of Prolog+CG data, but the datatype most often used is conceptual graphs.

Next

Next, we treat the problem of how to write graphs that extend over more than one textual line.


Multi-line graphs

Introduction

Prolog+CG has a simple yet sufficient mechanism for representing graphs that extend over multiple lines. On this page, we specify the syntax of this mechanism.

Hyphens, commas, and semicolons

In order to connect a concept with more than one relation, simply put a hyphen after the concept, then write each branch on a separate line with commas (',') to separate the branches. End the list with semicolon (';').

Example

For example:

Entity > Proposition, Act, Animal, Right.

Animal = Wolf, Lamb.
Act = Persuade, Eat.

// The Wolf persuades the Lamb that the Wolf has a right 
// to eat the lamb.
prop([Proposition =
       [Act : Persuade]-
          -AGNT->[Animal : Wolf],
          -RCPT->[Animal : Lamb],
          -THME->[Proposition =
                   [Animal : Wolf]-
                    -POSS->[Right = 
                             [Proposition =
                               [Animal : Wolf]<-AGNT-[Act : Eat]-
                                -PTNT->[Animal : Lamb]
                             ]
                           ]
                 ];
     ]).

This example is available in the AAU directory as Aesop6.plgCG.

This is a complicated example with nesting to several levels of depth. The important details to pick out right now are the way hyphens are used to indicate that the branches continue on subsequent lines, how they are separated with commas, and how the lists are ended with semicolon. Note also how the semicolon is optional if the list is at the end of the conceptual graph. Thus the only semicolon that exists in the above graph is also optional and could have been left out.

Summary

To have several relations be connected to the same concept, simply put a hyphen after the concept, place each relation on a separate line, place commas in between, and end the list with a semicolon. The semicolon is optional if the list is at the end of a conceptual graph.

Next

Next, we specify how to represent coreferents.


Coreferents

Introduction

In graphical conceptual graphs, we represent that two concepts refer to the same individual by placing a dotted line between the two concepts:

Coreferents as variables

In Prolog+CG, we do this a little differently. Instead of drawing a dotted line, we simply use the same variable name as the referent of both concepts. For example:

Entity > Animal, Act.

Act = Say.

// An animal is talking to itself.
SpeechAct([Animal : A]<-AGNT-[Act : Say]-RCPT->[Animal : A]).

This example is available in the AAU directory as Aesop7.plgCG.

This graph can be drawn as follows:

Note that this can be extended to any number of concepts being coreferent. Simply use the same variable as the referent of all concepts.

Note, however, that the general scoping rules, which are explained in Part III, must be followed so that the variable names actually refer to the same variable.

Summary

In order to represent coreference links, simply use the same variable as the referent of both concepts. More than two concepts can be involved if only variable scoping rules are obeyed so that the variable name used actually refers to the same variable.


CG primitives

Introduction

Prolog+CG offers some primitives which make it easier to write useful CG-programs. A primitive is a piece of program code which has been written, and so can be "called" or used easily.

We look at two kinds of primitives:

A goal is a part of a rule or query which must be satisfied for the rule or query to succeed.

The goals which we discuss in this chapter are all provided by Prolog+CG. You do not have to do anything special for them to be available.


CG goals

Introduction

In this section, we deal with the following CG goals

  1. branchOfCG
  2. concOfCG
  3. subsume
  4. generalize
  5. maximalJoin


branchOfCG

Introduction

A branch of a CG is two concepts connected by a relation. The two patterns available are:

[C1]-Rel->[C2]

and

[C2]<-Rel-[C1]

Signature

The signature of branchOfCG/2 is as follows:

branchOfCG(B,G)

where B is a branch (as described above) and G is a graph.

Operation

The branchOfCG/2 predicate is used for finding out whether a branch is part of a CG.

This is done using matching. This means that you can use variables in the branch.

The process only works at the outermost level of the graph G. That is, branchOfCG will not find branches that are nested inside concepts of G.

Example

//
// branchOfCG example
//
// Available in the AAU directory as branchOfCG.plgCG
//
// Ulrik Petersen
// Created: September 19, 2003
// Last update: September 19, 2003

// Type hierarchy
Entity > Animal, Act, Proposition.

// Catalog of instances
Act = Say.
Animal = Dolly.

// Dolly says to Dollay: "B-a-a-a-a-a"
graph(gr1, [Act : Say]-
                -AGNT->[Animal : Dolly],
                -RCPT->[Animal : Dolly],
                -THME->[Proposition = "B-a-a-a-a-a"]).

// List all branches
branch(B) :-
    graph(L, G),
    branchOfCG(B, G).

// Find the agent 
agent(A) :-
    graph(L, G),
    branchOfCG([Act]-AGNT->[Animal: A], G).

If we write the following query:

?- branch(B).

The answer is:

{B = [Act : Say]-AGNT->[Animal : Dolly]}
{B = [Act : Say]-RCPT->[Animal : Dolly]}
{B = [Act : Say]-THME->[Proposition = "B-a-a-a-a-a"]}

This is a list of all the branches in the graph.

If we now write the following query:

?- agent(A).

The answer is:

{A = Dolly}

This shows the fact that branchOfCG allows binding of variables to parts of the CG which match between the branch and the CG.

Summary

Thus branchOfCG/2 is used to find out whether a branch is part of a CG, and to retrieve parts of a branch into variables.


concOfCG

Introduction

The concOfCG/2 goal is used to identify concepts of CGs.

Signature

concOfCG(C,G)

Operation

It checks if the concept C is a concept of the CG G. This is done using matching. Thus you can also use a variable in place of C and get a list of all of the concepts in G.

Example

For example, consider the following query:

?- concOfCG(C, [Animal]<-AGNT-[Act: Say]).

It yields the following answers:

{C = [Animal]}
{C = [Act : Say]}

Explanation

This query looks for concepts (through the variable C) in the small graph "[Animal]<-AGNT-[Act: Say]".

The answer we get back corresponds to the two concepts in the graph.

Example 2

On the other hand, consider the following program:

// Type hierarchy
Entity > Act, Animal.

// Catalog of instances
Act = Say.

// Fact
cg([Animal]<-AGNT-[Act: Say]).

// Rule
cg_has_concept(C) :- cg(G), concOfCG(C,G).

Explanation

We have a very small type-hierarchy and a very small catalog of instances.

Then we have a fact called "cg" which specifies a CG.

Lastly, we have a rule which has two subgoals.

The first subgoal, "cg(G)", binds the value of the CG in the "cg" fact to the variable G.

The second subgoal, "concOfCG(C,G)", checks whether the concept in the varaible C is a concept in the CG in the variable G. Because we have just bound the variable G to the CG from the "cg" fact, this will check whether C is a concept in this CG.

Usage

If we now ask the query:

?- cg_has_concept([Animal]).

We get the following answer:

{}

This means yes.

Summary

Thus concOfCG/2 is used for finding out whether a specific concept is a concept in a graph.


subsume

Introduction

The "subsume" goal is used to check whether one CG is more general than another CG.

Signature

subsume(g1,g2)

Operation

The subsume goal checks whether the CG g1 is more general than the CG g2.

Here are ways to generalize a graph:

Example

// Type-hierarchy
Entity > Animal, Act.
Animal > Carnivore, Herbivore.
Act > Eat, Persuade.

// Catalog of instances
Carnivore = Wolf, Fox.
Herbivore = Lamb, Chicken.

// Graph facts
gr(graph1, [Carnivore: Wolf]<-AGNT-[Eat]-PTNT->[Herbivore: Lamb]).
gr(graph2, [Carnivore: Fox]<-AGNT-[Persuade]-PTNT->[Herbivore: Chicken]).

// Rules
CarnivoreEatsAnimal(L) :- gr(L, G), 
                          subsume([Carnivore]<-AGNT-[Eat]-PTNT->[Animal], G).
AnimalActsOnAnimal(L) :- gr(L, G), 
                         subsume([Animal]<-AGNT-[Act]-PTNT->[Animal], G).
AnimalPersuades(L) :- gr(L, G), 
                      subsume([Animal]<-AGNT-[Persuade], G).

Explanation

First, we have the usual type-hierarchy and catalog of instances.

Then we have two facts called "gr" which specify two CGs. The CGs are given the names "graph1" and "graph2".

Lastly, we have three rules. They all take a formal parameter called "L" (for "label"). The first thing they then do is to call the "gr" facts to get the label and the graph of each "gr" fact. Then they use the "subsume" goal to check something.

In the following, we describe each of the rules in turn.

CarnivoreEatsAnimal

The CarnivoreEatsAnimal rule finds those graphs in which a carnivore eats an animal.

We repeat it here:

CarnivoreEatsAnimal(L) :- gr(L, G), 
                          subsume([Carnivore]<-AGNT-[Eat]-PTNT->[Animal], G).

If we ask the following query:

?- CarnivoreEatsAnimal(L).

we get the following answer:

{L = graph1}

This is because the only graph which subsumes the graph in CarnivoreEatsAnimal is graph1.

AnimalActsOnAnimal

The AnimalActsOnAnimal rule looks for a more general graph.

AnimalActsOnAnimal(L) :- gr(L, G), 
                         subsume([Animal]<-AGNT-[Act]-PTNT->[Animal], G).

Here, the graphs in the "gr" facts are checked for subsumption with a graph that just says than an animal is an agent of an act which has a patient which is an animal.

This is more general than both of the graphs in the example, because:

If we ask the following query:

?- AnimalActsOnAnimal(L).

we get the following answer:

{L = graph1}
{L = graph2}

This reflects the facts that the graph in the rule is a generalization of both graphs.

AnimalPersuades

The AnimalPersuades rule finds graphs in which an animal is the agent of persuade.

AnimalPersuades(L) :- gr(L, G), 
                      subsume([Animal]<-AGNT-[Persuade], G).

This finds only graph2:

?- AnimalPersuades(L).
 
{L = graph2}

The graph in the rule is a generalization of graph2 because:

Summary

Thus the subsume goal checks whether a graph g1 is a generalization of graph g2. Generalizations arise through three procedures, namely subgraphing, replacement of types by a supertype, and erasure of referents.


generalize

Introduction

The generalize/3 goal is used to find the generalization of two graphs.

We have already described how a graph can be generalized. The generalize/3 goal find the largest graph which is a minimal generalization of the two input graphs. We will explain what this means below.

Signature

The signature of generalize/3 is as follows:

generalize(g1,g2,g3)

where g1,g2,g3 are graphs.

Operation

The generalize/3 goal is used for finding out what the largest minimal generalization of the two graphs g1 and g2 is. The result is returned in g3.

Thus the generalize/3 goal climbs upwards in the type-hierarchy, finding a common subgraph of g1 and g2 which has type-labels which are as low down in the type-hierarchy as possible while still being a generalization.

The result is the largest generalization possible because as much as possible of both graphs are taken into account.

The result is a minimal generalization because the algorithm only crawls as high up in the type-hierarchy as needed to find the minimum common supertype.

Example

//
// generalize/3 example
//
// Available in the AAU directory as generalize.plgCG
//
// Ulrik Petersen
// Created: September 20, 2003
// Last update: September 20, 2003
//

// type-hierarchy
Entity > Physical, Abstract.
Abstract > Property.
Property > Color, Manner.
Manner > Fast.
Physical > Process, Object.
Process > Act.
Act > Drive, Sell.
Object > Vehicle, Person.
Vehicle > Truck, Car.
Car > Porsche.
Person > Man, Woman.

// Catalog of instances
Woman = Elizabeth, Charlotte.
Man = Frank, Joe.
Color = Red, Blue.

// Graphs

// Frank drives a blue car.
graph(Frank, [Drive]-
         -AGNT->[Man: Frank],
         -PTNT->[Car],
         -CHRC->[Color: Blue]).

// Elizabeth drives a red truck fast.
graph(Elizabeth, [Drive]-
         -AGNT->[Woman: Elizabeth],
         -PTNT->[Truck],
         -MANR->[Fast],
         -CHRC->[Color: Red]).

// Joe sells a red Porsche to Charlotte.
graph(Joe, [Sell]-
        -AGNT->[Man: Joe],
        -PTNT->[Porsche],
        -CHRC->[Color: Red],
        -RCPT->[Woman: Charlotte]).

General(L1, L2, g3) :-
        graph(L1, g1),
        graph(L2, g2),
        generalize(g1, g2, g3).

Elizabeth and Joe

If we write the following query:

?-General(Elizabeth, Joe, g3).

The answer is:

{g3 = [Act] -
            -AGNT->[Person],
            -PTNT->[Vehicle],
            -CHRC->[Color : Red]}

Note how:

Frank and Elizabeth

If we now write the following query:

?- General(Frank, Elizabeth, g3).

The answer is:

{g3 = [Drive] -
              -AGNT->[Person],
              -PTNT->[Vehicle],
              -CHRC->[Color]}

Note how:

Frank and Joe

If we now write the following query:

?-General(Frank, Joe, g3).

The answer is:

{g3 = [Act] -
            -AGNT->[Man],
            -PTNT->[Car],
            -CHRC->[Color]}

Note how:

Summary

Thus generalize/3 is used to find the largest possible minimal generalization of two graphs.


maximalJoin

Introduction

The maximalJoin/3 goal is used to find the maximal join of two graphs.

Signature

The signature of maximalJoin/3 is as follows:

maximalJoin(g1,g2,g3)

where g1,g2,g3 are graphs.

Operation

The maximalJoin/3 goal is used for finding out what the largest maximal joinof the two graphs g1 and g2 is. The result is returned in g3.

A maximal join is sort of the opposite of a generalization.

Instead of finding what is common to both graphs, and taking everything away that is not common, maximalJoin joins two graphs on every possible connection point, thus producing a graph which is larger than either graph.

Instead of going upwards in the type-hierarchy to find the minimum common supertype of two matching concepts, maximalJoin looks downwards in the type-hierarchy to find the maximal common subtype of both concepts.

Example

//
// maximalJoin example
//
// Available in the AAU directory as maximalJoin.plgCG
//
// Ulrik Petersen
// Created: September 20, 2003
// Last update: September 20, 2003
//

// Type hierarchy
Entity > Physical, Abstract.
Abstract > Proposition, Property.
Property > Manner, Attribute.
Manner > Indignantly.
Attribute > Beautiful, Evil, Ugly, New, Scandalous.
Physical > Object, Process.
Process > Act.
Act > Buy, Say.
Object > Person, Artefact.
Arteface > Dress.
Person > Man, Woman, Married.
Man > Husband.
Woman > Wife.
Married > Husband, Wife.

// Catalog of instances
Woman = Sue, Gill.
Man = Mark.

// Graphs

// Sue says indignantly to Mark: "Gill bought a new, scandalous dress".
graph(graph1, [Say]-
        -AGNT->[Woman: Sue],
        -RCPT->[Man: Mark],
        -MANR->[Indignantly],
        -THME->[Proposition =
             [Buy]-
                -AGNT->[Woman: Gill],
                -THME->[Dress]-
                      -ATTR->[New],
                      -ATTR->[Scandalous]
                 ]).

// Sue is a beautiful married person, 
// and she has a husband whose name is Mark.
graph(graph2, [Married: Sue]-
                -POSS->[Husband : Mark],
                -ATTR->[Beautiful]).

// Sue says to the married person Mark: "Gill is an ugly, evil woman".
graph(graph3, [Say]-
          -AGNT->[Woman: Sue],
          -RCPT->[Married: Mark],
          -THME->[Proposition =
                [Woman: Gill]-
                   -ATTR->[Ugly],
                   -ATTR->[Evil]
                ]).

// Rule

join(L1, L2, g3) :-
     graph(L1, g1),
     graph(L2, g2),
     maximalJoin(g1, g2, g3).

graph2 and graph3

If we write the following query:

?- join(graph2, graph3, g3).

The answer is:

{g3 = [Say] -
            -AGNT->[Wife : Sue] -
                                -POSS->[Husband : Mark],
                                -ATTR->[Beautiful];,
            -RCPT->[Married : Mark],
            -THME->[Proposition = [Woman : Gill] -
                                                 -ATTR->[Ugly],
                                                 -ATTR->[Evil]]}

Note how:

graph1 and graph2

If we now write the following query:

?- join(graph1, graph2, g3).

The answer is:

{g3 = [Say] -
            -AGNT->[Wife : Sue] -
                                -POSS->[Husband : Mark],
                                -ATTR->[Beautiful];,
            -RCPT->[Man : Mark],
            -MANR->[Indignantly],
            -THME->[Proposition = [Buy] -
                                        -AGNT->[Woman : Gill],
                                        -THME->[Dress] -
                                                       -ATTR->[New],
                                                       -ATTR->[Scandalous];]}

This is basically the same operation as the previous one.

graph1 and graph3

If we now write the following query:

?-join(graph1, graph3, g3).

The answer is:

{g3 = [Say] -
            -AGNT->[Woman : Sue],
            -RCPT->[Husband : Mark],
            -THME->[Proposition = [Buy] -
                                        -AGNT->[Woman : Gill] -
                                                              -ATTR->[Ugly],
                                                              -ATTR->[Evil];,
                                        -THME->[Dress] -
                                                       -ATTR->[New],
                                                       -ATTR->[Scandalous];],
            -MANR->[Indignantly]}

Note how:

Summary

Thus maximalJoin/3 is used to find the maximal join of two graphs.

A maximal join takes as much from both graphs as possible, joining on at least one concept, using the maximum common subtype of two concept types where possible.


Type goals

Introduction

In this section, we deal with the following goals relating to types and instances:

  1. isSubType
  2. isSuperType
  3. isInstance
  4. superTypes
  5. immediateSubTypes
  6. maxComSubType
  7. minComSuperType


isSubType

Introduction

The isSubType goal is used to check whether one type is a subtype of another.

Signature

isSubType(T1,T2)

Operation

This goal checks whether T1 is a subtype of T2.

Example

// Type hierarchy
Entity > Animate, Inanimate.
Animate > Animal, Human.
Inanimate > Table, Chair, BeerMug.

// Rules
is_animate(T) :- isSubType(T, Animate).
is_inanimate(T) :- isSubType(T, Inanimate).

This is available in the AAU directory as isSubType.plgCG.

Explanation

First, we have the usual type-hierarchy.

Then we have two rules called "is_animate" and "is_inanimate". They both take one formal parameter called "T". The body of the rule then checks whether T is a subtype of "Animate" or "Inanimate" respectively.

Usage

If we ask the following query:

?- is_animate(Human).

we get the following answer:

{}

This means yes. This is because in the type-hierarchy, Human is is a subtype of Animate.

On the other hand, if we ask

?-is_animate(Table).

we get the following answer:

 no.

This is because in the type-hierarchy, Table is not a subtype of Animate.

Summary

Thus the isSubType goal is used to check whether one type is a subtype of another type.


isSuperType

Introduction

The isSubType goal is used to check whether one type is a supertype of another.

Signature

isSuperType(T1,T2)

Operation

This goal checks whether T1 is a supertype of T2.

This is analogous to isSubType, it just looks upwards instead of downwards in the type-hierarchy.


isInstance

Introduction

The isInstance goal is used to check whether a referent is an instance of a given type.

Signature

isInstance(I,T)

Operation

This goal checks whether I is an instance of the type T.

I must be either an identifier or a string.

Example

// Type hierarchy
Entity > Philosopher.

// Catalog of instances
Philosopher = Peirce, Whitehead, Heraclitus.

// Rule
is_philosopher(I) :- isInstance(I, Philosopher).

Explanation

First, we have the usual type-hierarchy and catalog of instances.

The type hierarchy is very simple, it only has two types, with Philosopher being the only subtype of Entity.

Then the catalog of instances specifies three instances of Philosopher, namely Peirce, Whitehead, and Heraclitus.

Then, we have a rule called "is_philosopher". It takes the formal parameter I, which the body of the rule then passes to isInstance. The isInstance goal checks whether I is an instance of the type Philosopher.

Usage

If we ask the following query:

?- is_philosopher(Peirce).

we get the following answer:

{}

This means yes. This is because in the catalog of instances, Peirce is an instance of the type Philosopher.

If we ask the following query:

?- is_philosopher(Petersen).

we get the following answer:

 no.

This is because Petersen is not an instance of Philosopher in the catalog of instances.

Summary

Thus the isInstance goal is used to check whether an identifier or a string is an instance of a given type.


superTypes

Introduction

The superTypes goal is used to get a list of the supertypes of a given type.

Signature

superTypes(T,L)

Operation

This goal returns, in the list L, all the supertypes of the type T.

Example

// Type hierarchy
Entity > Physical, Abstract.
Physical > Animate, Inanimate.
Animate > Animal, Human.
Human > Man, Woman.
Abstract > Point, Line, Circle.

This example is available in the AAU directory as superTypes.plgCG.

Explanation

This example only has a somewhat elaborate type-hierarchy.

Usage

If we ask the following query:

?-superTypes(Woman, L).

we get the following answer:

{L = (Human, Animate, Physical, Entity)}

This is precisely the list of all supertypes of the type Woman.

Similarly, if we ask the following query:

?- superTypes(Circle, L).

we get the following answer:

{L = (Abstract, Entity)}

This is also the list of all supertypes of the type Circle.

Summary

Thus the superTypes goal returns a list of all of the supertypes of a given type.


immediateSubTypes

Introduction

The immediateSubTypes goal is used to get a list of the immediate subtypes of a given type.

Signature

immediateSubTypes(T,L)

Operation

This goal returns, in the list L, all the immediate subtypes of the type T.

Example

// Type hierarchy
Entity > Physical, Abstract.
Abstract > Point, Line, Circle.

This example is available in the AAU directory as immediateSubTypes.plgCG.

Explanation

This example only has a very simple type-hierarchy.

Usage

If we ask the following query:

?- immediateSubTypes(Entity, L).

we get the following answer:

{L = (Physical, Abstract)}

This is precisely the list of all immediate subtypes of the type Entity.

Similarly, if we ask the following query:

?-immediateSubTypes(Abstract, L).

we get the following answer:

{L = (Point, Line, Circle)}

This is also the list of all immediate subtypes of the type Abstract.

Summary

Thus the immediateSubTypes goal returns a list of all of the immediate subtypes of a given type.


maxComSubType

Introduction

The maxComSubType goal is used to find the maximum common subtype of two types.

Signature

maxComSubType(Type1,Type2,T)

Operation

This goal returns, in the variable T, the maximum common subtype of Type1 and Type2.

If Type1 and Type2 have no explicit maximum common subtype, then the built-in type "Absurd" is returned.

Example

// Type hierarchy
Entity > Male, Female, Adult.
Adult > Man, Woman.
Male > Man.
Female > Woman.

This example is available in the AAU directory as maxComSubType.plgCG.

Explanation

This example only has a very simple type-hierarchy.

Usage

If we ask the following query:

?- maxComSubType(Female, Adult, T).

we get the following answer:

{T = Woman}

This is precisely the maximum common subtype of Female and Adult.

Similarly, if we ask the following query:

?-maxComSubType(Male, Adult, T).

we get the following answer:

{T = Man}

This is also the maximum common subtype of Male and Adult.

Summary

Thus the maxComSubType goal finds the maximum common subtype of two types.


minComSuperType

Introduction

The minComSuperType goal is used to find the minimum common supertype of two types.

Signature

minComSuperType(Type1,Type2,T)

Operation

This goal returns, in the variable T, the minimum common supertype of Type1 and Type2.

If Type1 and Type2 have no explicit minimum common supertype, then the built-in type "Universal" is returned.

Example

// Type hierarchy
Entity > Animal.
Animal > Mammal, Bird.
Mammal > Elephant, Cat.

This example is available in the AAU directory as minComSuperType.plgCG.

Explanation

This example only has a very simple type-hierarchy.

Usage

If we ask the following query:

?-minComSuperType(Mammal, Bird, T).

we get the following answer:

{T = Animal}

This is because the minimum common supertype of Mammal and Bird is Animal.

If we now ask the following query:

?-minComSuperType(Mammal, Cat, T).

we get the following answer:

{T = Mammal}

This is because Mammal is a supertype of Cat, but Mammal is also a supertype of itself. This is because any type is a supertype of itself. Thus Mammal is the minimum common supertype of Cat and Mammal.

Summary

Thus the minComSuperType goal finds the minimum common supertype of two types.


Prolog for CG users

In this chapter, we briefly introduce key concepts from Prolog.

This is done with those people in mind who do not wish to become full-fledged Prolog programmers, but who simply want to use Prolog+CG to formalize texts.


Atoms, Strings, and Numbers

Introduction

Prolog+CG has three kinds of constants. A constant is a value which does not change.

Atoms

An atom is simply an identifier. For example, the following are all atoms:

When writing CGs, atoms are used for concept types and concept type instances.

Strings

A string is a sequence of characters which is "enclosed in double quotes". For example:

When writing CGs, strings can be used as referents of concepts.

For example:

// Type hiearchy
Entity > Outcry.

// Graph fact
gr([Outcry : "Ouch!"]).

Numbers

A number in Prolog+CG is either an integer or a real (decimal point) number.

For example:

When writing CGs, numbers can be used as concept descriptors of concepts.

For example:

// Type hierarchy
Entity > Number.

// Catalog of instances
Number = Pi. 

// Graph fact
gr([Number : Pi = 3.141592]).

This example is available in the AAU directory as pi.plgCG.


Structures, relationships and terms

Introduction

A structure is a way of expressing a relationship among entities. For example:

gr(graph1, [Cat]).

Here, the structure "gr" expresses the fact that there is a relationship between the atom "graph1" and the CG "[Cat]".

What is a structure?

A structure has the following syntax:

  1. It starts with an identifier,
  2. followed by an opening parenthesis, "("
  3. followed by a comma-separated list of terms
  4. and ends with a closing parenthesis, ")".

Terms

The "terms" in the comma-separaed list between the parentheses can be any of the following:

Thus "term" is the name we give to any kind of data in Prolog+CG.

Writing CGs

When writing CGs, you most often use structures to contain graphs. For example:

// Type hierarchy
Entity > Animal, Act.
Animal > Wolf, Lamb.

// Catalog of instances
Act = Hunt, Graze.

// Graph facts
gr(graph1, [Wolf]<-AGNT-[Act: Hunt]).
gr(graph2, [Lamb]<-AGNT-[Act: Graze]).

Here, the structure "gr" is used twice to write graphs and associate them with an atom ("graph1" or "graph2").

Further rules

Summary

Thus structures can be used to represent arbitrary relationships between terms. This is done by means of specific syntax, including an identifier, an opening parenthesis, a comma-separated list of terms, and a closing parenthesis. The comma-separated list of terms can be any length, including 1.

"Term" is the name we give to any kind of data in Prolog+CG. This includes all of the kinds listed above.


Variables

What is a variable?

A variable is a piece of the computer's memory which can hold a value, and which we have given a name.

For example, the variable L might have the value Romeo, which is an atom.

The variable G1 might have the value [Cat]-ON->[Mat], which is a CG.

These are just examples.

Bound and free variables

A variable's value can change as the program runs. This is known as binding the variable to different values.

A variable that is bound is a variable that has a value.

A variable is is free is a variable that does not have a value.

Variable syntax

Variables have to follow a number of rules.

Rules

A variable:

Examples of variables

So for example, the following are all variables:

Anti-examples

The following are not variables:

Thus variables have a specific syntax, which follows three simple rules.

Writing CGs

When writing CGs, you can use variables as almost any part of a CG. This includes:

Example

We have already seen many examples of variables being used in writing CGs.

Here is one more:

// Type hierarchy
Entity > Animal, Act.
Animal > Cat, Dog.

// Catalog of instances
Act = Talk, Bark, Kick.
Cat = Garfield.
Dog = Odie.

// "A cat is talking to itself."
// Note how the same variable, "C" is used as the referent of
// both Cat concepts.  This means that they are coreferents.
gr(graph1, [Cat: C]<-AGNT-[Act: Talk]-RCPT->[Cat: C]).

// "Odie is barking at Garfield".
gr(graph2, [Dog: Odie]<-AGNT-[Act: Bark]-RCPT->[Cat: Garfield]).

// "Garfield is kicking Odie"
gr(graph3, [Cat: Garfield]<-AGNT-[Act: Kick]-PTNT->[Dog: Odie]).

// Rule: Animal A1 acts on Animal A2 with relation R
acts_on(A1, R, A2, L) :- gr(L, G), subsume([Animal: A1]<-AGNT-[Act]-R->[Animal: A2], G).

Usage

If we now ask the following query:

?- acts_on(Garfield, PTNT, Odie, L).

we get the following answer:

{L = graph3}

This is because in graph3, Garfield acts on Odie with the relation PTNT.

Similarly, if we ask the following query:

?- acts_on(Odie, RCPT, Garfield, L).

we get the following answer:

{L = graph2}

This is because in graph2, Odie acts on Garfield with the relation RCPT.

Summary

Thus variables are pieces of the computer's memory which can hold values, and which we have given a name.

Variables can be free or bound. A free variable does not have a value, whereas a bound variable does.

Variables must follow three simply syntax rules, or they are not variables.

You can use variables to represent almost any part of a CG.


Facts

Introduction

A fact expresses something static, e.g., a graph or a structure.

A rule expresses something dynamic, i.e., something that can be computed.

Facts

Syntax

A consists of a term followed by a period:

term.

The term can be any kind of term, except a variable or a number.

Examples

Consider the following facts:

// A structure
graph(graph1, [Cat]).
graph(graph2, [Dog]).

// A string
"It is raining.".

// An identifier
AlfredWasWise.

Structures are the most useful kind of terms to be used for facts.


Rules, Goals and Subgoals

Introduction

A rule expresses something dynamic, i.e., something that can be computed.

This contrasts with facts, which are static.

Rules

Syntax

The syntax of a rule consist of three things: a head, an entails-symbol (":-"), a body, and a period (".").

Simply put:

head :- body.

Head

The head can be any kind of term except variables, lists, and numbers.

In particular, a head can be a structure, which is what you will use most often.

Body

The body consists of a comma-separated list of subgoals. To explain what a subgoal is, we must first explain what a goal is.

Goal

A goal is something that Prolog+CG can seek to satisfy. That is, it tries to prove that the goal is true.

We have already met goals in the form of queries. For example:

?- is_philosopher(Peirce).

Here, "is_philosopher(Peirce)" is a goal which Prolog+CG must prove or satisfy in order for the query to succeed.

Subgoal

A subgoal is a goal in a rule or query. There can be more than one subgoal in a query or the body of a rule.

For example:

CarnivoreEatsAnimal(L) :- gr(L, G), 
                          subsume([Carnivore]<-AGNT-[Eat]-PTNT->[Animal], G).

Here, the body of the rule consists of two subgoals:

Satisfying rules

The head of the rule can be "satisfied" or "proved" if the body of the rule can be "satisfied" or proved.

The body of the rule can be "satisfied" or "proved" if all of its subgoals can be "satisfied" or proved. This is done in the order in which they are listed.

Summary

Thus a rule consists of a head, an "entails" symbol, a body, and a period.

The head can be proved if the body can be proved. The body can be proved if all its subgoals can be proved, in the order in which they are listed.

A subgoal is a goal in a rule or query. A goal is something that Prolog+CG will seek to satisfy or prove.


Clauses and predicates

Clauses

A fact is a clause, and a rule is a clause. This can be expressed as in the following type-hierarchy:

Thus "clause" is the general name we give to rules and facts collectively.

Predicates

Recall that clauses are either facts or rules.

Facts can be a number of things, including structures and atoms, and so can the heads of rules.

If more than one fact consists of the same structure or atom, they are collectively called a predicate.

Similarly, if more than one rule have heads that are the same atom or structure, they are collectively called a predicate.

Example

// Type hierarchy
Animal > Dog, Cat.

// A predicate of facts
graph(graph1, [Cat]).
graph(graph2, [Dog]).

// A predicate of rules
animal_is_in_graph(L) :- graph(L, G), concOfCG([Dog], G).
animal_is_in_graph(L) :- graph(L, G), concOfCG([Cat], G).

Note how the "animal_is_in_graph" predicate could have been reduced to one rule by taking advantage of the type hierarchy:

animal_is_in_graph(L) :- graph(L, G), concOfCG([Animal], G).

Summary

Thus a clause is either a rule or a fact. A predicate is a collection of facts which are the same structure or atom, or a collection of rules which have the same structure or atom in their heads.


Matching

Introduction

Matching is an important process used while satisfying (sub)goals of rules and queries.

'Matching' refers to the process of comparing terms of (sub)goals with each other, and in the process making variable bindings.

Explanation

When trying to satisfy a (sub)goal of a rule or query, Prolog+CG attems to match the (sub)goal with either:

This is done using all the facts and rule-heads of the program, from the top of the program to the bottom.

There are certain rules when matching:

  1. An atom must be identical to the other atom for them to match.
  2. A structure such as

    graph(cg1, [Animal])
    matches another structure if and only if:

    1. the names of the structure are the same (here, 'graph'), and
    2. the two structures have the same number of terms in their lists of terms, and
    3. each of the terms in the lists match, in the order in which they appear (from left to right).
  3. when matching a variable with a term:

    1. if the variable is bound already, the value of the variable must match the term.
    2. if the variable is free, the matching succeeds, and the value of the variable becomes whatever the term was.

Examples

It is easiest to explain how matching works by using a small example.

Consider the following Prolog+CG program:

// Type-hierarchy
Animate > Animal, Human.

// Graph facts
graph(gr1, [Animal]).
graph(gr2, [Human]).

// Rule
gr(X,Y) :- graph(X,Y).

When asking the following query:

?- gr(X,Y).

the answer is:

{X = gr1, Y = [Animal]}
{X = gr2, Y = [Human]}

This is because:


Queries

Introduction

Queries are just like the body of a rule:

Queries are written in the Prolog+CG user interface, in the lower part of the main window.

Answers

A query always gives an answer. This can be:

  1. no.
    meaning that the query did not succeed.
  2. {}
    meaning "yes", or that the query did succeed and that there were no variable bindings.
  3. A set of variable bindings, meaning that the query succeeded with the given variable bindings. For example:

    {X = gr1, Y = [Animal]}
    {X = gr2, Y = [Human]}
    


Lists

Introduction

Example

For example, the the superTypes primitive returns a list of supertypes.

Consider the following type-hierarchy:

// Type hierarchy
Entity > Physical, Abstract.
Physical > Animate, Inanimate.
Animate > Animal, Human.
Human > Man, Woman.
Abstract > Point, Line, Circle.

If we now ask the following query:

?-superTypes(Woman, L).

we get the following answer:

{L = (Human, Animate, Physical, Entity)}

Summary

Thus a list is a sequence of one or more Prolog+CG data values, separated by commas and surrounded by parentheses.


Formalizing texts

In this chapter, we discuss some problems related to formal representations of texts. We demonstrate how a text can be formalized and turned into a knowledge base in Prolog+CG. We also give some additional examples.

Formalization can be viewed as a process and as a product.

Here, the product will be a knowledge base, containing a rich semantic representation of a domain. The knowledge base must be constructed in such a way that the semantics of all relevant elements in the domain are accounted for, and it must be constructed for in such a way that it becomes possible to reason over the knowledge base in a suitable manner.

In the preceding paragraph, the words "relevant" and "suitable" point to the fact that every formal representation is indeed an interpretation governed by the perspective of those who construct the knowledge base. It reflects the need to think about formalization not only as a product, but as an ongoing process as well.

In any process of formalization, the domain must be carefully observed, and the purpose of having a knowledge base as well as the perspective of those who will eventually use the knowledge base must be taken into account.

Consider a simple question: what is the ontological status of a human being? Which one of the following descriptions is the more correct?

a)
universal > animate > animal  > mammal > human_being.
b)
universal > animate > animal, human_being.

Solution a) might be suitable for representing biological facts, whereas solution b) enables us to make a clear distinction between man and beast, which is a useful distinction e.g. in analyzing narratives. The point is that the "better" representation is the one that reflects not only the domain in question but also the intended use of the knowledge base.

Prolog+CG enables us to combine two kinds of reasoning with a knowledge base:

In formalizing a text -- more generally speaking: a domain -- both of these options should be kept in mind.

While working to build the knowledge base, you are likely to experience the need to iteratively work on the hierarchy and on the graphs. Often a representation of a new sentence gives rise to rethink the structure of (parts of) the type hierarchy -- and vise versa.

To avoid this process to become too chaotic, we recommend that you pay careful attention to the construction of the top of the hierarchy, while thinking about the following questions:


Note: This introduction and the next section were written by Henrik Schärfe. He is responsible for the lucidity, not me.
Ulrik Petersen


Nuts and bolts

The following pages

In the following pages we will demonstrate how (a small part of) a text can be represented in Prolog+CG. Through an example, we demonstrate:

The example of Macbeth

In the following, we will represent a few sentences and expressions from the play "Macbeth" by William Shakespeare.

Consider the following quotes:

Macbeth: "Is that a dagger which I see before me?" (2.1.31)
Macbeth: "I'll fight, till from my bones my flesh be hacked." (5.3.34)

These examples are available as macbeth.plgCG and macbeth2.plgCG in the AAU directory.

Next

Next, we describe how to organize the knowledge base.


Organizing the knowledge base

In Prolog+CG a knowledge base consists of:

We recommend that you place the ontology at the top of the document, and divide it into two sections: a hierarchy of types and a catalogue of individuals.

It is often useful to partition the body of graphs in parts that allow you to search through a selected part of the graphs. In this way it is also possible to compose queries consisting of expressions from different parts of the knowledge base.


Organizing the graphs

Introduction

One simple way to organize your graphs is by including every graph in a structure, pairing each graph with an identifier.

Schema

Use facts of the following schema to organize graphs:

graph(graph-name, Graph)

For example:

graph(gr1, [Animal])

The graph-name should be an identifier.

In the literature, the normal way to refer to a specific place in a play is to refer to act, scene, and line. The graphs of the Macbeth knowledge base could be partitioned accordingly:

 Gr(act_x, scene_y, line_z, [graph]).

This would enable us to let a query report the exact location of a quote. For the present purposes, however, we shall only refer to the act number:

 Gr(act_x, [graph]).


Writing the graphs

Consider again the following quotes:

Macbeth: "Is that a dagger which I see before me? (2.1.31)
Macbeth: "I'll fight, till from my bones my flesh be hacked." (5.3.34)

Both quotes are utterances, and we use a template to represent the utterance as an act that has a person as agent and a proposition as theme, e.g:

 gr(act2, [act: ask]-
            -agnt->[person: Macbeth],
            -thme->[proposition = "Is that a dagger which I see before me?"]).

Here, the content of the proposition (the referent) is written as a string, but we can also represent the content as an embedded graph:

 gr(act2,
  [act: ask]-
	-agnt->[person: Macbeth],
	-thme->[proposition = 
		[act: see]-
			-agnt->[person: pn_I]
			-obj->[object: *x]-
				-bfore->[person: pn_me],
				-type->[dagger]]).

 gr(act5,
  [act: say]-
    -agnt->[person: Macbeth],
    -thme->[proposition = 
	[act: will_fight]-
	   -agnt->[person: pn_I],
	   -until->[state =
		      [hacked]-
			-ptnt->[flesh]<-poss-[person: pn_my],
			-from->[bone: {}]<-poss-[person: pn_my]]]).

Next

Next, we will build an ontology, consisting of a type hierarchy and a catalog of individuals.


The ontology

Introduction

Although the text is fairly short it contains a variety of words, each of which requires some consideration. Among the interesting problems in this text are:

The ambiguous word "before"

"Before" can be a temporal relation (I will finish eating before you do), but in this text it is a spatial relation. Prolog+CG does not require an explicit hierarchy of relation types, but it should be noted that the semantics of the domain is represented using an implicit hierarchy of such relations. The same goes for "until" and "from".

The use of pronouns

In this representation we have chosen to represent the text in a fairly verbatim manner, including the use of personal pronouns. In order to do this, a category [pronoun] has been added as a subtype of the category [person].

The result

The result may look like this:

// Type hierarchy
universal > object, process, proposition.
object > person, artifact.
person > pronoun.
artifact > weapon.
weapon > dagger.
process > act, state.

// Catalogue of individuals
act = ask, say.
person = Macbeth.
pronoun = pr_I, pr_me.

The basic premise

The basic premise behind this kind of formalization is that a lot of the semantic information in a conceptual graph can be found in the type-hierarchy.

The premise is that the type-hierarchy explicates distinction which are relevant to the purposes and intentions of the formalizing agent (you, for example), and that the type-hierarchy says significant things about the formalized domain, and how it is conceptualized or categorized.

Big questions lurk just beneath the surface here! You may find it useful to consider some of the philosophical issues at work, e.g. the debate between the realists and the conceptualists about universals vs. concepts.

This premise presupposes that care has been taken in constructing the type-hierarchy.


Predicates

Introduction

In addition to the ontology and the graphs, a knowledge base often contains a number of predicates, suggesting how the knowledge base might be used.

Built-in goals

The built-in goals of Prolog+CG provide for a variety of ways in which knowledge can be extracted from a knowledge base.

Examples

You can open the macbeth.plgCG program from the AAU directory and run the following predicates to see how they work:

Lists branches of all graphs:

branches(B):-
gr(L,G),
branchOfCG(B,G).

Lists all concepts from the outer context:

concepts(C):-
gr(L,G),
concOfCG(C,G).

Lists all concepts from graphs embedded as the referent of propositions.

conceptsProp(C):-
gr(L,G),
subsume([proposition],G),
branchOfCG([proposition = P], G),
concOfCG(C, P).

Combining the two previous goals:

AllConcepts(C):-
concepts(C).
AllConcepts(C):-
conceptsProp(C).

Subsuming graphs in which a person is the agent of some action:

action(G):-
gr(L,G),
subsume([act]-agnt->[person],G).

Resolving the referents of a graph containing an action:

actor(a,b):-
gr(L,G),
subsume([act]-agnt->[person],G),
branchOfCG([act:a]-agnt->[person: b],G).


Adding knowledge

Introduction

So far we have been concerned with extracting knowledge that already exists in the graphs by manipulating them in various ways. But Prolog+CG also allows us to combine knowledge from different graphs, whereby new information may be reached.

In the following, consider the program macbeth2.plgCG in the AAU directory, which contains some minor additions to the original:

the following has been added to the type hierarchy:

person > man, pronoun, royal, thane.
man > king.
royal > king.

some comments have been added to the collection of graphs:

com(act2, [man: Macbeth]).
com(act5, [royal: Macbeth]).

The comments basically say that in act 2 Macbeth is considered a man, and in act 5 he is considered to be royal.

Finally, the first graph is refined just a little to include the fact that in act 2 Macbeth is a thane, and in act 5 he is a king:

 gr(act2,
  [act: ask]-
	-agnt->[thane: Macbeth]
   (...)

 gr(act5,
  [act: ask]-
	-agnt->[king: Macbeth]
   (...)

Generalizing

Generalization of graphs means that the common information found in two graphs is produced as a third graph. This means that the structure of the two graphs in question is compared, and that the concepts in a shared structure are rendered in terms of the least concept that subsumes them both (the least common subsumer).

In order to generalize the two utterances of Macbeth, use the predicate general(G) in the macbeth2.plgCG program, or write the query in full:

Generalize(
[act: ask]-
	-agnt->[thane: Macbeth],
	-thme->[proposition = 
		[act: see]-
			-agnt->[person: pn_I]
			-obj->[object: *x]-
				-bfore->[person: pn_me],
				-type->[dagger]],
[act: say]-
    -agnt->[king: Macbeth],
    -thme->[proposition = 
	[act: will_fight]-
	   -agnt->[person: pn_I],
	   -until->[state =
		      [hacked]-
			-ptnt->[flesh]<-poss-[person: pn_my],
			-from->[bone: {*}]<-poss-[person: pn_my]]],
G).

This yields the result:

{G = [act] -
            -agnt->[person : Macbeth],
            -thme->[proposition = [act]-agnt->[person : pn_I]]}

What we see here is the information that is common to both graphs. Note that [act: say] and [act: ask] have been generalized to [act], which is the least common subsumer. Likewise, [thane: Macbeth] and [king: Macbeth] have been generalized to [person: Macbeth].

The new graph also reveals the fact that in both graphs Macbeth talks about himself as the agent of doing something.

The more general graph shows us something new about the knowledge base, but at the same time, some information is left out.

Joining

Where generalization looks upward in the hierarchy, Join looks downwards in the hierarchy to find a the greatest lower bound of two concepts.

Let us investigate the join of the two small graphs containing comments. Use the predicate join(G) in the macbeth2.plgCG program, or write the query in full:

MaximalJoin([man: Macbeth], [royal: Macbeth], J).
This yields the result:
{J = [king : Macbeth]}

The reason is that [king] is the greatest type that is the subtype of both [man] and [royal].

The result is correct, but is raises a question, central to processing of semantic representations, namely how results may be interpreted.

This example is of course constructed in order to draw attention to the problem, but it is not an unreasonable scenario: all we did was to add "innocent" information to the knowledge base. The typehierarchy contains no controversial information, nor does the comments. The result, however, is only true in act 5, where Macbeth is king. In act 2 he is still a nobleman of lesser importance: a thane.

Next

Next we will demonstrate some templates you may find useful in your own translations of texts.


Templates

Introduction

A template, in this context, is a configuration of concepts and relations which can be used again and again when formalizing texts.

Here are some benefits of templates:

Further notes

If you have formalized a lot of text, you will find that certain configurations recur. It is good to make a portfolio of templates from such experiences, so that you can refer to it again next time the same configuration comes up.

On the following pages, we give examples of templates. Some are from the research of Henrik Schärfe or the work of Ulrik Petersen. Others are in widespread use in the CG community.


Act

Introduction

An Act has an agent, and possibly a patient, theme, recipient, or other role-relation.

Template

  [Act]-
    -AGNT->[Animate],    // Should always be there
    -PTNT/RCPT/BENF->[Physical],  // Use only one
    -MANR->[Manner],     // Optional
    -LOC->[Physical],    // Optional
    ...                  // Optional

Template example

// Act-template example
//
// Available in the AAU directory as Act-template.plgCG
//
// Ulrik Petersen
// Created: mid-September 2003
// Last update: September 18, 2003
//


// Type hierarchy
Entity > Physical, Abstract.
Abstract > Attribute, Manner.
Attribute > Animate, Inanimate.
Manner > Violently.
Physical > Process, Object.
Process > Act.
Object > Person, Animal, Book, Behind.
Animate > Person, Animal.
Inanimate > Book, Behind.

// Catalog of instances
Act = Give, Take, Kick.
Person = John, Mary.
Animal = Garfield, Odie.
Behind = Odies_behind.


// Template examples

// John gives the book to Mary
graph(act1, [Act : Give]-                    
              -AGNT->[Person : John],
              -RCPT->[Person : Mary],
              -THME->[Book]).

// Mary takes the book from John
graph(act2, [Act : Take]-                  
              -AGNT->[Person : Mary],
              -ORGN->[Person: John],
              -THME->[Book]).

// Garfield kicks Odie violently in the behind
graph(act3, [Act: Kick]-                   
              -AGNT->[Cat : Garfield],  
              -PTNT->[Dog : Odie],
              -MANR->[Violently],
              -LOC->[Behind: Odies_behind]).

Reference

This template is generally accepted in the CG community.


Utterance

Introduction

An utterance is something (thme) that is said by somebody (agnt) to somebody (rcpt). It can also have other relations, such as manner (manr), time (ptim), characteristic (chrc), etc.

What is said is usually nested inside a proposition.

Template

  [Utterance]-
     -AGNT->[Animate],           // Speaker
     -RCPT->[Animate],           // Hearer
     -MANR->[Attribute],         // Optional
     -CHRC->[Attribute],         // Optional
     -PTIM->[Time_reference],    // Optional
     -THME->[Proposition = ...]  // What is said

Examples of template

// Utterance-template example
//
// Available in the AAU directory as Utterance-template.plgCG
//
// Ulrik Petersen
// Created: mid-September, 2003
// Last update: September 18, 2003
//


// Type hierarchy
Entity > Physical, Abstract.
Abstract > Proposition, Manner.
Proposition > Property.
Property > Beautiful, Fast.
Manner > Awedly.
Physical > Act, Object.
Object >Person, Shawl, Car.
Act > Utterance.

// Catalog of instances
Person = Susan, Farhana, Sadia, Mark, Marzia, Mudhaffar.

// Template examples

// Susan says to Farhana: "Sadia's shawl is beautiful."
graph(uttr1, [Utterance]-
                        -AGNT->[Person: Susan],
                        -RCPT->[Person: Farhana],
                        -THME->[Proposition = [Shawl]-
                                    -POSS->[Person: Sadia],
                                    -CHRC->[Beautiful]
                               ]).

// Mark says awedly to Marzia: "Mudhaffar's car is fast."
graph(uttr2, [Utterance]-
                        -AGNT->[Person: Mark],
                        -RCPT->[Person: Marzia],
                        -MANR->[Awedly],
                        -THME->[Proposition = [Car]-
                                      -POSS->[Person: Mudhaffar],
                                      -CHRC->[Fast]  
                               ]).

// Example of a rule

// Speaker (S) taks to Hearer (H) in graph with label L
Talks(S,H,L) :- graph(L, G), 
                branchOfCG([Utterance]-AGNT->[Person: S], G),
                branchOfCG([Utterance]-RCPT->[Person: H], G).

Example rule

We have included a rule to show how to exploit this template.

The predicate "Talks(S,H,L)" finds the speaker (S), hearer (H) and graph-label (L) of the graph in question.

If we ask the query:

?- Talks(S,H,L).

We get the following answer:

{S = Susan, H = Farhana, L = uttr1}
{S = Mark, H = Marzia, L = uttr2}

Reference

This template is from the work of Henrik Schärfe.


AND

Introduction

In normal CG notation, two connected graphs that stand side by side are implicitly assumed to be logically connected by "and".

Since Prolog+CG does not allow two adjacent graphs that are not connected to each other, we have to find some other way of representing "AND".

Template

One possible solution would be to surround the two graphs with concepts of type "Situation", "Proposition", or the like, and then place a relation called "AND" in between.

[Proposition = ...]-AND->[Proposition = ...]

Below we give an example of this:

Example of template

// AND-Template 
//
// Available in the AAU directory as And-template.plgCG
//
// Ulrik Petersen
// Created: Mid-September 2003
// Last update: September 18, 2003
//



// Type hierarchy
Entity > Physical, Abstract.
Abstract > Proposition, Attribute.
Attribute > Mortal.
Physical > Object.
Object > Person.
Person > Man.

// Catalog of instances
Person = Socrates.
Man = Socrates.

// Socrates is a man, and Socrates is Mortal
graph(Socrates1, [Proposition =
                      [Man: Socrates]
                 ]-AND->[Proposition =
                      [Person: Socrates]-ATTR->[Mortal]
                 ]).

Reference

This template comes from Ulrik Petersen.


If/Then

Introduction

In many situations, one will want to write "If ... Then" structures.

The accepted way of doing this in the CG community is as follows:

  [If:
     [... the if-part ...]
     [Then:
        [... the then-part ...]
     ]
  ]

However, we cannot do it this way, since this would require two adjacent, non-connected graphs (namely the if-part and the Then-part).

Template

So we have to invent our own solution. One such is exemplified here:

  [If =
     [Propositon = ... the if-part ...
     ]-AND->[Then = ... the then-part ...]
  ]

The types If and Then are made to be subtypes of Proposition:

Entity > Physical, Abstract.
Abstract > Proposition.
Proposition > If, Then.

Example of template

// If-Then template example
//
// Available in the AAU directory as If-Then-template.plgCG
//
// Ulrik Petersen
// Created: mid-September, 2003
// Last update: September 18, 2003
//


// Type hierarchy
Entity > Physical, Abstract.
Abstract > Proposition, Act.
Proposition > If, Then.
Physical > Object.
Object > Ball, Person.

// Catalog of instances
Act = Drop, Fall.
Person = You.

// Graph fact: If you drop a ball, it falls
graph(IfThen1, [If =  
                   [Proposition = 
                        [Act: Drop]-
                            -AGNT->[Person: You],
                            -THME->[Ball : X]
                   ]-AND->[Then =
                             [Act: Fall]-AGNT->[Ball : X]
                          ]
               ]).

Note how this makes use of the Act template and the AND template.

Note also how it uses the variable "X" to show coreference.

Reference

This solution comes from Ulrik Petersen.

The general method described first is generally accepted in the CG community. See Sowa (2000), pp. 141, 280 for examples.


Non-literal expressions

Introduction

In Schärfe (2002), researcher Henrik Schärfe showed how to represent non-literal expressions in Prolog+CG.

Ontological background

Schärfe proposed to place the various kinds of non-literal expressions in the type-hierarchy. For example:

Proposition > Non_literal.
// Note: This list could easily be extended...
Non_literal > Hyperbole, Idiom, Irony, Metaphor, Metonymy, Simile.

Template

This provides the ontological framework within which to place non-literal expressions. Schärfe then proposed the following canonical graph:

[Non_literal = [Universal]]

Template for metaphor

From this canonical graph, Schärfe proposed the following template for metaphors:

[target_domain]-R1->[metaphor = [source_domain]]

Below, we give examples of this, drawn from Schärfe (2002).

Template examples

//
// Non-literal expressions template example
//
// Available in the AAU directory as Non-literal-template.plgCG
//
// Adapted from Scharfe, Henrik (2002), "CG Representations of 
//    Non-literal Expressions." in U. Priss, D Corbett, G.Angelova 
//   (Eds.) "Conceptual Structures: Integration and Interfaces."
//   Springer Verlag, Berlin, New York. LNAI 2393. pp. 166-176.
//
// Ulrik Petersen
// Created: Mid-September, 2003
// Last update: September 18, 2003
//


// Type hierarchy
Entity > Physical, Abstract.
Abstract > Proposition, Description, Feeling.
Proposition > Non_literal.

// Note: This list could easily be extended...
Non_literal > Hyperbole, Idiom, Irony, Metaphor, Metonymy, Simile.

Description > Title.
Feeling > Thirsty.

Physical > Object.
Object > Animate, Inanimate.
Animate > Person, Animal.
Animal > Snake.
Inanimate > Artefact, Plant.
Artefact > Car.
Plant > Grass.

// Catalog of instances
Title = Head_of_department.

//
// Graph examples
//

// The car is thirsty
graph(gr1, [Car: X]-ATTR->[Metaphor = [Car: X]<-EXPR-[Thirsty] ]).

// The head of the department is a snake in the grass
graph(gr2, [Person: X]-
                 -CHRC->[Title: Head_of_department],
                 -ATTR->[Metaphor = [Snake]-LOC->[Grass]]).

// Rules

// Find the source domain of a metaphor
source(L, S) :-
    graph(L, G),   // Get the graph and its label
    subsume([Metaphor], G),  // Check that it has a metaphor
    branchOfCG(S-R->[Metaphor], G).  // Find the source domain 
    
// Find the target domain of a metaphor
target(L, T) :- 
    graph(L, G),       // Get the graph and its label
    subsume([Metaphor], G),  // Check that it has a metaphor
    concOfCG([Metaphor = T], G).  // Get the metaphor's target domain

Reference

See Schärfe (2002) for a fuller treatment.


Examples

Introduction

In the following, we give a number of examples of formalized texts.


Lion and Mouse

Introduction

The following example has been adapted from the research of Henrik Schärfe.

Modified by Ulrik Petersen for the purposes of this course.

Example

//
// Lion-and-Mouse example.  One of Aesop's fables.
//
// Adapted from the work of Henrik Scharfe 
// by Ulrik Petersen
// Created: September 13, 2003
// Last update: September 23, 2003
//
// Available in the AAU directory as Lion-and-Mouse.plgCG
//
// The text is:
//
// "A LION was awakened from sleep by a Mouse running over his face. 
// Rising up angrily, he caught him and was about to kill him, when the 
// Mouse piteously entreated, saying: "If you would only spare my life, 
// I would be sure to repay your kindness." The Lion laughed and let him go.
// It happened shortly after this that the Lion was caught by some hunters, 
// who bound him by ropes to the ground. The Mouse, recognizing his roar,
// came, gnawed the rope with his teeth, and set him free, exclaimed "You 
// ridiculed the idea of my ever being able to help you, expecting to receive 
// from me any repayment of your favor; now you know that it is possible 
// for even a Mouse to help a Lion." 
//

// Type-hierarchy
entity > physical, abstract.
abstract > description, proposition, schema.
description > manner, idea, attribute.
manner > angrily, piteously.
attribute > possible.
proposition > if, then.
schema > quantity.
physical > process, object, situation, execution.
process > act, life.
object > animal, face, person, artefact, natural_resource, bodypart.
situation > state.
execution > kindness, temporal_reference.

// Catalog of instances.

animal = lion, mouse.
person = hunters, you, me.
act = run, caught, awakened, rising_up, entreated, spare, repay,
          about_to_kill, laughed, let_go, bound, recognizing, roar, gnawed,
          set_free, exclaimed, ridiculed, help, know.
quantity = some.
temporal_reference = shortly_after.
artefact = ropes.
natural_resource = ground.
body_part = teeth.
state = being_able.


// Each fable has a part-number (e.g., pa1, pa2).
// Each part corresponds to roughly one sentence.
//

fab4(pa1,

    [act: awakened]-
    -ptnt->[animal:lion],
    -agnt->[animal:mouse],
    -caus->[situation = [act:run]-
      -agnt->[animal:mouse],
      -path->[face]<-poss-[animal:lion]]).

fab4(pa2,

    [act:caught]-
    -agnt->[animal:lion],
    -ptnt->[animal:mouse],
    -ptim->[act:rising_up]-
      -agnt->[animal:lion],
      -manr->[angrily]).

fab4(pa3,

    [act : entreated = 
       [proposition = 
          [if = [animal:lion]<-agnt-[act:spare]-thme->[life]<-poss-[animal:mouse]
       ]-cond->[then = 
          [act : repay]-
            -agnt->[animal:mouse],
            -thme->[kindness],
            -rcpt->[animal:lion]
                       ]
       ]
    ]-
      -manr->[piteously],
      -agnt->[animal:mouse],
      -rcpt->[animal:lion],
      -ptim->[act:about_to_kill]-
        -agnt->[animal:lion],
        -ptnt->[animal:mouse]).

fab4(pa4,

    [animal:lion]<-agnt-[act:laughed]).

fab4(pa5,

    [act:let_go]-
    -ptnt->[animal:mouse],
    -agnt->[animal:lion]).

fab4(pa6,

    [act:caught]-
    -ptnt->[animal:lion],
    -agnt->[person:hunters]-quan->[quantity:some],
    -ptim->[temporal_reference:shortly_after]).

fab4(pa7,

    [act:bound]-
    -agnt->[person:hunters],
    -ptnt->[animal:lion],
    -inst->[artefact:ropes],
    -dest->[natural_resource:ground]).

fab4(pa8,

    [act:recognizing]-
    -agnt->[animal:mouse],
    -thme->[act:roar]-agnt->[animal:lion]).

fab4(pa9,

    [act:gnawed]-
    -agnt->[animal:mouse],
    -obj->[artefact:ropes],
    -inst->[bodypart:teeth]).

fab4(pa10,

    [act:set_free]-
    -agnt->[animal:mouse],
    -ptnt->[animal:lion]).

fab4(pa11,

    [act : exclaimed = 
       [person:you]<-agnt-[act : ridiculed = 
         [idea = 
              [state: being_able]-
                  -thme->[situation = [act:help]-
                                        -agnt->[person : me],
                                        -rcpt->[person : you]],
                  -expr->[person : me]
              ]
         ]]-
    -agnt->[animal:mouse],
    -rcpt->[animal:lion]).

fab4(pa12,

    [act : exclaimed = [act:know]-
       -agnt->[person:you],
       -thme->[situation = 
                          [animal:mouse]<-agnt-[act:help]-benf->[animal:lion]
                      ]-attr->[possible]
    ]-
    -agnt->[animal:mouse],
    -rcpt->[animal:lion]).



// Rules

// Connect fable number, part, and graph
fable(4, p, g) :- fab4(p, g).

// X does Act Z to Y in graph G where Z and Y are connected by relation R
doesHow(G, X, Y, Z, R) :-
   subsume([entity]<-agnt-[act]-R->[entity], G),
   branchOfCG([act : Z]-agnt->[entity : X], G),
   branchOfCG([act : Z]-R->[entity : Y], G).

// X does Act Z to Y in graph G where Y is a patient of Act Z
doesPtnt(G, X, Y, Z) :-
   doesHow(G, X, Y, Z, ptnt).

// Lion does something (W) to the mouse, where the mouse is a patient of the act
// in fable f, part p
lion_mouse(f, p, W) :-
   fable(f, p, G),
   doesPtnt(G, lion, mouse, W).

// Mouse does something (W) to lion where the lion is a patient of the act
// in fable f, part p
mouse_lion(f, p, W) :-
   fable(f, p, G),
   doesPtnt(G, mouse, lion, W).

// X caught Y
// in fable f, part p
caught(f, p, X, Y) :-
   fable(f, p, G),
   doesPtnt(G, X, Y, caught).

// X exclaimed W to Y
// in fable f, part p
exclaimed(f, p, X, Y, W) :-
   fable(f, p, G),
   doesHow(G, X, Y, exclaimed, rcpt),
   concOfCG([act : exclaimed = W], G).

Usage

The following is an edited transcript of some queries:

?- lion_mouse(f, p, W).
 
{f = 4, p = pa2, W = caught}
{f = 4, p = pa3, W = about_to_kill}
{f = 4, p = pa5, W = let_go}

?- mouse_lion(f, p, W).
 
{f = 4, p = pa1, W = awakened}
{f = 4, p = pa10, W = set_free}

?- caught(f, p, X, Y).
 
{f = 4, p = pa2, X = lion, Y = mouse}
{f = 4, p = pa6, X = hunters, Y = lion}

?- exclaimed(f, p, X, Y, W).
 
{f = 4, p = pa11, X = mouse, Y = lion, W = [act : ridiculed = 
            [idea = [state : being_able] -
                        -thme->[situation = [act : help] -
                                                -agnt->[person : me],
                                                -rcpt->[person : you]],
                        -expr->[person : me]]]-agnt->[person : you]}
{f = 4, p = pa12, X = mouse, Y = lion, W = [act : know] -
            -agnt->[person : you],
            -thme->[situation = [act : help] -
                         -benf->[animal : lion],
                         -agnt->[animal : mouse]]-attr->[possible]}


Macbeth 1

Introduction

The following text is a formalization of the following quotes from Macbeth by William Shakespeare:

Macbeth: "Is that a dagger which I see before me?" (2.1.31)
Macbeth: "I'll fight, till from my bones my flesh be hacked." (5.3.34)

Example

//
// macbeth.plgCG
//
// Written by Henrik Scharfe, September 2003
// Last update: September 23, 2003
//

// Type hierarchy
universal > object, process, proposition.
object > person, artifact.
person > pronoun.
artifact > weapon.
weapon > dagger.
process > act, state.

// Catalogue of individuals
act = ask, hacked, say.
person = Macbeth.
pronoun = pn_I, pn_me, pn_my.

// Graphs

gr(act2,
  [act: ask]-
        -agnt->[person: Macbeth],
        -thme->[proposition = 
                    [act: see]-
                       -agnt->[person: pn_I]
                       -obj->[object: *x]-
                                 -bfore->[person: pn_me],
                                 -type->[dagger]]).

gr(act5,
  [act: say]-
    -agnt->[person: Macbeth],
    -thme->[proposition = 
               [act: will_fight]-
                   -agnt->[person: pn_I],
                   -until->[state =
                               [act:hacked]-
                                    -ptnt->[flesh]<-poss-[person: pn_my],
                                    -from->[bone: {}]<-poss-[person: pn_my]]]).


// predicates

branches(B):-
gr(L,G),
branchOfCG(B,G).

concepts(C):-
gr(L,G),
concOfCG(C,G).

//extracting the concepts in the embedded graph
conceptsProp(C):-
gr(L,G),
subsume([proposition],G),
branchOfCG([proposition = P], G),
concOfCG(C, P).

//extracting all concepts
AllConcepts(C):-
concepts(C).
AllConcepts(C):-
conceptsProp(C).

// Subsuming action
action(G):-
gr(L,G),
subsume([act]-agnt->[person],G).

// extracting referents
actor(a,b):-
gr(L,G),
subsume([act]-agnt->[person],G),
branchOfCG([act:a]-agnt->[person: b],G).


Colophon

This example is available in the AAU directory as "macbeth.plgCG".

It was written by Henrik Schärfe.


Macbeth 2

Introduction

The following text is a formalization of the following quotes from Macbeth by William Shakespeare:

Macbeth: "Is that a dagger which I see before me?" (2.1.31)
Macbeth: "I'll fight, till from my bones my flesh be hacked." (5.3.34)

Example

//
// macbeth2.plgCG
//
// Written by Henrik Scharfe, September 2003
// Last update: September 23, 2003
//

universal > object, process, proposition.
object > person, artifact.
person > pronoun, royal, man.
man > king.
royal > king.
artifact > weapon.
weapon > dagger.
process > act, state.

// Catalogue of individuals
act = ask, hacked, say.
person = Macbeth.
pronoun = pn_I, pn_me, pn_my.


 gr(act2,
  [act: ask]-
        -agnt->[person: Macbeth],
        -thme->[proposition = 
                [act: see]-
                        -agnt->[person: pn_I]
                        -obj->[object: *x]-
                                -bfore->[person: pn_me],
                                -type->[dagger]]).

 gr(act5,
  [act: say]-
    -agnt->[person: Macbeth],
    -thme->[proposition = 
               [act: will_fight]-
                    -agnt->[person: pn_I],
                    -until->[state =
                                 [act:hacked]-
                                    -ptnt->[flesh]<-poss-[person: pn_my],
                                    -from->[bone: {}]<-poss-[person: pn_my]]]).


com(act2, [man: Macbeth]).
com(act5, [royal: Macbeth]).


// predicates

branches(B):-
gr(L,G),
branchOfCG(B,G).

concepts(C):-
gr(L,G),
concOfCG(C,G).

//extracting the concepts in the embedded graph
conceptsProp(C):-
gr(L,G),
subsume([proposition],G),
branchOfCG([proposition = P], G),
concOfCG(C, P).

//extracting all concepts
AllConcepts(C):-
concepts(C).
AllConcepts(C):-
conceptsProp(C).
// Subsuming action
action(G):-
gr(L,G),
subsume([act]-agnt->[person],G).

// extracting referents
actor(a,b):-
gr(L,G),
subsume([act]-agnt->[person],G),
branchOfCG([act:a]-agnt->[person: b],G).

com2(a):-
com(act2,a).

com5(b):-
com(act5,b).

join(J):-
com2(a),
com5(b),
maximalJoin(a,b,J).

// Generalizing the graphs. The generalization of graphs 2 and 3 
// reveals that thay have more in common than just a person 
// saying something...

act2(a):-
gr(act2,a).

act5(b):-
gr(act5,b).


general(G):-
act2(A),
act5(B),
generalize(A,B,G).

isSubType(dagger, weapon).

weapon(a):-
AllConcepts(a),
isSubType(a, weapon).

Colophon

This example is available in the AAU directory as "macbeth2.plgCG".

It was written by Henrik Schärfe.


Garfield

Example of exploiting transitivity

Consider the following Prolog+CG program:

// Type-hierarchy
//
// Example of exploiting transitivity of type-hierarchy
// Available in the AAU directory as "GarfieldOdieJon.plgCG"

// Type-hierarchy
Entity > Animate, Act.
Animate > Animal, Human. 
Animal > Cat, Dog.

// Catalog of instances
Cat = Garfield.
Dog = Odie.
Human = Jon.
Act = Kick, Like, Love.

// Graphs

// Garfield kicks Odie
graph(gr1, [Cat: Garfield]<-AGNT-[Act: Kick]-PTNT->[Dog: Odie]).

// Jon likes Garfield
graph(gr2, [Human: Jon]<-AGNT-[Act: Like]-THME->[Cat: Garfield]).

// Odie likes Garfield
graph(gr3, [Dog: Odie]<-AGNT-[Act: Like]-THME->[Cat: Garfield]).

// Garfield loves Garfield
graph(gr4, [Cat: Garfield]<-AGNT-[Act: Love]-THME->[Cat: Garfield]).


// Rules
AnimalDoes(L,G) :- graph(L, G), subsume([Animal]<-AGNT-[Act], G).
AnimateDoes(L,G) :- graph(L, G), subsume([Animate]<-AGNT-[Act], G).

If we now ask the query:

?- AnimalDoes(L,G).

We get the following answer:

{L = gr1, G = [Act : Kick] -
                           -PTNT->[Dog : Odie],
                           -AGNT->[Cat : Garfield]}
{L = gr3, G = [Act : Like] -
                           -THME->[Cat : Garfield],
                           -AGNT->[Dog : Odie]}
{L = gr4, G = [Act : Love] -
                           -THME->[Cat : Garfield],
                           -AGNT->[Cat : Garfield]}

This reflects the fact that both "Dog" and "Cat" are subtypes of "Animal". Since the "subsume" goal looks for graphs which are more general than other graphs, all of these three graphs match the graph which has "Animal" in it.

Likewise, if we ask the query:

?- AnimateDoes(L,G).

We get the following answer:

{L = gr1, G = [Act : Kick] -
                           -PTNT->[Dog : Odie],
                           -AGNT->[Cat : Garfield]}
{L = gr2, G = [Act : Like] -
                           -THME->[Cat : Garfield],
                           -AGNT->[Human : Jon]}
{L = gr3, G = [Act : Like] -
                           -THME->[Cat : Garfield],
                           -AGNT->[Dog : Odie]}
{L = gr4, G = [Act : Love] -
                           -THME->[Cat : Garfield],
                           -AGNT->[Cat : Garfield]}

This is the same answer as before, except that graph 2, "Jon likes Garfield" is also in the results. This is because "Human" is a subtype of "Animate", just like "Dog" and "Cat" are.


branchOfCG

The branchOfCG goal checks whether the branch B is a part of the (perhaps) larger CG G.

The goal does bind variables in the branch B to their counterparts in the graph G. This means that you can use branchOfCG to extract parts of a graph.

For example, if you have just used subsume to check that a graph conforms to a certain pattern, you can extract nested, inner parts of that pattern with branchOfCG. Then you can do more analysis of the inner parts.

Or, as another example, you can get certain parts of a branch of the graph:

// The car is thirsty
graph(CarIsThirsty, [Car: X]-ATTR->[Metaphor = [Car: X]<-EXPR-[Thirsty] ]).

// The head of the department is a snake in the grass
graph(HeadIsSnake, [Person: X]-
                      -CHRC->[Title: Head_of_department],
                      -ATTR->[Metaphor = [Snake]-LOC->[Grass]]).

// Rule

// Find the source domain of a metaphor
source(L, S) :-
    graph(L, G),   // Get the graph and its label
    subsume([Metaphor], G),  // Check that it has a metaphor
    branchOfCG(S-R->[Metaphor], G).  // Find the source domain 
                  // Note how the variable S stands for the whole concept
                  // Note also how we used the variable R to mean any relation


concOfCG

The concOfCG goal is used to check whether a certain concept C is part of a CG G.

The goal does bind variables in the concept C to their counterparts in the graph G. This means that you can use concOfCG to extract parts of a graph.

For example, if you have used subsume or branchOfCG to check that a graph conforms to a certain pattern, you can extract the referent of a specific concept in the graph:

// The car is thirsty
graph(CarIsThirsty, [Car: X]-ATTR->[Metaphor = [Car: X]<-EXPR-[Thirsty] ]).

// The head of the department is a snake in the grass
graph(HeadIsSnake, [Person: X]-
                      -CHRC->[Title: Head_of_department],
                      -ATTR->[Metaphor = [Snake]-LOC->[Grass]]).

// Rule

// Find the target domain of a metaphor
target(L, T) :- 
    graph(L, G),       // Get the graph and its label
    subsume([Metaphor], G),  // Check that it has a metaphor
    concOfCG([Metaphor = T], G).  // Get the metaphor's target domain


Conflict-act

Introduction

Here we give some examples of ontology-driven searches.

Example

//
//  CONFLICT ACT EXAMPLE
//
//       Based on Henrik Scharfe's formalization of the Gideon-story
//       from Judges 6-8 in the Bible.
//
//       Ulrik Petersen
//       Created: September 13, 2003
//       Last update: September 13, 2003

// Type hierarchy
Entity > Physical.
Physical > Object, Collection, Process.
Object > Rock, Person, Winepress.
Collection > People_group, Men.
Process > Act.
Act > Conflict_act.
Conflict_act > Kill, Pursue.

// Catalog of instances
Men = Ephraim.
Person = Oreb, Zeeb.
Rock = Rock_of_Oreb.
Winepress = Winepress_of_Zeeb.
People_group = Midian.

// The men of Ephraim killed Oreb at the Rock of Oreb.
jud7(verse25b,
   [Kill]-
      -agnt->[Men : Ephraim],
      -ptnt->[Person : Oreb],
      -loc->[Rock: Rock_of_Oreb]).
                   
// The men of Ephraim killed Zeeb in the winepress of Zeeb.                                                             
jud7(verse25c,
   [Kill]-
      -agnt->[Men : Ephraim],
      -ptnt->[Person : Zeeb],
      -loc->[Winepress: Winepress_of_Zeeb]).

// The mean of Ephraim pursued Midian.
jud7(verse25d,
   [Pursue]-
       -agnt->[Men : Ephraim],
       -ptnt->[People_group : Midian]).

// Rules

// Connect Chapter 7 together into one predicate
judges(7, v, G) :- jud7(v, G).

// Conflict act
// returns agent (s1), action (a), and ptnt (s2) of conflict-acts.
conflict(c,v,s1,a,s2) :-
   judges(c,v,g),   // Get the chapter, verse, and graph
   subsume([Conflict_act]-
              -agnt->[Entity],
              -ptnt->[Entity], g),  // Make sure there is a conflict-act in g
   branchOfCG([Conflict_act]-agnt->[r : s1],g),  // Get the agnt (s1)
   branchOfCG([Conflict_act]-ptnt->[s : s2],g),  // Get the patient (s2)
   branchOfCG([a]-agnt->[r : s1], g),  // Get the conlict-act
   isSubType(a, Conflict_act).  // Make sure it is a conflict-act

Usage

If we ask the query:

?- conflict(c,v,s1,a,s2).

We get the following answer:

{c = 7, v = verse25b, s1 = Ephraim, a = Kill, s2 = Oreb}
{c = 7, v = verse25c, s1 = Ephraim, a = Kill, s2 = Zeeb}
{c = 7, v = verse25d, s1 = Ephraim, a = Pursue, s2 = Midian}


Reusing predicates

Introduction

Often it will pay to write predicates in a general way, so that they can be reused by other predicates.

Example

// Finds the Agent (A), Undergoer (U), the
// relation of the undergoer to the action (R), 
// and Act-type (T) in graph G
act(G, T, A, U, R) :-
   subsume([Act]-
             -AGNT->[Entity],
             -R->[Entity], G), // Make sure that G has an Act-template
   branchOfCG([Act : T]-AGNT->[X : A], G), // Get the agent, A, and the type, T
   branchOfCG([Act : T]-R->[Y : U], 
              G). // Get the undergoer U, and make sure it is the same act T.

This could be reused in other predicates:

// Find killer (A) and killed (U)
kills(G, A, U) :-
   act(G, Kill, A, U, PTNT).

// Find speaker and hearer
talks(G, S, H) :-
   act(G, Talk, S, H, RCPT).

// Find speaker, hearer and thematic content.
talks_about(G, S, H, P) :-
   act(G, Talk, S, H, RCPT),
   act(G, Talk, S, P, THME).

Next

Part II has come to an end. In part III, we look at Prolog in more detail.