Sequential Matching in Expresso

---

I In the second week of gsoc, I extended the rule syntax to handle sequential matchers, to have proper support for functions having variadic arguments, what is quite common in clojure. They, as the name suggest, match zero or more arguments in the expression. In this post, I like to demonstrate their use and how they enable rules to be more expressive.

Table of Contents

• 1 Introduction
• 2 Example: Simplification Rules in Expresso
• 3 Cool example of sequential matching
• 4 Whats next

1 Introduction

For introduction, here is an expresso rule that cancels out a zero in an expression

(use 'numeric.expresso.rules)
(use 'numeric.expresso.construct)
(with-expresso [+]

  (def cancel-zero-rule (rule (+ 0 ?x) :=> ?x))

  (apply-rule cancel-zero-rule (+ 3 0)) ;=> 3
  (apply-rule cancel-zero-rule (+ 3 0 2)) ;=> nil
)

Because expresso knows that clojure.core/+ is a commutative operation, it matches not regarding the order of arguments, but if there is a permutation, which will match. Therefore, the first call to apply-rule succeeds binding ?x to 3. But, as the rule is written, it expects + to take exactly two arguments. That is why the secand call to apply-rule fails. In many languages, + takes two arguments, but in clojure (and other lisps) + (and many other functions) are variadic, so they support zero, one or more arguments. Below is the version of the rule, which supports the lispy variadic + function

(use 'numeric.expresso.rules)
(use 'numeric.expresso.construct)
(with-expresso [+]

  (def cancel-zero-rule (rule (+ 0 ?&*) :=> (+ ?&*)))

  (apply-rule cancel-zero-rule (+ 3 0)) ;=> (clojure.core/+ 3)
  (apply-rule cancel-zero-rule (+ 3 0 2)) ;=>(clojure.core/+ 3 2) 
)  

The commutative matching functions only allows for one seq-matcher in the pattern. More than one seq-matcher would not make sense, if the order of the arguments doesn't matter. The normal expression match function supports multiple seq-matchers, I will give an example for that below.

2 Example: Simplification Rules in Expresso

To demonstrate the usefulness of expressos rule syntax I present a few common simplification rules for + and *

(with-expresso [+ - * /]

  (def simplification-rules
    [(rule (+ 0 ?&*) :=> (+ ?&*))
     (rule (+ ?x ?x ?&*) :=> (+ (* 2 ?x) ?&*))
     (rule (* 0 ?&*) :=> 0)
     (rule (* 1 ?&*) :=> (* ?&*))
     (rule (+ (* ?x ?&*a) (* ?x ?&*b) ?&*r)
           :=> (+ (* ?x (+ (* ?&*a) (* ?&*b))) ?&*r))
     (rule (*) :=> 1)
     (rule (+) :=> 0)
     (rule (* ?x) :=> ?x)
     (rule (+ ?x) :=> ?x)])

  (transform-with-rules simplification-rules (+ 1 2 0)) ;=> (clojure.core/+ 1 2)
  (transform-with-rules simplification-rules (* (+ 'x 'x) 1))
   ;=> (clojure.core/* 2 x)
  (transform-with-rules simplification-rules (+ 'x (* 'x 3 1) 'x (* 'y 0)))
   ;=>(clojure.core/* x (clojure.core/+ 3 2))

Especially the fifth rule shows the power of a custom matching function and seq-matchers. It quite literally states the simplification of factoring out. Also note the last call to transform-with-rules. It simplifies (* 'y 0) => 0 and (* 'x 3 1) => (* 'x 3) and (+ 'x (* 'x 3) 'x 0) => (+ 'x (* 'x 3) 'x) => (+ (* 2 'x) (* 'x 3)) => (* 'x (+ 3 2)).

3 Cool example of sequential matching

I want to finish with a very cool example of sequential matching in an associative context. Here, ° denotes a list concatenation operator, so that (° 1 2 3) is the list containing 1 2 3. It is possible to expresso insertion sort as application of only one rule. Here is how:

(use 'clojure.core.logic)
(defn biggero [x y] (project [x y] (== true (> x y))))
(with-expresso [°]

  (def sort-rule (rule (° ?&*1 ?x ?&*2 ?y ?&*3) :=> (° ?&*1 ?y ?&*2 ?x ?&*3)
                       :if (biggero ?y ?x)))

  (transform-with-rules [sort-rule] (° 1 4 2 6 5 4 3 7 8 9))
   ;=> (numeric.expresso.construct/° 9 8 7 6 5 4 4 3 2 1)
)

Btw: I don't recommend using this from a performance perspective :)

4 Whats next

In the next week I want to give the rule based translator a test by writing rules to simplify an expression to a normal form, which could also be the default input for the more sophisticated transformations of expresso. I also want to add support for a ?&+ seq-matcher, which matches one or more arguments