
;;;Carin Meier (2016)
;;;One Fish Spec Fish
;;;Squid's Blog
;;;http://gigasquidsoftware.com/blog/2016/05/29/one-fish-spec-fish/
;;;https://github.com/gigasquid/genetic-programming-spec



(defproject genetic-programming-spec "0.1.0-SNAPSHOT"
  :description "FIXME: write description"
  :url "http://example.com/FIXME"
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :dependencies [[org.clojure/clojure "1.9.0-alpha17"]
                 [org.clojure/test.check "0.9.0"] ])


================================================


;;;;Spec tutorial:
;;; Specifications for functions that enable tests and data-code  generation


(ns genetic-programming-spec.tutorial
  (:require [clojure.set :as set]
            [clojure.spec.alpha :as s]
            [clojure.walk :as walk]
            [clojure.spec.test.alpha :as stest]))



(def fish-numbers {0 "Zero"
                   1 "One"
                   2 "Two"})

(s/def ::fish-number (set (keys fish-numbers)))
(set (keys fish-numbers));#{0 1 2}
(s/valid? ::fish-number 1) ; true
(s/valid? ::fish-number 5) ; false


(s/explain ::fish-number 5)
;;val: 5 fails spec: :genetic-programming-spec.tutorial/fish-number 
;;predicate: (set (keys fish-numbers))
;;:clojure.spec.alpha/spec  :genetic-programming-spec.tutorial/fish-number
;;:clojure.spec.alpha/value  5


