Functional Patterns in a Logic Language

Posted on January 3, 2016 by Josh

Purpose

This isn’t a primer in core.logic, but instead supposed to pique the reader’s interest in the alien world of logic programming.

To do so, I’ll translate the functions map, filter, and reduce into their relational counterparts.

A Motivating Example

Imagine you need to inspect all lists of numbers that simultaneously sum to 42, and multiply to 152. How many lines of code would that take you to write that?

Here’s the relational version of the solution, simplified (barely).

(run* [q]
  ;; find all lists that sum to 42 and multiply to 152
  (reduceo + 0 q 42)
  (reduceo * 1 q 152)) 
  
  ;; => ([4 38] [38 4] [2 2 38] [2 38 2] [38 2 2])

So there are 5 lists that qualify.

A Crazier Example: Quines

A quine is a program that, when evaluated, returns it’s own source code. These are tougher than you’d think to find, but they exist in most languages.

William E. Byrd is a logic machine and wrote an interesting paper detailing a program which finds quines, and the more complex twines, and thrines.

Here’s the entire program for finding all possible (infinite?) quines in a lisp language:

(run* [q] (eval-expo q '() q))

So, it finds all programs q that when evaluated in the “empty environment” ('()), return q.

Details for my reduceo example

reduce is a useful function for compressing lists down into something.

ex: (reduce + 0 [1 2 3]) ;; => 6

A function takes inputs and returns an output.

A relation however can be viewed as a set of all inputs-output tuples that are related according to some relationship.

consider: (reduceo + 0 _ 6) (notice reduceo doesn’t return anything, the _ is pseudo-syntax of a “hole” to be filled, and the 6 is just part of the relationship)

lists that fill the hole and satisfy the relation: ([6], [1 5], [1 1 1 1 1 1], [1 2 3], ...)

Wow. And I thought functional practices were declarative. With core.logic, you really just describe your problem and get back answers.

Note:

You may notice that clojure’s stock + is a function, which is incompatible with this relations-based language. My motivating example uses not the function +, but the similar relationship + from clojure.core.logic.fd, which looks kind of like this: (fd/+ a b answer).

The Guts

I think the code is fairly simple to read through if you understand the basics of core.logic, but please let me know if there’s something I need to clarify! You should be able to copy-paste this and play around with it!

You’ll notice, I wrote functions reducef, mapf, filterf, this is a re-implementation of the core functions, which allowed me to better understand how the relational version needed to be built, and I left them in so that my readership can appreciate the similarities and differences.

disclaimer: I’m a logic noob, so you’ll probably find a lot you’d like to change, point it out and I’ll fix it!

(ns clj-scratch.core-logic
  (:require [clojure.core.logic :refer :all]
            [clojure.core.logic.fd :as fd]))

;; A couple useful relations for playing around with things ----------

(defn inco [x a]
  (fd/+ 1 x a))

(defn eveno [n]
  (fresh [a]
    (conde
     [(== 0 n)]
     [(fd/+ 2 a n)
      (eveno a)])))


;; REDUCE ----------

(defn reducef [f base coll]
  (if (empty? coll)
    base
    (reducef f
             (f base (first coll))
             (rest coll))))

(reducef + 0 [1 2 3]) ;; => 6

(defn reduceo [relo base coll answer]
  (conde
   [(emptyo coll) (== answer base)]
   [(fresh [new-coll new-base fst]
      (firsto coll fst)
      (resto coll new-coll)
      (relo base fst new-base)
      (reduceo relo new-base new-coll answer))]))

(run 10 [q]
  (reduceo fd/+ 42 [1 2 3 q] 52)) ;; => (4)
(run 10 [q]
  (reduceo fd/+ 42 [1 2 3 4] q))  ;; => (52)
(run 10 [q]
  (reduceo fd/+ q [1 2 3 4] 52))  ;; => (42)

;; MAP ----------

(defn mapf [f coll]
  (reducef (fn [m x] (conj m (f x))) [] coll))

(mapf inc [1 2 3]) ;; => [2 3 4]

(defprotocol Mapo
  (mapo-helper [coll relo answer]))

(extend-protocol Mapo
  clojure.lang.PersistentVector
  (mapo-helper [coll relo answer] 
    (reduceo (fn [coll x new-coll]
               (fresh [x2]
                 (relo x x2)
                 (conjo coll x2 new-coll)))
             [] coll answer)))

(defn mapo
  "flips `coll` to first position, so `extend-protocol` can dispatch
  on it"
  [relo coll answer]
  (mapo-helper coll relo answer))

(run 10 [q]
  (mapo inco [1 2 3 4] q)) ;; => ([2 3 4 5])
(run 10 [q]
  (mapo inco [1 2 3 q] [2 3 4 5])) ;; => (4)

;; FILTER ----------

(defn filterf [f coll]
  (reducef (fn [coll x] (if (f x)
                          (conj coll x)
                          coll))
           []
           coll))

(filterf even? (range 10)) ;; => [0 2 4 6 8]

(defprotocol Filtero
  (filtero-helper [coll relo answer]))
(extend-protocol Filtero
    clojure.lang.PersistentVector
    (filtero-helper [coll relo answer]
      (reduceo (fn [coll x new-coll]
                 (condu
                  [(relo x)
                   (conjo coll x new-coll)]
                  [(== coll new-coll)]))
               [] coll answer)))
(defn filtero [relo coll answer]
  (filtero-helper coll relo answer))

(run 10 [q]
  (filtero eveno [1 2 3 4 5 6] q)) ;; ([2 4 6])

      
;; That Cool example ----------
;;   notice that to help out `run`, I constrain 
;;   my answer-space a bit

(run 10 [q]
  ;; constrain the answers to lists of length 2 or 3
  ;; and ints of range 0-1000
  (fresh [x y z]
    (conde [(== q [x y])]
           [(== q [x y z])])
    (fd/in x y z (fd/interval 0 1000)))

  ;; find all lists that sum to 42 and multiply to 152
  (reduceo fd/+ 0 q 42)
  (reduceo fd/* 1 q 152))