Problem Set: MiniKanren

Objectives

During this activity, students should be able to:

Write simple logic functions using the Clojure programming language and the MiniKanren library.

This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

Activity Description

This activity can be developed individually or in pairs.

Solve the following set of relational programming exercises using Clojure and the core.logic library (Clojure’s implementation of MiniKanren). Place all your functions and unit tests in a file called minikanren.clj.

Note:

To import correctly all the required libraries, place the following use and require instructions at the top of your source file:

(use 'clojure.test)
(require '[clojure.core.logic :as l])
(require '[clojure.core.logic.fd :as fd])

(removeo x lst result): This logic function succeeds if it’s able to remove the first occurrence of x from lst giving result. Unit tests:

(deftest test-removeo
  (is (= [[:b :c :d :e]]
         (l/run 1 [q]
           (removeo :a [:a :b :c :d :e] q))))
  (is (= [[:a :b :d :e]]
         (l/run 1 [q]
           (removeo :c [:a :b :c :d :e] q))))
  (is (= [:d]
         (l/run 1 [q]
           (removeo q [:a :b :c :d :e] [:a :b :c :e]))))
  (is (= []
         (l/run 1 [q]
           (removeo :x [:a :b :c :d :e] q))))
  (is (= [[:x :a :b :c :d :e]
          [:a :x :b :c :d :e]
          [:a :b :x :c :d :e]
          [:a :b :c :x :d :e]
          [:a :b :c :d :x :e]
          [:a :b :c :d :e :x]]
         (l/run 6 [q]
           (removeo :x q [:a :b :c :d :e]))))
  (is (= [[:a [:b :c :d :e]]
          [:b [:a :c :d :e]]
          [:c [:a :b :d :e]]
          [:d [:a :b :c :e]]
          [:e [:a :b :c :d]]]
         (l/run* [q1 q2]
           (removeo q1 [:a :b :c :d :e] q2)))))

(palindromeo lst): This logic function succeeds if lst is a palindrome list (it reads the same from left to right than from right to left). Unit tests:

(deftest test-palindromeo
  (is (= [:yes]
         (l/run 1 [q]
           (palindromeo [])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (palindromeo [:a])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (palindromeo [:a :b :c :b :a])
           (l/== q :yes))))
  (is (= []
         (l/run 1 [q]
           (palindromeo [:a :b :c :d])
           (l/== q :yes))))
  (is (= '[[]
           [_0]
           [_0 _0]
           [_0 _1 _0]
           [_0 _1 _1 _0]
           [_0 _1 _2 _1 _0]
           [_0 _1 _2 _2 _1 _0]]
         (l/run 7 [q]
           (palindromeo q)))))

(rotateo lst result): This logic function succeeds when lst is rotated left one position giving result. In other words, the first element of lst becomes the last element of result. Unit tests:

(deftest test-rotateo
  (is (= [:yes]
         (l/run 1 [q]
           (rotateo [:a :b :c :d :e]
                    [:b :c :d :e :a])
           (l/== q :yes))))
  (is (= []
         (l/run 1 [q]
           (rotateo [:a :b :c :d :e]
                    [:a :b :c :d :e])
           (l/== q :yes))))
  (is (= []
         (l/run 1 [q]
           (rotateo [] q))))
  (is (= [[:a]]
         (l/run 1 [q]
           (rotateo [:a] q))))
  (is (= [[:b :c :d :e :a]]
         (l/run 1 [q]
           (rotateo [:a :b :c :d :e] q))))
  (is (= [[:e :a :b :c :d]]
         (l/run 1 [q]
           (rotateo q [:a :b :c :d :e]))))
  (is (= '[[[_0] [_0]]
           [[_0 _1] [_1 _0]]
           [[_0 _1 _2] [_1 _2 _0]]
           [[_0 _1 _2 _3] [_1 _2 _3 _0]]
           [[_0 _1 _2 _3 _4] [_1 _2 _3 _4 _0]]
           [[_0 _1 _2 _3 _4 _5] [_1 _2 _3 _4 _5 _0]]
           [[_0 _1 _2 _3 _4 _5 _6] [_1 _2 _3 _4 _5 _6 _0]]]
         (l/run 7 [q1 q2]
           (rotateo q1 q2)))))

(evensizeo lst) and (oddsizeo lst): These two logic functions should be defined in a mutually recursive fashion. That is, each one should be defined in terms of the other one. These functions succeed if the number of elements in lst is even or odd, respectively.

Tip: Remember to use the declare macro to indicate that a certain function can be called before it’s actually defined. This is necessary whenever you define mutually recursive functions.

Unit tests:

(deftest test-evensizeo-oddsizeo
  (is (= [:yes]
         (l/run 1 [q]
           (evensizeo [])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (oddsizeo [:x])
           (l/== q :yes))))
  (is (= []
         (l/run 1 [q]
           (evensizeo [:x])
           (l/== q :yes))))
  (is (= []
         (l/run 1 [q]
           (oddsizeo [])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (evensizeo [:a :b :c :d :e :f])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (oddsizeo [:a :b :c :d :e])
           (l/== q :yes))))
  (is (= '[[]
           [_0 _1]
           [_0 _1 _2 _3]
           [_0 _1 _2 _3 _4 _5]
           [_0 _1 _2 _3 _4 _5 _6 _7]]
         (l/run 5 [q]
           (evensizeo q))))
  (is (= '[[_0]
           [_0 _1 _2]
           [_0 _1 _2 _3 _4]
           [_0 _1 _2 _3 _4 _5 _6]
           [_0 _1 _2 _3 _4 _5 _6 _7 _8]]
         (l/run 5 [q]
           (oddsizeo q)))))

