99 Clojure Problems – 48: Truth Tables for Logical Expressions (3)

Generalize problem 47 in such a way that the logical expression may contain any number of logical variables. Define table in a way that (table vector expr) prints the truth table for the expression expr, which contains the logical variables enumerated in vector.

Example

ninety-nine-clojure.logic> (table (i [a b c], (a and (b or c) equ a and b or a and c)))

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

Discussion

This is more of a refactoring of the previous solution than anything else. I learned a bit more about how macros work in Clojure and discovered that some of the problems I solved last time were actually non-problems.

There are three places in our current code that prevent us from specifying expressions with arbitrary many logical variables: The input values were hard-coded to the four possible combinations of two boolean arguments. The header used when printing the truth table was hard-coded. Finally the macro that supported the defintion of a logical expresion in infix notation was limited to two arguments as well.

Possible input values

We want to create all possible ordered sets that can be created out of the n sets of input parameters for each logical variable. For two boolean parameters (that's what we had so far) it looks like this:

        +                             
        |  true         false         
+------------------------------------+
  true  | [true true]   [true false]  
        |                             
  false | [false true]  [false false] 
        +                             

I initially thought of this problem as a for comprehension in the form of

(for [x [true false] y [true false]] [x y])

To make that work for n arguments I would have to implement another macro to create a for comprehension with n generators. When I realised that the operation here is just an n-fold Cartesian product, I knew that this was not necessary. I decided to use clojure.math.combinatorics which was already a dependency of the project to calculate the Cartesian product of n sets of Boolean parameters instead.

Generating functions with a given arity

I had introduced the 'i' macro to have a simple and elegant way to express that its argument was to be interpreted as a logical expression in infix notation.

(i (a or b))

To support n logical variables we now need to move away from this succinct syntax a bit and specify the logical variables in use in a separate argument.

(i [a b c] (a and (b or c)))

Implementing this was way easier than I thought. It looks similar to this:

(defmacro [bindings & expr]
   `(fn ~bindings (infix ~expr)))

I also noticed that the deep code walking and code replacement I introduced last time, was completely unnecessary. I thought you need generated symbols, but that is only true if you want to use let inside a syntax quote, which I did not. I had probably stumbled over Clojure's quoting rules, which are one of the more complicated bits of the language.

This new argument was interesting in another respect: I wanted to use it to create a header for the truth table. But wanted to avoid this duplication:

(table [a b] (i [a b] (a or b)))

Extracting metadata from a function

A possible solution: Clojure functions have metadata about their arity which is exactly what we want and need to generate the header of the truth table. But the metadata is only present on functions created via defn. The one used here was anonymous. In addition you should be able to do

(table and)

That is not even a function. As we already know 'and' is a macro in Clojure but it has the necessary metadata. Even more than we need:

(:arglists (meta #'and))
([] [x] [x & next])

The hash-quote is a reader macro that translates to (var and) which resolves to the var object (as opposed to it's value) where the metadata is stored. The problem here: 'and' has more than one argument list and the relevant one in this context contains a var arg.

I ended up offering both APIs:

(table '[a b] and)
(table (i [a b] (a and b)))

The second variant uses the metadata to infer the header of the truth table while it's explicit in the first variant. I'm not entirely happy with that result as it seems a bit brittle: in the second variant it just uses the first argument list and falls flat on its face when the argument does not contain any metadata, which could well happen if you just specify an anonymous function yourself instead of using the 'i' macro.

Have a look at the complete code here on Github.

Read more about this series.