# Using Prolog with AllegroGraph 3.3

## Introduction

We would urge you to first do this tutorial and then study the Allegro Prolog documentation if necessary. This is a basic tutorial on how to use Prolog with AllegroGraph 3.3. It should be enough to get you going but if you have any questions please write to us and we will help you. In this example we will focus mainly on how to use the following constructs:

- select
- q-
- q
- <--
- <-
- ??
- !

When consulting the Reference Guide, one should understand the conventions for documenting Prolog functors. A Prolog functor clause looks like a regular Lisp function call, the symbol naming the functor being the first element of the list and the remaining elements being arguments. But arguments to a Prolog functor call can either be supplied as input to the functor, or unsupplied so that the clause might return that argument as a result by unifying some data to it, or may be a tree of nodes containing both ground data an Prolog variables. The common example is the functor `append` which has three arguments and succeeds for any solution there the third argument is the same as the first two arguments appended. The remarkable thing about Prolog semantics is that append is a declarative relation that succeeds regardless which arguments are supplied as inputs and which are supplied as outputs. `<ret>` indicates where the user would type a return to ask Prolog to find the next result.

        > (?- (append (1 2) (3) ?z))
        ?z = (1 2 3)
        <ret>
        No.
        > (?- (append (1 2) ?y (1 2 3)))
        ?y = (3)
        <ret>
        No.
        > (?- (append ?x ?y (1 2 3)))
        ?x = ()
        ?y = (1 2 3)
        <ret>
        ?x = (1)
        ?y = (2 3)
        <ret>
        ?x = (1 2)
        ?y = (3)
        <ret>
        ?x = (1 2 3)
        ?y = ()
        <ret>
        No.
        > (?- (append ? (1 ?next . ?) (1 2 1 3 4 1 5 1)))
        ?next = 2
        <ret>
        ?next = 3
        <ret>
        ?next = 5
        <ret>
        No.

The last example successively unifies to each element in the list immediately preceded by a `1`. It shows the power of unification against partially ground tree structure.

Now we return to the the notational convention: A functor argument that is an input to the functor and which must be supplied is marked in the documentaiton with a `+`. A functor argument that is returned by the functor and which must not be supplied is marked with a `-`. An argument that can be either is marked with ±. (Prolog documentation generally used `?` for this, but in Lisp-bnased Prologs that character is used as the first character of a symbol that is a Prolog variable, overloading using it to indicate and input-output argument would be very confusing.) Within this convention append would be notated as `(append &plusmn;left &plusmn;right &plusmn;result). But a functor like` part=`which simply checks whether two parts are the same UPI and which requires two actual which requires two actual furure-part or UPI arguments, would be documented` (part= +upi1 +upi2)`.

The rest of this tutorial will be based on a tiny genealogy database of the Kennedy family.

Please open the file `kennedy.ntriples` that came with this distribution in a text editor or with TopBraidComposer and study the contents of the file. Notice that people in this file have a type, sometimes multiple children, multiple spouses, multiple professions, and go to multiple colleges or universities.

This tutorial uses Lisp as the base language but there is also a Java example with the same content.

First let us get AllegroGraph ready to use:

    > (require :agraph)
    ;; .... output deleted.

    > (in-package :triple-store-user)
    #<The db.agraph.user package>

    > (enable-!-reader)
    #<Function read-!>
    t

    > (register-namespace "ex" "http://www.franz.com/simple#"
       :errorp nil)
    "http://www.franz.com/simple#"

Now we can create a triple-store and load it with data. The function create-triple-store creates a new triple-store and opens it. If you use the triple-store name "temp/test", then AllegroGraph will create a new directory named `temp` in your current directory (use the top-level command `:pwd` if you want to see what this is). It will then make another directory named `test` as a sub-directory of `temp`. All of this triple-store's data will be placed in this new directory `temp/test`:

    > (defun fill-kennedy-db ()
        (create-triple-store "temp/test"
                             :if-exists :supersede)
        (time
         (load-ntriples #p"sys:agraph;tutorial-files;kennedy.ntriples"))
        (index-all-triples))
    fill-kennedy-db
    > (fill-kennedy-db)
    ;; .... output deleted.

So let us first look at `person1` in this database:

    > (print-triples
       (get-triples-list :s !ex:person1))
    <http://www.franz.com/simple#person1> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.franz.com/simple#person> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#first-name> <http://www.franz.com/simple#Joseph> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#middle-initial> <http://www.franz.com/simple#Patrick> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#last-name> <http://www.franz.com/simple#Kennedy> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#birth-year> <http://www.franz.com/simple#1888> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#death-year> <http://www.franz.com/simple#1969> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#sex> <http://www.franz.com/simple#male> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#spouse> <http://www.franz.com/simple#person2> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#suffix> <http://www.franz.com/simple#none> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person9> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person13> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person17> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person4> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person6> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person15> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person11> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person3> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#has-child> <http://www.franz.com/simple#person7> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#profession> <http://www.franz.com/simple#producer> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#profession> <http://www.franz.com/simple#banker> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#profession> <http://www.franz.com/simple#ambassador> .
    <http://www.franz.com/simple#person1> <http://www.franz.com/simple#alma-mater> <http://www.franz.com/simple#Harvard> .

Now we are ready to try the select statement in combination with the Prolog q functor. Let us try to find all the children of `person1`. Just type the following in the listener. Afterward, I'll explain.

    > (select (?x)
       (q- !ex:person1 !ex:has-child ?x))
    (("http://www.franz.com/simple#person9")
     ("http://www.franz.com/simple#person13")
     ("http://www.franz.com/simple#person17")
     ("http://www.franz.com/simple#person4")
     ("http://www.franz.com/simple#person6")
     ("http://www.franz.com/simple#person15")
     ("http://www.franz.com/simple#person11")
     ("http://www.franz.com/simple#person3")
     ("http://www.franz.com/simple#person7"))

`select` is a wrapper used around one or more Prolog statements. The first element after select is template for the format and variables that you want to bind and return. So in this example above we want to bind the variable `?x`. The rest of the elements tell Prolog what we want to bind `?x` to.

This `select` `statement has only one clause, namely` (q- !ex:person1 !ex:has-child ?x)`