(splito lst a b): This logic function succeeds when splitting lst gives a and b. The first, third, fifth, etc. elements of lst go to a, while the second, fourth, sixth, etc. elements go to b. Unit tests:

(deftest test-splito
  (is (= [:yes]
         (l/run 1 [q]
           (splito [] [] [])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (splito [:a] [:a] [])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (splito [:a :b] [:a] [:b])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (splito [:a :b :c :d :e :f]
                   [:a :c :e]
                   [:b :d :f])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (splito [:a :b :c :d :e :f :g]
                   [:a :c :e :g]
                   [:b :d :f])
           (l/== q :yes))))
  (is (= [[[:a :c :e] [:b :d :f]]]
         (l/run 1 [q1 q2]
           (splito [:a :b :c :d :e :f] q1 q2))))
  (is (= [[:a :b :c :d :e :f :g]]
         (l/run 1 [q]
           (splito q [:a :c :e :g] [:b :d :f]))))
  (is (= '[[[] [] []]
           [[_0] [_0] []]
           [[_0 _1] [_0] [_1]]
           [[_0 _1 _2] [_0 _2] [_1]]
           [[_0 _1 _2 _3] [_0 _2] [_1 _3]]
           [[_0 _1 _2 _3 _4] [_0 _2 _4] [_1 _3]]
           [[_0 _1 _2 _3 _4 _5] [_0 _2 _4] [_1 _3 _5]]]
         (l/run 7 [q1 q2 q3]
           (splito q1 q2 q3)))))

(equalo lst): This logic function succeeds if all the elements contained in lst unify to the same value, otherwise fails. The function should always succeed if lst is empty or has only one element. Unit tests:

(deftest test-equalo
  (is (= [:yes]
         (l/run 1 [q]
           (equalo [])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (equalo [:x])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (equalo [:x :x])
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (equalo [:x :x :x :x :x])
           (l/== q :yes))))
  (is (= [:x]
         (l/run 1 [q]
           (equalo [:x :x q :x]))))
  (is (= '[_0]
         (l/run 1 [q]
           (equalo [q q q q q q]))))
  (is (= '([_0 _0 _0 _0 _0])
         (l/run 1 [q1 q2 q3 q4 q5]
           (equalo [q1 q2 q3 q4 q5]))))
  (is (= []
         (l/run 1 [q]
           (equalo [:x :y])
           (l/== q :yes))))
  (is (= []
         (l/run 1 [q1 q2]
           (equalo [q1 q1 q2 q1 q1])
           (l/!= q1 q2))))
  (is (= '([]
           [_0]
           [_0 _0]
           [_0 _0 _0]
           [_0 _0 _0 _0]
           [_0 _0 _0 _0 _0]
           [_0 _0 _0 _0 _0 _0])
         (l/run 7 [q]
           (equalo q)))))

(counto lst result): This logic function unifies result with the number of elements contained in lst. Unit tests:

(deftest test-counto
  (is (= [0]
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto [] q))))
  (is (= [1]
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto [:a] q))))
  (is (= [2]
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto [:a :b] q))))
  (is (= [3]
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto [:a :b :c] q))))
  (is (= [10]
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto (repeat 10 :x) q))))
  (is (= '([_0])
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto q 1))))
  (is (= '([_0 _1 _2 _3 _4])
         (l/run 1 [q]
           (fd/in q (fd/interval 0 10))
           (counto q 5))))
  (is (= '([[] 0]
           [(_0) 1]
           [(_0 _1) 2]
           [(_0 _1 _2) 3]
           [(_0 _1 _2 _3) 4]
           [(_0 _1 _2 _3 _4) 5]
           [(_0 _1 _2 _3 _4 _5) 6])
         (l/run 7 [q1 q2]
           (fd/in q1 q2 (fd/interval 0 10))
           (counto q1 q2)))))

