"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.
No comments:
Post a Comment