If you have studied how get-triples works you probably can guess what happens here. `q-` is a Prolog functor that is our link to the data in the triple-store. It calls `get-triples` and unifies the `?x` with the objects of all triples with subject `!ex:person1` and predicate `!ex:has-child`.

So let us make it a little bit more complex. Let us find all the children of the children of person1. Here is how you do it:

    > (select (?y)
       (q- !ex:person1 !ex:has-child ?x)
       (q- ?x !ex:has-child ?y))
    (("http://www.franz.com/simple#person33")
     ("http://www.franz.com/simple#person26")
     ("http://www.franz.com/simple#person28")
     ("http://www.franz.com/simple#person31")
     ("http://www.franz.com/simple#person25")
     ("http://www.franz.com/simple#person62")
     ("http://www.franz.com/simple#person56")
     ("http://www.franz.com/simple#person42")
     ("http://www.franz.com/simple#person47")
     ("http://www.franz.com/simple#person51") ...)

Although Prolog is a declarative language, a procedural reading of this query works better for most people. So the previous query can be read as

> Find all triples that start with `!ex:person1` `!ex:has-child`. For each match set `?x` to the object of that triple; then for each triple that starts with `?x` `!ex:has-child` find the `?y`

The following example should now be easy to understand. Here we are trying to find all the spouses of the grand-children of `?z`. Notice that we ignore the `?x` and`?y` in the query. The select will only return the `?z`

    > (select (?z)
       (q- !ex:person1 !ex:has-child ?x)
       (q- ?x !ex:has-child ?y)
       (q- ?y !ex:spouse ?z))
    (("http://www.franz.com/simple#person34")
     ("http://www.franz.com/simple#person27")
     ("http://www.franz.com/simple#person30")
     ("http://www.franz.com/simple#person32")
     ("http://www.franz.com/simple#person63")
     ("http://www.franz.com/simple#person57")
     ("http://www.franz.com/simple#person43")
     ("http://www.franz.com/simple#person49")
     ("http://www.franz.com/simple#person48")
     ("http://www.franz.com/simple#person52") ...)

