99 Clojure Problems – 46: Truth Tables For Logical Expressions

Define functions and, or, nand, nor, xor, impl, and equ (for logical equivalence) which return true or false according to the result of their respective operations; e.g. (and A B) is true if and only if both A and B are true.

A logical expression in two variables can then be written in prefix notation, as in the following example: (and (or A B) (nand A B)).

Now, write a predicate table which prints the truth table of a given logical expression in two variables.

Example

ninety-nine-clojure.logic> (table impl)

|    :a |    :b | :result |
|-------+-------+---------|
|  true |  true |    true |
|  true | false |   false |
| false |  true |    true |
| false | false |    true |

Discussion

This problem has three parts: Implementing the logical expressions as functions. Implementing the truth table function and finally—and this is Clojure specific—thinking about how to deal with the built-in logical expressions 'and' and 'or'.

Logical expressions in Clojure

Once you have implemented 'and', 'or' and 'not' you can implement all other logical expressions in terms of these three "primitives". In Clojure 'and' and 'or' are macros. I don't want to give an introduction to macros here (I recommend having a look at the most excellent Joy of Clojure or Clojure for the Brave and True) But I will say that much: As Clojure's code is just data, macros allow you to transform that data before compilation into other code/data.

Bearing that in mind and trying to understand clojure.core/and we hope to get an idea how to implement the most basic logical expressions for this problem ourselves. This is how the 'and' macro is implemented in Clojure:

(defmacro and
  ([] true)
  ([x] x)
  ([x & next]
   `(let [and# ~x]
      (if and# (and ~@next) and#))))

Even without understanding every last detail of this macro definition, we can see that Clojure's 'and' transforms the and-expression into a recursive series of if-expressions.

Filling in concrete values and using macroexpand makes things a bit clearer:

ninety-nine-clojure.logic> (macroexpand '(and true false))
(let* [and__3941__auto__ true] 
  (if and__3941__auto__ 
     (clojure.core/and false) 
     and__3941__auto__))

Expanded to the first level, we see how the and-expression is now an 'if' inside a 'let'. A recursive call to 'and' for the second argument is still unexpanded. This should give us enough inspiration to implement simple 'and' and 'or' functions of our own.

But we can also reuse the existing control structures Clojure offers right away to build the higher level expressions for 'nand', 'nor', 'equ', 'impl' and 'xor'.

Creating a truth table

The next step is to build the table function. I cheated a bit and used Clojure's print-table, hard-coding the possible inputs for a function with two boolean arguments. Print-table takes a sequence of maps for each row. To get the desired effect I interleaved a descriptive header with the result of evaluating the logical expressions and turned that into a sorted map. But it should not be too hard to built a simple printing function yourself.

Make it work with the built-in expressions

Now this last part is only relevant if you were lazy, as I was, and reused the existing Clojure expressions for 'and' and 'or'. Try to create a truth table for them and you will get a response similar to the following:

(table and)
CompilerException java.lang.RuntimeException: Can't take value of a macro: #'clojure.core/and, compiling:(NO_SOURCE_PATH:1:1) 

Now we already know that 'and' is implemented as a macro. Unless we are quoting we can't use it as a value:

(table 'and)

If we want to provide an API where the user does not need to know whether the argument to our table function is a macro and therefore has to be quoted, we have to write a macro ourselves.

Now this is a bit tricky and took a while. The hardest bit was was a helper macro I created to evaluate the logical expression (possibly a macro) for all input values, even though this is shamelessly taken from an answer on stackoverflow. The helper wraps the macro in a function where it is eval'd after making it referable by quoting it like so (with exemplary values added for clarity):

(list 'and true false)

I called it evaluator:

(defmacro evaluator [expr]
  `(fn [& args#]
     (eval `(~'~expr ~@args#))))

It uses two levels of syntax-quoting (`). The first to allow the introduction of the args-symbol and the second to allow the unquote-splicing (~@args#) of the args vector in the quoted function call (~'~expr) which we are building inside our evaluator function.

This kind of complexity is in my experience the exception and I am not even sure if there is not an easier solution to my problem than the one I found. But given the fact that the argument to our function is already a macro, I don't see a solution avoiding macros. Please let me know if you think I'm wrong. In the meantime have a look at the source code.

Read more about this series.