Clojure functions which perform symbolic simplification using 'and'

Question

I am new to Clojure and I'm learning how to write a program that can simplify logical expressions (just 'and' for now to figure out how things work first). For example:

(and-simplify '(and true)) => true

(and-simplify '(and x true)) => x

(and-simplify '(and true false x)) => false

(and-simplify '(and x y z true)) => (and x y z)

I already knew how to simplify two arguments, that everything I can do right now is:

(defn and-simplify []

  (def x (and true false))
  println x)
(and-simplify)

I've read this post and tried to modify my code a little bit but it doesn't seem to get me anywhere:

(defn and-simplify [&expr]

  (def (and &expr))
)

What is the correct way that I should have done?

None of your examples require a function that takes a variable number of arguments. All of your examples take a single argument, which is a list of symbols. Hence you want to write a function that operates on that list. — jas, Mar 03 '20 at 12:28

score 2 · Accepted Answer · answered Mar 03 '20 at 13:10

Here's my take on it.

(defn simplify-and
  [[op & forms]]
  (let [known-falsy?  #(or (false? %) (nil? %))
        known-truthy? #(and (not (symbol? %))
                            (not (seq? %))
                            (not (known-falsy? %)))
        falsy-forms   (filter known-falsy? forms)
        unknown-forms (remove known-truthy? forms)]
    (if (seq falsy-forms)
      (first falsy-forms)
      (case (count unknown-forms)
        0 true
        1 (first unknown-forms)
        (cons op unknown-forms)))))

(comment (simplify-and `(and true 1 2 a)))

However, we can write a more generic simplify that uses multimethods to simplify lists, so that we can add more optimisations without modifying existing code. Here's that, with optimisations for and, or and + from clojure.core. This simplify only optimises lists based on namespace qualified names.

Check out the examples in the comment form. Hope it makes sense.

(defn- known-falsy? [form]
  (or (false? form) (nil? form)))

(defn- known-truthy? [form]
  (and (not (symbol? form))
       (not (seq? form))
       (not (known-falsy? form))))

(declare simplify)

(defmulti simplify-list first)
(defmethod simplify-list :default [form] form)

(defmethod simplify-list 'clojure.core/and
  [[op & forms]]
  (let [forms         (mapv simplify forms)
        falsy-forms   (filter known-falsy? forms)
        unknown-forms (remove known-truthy? forms)]
    (if (seq falsy-forms)
      (first falsy-forms)
      (case (count unknown-forms)
        0 true
        1 (first unknown-forms)
        (cons op unknown-forms)))))

(defmethod simplify-list 'clojure.core/or
  [[op & forms]]
  (let [forms         (mapv simplify forms)
        truthy-forms  (filter known-truthy? forms)
        unknown-forms (remove known-falsy? forms)]
    (if (seq truthy-forms)
      (first truthy-forms)
      (case (count unknown-forms)
        0 nil
        1 (first unknown-forms)
        (cons op unknown-forms)))))

(defmethod simplify-list 'clojure.core/+
  [[op & forms]]
  (let [{nums true non-nums false} (group-by number? (mapv simplify forms))
        sum (apply + nums)]
    (if (seq non-nums)
      (cons op (cons sum non-nums))
      sum)))

(defn simplify
  "takes a Clojure form with resolved symbols and performs
   peephole optimisations on it"
  [form]
  (cond (set? form)    (into #{} (map simplify) form)
        (vector? form) (mapv simplify form)
        (map? form)    (reduce-kv (fn [m k v] (assoc m (simplify k) (simplify v)))
                                  {} form)
        (seq? form)    (simplify-list form)
        :else          form))

(comment
 (simplify `(+ 1 2))
 (simplify `(foo 1 2))
 (simplify `(and true (+ 1 2 3 4 5 foo)))
 (simplify `(or false x))
 (simplify `(or false x nil y))
 (simplify `(or false x (and y nil z) (+ 1 2)))
)

Clojure functions which perform symbolic simplification using 'and'

1 Answers1