Now if you wanted to you could get the other variables back. Here is the same query but now you also want to see the grand-child.

    > (select (?y ?z)
        (q- !ex:person1 !ex:has-child ?x)
        (q- ?x !ex:has-child ?y)
        (q- ?y !ex:spouse ?z))
    (("http://www.franz.com/simple#person33" "http://www.franz.com/simple#person34")
     ("http://www.franz.com/simple#person26" "http://www.franz.com/simple#person27")
     ("http://www.franz.com/simple#person28" "http://www.franz.com/simple#person30")
     ("http://www.franz.com/simple#person31" "http://www.franz.com/simple#person32")
     ("http://www.franz.com/simple#person62" "http://www.franz.com/simple#person63")
     ("http://www.franz.com/simple#person56" "http://www.franz.com/simple#person57")
     ("http://www.franz.com/simple#person42" "http://www.franz.com/simple#person43")
     ("http://www.franz.com/simple#person47" "http://www.franz.com/simple#person49")
     ("http://www.franz.com/simple#person47" "http://www.franz.com/simple#person48")
     ("http://www.franz.com/simple#person51" "http://www.franz.com/simple#person52") ...)

So now we understand the `select` and the `q` statement. We are halfway there. Let us now define some Prolog functors.

The following defines a functor that says: `?x` is a male if in the triple store I can find an `?x` that has the `!ex:sex` `!ex:male`.

    > (<-- (male ?x)
        (q- ?x !ex:sex !ex:male))
    male

Let us try it out by finding all the sons of person1.

    > (select (?x)
        (q- !ex:person1 !ex:has-child ?x)
        (male ?x)) ;;; Note how we use NO q here!
    (("http://www.franz.com/simple#person13")
     ("http://www.franz.com/simple#person17")
     ("http://www.franz.com/simple#person4")
     ("http://www.franz.com/simple#person3"))

Now this is not too exciting, and it is equivalent to the following:

    (select (?x)
     (q- !ex:person1 !ex:has-child ?x)
     (q- ?x !ex:sex !ex:male))

So let us make it more complex:

    > (<-- (female ?x)
        (q- ?x !ex:sex !ex:female))
    female
    > (<-- (father ?x ?y)
        (male ?x)
        (q- ?x !ex:has-child ?y))
    father
    > (<-- (mother ?x ?y)
        (female ?x)
        (q- ?x !ex:has-child ?y))
    mother

The female, father, mother relations are all simple to understand. The following adds the idea of multiple rules (or functors). Notice how we define the parent relationship with two rules, where the first rule uses <-- and the second rule uses <-. The reason is that <-- means: wipe out all the previous rules that I had about parent and start anew whereas <- means, add to the existing rules for parent.

The following should be read as:

- `?x` is the parent of `?y` if `?x` is the father of `?y` or
- `?x` is the parent of `?y` if `?x` is the mother of `?y.`

  > (<-- (parent ?x ?y)

      (father ?x ?y))
      parent

  > (<- (parent ?x ?y)

      (mother ?x ?y))
      parent

So let us try it out by finding the grand children of person1

    > (select (?y)
        (parent !ex:person1 ?x)
        (parent ?x ?y))
    (("http://www.franz.com/simple#person33")
     ("http://www.franz.com/simple#person26")
     ("http://www.franz.com/simple#person28")
     ("http://www.franz.com/simple#person31")
     ("http://www.franz.com/simple#person25")
     ("http://www.franz.com/simple#person62")
     ("http://www.franz.com/simple#person56")
     ("http://www.franz.com/simple#person42")
     ("http://www.franz.com/simple#person47")
     ("http://www.franz.com/simple#person51") ...)

We could have done the same thing by defining a grandparent functor. See the next definition.

    > (<-- (grandparent ?x ?y)
        (parent ?x ?z)
        (parent ?z ?y))
    grandparent
    > (<-- (grandchild ?x ?y)
        (grandparent ?y ?x))
    grandchild

And here it gets really interesting because we now go for the first time to a recursive functor.

    > (<-- (ancestor ?x ?y)
        (parent ?x ?y))
    ancestor
    > (<-  (ancestor ?x ?y)
        (parent ?x ?z)
        (ancestor ?z ?y))
    ancestor

Read the previous two expressions as

- `?x` is the ancestor of `?y` if
  - `?x` is the parent of `?y` or
  - `?x` is the parent of some person `?z` and `?z` is the ancestor of `?y`

A descendant is of course the reverse of ancestor

    > (<-- (descendant ?x ?y)
        (ancestor ?y ?x))
    descendant

