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.

99 Clojure Problems – 47: Truth Tables for Logical Expressions (2)

"Continue problem P46 by defining and/2, or/2, etc as being operators. This allows to write the logical expression in the more natural way, as in the example: A and (A or not B). Define operator precedence as usual; i.e. as in Java."

If we want to have this 'natural way' of writing logical expressions we will have to introduce infix notation into Clojure's prefix world.

Example

ninety-nine-clojure.logic> (table (i (a and (a or not b))))

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

Discussion

How do we get the desired syntax?

If you have read the previous article you know that we are deep in macro-land and there is no way back. This can be seen as a macro anti-pattern (See "Macros all the way down" in Clojure for the Brave and True).

We are already in a situation where our truth table function can only be a macro because we want to pass in unquoted macros as parameters. This is also true for the infix problem: What we need in a first step is a macro that allows us to write something like this:

(table #(infix (%1 and (%1 or not %2))))

Remember the truth table macro expects expressions that take two arguments. A first step towards that goal is to create an anonymous function with two arguments (%1, %2) and process our logical expression with a yet to write infix function or macro to turn it back into Clojure code. The infix notation is not easy to read due to the numbered arguments but we will work on that later.

Infix in Clojure

It is a well established exercise to implement infix operators in a Lisp. There is the exercise 2.58 in SICP for example that teaches us about the benefits of prefix notation over infix notation. The chapter 1.22 in the "Joy of Clojure" shows us in a similar fashion how we can avoid all the troubles in Clojure that usually come with the rules of operator precedence and still have some infix notation if we want it.

Now to get a basic infix notation we just need a rather simple macro that puts the operator into function position and adds parens around it.

([a op b]
     `(~op (infix ~a) (infix ~b)))

It recursively calls itself on the symbols 'a' and 'b', which can be composite expressions in parens like:

(a and b) 

or a simple boolean value. I came up with this to deal with both cases:

 ([x] (if (seq? x)
         `(infix ~@x)
         x))

It says: If the argument is a sub-expression in list form and therefore sequential apply the infix macro again otherwise return the value.

We have got all the binary operators covered assuming that they all have the same precedence. (Which they don't e.g. in Java which was mentioned in the original Prolog problem description). A bit trickier are now the unary operators like 'not'. If we use parens as in '(not a) and b)' it will work out of the box, as this negation of 'a' is already valid Clojure. I am supporting expressions like 'a and not b' with the following extension of my infix macro:

([a b c d]
     (if (unary? a)
       `(~c (~a (infix ~b)) (infix ~d) )
       `(~b (infix ~a) (~c (infix ~d)))))

The basic idea here is to take advantage of Clojure's support for multi-arity functions/macros and deal with a unary operator before the second value/sub-expression by interpreting any call with four arguments in that way. Now this falls obviously down as soon as we have something like 'not a and not b'. We will have to cover that case seperately.

Optional noise reduction

I already mentioned that the usage of the infix macros in combination with the truth tables leaves room for improvement:

(table #(infix (%1 and (%1 or not %2))))

The numbered arguments of the anonymous function are a bit ugly. We would rather have something like this:

(table (i (a and (a or not b))))

We imagine that 'i' is the macro that triggers the infix magic and the rest is an easy to read logical expression. We imagine further that 'i' is a macro that transform our expression into a function of two arguments 'a' and 'b'. The result of the transformation would be the following piece of Clojure code:

(fn [a b] (and a (or a (not b))))

[Update: As it turns out the symbol replacement described below is unnecessary. Stay tuned for problem 48 for more detail on this.]

The problem with that idea: Clojure won't allow you to introduce new bindings in a syntax quote (`) that might capture existing variables. The gensym mechanism is there for you to generate unique symbols to be used in a macro that won't accidentally hijack existing variables.

A post on Fogus' blog about deep code walking macros lead me to this implementation:

(defmacro i
  [& args]  
  (let [a (gensym)
        b (gensym)
        code (clojure.walk/postwalk-replace {'a a 'b b} args)]
    `(fn [~a ~b] (infix ~@code))))

It has its limitations: you can only use 'a' and 'b' as variables, as they are hard-coded. I then uses a deep code walking function to replace the 'a's and 'b's with generated symbols, which will also be used to generate a wrapper function around the logical expressions.

That was not very hard, but there would be a bit more work involved to get rid of the limitations. We will look at that when we tackle the next problem which will require us to support logical expressions of arbitrary arity. The source for my complete solution is as always on Github.

Read more about this series.

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.