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 1: To import correctly the clojure.core.logic and clojure.test libraries, place the following use instructions at the top of your source file:

(use '[clojure.core.logic :rename {is logic-is}])
(use 'clojure.test)

NOTE 2: To run your code with the unit tests using Leiningen, at the terminal type:

lein exec -p logic.clj

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

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

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

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

(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
  (is (= [:yes]
         (run 1 [q] (converto 0 :zero) (== q :yes))))  
  (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))))
  (is (= []
         (run 1 [q] (converto 2 :one) (== q :yes))))
  (is (= []
         (run 1 [q] (converto 12 :twelve) (== q :yes))))         
  (is (= [7]
         (run 1 [q] (converto q :seven))))
  (is (= [:seven]
         (run 1 [q] (converto 7 q))))
  (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
  (is (= [:yes]
         (run 1 [q] (translateo [1 2 3] [:one :two :three]) (== q :yes))))
  (is (= []
         (run 1 [q] (translateo [1 2 3] [:one :two :four]) (== q :yes))))
  (is (= [:three]
         (run 1 [q] (translateo [1 2 3] [:one :two q]))))
  (is (= [[:four :five :six :seven :eight :nine]]
         (run 1 [q] (translateo [4 5 6 7 8 9] q))))
  (is (= [[1 2 0]]
         (run 1 [q] (translateo q [:one :two :zero]))))
  (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
  (is (= [:yes]
         (run 1 [q] (splito [] [] []) (== q :yes))))
  (is (= [:yes]
         (run 1 [q] (splito [:a] [:a] []) (== q :yes))))
  (is (= [:yes]
         (run 1 [q] (splito [:a :b] [:a] [:b]) (== q :yes))))
  (is (= [:yes]
         (run 1 [q] 
           (splito [:a :b :c :d :e :f] 
                   [:a :c :e] 
                   [:b :d :f]) 
           (== q :yes))))
  (is (= [:yes]
         (run 1 [q] 
           (splito [:a :b :c :d :e :f :g] 
                   [:a :c :e :g] 
                   [:b :d :f]) 
           (== q :yes))))
  (is (= [[[:a :c :e] [:b :d :f]]]
         (run 1 [q1 q2] (splito [:a :b :c :d :e :f] q1 q2))))
  (is (= [[:a :b :c :d :e :f :g]]
         (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]]]
         (run 7 [q1 q2 q3] (splito q1 q2 q3)))))

Deliverables

✔ Upload Instructions

Deliver a single file called logic.clj containing your solutions and the unit tests. Please provide the following information:

Request PIN

Only one team member needs to upload the file.

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

;----------------------------------------------------------
; Activity: MiniKanren
; Date: May 2, 2016.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Due date is Monday, May 2.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
10	The program contains syntax errors.
DA	The program was plagiarized.
10-100	Depending on the amount of exercises that were solved correctly.

Programming Languages