Logic programming - piotr-yuxuan/PoC GitHub Wiki

A lot of people have originated, comprehended and explained logic or constraint programming better than what I could ever do. However, here is a short example to show how mind-quakingly powerful can this be.

Let's say we start with the following state:

(def my-state
  {:positions {:white ['(queen [5 5] [1 2] nil)
                       '(rook [2 2])
                       '(pawn [3 2] nil)
                       '(pawn [4 2])]
               :black ['(king [1 7] nil)
                       '(bishop [2 7])
                       '(pawn [3 7])
                       '(pawn [4 7])]}
   :history []
   :player :white})

We want to provide tools to retrieve the following information:

  • Given this state, what are the locations of all pieces?
  • Given this state and a colour, what are the locations of all the pieces of that colour?
  • Given this state and a location, what is the type of the piece there?
  • Given this state and a position, what is the colour of the piece there?

Without logic programming, it would be straightforward to write a function to perform each task. Thus, you could have something like:

(declare all-positions-from-state
         positions-from-state-colour
         type-from-state-position
         colour-from-state-position)

(defn positions-from-state-colour
  [state colour]
  (reduce #(let [position (last %2)]
             (if position
               (assoc % position)
               %))
          '()
          (get-in initial-state [:positions colour]))

;; and so forth

However, functions would look basically the same because they deal with the same data. What if we could lay down some rules governing the way this data is made and reason about them? Logic programming grants you this ability:

(defn state->type-colour-position-o
  "Constraints such as colour is the colour of the piece at [x y] in the
  given state. At least one of the following symbol should refer to a
  logical variable: type, colour, position."
  [state type colour position]
  (fresh [tail item temp]
    (membero [colour tail] (vec (:positions state)))
    (membero item tail)
    (firsto item type)
    (lasto position item))

The vowel o at the end of the name usually denotes a logic-based function. This one takes the state as a fact; other arguments can be either logic variables either regular ones. Clojure dynamic typing allows that kind of marvel, yeah.

The logical rules (or goals, as core.logic calls them) can be explained that way:

  • (fresh [tail item temp]… defines new logic variables. They are free to take any value and they will be given some rules.
  • (membero [colour tail] (vec (:positions state))) means each element of (:positions state) is a vector of two items: the first former is called colour and the latter is tail.
  • (membero item tail) expresses item as any element of the tail.
  • (firsto item type) refers to the first element of each item as type.
  • (lasto position item) whilst the last element is position. lasto is not a built-in function but it's easy to define.

Once these rules have been uttered, one can give them all they know and ask them for what they want. If you know nothing special about the data within the state but just want the position, define three new logic variables afresh and ask for the possible positions:

(let [[type colour position] (repeatedly 3 lvar)
      asked position]
  (distinct (run* [q]
              (state->type-colour-position-o my-state type colour position)
              (l/== q asked))))
;; => (nil [2 2] [4 2] [2 7] [3 7] [4 7])

The value nil shows up because it's amongst the available values the logic variable position can take.

To get the list of all types of pieces that haven't been captured yet, nil must be avoided: we keep this special value away from possible value of position by using negation as a failure constraint (nafc).

(let [[type colour position] (repeatedly 3 lvar)
      chosen type]
  (distinct (run* [q]
              (state->type-colour-position-o my-state type colour position)
              (nafc nilo position)
              (l/== q chosen))))
;; => (rook pawn bishop)

The Royals don't show up because they have been captured. Of course, this can not hapen in a real game. May God save the Queen.

Finally, what colour is the piece at [2 2] of? Just ask it:

(let [type (lvar)
      colour (lvar)
      position [2 2]
      chosen colour]
  (distinct (run* [q]
              (state->type-colour-position-o my-state type colour position)
              (l/== q chosen))))
;; => (:white)

To put it in a nutshell, logic programming let the programmer expresses constraints over the data it wants to manipulate. Where a traditionnal function is an arrow from arguments to result, a logic-based function is a relation between arguments and the arrow can be somehow flipped. Contrarily to regular functions which express how to process argument to get a result, logic programming defines what the result should be. It can be a bit puzzling at first but methinks it's way worth getting used to it!

⚠️ **GitHub.com Fallback** ⚠️