Problem Set: MiniKanren

Objectives

During this activity, students should be able to:

Write simple logic functions using the Clojure programming language and the core.logic 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 logic.clj.

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

(use '[clojure.test :rename {is test-is}])
(use '[clojure.core.logic :rename {== ===}])
(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
  (test-is (= [[:b :c :d :e]]
              (run 1 [q] (removeo :a [:a :b :c :d :e] q))))
  (test-is (= [[:a :b :d :e]]
              (run 1 [q] (removeo :c [:a :b :c :d :e] q))))
  (test-is (= [:d]
              (run 1 [q] 
                (removeo q [:a :b :c :d :e] [:a :b :c :e]))))
  (test-is (= []
              (run 1 [q] (removeo :x [:a :b :c :d :e] q))))
  (test-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]]
              (run 6 [q] (removeo :x q [:a :b :c :d :e]))))
  (test-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]]]
              (run* [q1 q2]
                (removeo q1 [:a :b :c :d :e] q2)))))

(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
  (test-is (= [:yes]
              (run 1 [q]
                (rotateo [:a :b :c :d :e]
                         [:b :c :d :e :a])
                (=== q :yes))))
  (test-is (= []
              (run 1 [q]
                (rotateo [:a :b :c :d :e]
                         [:a :b :c :d :e])
                (=== q :yes))))
  (test-is (= []
              (run 1 [q] (rotateo [] q))))
  (test-is (= [[:a]]
              (run 1 [q] (rotateo [:a] q))))
  (test-is (= [[:b :c :d :e :a]]
              (run 1 [q] (rotateo [:a :b :c :d :e] q))))
  (test-is (= [[:e :a :b :c :d]]
              (run 1 [q] (rotateo q [:a :b :c :d :e]))))
  (test-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]]]
              (run 7 [q1 q2] (rotateo q1 q2)))))

(evensizeo lst) and (oddsizeo lst): These two mutually recursive logic functions succeed if the number of elements in lst is even or odd, respectively. Unit tests:

(deftest test-evensizeo-oddsizeo
  (test-is (= [:yes]
              (run 1 [q] (evensizeo []) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] (oddsizeo [:x]) (=== q :yes))))
  (test-is (= []
              (run 1 [q] (evensizeo [:x]) (=== q :yes))))
  (test-is (= []
              (run 1 [q] (oddsizeo []) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] 
                (evensizeo [:a :b :c :d :e :f]) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] 
                (oddsizeo [:a :b :c :d :e]) (=== q :yes))))
  (test-is (= '[[]
                [_0 _1]
                [_0 _1 _2 _3]
                [_0 _1 _2 _3 _4 _5]
                [_0 _1 _2 _3 _4 _5 _6 _7]]
              (run 5 [q] (evensizeo q))))
  (test-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]]
              (run 5 [q] (oddsizeo q)))))

(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
  (test-is (= [:yes]
              (run 1 [q] (palindromeo []) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] (palindromeo [:a]) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] 
                (palindromeo [:a :b :c :b :a]) (=== q :yes))))
  (test-is (= []
              (run 1 [q] 
                (palindromeo [:a :b :c :d]) (=== q :yes))))
  (test-is (= '[[]
                [_0]
                [_0 _0]
                [_0 _1 _0]
                [_0 _1 _1 _0]
                [_0 _1 _2 _1 _0]
                [_0 _1 _2 _2 _1 _0]]
              (run 7 [q] (palindromeo q)))))

(converto d k): This logic function succeeds when digit d corresponds to the keyword k (for example digit 7 with keyword :seven). Unit tests:

(deftest test-converto
  (test-is (= [:yes]
              (run 1 [q] (converto 0 :zero) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q]
                (converto 0 :zero)
                (converto 1 :one)
                (converto 2 :two)
                (converto 3 :three)
                (converto 4 :four)
                (converto 5 :five)
                (converto 6 :six)
                (converto 7 :seven)
                (converto 8 :eight)
                (converto 9 :nine)
                (=== q :yes))))
  (test-is (= []
              (run 1 [q] (converto 12 :twelve) (=== q :yes))))
  (test-is (= [7]
              (run 1 [q] (converto q :seven))))
  (test-is (= [:seven]
              (run 1 [q] (converto 7 q))))
  (test-is (= [[1 :two 3]]
              (run 1 [q1 q2 q3]
                (converto q1 :one)
                (converto 2 q2)
                (converto q3 :three)))))

