Clojure core.logic : nafc and ground

Question

I'm representing a simple data-base in Clojure's core.logic.

There are two predicates : page(p) and link(p,q).

page(p) represents the existence of pages in a wiki called p

link(p,q) represents that page p contains a link to page q.

I'm now trying to query this database to find

• a) broken links (that is links in page p, for which there's no page q), and
• b) orphaned pages (pages that have no links to them)

My code for these queries is this :

(defn broken-links []
  (pldb/with-db @facts
    (logic/run* [p q]
      (link p q)
      (logic/nafc page q)
      )))

(defn orphans []
  (pldb/with-db @facts
    (logic/run* [p q]
      (logic/nafc link p q)
      (page q)
      )))

broken-links is working as expected, but orphans is giving me a list of :- symbols.

I'm assuming that this has something to do with nafc's limitation. According to the documentation :

EXPERIMENTAL: negation as failure constraint. All arguments to the goal c must be ground. If some argument is not ground the execution of this constraint will be delayed.

And these are "delayed" because they are not "ground".

Can someone explain what ground really means here. I know it's "has no free variables" but I still don't really understand what that means in this context.

Secondly, how should I write this orphans query?

Answer 1

In the context of nafc, non-ground inputs are handled by giving non-ground outputs, so to get meaningful answers your inputs "must be ground." It cannot negate a constraint involving non-ground values.

For example, this program gives all possible values of q where q satisfies emptyo:

(run* [q]
  (emptyo q))
;=> (())

If we ask for all possible values of q that don't satisfy emptyo we get this:

(run* [q]
  (nafc emptyo q))
;=> ((_0 :- (clojure.core.logic/nafc #object[clojure.core.logic$emptyo 0x212442c1 "clojure.core.logic$emptyo@212442c1"] _0)))

A simplified phrasing is ((_0 :- (nafc emptyo _0))), which means there's only one answer but it could be any value that satisfies the RHS constraint. The logic program can't give us ground values because it doesn't know every possible non-empty list.

Here's an example DB setup for completeness:

(pldb/db-rel page q)
(pldb/db-rel link p q)
(def facts
  (pldb/db
    [page 'a]
    [page 'b]
    [page 'z]
    [link 'a 'b]
    [link 'b 'c]))

And your working broken-link program:

;; find links to non-pages
(pldb/with-db facts
  (run* [p q]
    (link p q)
    (nafc page q)))
;=> ([b c])

Here's a way to write the orphaned page program:

;; find pages without incoming links
(pldb/with-db facts
  (run* [q]
    (fresh [p]
      (page q)
      (conda
        [(link p q) fail]
        [succeed]))))
;=> (a z)

The negation here is expressed with conda to form a kind of if-else logic: if there is a link to page q we fail else we succeed.

Also note the use of fresh to introduce a logic variable p that isn't part of the desired answer output, since we only care about orphaned page values.