Tuesday, June 1, 2010

Truth tables in Clojure

In an effort to learn Clojure, I'm working through these 99 Lisp problems.

One of the challenges found on there is to display a truth table for any arbitrary boolean expression.

So given an expression such as this:
(and (or :a :b) (nand :a :c))

In an imperative language, such an expression would look like this (pseudo-code):
((:a or :b) and (:a nand :c))

The challenge is to produce an output table which looks like this:
:a = true, :b = true, :c = true, :result = false
:a = true, :b = true, :c = false, :result = true
:a = true, :b = false, :c = true, :result = false
:a = true, :b = false, :c = false, :result = true
:a = false, :b = true, :c = true, :result = true
:a = false, :b = true, :c = false, :result = true
:a = false, :b = false, :c = true, :result = false
:a = false, :b = false, :c = false, :result = false

To make this happen we need several pieces.

1. a "not and" predicate function. This returns "true" when "and" would return "false" and vice-versa.
2. A way of getting all of the distinct keywords out of our expression. For the example expression, this would return :a, :b, :c
3. A way of generating all of the combinations of "true" and "false" for as many keywords as were in the expression. For example, [true true true], [true true false], [true false true], etc.
4. A way of substituting "true" or "false" for each keyword for the purpose of evaluating the expression.
5. Putting it all together to print out the truth-table with the results.

1. nand is easy. It is simply the opposite of "and".
(defn nand [a b]
  (not (and a b)))
(nand true true)
"false"

2. The keywords-seq function traverses through each nested list within the expression and returns a flat, distinct set of keywords
(defn- keywords-seq [expr]
  (letfn
      [(keywords
        [expr]
        (lazy-seq
         (if (empty? expr)
           '()
           (cond
            (seq? (first expr)) (keywords (concat (first expr) (rest expr)))
            (keyword? (first expr)) (cons (first expr) (keywords (rest expr)))
            :else (keywords (rest expr))))))]
    (sort (seq (set (keywords expr))))))
(keywords-seq '(and (or :a :b) (nand :a :c)))
"(:a :b :c)"

3. For all the combinations of "true" and "false" needed for a truth table, I used the selections function from clojure.contrib.combinatorics. For example:
(use '[clojure.contrib.combinatorics :only (selections)])
(selections [true false] 3)
((true true true) (true true false) (true false true) ...

4. To substitute "true" or "false" in place of keywords, I created a replace-all function. This takes a map of keywords with "true" or "false" as values and substitutes them into the expression, returning the expression with the substituted values.
(defn- replace-all [smap coll]
  (lazy-seq
   (if (empty? coll)
     '()
     (let [coll (replace smap coll)]
       (if (seq? (first coll))
         (cons (replace-all smap (first coll)) (replace-all smap (rest coll)))
         (cons (first coll) (replace-all smap (rest coll))))))))
(replace-all {:a true :b false :c true} '(and (or :a :b) (nand :a :c)))
"(and (or true false) (nand true true))"

5. Now for the good stuff. Let's put all this stuff together and print out the truth table. The main thing this function does is zipmap together the keywords with each "true"-"false" combination sequence. Once we have this map, we can use it to evaluate the expression to produce the result. We do this by running "eval" on the result of sending that map and the expression to replace-all. Then, we print out a formatted string of each input value with the result.
(defn print-truth-table [expr]
  (let [kws (keywords-seq expr)]
  (do
    (println (str "expression: " expr))
    (doseq
        [kwm (for [p (selections [true false] (count kws))]
               (zipmap kws p))]
      (do
        (doseq [m (into (sorted-map) kwm)]
          (print (format "%s = %s, " (first m) (second m))))
        (print (format ":result = %s" (eval (replace-all kwm expr))))
        (println))))))
(print-truth-table '(and (or :a :b) (nand :a :c)))
"
expression: (and (or :a :b) (nand :a :c))
:a = true, :b = true, :c = true, :result = false
:a = true, :b = true, :c = false, :result = true
:a = true, :b = false, :c = true, :result = false
:a = true, :b = false, :c = false, :result = true
:a = false, :b = true, :c = true, :result = true
:a = false, :b = true, :c = false, :result = true
:a = false, :b = false, :c = true, :result = false
:a = false, :b = false, :c = false, :result = false
"

For a point of reference, let's run this with the two classic truth tables. That is, a single "and" and a single "or".
(print-truth-table '(and :a :b))
"
expression: (and :a :b)
:a = true, :b = true, :result = true
:a = true, :b = false, :result = false
:a = false, :b = true, :result = false
:a = false, :b = false, :result = false
"

(print-truth-table '(or :a :b))
"
expression: (or :a :b)
:a = true, :b = true, :result = true
:a = true, :b = false, :result = true
:a = false, :b = true, :result = true
:a = false, :b = false, :result = false
"

Even though I'm sure my Clojure code is sub-optimal in a variety of ways, it still works and wasn't too difficult to implement. I could not imagine having to write this in traditional, imperative language such as Java or C#. It would surely take a lot more code to say the least.