(translateo lst result): This logic function succeeds when all digits contained in lst are converted to their corresponding keywords (using the converto logic function from the previous problem) giving result. Unit tests:

(deftest test-translateo
  (test-is (= [:yes]
              (run 1 [q] 
                (translateo [1 2 3] [:one :two :three]) 
                (=== q :yes))))
  (test-is (= []
              (run 1 [q] 
                (translateo [1 2 3] [:one :two :four]) 
                (=== q :yes))))
  (test-is (= [:three]
              (run 1 [q] (translateo [1 2 3] [:one :two q]))))
  (test-is (= [[:four :five :six :seven :eight :nine]]
              (run 1 [q] (translateo [4 5 6 7 8 9] q))))
  (test-is (= [[1 2 0]]
              (run 1 [q] (translateo q [:one :two :zero]))))
  (test-is (= [[[] []]]
              (run 1 [q1 q2] (translateo q1 q2)))))

(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
  (test-is (= [:yes]
              (run 1 [q] (splito [] [] []) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] (splito [:a] [:a] []) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] 
                (splito [:a :b] [:a] [:b]) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q]
                (splito [:a :b :c :d :e :f]
                        [:a :c :e]
                        [:b :d :f])
                (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q]
                (splito [:a :b :c :d :e :f :g]
                        [:a :c :e :g]
                        [:b :d :f])
                (=== q :yes))))
  (test-is (= [[[:a :c :e] [:b :d :f]]]
              (run 1 [q1 q2] 
                (splito [:a :b :c :d :e :f] q1 q2))))
  (test-is (= [[:a :b :c :d :e :f :g]]
              (run 1 [q] (splito q [:a :c :e :g] [:b :d :f]))))
  (test-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]]]
              (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
  (test-is (= [:yes]
              (run 1 [q] (equalo []) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] (equalo [:x]) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] (equalo [:x :x]) (=== q :yes))))
  (test-is (= [:yes]
              (run 1 [q] 
                (equalo [:x :x :x :x :x]) (=== q :yes))))
  (test-is (= [:x]
              (run 1 [q] (equalo [:x :x q :x]))))
  (test-is (= '[_0]
              (run 1 [q] (equalo [q q q q q q]))))
  (test-is (= '([_0 _0 _0 _0 _0])
              (run 1 [q1 q2 q3 q4 q5] 
                (equalo [q1 q2 q3 q4 q5]))))
  (test-is (= []
              (run 1 [q] (equalo [:x :y]) (=== q :yes))))
  (test-is (= []
              (run 1 [q1 q2] 
                (equalo [q1 q1 q2 q1 q1]) (!= q1 q2))))
  (test-is (= '([]
                [_0]
                [_0 _0]
                [_0 _0 _0]
                [_0 _0 _0 _0]
                [_0 _0 _0 _0 _0]
                [_0 _0 _0 _0 _0 _0])
              (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
  (test-is (= [0]
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto [] q))))
  (test-is (= [1]
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto [:a] q))))
  (test-is (= [2]
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto [:a :b] q))))
  (test-is (= [3]
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto [:a :b :c] q))))
  (test-is (= [10]
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto (repeat 10 :x) q))))
  (test-is (= '([_0])
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto q 1))))
  (test-is (= '([_0 _1 _2 _3 _4])
              (run 1 [q]
                (fd/in q (fd/interval 0 10))
                (counto q 5))))
  (test-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])
              (run 7 [q1 q2]
                (fd/in q1 q2 (fd/interval 0 10))
                (counto q1 q2)))))

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

(deftest test-rangeo
  (test-is (= [[3 4 5 6 7 8 9 10]]
              (run 1 [q]
                (rangeo 3 10 q))))
  (test-is (= [[7]]
              (run 1 [q]
                (rangeo 7 7 q))))
  (test-is (= [[]]
              (run 1 [q]
                (rangeo 10 1 q))))
  (test-is (= [6]
              (run 1 [q]
                (fd/in q (fd/interval 1 10))
                (rangeo 2 q [2 3 4 5 6]))))
  (test-is (= [[2 6]]
              (run 1 [q1 q2]
                (fd/in q1 q2 (fd/interval 1 10))
                (rangeo q1 q2 [2 3 4 5 6]))))
  (test-is (= #{[]
                [1] [1 2] [1 2 3] [1 2 3 4]
                [2] [2 3] [2 3 4]
                [3] [3 4]
                [4]}
              (set
                (run* [q]
                  (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 26, 2017.
; 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 logic.clj file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Thursday, September 7.

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.