(facto n result): This logic function succeeds if the factorial of n is equal to result. Mathematically, the factorial of an integer number n greater or equal to zero can be defined recursively as follows:

Unit tests:

(deftest test-facto
  (is (= [1]
         (l/run 1 [q]
           (facto 0 q))))
  (is (= [1]
         (l/run 1 [q]
           (facto 1 q))))
  (is (= [720]
         (l/run 1 [q]
           (facto 6 q))))
  (is (= [2432902008176640000]
         (l/run 1 [q]
           (facto 20 q))))
  (is (= [0 1]
         (l/run 2 [q]
           (facto q 1))))
  (is (= [5]
         (l/run 1 [q]
           (facto q 120))))
  (is (= [10]
         (l/run 1 [q]
           (facto q 3628800))))
  (is (= [:yes]
         (l/run 1 [q]
           (facto 4 24)
           (l/== q :yes))))
  (is (= [:yes]
         (l/run 1 [q]
           (facto 15 1307674368000)
           (l/== q :yes))))
  (is (= [[0 1]
          [1 1]
          [2 2]
          [3 6]
          [4 24]
          [5 120]
          [6 720]
          [7 5040]
          [8 40320]
          [9 362880]]
         (l/run 10 [n r]
           (facto n r)))))

(powo base exp result): This logic function succeeds if base raised to the power exp is equal to result.

Tip: If you use fresh variables in your function, make sure to define their finite domains (using an interval between 0 and 100) like this:

(l/fresh [temp]
  (fd/in temp (fd/interval 0 100))
  ...)

Unit tests:

(deftest test-powo
  (is (= [:yes]
         (l/run 1 [q]
           (powo 3 2 9)
           (l/== q :yes))))
  (is (= [32]
         (l/run 1 [q]
           (powo 2 5 q))))
  (is (= [5]
         (l/run 1 [q]
           (powo q 2 25))))
  (is (= [3]
         (l/run 1 [q]
           (powo 2 q 8))))
  (is (= [1]
         (l/run 1 [q]
           (powo q q q))))
  (is (= #{[64 1] [8 2] [4 3] [2 6]}
         (set
           (l/run* [a b]
             (powo a b 64)))))
  (is (= '[_0]
         (l/run 1 [q]
           (powo q 0 1))))
  (is (= (set (range 101))
         (set
           (l/run* [q]
             (fd/in q (fd/interval 0 100))
             (powo q 1 q))))))

(rangeo start end result): This logic function unifies result with a sequence of incremental integers from start to end (inclusive). Unit tests:

(deftest test-rangeo
  (is (= [[3 4 5 6 7 8 9 10]]
         (l/run 1 [q]
           (rangeo 3 10 q))))
  (is (= [[7]]
         (l/run 1 [q]
           (rangeo 7 7 q))))
  (is (= [[]]
         (l/run 1 [q]
           (rangeo 10 1 q))))
  (is (= [6]
         (l/run 1 [q]
           (fd/in q (fd/interval 1 10))
           (rangeo 2 q [2 3 4 5 6]))))
  (is (= [[2 6]]
         (l/run 1 [q1 q2]
           (fd/in q1 q2 (fd/interval 1 10))
           (rangeo q1 q2 [2 3 4 5 6]))))
  (is (= #{[]
           [1] [1 2] [1 2 3] [1 2 3 4]
           [2] [2 3] [2 3 4]
           [3] [3 4]
           [4]}
         (set
           (l/run* [q]
             (l/fresh [start end]
               (fd/in start end (fd/interval 1 4))
               (rangeo start end q)))))))

Deliverables

The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

;----------------------------------------------------------
; Problem Set: MiniKanren
; Date: November 25, 2018.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Also, each function should include a documentation string (docstring) with a brief description of its behavior. For example:

(defn max2
  "Returns the largest of the two numbers x and y."
  [x y]
  (if (> x y) x y))

Upload Instructions

To deliver the minikanren.clj file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Sunday, November 25.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
-30	A docstring is missing in one or more functions.
10	The program contains syntax errors.
1	The program was plagiarized in whole or in part.
10-100	Depending on the amount of exercises that were solved correctly.