;Specifications are added in the form of predicates
(s/def ::color #{"Red" "Blue" "Dun"})
(s/def ::first-line (s/cat :n1 ::fish-number :n2 ::fish-number :c1 ::color :c2 ::color))
(s/explain ::first-line  [1 2 "Red" "Black"])
;; In: [3] val: "Black" fails spec: :genetic-programming-spec.tutorial/color at: 
;; [:c2] predicate: #{"Blue" "Dun" "Red"}
;; :clojure.spec.alpha/spec  :genetic-programming-spec.tutorial/first-line
;; :clojure.spec.alpha/value  [1 2 "Red" "Black"]

;0 1 is allowed, 1 0 not.
(defn one-bigger? [{:keys [n1 n2]}]
  (= n2 (inc n1)))

;numbers must match a series, colors must be different
(s/def ::first-line (s/and (s/cat :n1 ::fish-number :n2 ::fish-number 
                                  :c1 ::color :c2 ::color)
                           one-bigger?
                           #(not= (:c1 %) (:c2 %))))

(s/valid? ::first-line [1 2 "Red" "Blue"]) ;true

;destructuring: who is what
(s/conform ::first-line [1 2 "Red" "Blue"])
;=> {:n1 1, :n2 2, :c1 "Red", :c2 "Blue"}

(s/valid? ::first-line [2 1 "Red" "Blue"]) ;=> false
(s/explain ::first-line [2 1 "Red" "Blue"])
;; val: {:n1 2, :n2 1, :c1 "Red", :c2 "Blue"} fails spec: 
;; :genetic-programming-spec.tutorial/first-line predicate: one-bigger?

(s/valid? ::first-line   [0 2 "Red" "Blue"]);false
(s/explain ::first-line  [0 2 "Red" "Blue"])
; val: {:n1 0, :n2 2, :c1 "Red", :c2 "Blue"} fails spec: 
; :genetic-programming-spec.tutorial/first-line predicate: one-bigger?
; :clojure.spec.alpha/spec  :genetic-programming-spec.tutorial/first-line
; :clojure.spec.alpha/value  [0 2 "Red" "Blue"]


(s/conform ::first-line  [0 2 "Red" "Blue"])
; :clojure.spec.alpha/invalid


;Data generation:
(s/exercise ::first-line 5)
(comment
;; output:
([(0 1 "Dun" "Blue")
  {:n1 0,
   :n2 1,
   :c1 "Dun",
   :c2 "Blue"}]
 [(0 1 "Blue" "Red")
  {:n1 0,
   :n2 1,
   :c1 "Blue",
   :c2 "Red"}]
 [(1 2 "Dun" "Red")
  {:n1 1, :n2 2, :c1 "Dun", :c2 "Red"}]
 [(0 1 "Dun" "Blue")
  {:n1 0,
   :n2 1,
   :c1 "Dun",
   :c2 "Blue"}]
 [(0 1 "Dun" "Blue")
  {:n1 0,
   :n2 1,
   :c1 "Dun",
   :c2 "Blue"}])
);end of comment


;Rhymes are added to the spec: two-> blue; one -> dun
(defn fish-number-rhymes-with-color? [{n :n2 c :c2}]
  (or
   (= [n c] [2 "Blue"])
   (= [n c] [1 "Dun"])))

;Putting all together
(s/def ::first-line (s/and (s/cat :n1 ::fish-number :n2 ::fish-number :c1 ::color :c2 ::color)
                           one-bigger?
                           #(not= (:c1 %) (:c2 %))
                           fish-number-rhymes-with-color?))

(s/valid? ::first-line [1 2 "Red" "Blue"]) ; true
(s/explain ::first-line [1 2 "Red" "Dun"])
;;  {:n1 1, :n2 2, :c1 "Red", :c2 "Dun"} fails spec:
;;  :genetic-programming-spec.tutorial/first-line predicate: 
;;  fish-number-rhymes-with-color?
;;  :clojure.spec.alpha/spec  :genetic-programming-spec.tutorial/first-line
;;  :clojure.spec.alpha/value  [1 2 "Red" "Dun"]


(s/exercise ::first-line)
;; output:
(comment
  (s/exercise ::first-line)
([(0 1 "Blue" "Dun")
  {:n1 0,
   :n2 1,
   :c1 "Blue",
   :c2 "Dun"}]
 [(1 2 "Red" "Blue")
  {:n1 1,
   :n2 2,
   :c1 "Red",
   :c2 "Blue"}]
 [(0 1 "Red" "Dun")
  {:n1 0, :n2 1, :c1 "Red", :c2 "Dun"}]
 [(0 1 "Red" "Dun")
  {:n1 0, :n2 1, :c1 "Red", :c2 "Dun"}]
 [(1 2 "Red" "Blue")
  {:n1 1,
   :n2 2,
   :c1 "Red",
   :c2 "Blue"}]
 [(1 2 "Red" "Blue")
  {:n1 1,
   :n2 2,
   :c1 "Red",
   :c2 "Blue"}]
 [(1 2 "Red" "Blue")
  {:n1 1,
   :n2 2,
   :c1 "Red",
   :c2 "Blue"}]
 [(0 1 "Red" "Dun")
  {:n1 0, :n2 1, :c1 "Red", :c2 "Dun"}]
 [(1 2 "Red" "Blue")
  {:n1 1,
   :n2 2,
   :c1 "Red",
   :c2 "Blue"}]
 [(0 1 "Red" "Dun")
  {:n1 0, :n2 1, :c1 "Red", :c2 "Dun"}])
  
);end of comment

;Poem builder
(defn fish-line [n1 n2 c1 c2]
  (clojure.string/join " "
    (map #(str % " fish.")
      [(get fish-numbers n1)
       (get fish-numbers n2)
       c1
       c2])))

(fish-line 0 1 "Red" "Dun")
;Zero fish. One fish. Red fish. Dun fish.

;We can specify that the args for the fish-line function be validated with ::first-line 
;and the return value is a string.
(s/fdef fish-line
        :args ::first-line
        :ret  string?)





;Instruments the vars 
(stest/instrument `fish-line)

(fish-line 1 2 "Red" "Blue")
; "One fish. Two fish. Red fish. Blue fish."


(fish-line 2 1 "Red" "Blue")

 ;output:
 (comment
   
  ExceptionInfo Call to #'genetic-programming-spec.tutorial/fish-line did not conform to spec:
val: {:n1 2, :n2 1, :c1 "Red", :c2 "Blue"} fails at: [:args] predicate: one-bigger?
:clojure.spec.alpha/spec  #object[clojure.spec.alpha$and_spec_impl$reify__875 0x53703ca1 "clojure.spec.alpha$and_spec_impl$reify__875@53703ca1"]
:clojure.spec.alpha/value  (2 1 "Red" "Blue")
:clojure.spec.alpha/args  (2 1 "Red" "Blue")
:clojure.spec.alpha/failure  :instrument
:clojure.spec.test.alpha/caller  {:file "form-init7000180716424706450.clj", :line 1, :var-scope genetic-programming-spec.tutorial/eval9500}
  clojure.core/ex-info (core.clj:4725) 
 )

 
 



==============================================================






(ns genetic-programming-spec.core
  (:require [clojure.set :as set]
            [clojure.spec.alpha :as s]
            [clojure.walk :as walk]))




;constrains for creatures
(def seqs ['s/+ 's/*])
(def and-ors ['s/and 's/or])
(def preds ['integer? 'string? 'boolean? '(s/and integer? even?) '(s/and integer? odd?)])
;parameters
(def seq-prob 0.3)
(def nest-prob 0.0)
(def and-or-prob 0.85)
(def mutate-prob 0.1)
(def crossover-prob 0.7)
(def new-node-prob 0.05)
(def max-depth 4)

;declare: defs the supplied var names with no bindings, 
;useful for making forward declarations, recursive callings
;and loops.
(declare make-random-seq)

(defn make-random-arg [n]
  (if (and (pos? n) (< (rand) seq-prob))
    (make-random-seq n)
    (rand-nth preds)))

(comment
  (make-random-arg 3);string?
  (make-random-arg 3);(s/and integer? even?)
)



(defn make-random-seq [n]
  (cond

    (< (rand) nest-prob)
    `(s/spec (~(rand-nth seqs) ~(make-random-arg (dec n))))


    (< (rand) and-or-prob)
    `(~(rand-nth and-ors) ~(make-random-arg (dec n)) ~(make-random-arg (dec n)))

    :else
    `(~(rand-nth seqs) ~(make-random-arg (dec n)))))

(comment
  (make-random-seq 3)
  ;(s/or
  ; (s/or (s/and integer? odd?) boolean?)
  ; (s/+ (s/or string? boolean?)))
)



(defn make-random-cat [len]
  (let [args (reduce (fn [r i]
                       (conj r (keyword (str i)) (make-random-arg max-depth))) [] (range len))]
    `(s/cat ~@args)))

(comment
   (reduce (fn [r i]
               (conj r (keyword (str i)) (make-random-arg max-depth))) [] (range 5))
 ;[:0
 ; (s/and integer? odd?)
 ; :1
 ; (s/and integer? odd?)
 ; :2
 ; string?
 ; :3
 ; (s/and
 ;  integer?
 ;  (s/and integer? even?))
 ; :4
 ; string?]


 
 
 
 ;Clojure: What is the meaning of ` and ~@?
 ;https://stackoverflow.com/questions/8812839/clojure-what-is-the-meaning-of-and
 ;mikera (2012)
 ;` is the syntax-quote, which is used to write code 
 ;as data without evaluating it. Note that it is clever enough 
 ;to resolve symbols that represent functions to the correct namespace.
 ;Examples:

 
 `(+ 1 2); a list containing the + function and two arguments
 ;(clojure.core/+ 1 2)    

 (eval `(+ 1 2))
 ; 3                       ; the result of evaluating the list

 ;  ~@ is the unquote-splicing operator, 
 ;which will enable you to expand a list of elements within some quoted data/code.

;Examples:

(def args [3 4 5 6])
`(+ 1 2 ~@args 7 8);(clojure.core/+ 1 2 3 4 5 6 7 8)
`(+ ~@(range 10)); (clojure.core/+ 0 1 2 3 4 5 6 7 8 9)





  ;catenation
  (into [] (comp cat cat (map inc)) [[[1] [2]] [[3] [4]]]);[2 3 4 5]
  
  (make-random-cat 4)
   ;(clojure.spec.alpha/cat
   ; :0
   ; (s/and integer? odd?)
   ; :1
   ; integer?
   ; :2
   ; (s/and integer? odd?)
   ; :3
   ; integer?)
)


(defn score [creature test-data]
  (try
   (let [problems (:clojure.spec.alpha/problems 
                    (s/explain-data (eval (:program creature)) test-data))]
     (if problems
       (assoc creature :score (get-in problems [0 :in 0]))
       (assoc creature :score 100)))
   (catch Throwable e (assoc creature :score 0))))

(comment
  (s/explain-data (eval 
        (:program {:program '(s/cat :0 int? :1 string?):score 0})) [1 "bbb"])
  ;nil
  (s/explain-data (eval (:program {:program '(s/cat :0 int? :1 string?):score 0})) [1 true])
   ;#:clojure.spec.alpha
   ;{:problems
   ;   [{:path [:1],
   ;     :pred
   ;     clojure.core/string?,
   ;     :val true,
   ;     :via [],
   ;     :in [1]}],
   ;    :spec
   ;    {:clojure.spec.alpha/op
   ;     :clojure.spec.alpha/pcat,
   ;     :ps
   ;     [#object[clojure.core$int_QMARK_ 0xfc5b755 "clojure.core$int_QMARK_@fc5b755"]
   ;      #object[clojure.core$string_QMARK___4952 0x27cf3151 "clojure.core$string_QMARK___4952@27cf3151"]],
   ;     :ret {},
   ;     :ks [:0 :1],
   ;     :forms
   ;     [clojure.core/int?
   ;      clojure.core/string?],
   ;     :rep+ nil},
   ;    :value [1 true]}
   
   
   
   
   ;; We can use get-in for reaching into nested maps:
  (def m {:username "sally"
          :profile {:name "Sally Clojurian"
                    :address {:city "Austin" :state "TX"}}})
  (get-in m [:profile :name]);"Sally Clojurian"
  (get-in m [:profile :address :city]);"Austin"
  (get-in m [:profile :address :zip-code]);nil
  (get-in m [:profile :address :zip-code] "no zip code!");"no zip code!"
  
  
 
   (assoc {} :key1 "value" :key2 "another value")
   ;{:key1 "value", :key2 "another value"}
   

   (score {:program '(s/cat :0 int? :1 string?)} ["d" true])
   ;{:program (s/cat :0 int? :1 string?),
   ; :score 0}
   (score {:program '(s/cat :0 int? :1 string?)} [1 true])
   ;{:program (s/cat :0 int? :1 string?),
   ;:score 1}
   (score {:program '(s/cat :0 int? :1 string?)} [1 "f"])
   ;{:program (s/cat :0 int? :1 string?),
    ;:score 100}
 );end of comment




(defn mutable? [node];????????????????
  (or (when (seq? node)
        (contains? (set/union (set seqs) #{'clojure.spec/spec}) (first node)))
      (contains? (set preds) node)))

(comment
  (mutable?  (s/and integer? even?));false
  (mutable?   integer?  );false
  (mutable? 'integer?);true
  (mutable? '(s/and integer? odd?));true
)




(defn mutate [creature]
  (let [program (:program creature)
        mutated-program (walk/postwalk (fn [x] 
                            (if (and (mutable? x) (< (rand) mutate-prob))
                             (make-random-arg max-depth)
                             x)) program)]
    (assoc creature :program mutated-program)))

(comment
  
  (use 'clojure.walk) 
  (postwalk-demo [[1 2] [3 4 [5 6]] [7 8]])
  ;nil
	;Walked: 1
	;Walked: 2
	;Walked: [1 2]
	;Walked: 3
	;Walked: 4
	;Walked: 5
	;Walked: 6
	;Walked: [5 6]
	;Walked: [3 4 [5 6]]
	;Walked: 7
	;Walked: 8
	;Walked: [7 8]
	;Walked: [[1 2] [3 4 [5 6]] [7 8]]
	;[[1 2] [3 4 [5 6]] [7 8]]
  
  (postwalk-demo {:a 1 :b 2})
	;Walked: :a
	;Walked: 1
	;Walked: [:a 1]
	;Walked: :b
	;Walked: 2
	;Walked: [:b 2]
	;Walked: {:a 1, :b 2}
	;{:a 1, :b 2}
 
  (postwalk-demo {:program '(clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)})
	;Walked: :program
	;Walked: clojure.spec/cat
	;Walked: :0
	;Walked: s/and
	;Walked: integer?
	;Walked: odd?
	;Walked: (s/and integer? odd?)
	;Walked: :1
	;Walked: integer?
	;Walked: (clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)
	;Walked: [:program (clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)]
	;Walked: {:program (clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)}
	;{:program
	; (clojure.spec/cat
	;  :0
	;  (s/and integer? odd?)
	;  :1
	;  integer?)};



  (mutate {:program '(clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)})
  ;{:program
  ;(clojure.spec/cat
  ; :0
  ; (s/*
  ;  (s/or
  ;   (s/and integer? odd?)
  ;   integer?))
  ; :1
  ; (s/and integer? even?))}
)



(defn crossover [creature1 creature2]
  (let [program1 (:program creature1)
        program2 (:program creature2)
        chosen-node (first (walk/walk #(when (and (< (rand) crossover-prob) (mutable? %)) %)
                                       #(remove nil? %) program1))
        crossed-over? (atom false)
        crossover-program (if chosen-node
                             (walk/postwalk (fn [x] (if (and (mutable? x) (< (rand) crossover-prob) (not @crossed-over?))
                                                (do (reset! crossed-over? true) chosen-node)
                                                x)) program2)
                             program2)]
    {:program crossover-program}))


(comment
  
  ;choose node
  (first (walk/walk 
                    #(when (and (< (rand)  crossover-prob) (mutable? %)) %)
                     #(remove nil? %) '(clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)) )
  ;(s/and integer? odd?)

  
  (walk/postwalk (fn [x] (if (and (mutable? x)
                 (< (rand) crossover-prob)  )
                 (do  '(s/and integer? odd?) '(s/and integer? odd?))
                     x)) '(clojure.spec/cat :0 string? :1 boolean?))
  ;(clojure.spec/cat
  ; :0
  ; (s/and integer? odd?)
  ; :1
  ; (s/and integer? odd?))
  

 (crossover {:program '(clojure.spec/cat :0 (s/and integer? odd?) :1 integer?)}
              {:program '(clojure.spec/cat :0 string? :1 boolean?)})
 ;{:program
 ; (clojure.spec/cat
 ;  :0
 ;  string?
 ;  :1
 ;  (s/and integer? odd?))} 
)  




(defn initial-population [popsize max-cat-length]
  (for [i (range popsize)]
    {:program (make-random-cat (inc (rand-int max-cat-length)))}))

(comment
  (initial-population 3 4)
   ;({:program
   ;  (clojure.spec.alpha/cat :0 boolean?)}
   ; {:program
   ;  (clojure.spec.alpha/cat
   ;   :0
   ;   (s/and integer? even?)
   ;   :1
   ;   (s/or boolean? string?)
   ;   :2
   ;   (s/and
   ;    (s/or boolean? string?)
   ;    string?))}
   ; {:program
   ;  (clojure.spec.alpha/cat
   ;   :0
   ;   (s/and integer? odd?)
   ;   :1
   ;   boolean?
   ;   :2
   ;   integer?)})
)  

(defn select-best [creatures tournament-size]
  (let [selected (repeatedly tournament-size #(rand-nth creatures))]
    (-> (sort-by :score selected) reverse first)))


(comment
 (select-best  (initial-population 40 3) 5)
 ;{:program
 ; (clojure.spec.alpha/cat
 ;  :0
 ;  (s/+ (s/and integer? even?)))} 
)  






(defn perfect-fit [creatures]
  (first (filter #(= 100 (:score %)) creatures)))
  
  
  
  
(defn evolve [pop-size max-gen tournament-size test-data]
  (loop [n max-gen
         creatures (initial-population pop-size (count test-data))]
    (println "generation " (- max-gen n))
    (let [scored-creatures (map (fn [creature] (score creature test-data)) creatures)]
     (if (or (zero? n) (perfect-fit scored-creatures))
       scored-creatures
       (let [elites (take 2 (reverse (sort-by :score scored-creatures)))
             new-creatures (for [i (range (- (count creatures) 2))]
                             ;; add a random node to improve diversity
                             (if (< (rand) new-node-prob)
                               {:program (make-random-cat (count test-data))}
                               (let [creature1 (select-best scored-creatures tournament-size)
                                     creature2 (select-best scored-creatures tournament-size)]
                                 (mutate (crossover creature1 creature2)))))]
         (println "best-scores" (map :score elites))
         (recur (dec n) (into new-creatures elites)))))))

(comment
  ;To run this program in the REPL
  
  (perfect-fit (evolve 100 100 7 ["hi" true 5 10 "boo"]))
               
   ;else
   
   
   
  (def creature-specs (evolve 100 100 7 ["hi" true 5 10 "boo"]))
  (perfect-fit creature-specs)
  ;output
  ;generation  3
  ;{:program
  ; (clojure.spec.alpha/cat
  ;  :0
  ;  string?
  ;  :1
  ;  boolean?
  ;  :2
  ;  integer?
  ;  :3
  ;  (s/and integer? even?)
  ;  :4
  ;  string?),
  ; :score 100}

  
  
  (s/exercise (eval (:program (perfect-fit creature-specs))) 5)
  ; ([("" true -1 0 "")
  ; {:0 "",
  ;  :1 true,
  ;  :2 [-1],
  ;  :3 0,
  ;  :4 ""}]
  ; [("" false -1 -1 0 "7")
  ;  {:0 "",
  ;   :1 false,
  ;   :2 [-1 -1],
  ;   :3 0,
  ;   :4 "7"}]
  ; [("ca" true 1 -1 1 0 "i")
  ;  {:0 "ca",
  ;     :1 true,
  ;     :2 [1 -1 1],
  ;     :3 0,
  ;     :4 "i"}]
  ; [("2N" true -1 0 "Kg")
  ;   {:0 "2N",
  ;    :1 true,
  ;    :2 [-1],
  ;     :3 0,
  ;    :4 "Kg"}]
  ; [("" false 7 -1 29 -9 1 -12 "h")
  ;  {:0 "",
  ;   :1 false,
  ;   :2 [7 -1 29 -9 1],
  ;   :3 -12,
  ;   :4 "h"}])
  
 );end of comment