So if we want to find all the male descendants of person1 then here is how to do it.

    > (select (?x)
        (descendant ?x !ex:person1)
        (male ?x))
    (("http://www.franz.com/simple#person13")
     ("http://www.franz.com/simple#person17")
     ("http://www.franz.com/simple#person4")
     ("http://www.franz.com/simple#person3")
     ("http://www.franz.com/simple#person33")
     ("http://www.franz.com/simple#person28")
     ("http://www.franz.com/simple#person31")
     ("http://www.franz.com/simple#person25")
     ("http://www.franz.com/simple#person62")
     ("http://www.franz.com/simple#person47") ...)

And then here are some puzzles that you can work out for yourself.. Note the use of `not` and part= in these statements. 'not' can contain any expression. `part=` will compare its two arguments as UPIs; It will not unify.

    > (<-- (aunt ?x ?y)
        (father ?z ?x)
        (female ?x)
        (father ?z ?w)
        (not (part= ?x ?w))
        (parent ?w ?y))
    aunt
    > (<-- (uncle ?x ?y)
        (father ?z ?x)
        (male ?x)
        (father ?z ?w)
        (not (part= ?x ?w))
        (parent ?w ?y))
    uncle

And the final query: find all the children of person1 that are uncles

    > (select (?x ?y)
        (parent !ex:person1 ?x)
        (uncle ?x ?y))
    (("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person33")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person26")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person28")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person31")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person25")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person62")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person56")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person42")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person47")
     ("http://www.franz.com/simple#person13"
      "http://www.franz.com/simple#person51")
     ...)
    >

There is another convenient shorthand to know in Allegro Prolog. It is often necessary to use small bits of Lisp code inside a series of prolog clauses. A typical example is here, where it is necessary inside a sequence of prolog clauses to retrieve a value from the surrounding Lisp environment. Here we define a Lisp function that returns the first and last name of every person born in the argument year.

        > (defun born-in-year (year)
            (select0 (?first-name ?last-name)
              (lisp ?year (literal (princ-to-string year)))
              (q- ?person !ex:birth-year ?year)
              (q- ?person !ex:first-name ?first-name)
              (q- ?person !ex:last-name ?last-name)))
        born-in-year
        > (born-in-year 1915)
        (({Joseph} {Kennedy}) ({Robert} {Shriver}))
        t

The year argument may be a string or an integer, but we need to convert it to a string since that's the way birth years are stored in this particular database. Then the argument needs to be interned as a literal. But the important point is that we need to get the value of year from the surrounding Lisp environments and bind it to a Prolog variable (here named `?year`) so it can be passed to `q-`.

This necessary transfer of data into the Prolog environment clutters the code and makes it harder to read. The `??` syntax marker can eliminate much of this:

        > (defun born-in-year (year)
            (select0 (?first-name ?last-name)
              (q- ?person !ex:birth-year (?? (literal (princ-to-string year))))
              (q- ?person !ex:first-name ?first-name)
              (q- ?person !ex:last-name ?last-name)))

This is nothing more than a syntactic shorthand of the previous example and operates just like it. It eliminates the need for the Prolog variable to be visible. The body of `??` has syntax like Lisp progn and substitutes the value computed by the progn body into the Prolog clause.

There is a problem with the syntax for the Prolog cut and AllegroGraph's future-part syntax. Prolog uses the exclamation point ! to denote the cut operation. When executed, a cut clears all previous backtracking points within the current predicate. For example,

         > (<-- (parent ?x)
                (parent ?x ?)
                !)

defines a predicate that tests whether the argument person a parent, but if so succeeds only once. The ! is traditional Prolog notation, but AllegroGraph uses the ! character as a reader macro to create a future part, so the above definition will signal a read error when the AllegroGraph readtable is in effect (see the !-reader macro section).

The simplest way to resolve this is to preface the Prolog ! with a backslash in any code that might be read with the AllegroGraph readtable in effect. The backslash suppresses any reader macro for the following character. This adds minimal clutter to the source code, and is completely harmless even when the AllegroGraph readtable is not in effect.

         > (<-- (is-a-parent ?x)
                (parent ?x ?)
                \!)

Be aware that sometimes names with syntax parent/2 will appear in Prolog documentation and in the debugger. The portion of the name is the predicate name -- also called a functor and the same as the Lisp symbol naming the predicate. The non-negative integer after the slash is the arity, which is the number of arguments to the predicate. Two predicates with the same functor but different arity are completely unrelated to one another. In the example above the predicate parent/1 has no relation to the parent/2 predicate defined earlier in this document and which it calls.