Samstag, 29. Juni 2013

Sequential Matching in Expresso

Sequential Matching in Expresso

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.

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

Sonntag, 23. Juni 2013

[GSOC] Expressions, Rules and first Transformations

[GSOC] Expressions, Rules and first Transformations

[GSOC] Expressions, Rules and first Transformations

This is the status report after the 1st week of gsoc. While I still have normal schedule of university classes, I managed to get some time for coding (could'nt stop me doing this)

1 Expressions

Expressions are encoded as s-exp with metadata. Therefore, they can be constructed by hand, or with the expresso.construct namespace for convenience. The central function is ex, which generates the s-exp with op as symbol and args as arguments and with the appropriate metadata for the operation.

(use 'numeric.expresso.construct)

(ex `* 1 2 3) ;=> (clojure.core/* 1 2 3)
(properties (ex `/ 3 2 1)) 
 ;=> [:n-ary [:inverse-of clojure.core/*]]

ex gets the properties of the expression from the multimethod props, which can be extended by users

(defmethod props 'exp [_] [:positive [:arity 1]])

(properties (ex 'exp 0)) ;=> [:positive [:arity 1]]

constructing expressions with ex is still tedious, so there is the with-expression macro.

(with-expresso [+ - * /] (+ 1 2 (* 3 4))) 
;=> (clojure.core/+ 1 2 (clojure.core/* 3 4))
(properties
  (with-expresso [+ - * /] (+ 1 2 (* 3 4)))) 
;=> [:associative :commutative :n-ary]

It takes a vector as first argument and replaces in the code all occurences of the symbols with their namespaced-qualified name and calls ex with it.

Because expressions are just s-expressions with metadata (which gets preserved by core.logic) it is easy to manipulate them with core.logic.

2 Rules

Rules are the most important part of the core expression rule based transformer (obviously), so I really want a good rule design, in which

  • encoding arbitrary transformations as rules is supported
  • it is easy to construct rules syntactically
  • rules are not a black-box for expresso, so that rules can be optimized (i.e. pruning the rules to those applicable to the expression)

2.1 Rule representation

Expresso rules are represented by a vector of [pat trans guard] where pat is an syntactical pattern, which gets matched against the expression. Guard is a core.logic relation, which gets checked after a succesfull match. Trans specifies the new form of expression. In the simple case it can be a syntactic expression, or it can be a core.logic relation (details later). The macro rule constructs a rule. Variables are encoded as a symbol starting with ?.

(use 'numeric.expresso.rules)
(use 'clojure.core.logic)
(with-expresso [* + - = /]
(def rules [(rule (* ?x 1) :=> ?x)
            (rule (* ?x 0) :=> 0)
            (rule (+ ?x 0) :=> ?x)
            (rule (+ ?x (- ?x)) :=> 0)
            (rule (- ?x ?x) :=> (- (* 2 ?x)))])
;if no guard is provided rule inserts the succeed core.logic goal.

(def with-guard (rule (= (* ?a 'x) ?y) :=> (= 'x (/ ?y ?a)) :if (!= ?a 0)))

(apply-rule with-guard (= (* 'x 1) 2)) ;=> (clojure.core/= x (clojure.core// 2 1))
(apply-rule with-guard (= (* 'x 0) 2)) ;=> nil

;the transformation can be a relation itself,
(use 'numeric.expresso.solve)
(def calc-rule (rule ?x :=> (fn [res] (resulto ?x res)) :if (no-variablo ?x)))

(apply-rule calc-rule (* 3 (+ 2 1))) ;=>  9
(apply-rule calc-rule (* 'x 3)) ;=> nil
)

2.2 Expressions specify the matching algorithm

Look closely at the example of the rule with-guard. applying it to (= (* 'x 1) 2) matches with (= (* ?a 'x) ?y). This is not a strange bug, but intented behaviour. Let me explain the reasons for this:

If you have a rule based translator based on normal unification or pattern matching, it will match syntactically, not semantically. This is a problem, because, for example, (* 3 4) and (* 4 3) are semantically equivalent, but not syntactically. So to simplify multiplication with zero you would have to write multiple rules

(with-expresso [*]
  (rule (* ?x 0) :=> 0)
  (rule (* 0 ?x) :=> 0))

It is getting (a lot) worse if you have expressions like (* 2 3 0 1), which is normal in clojure.

Therefore, in expresso, the rules decide the matching algorithms. And again, the matching function is stored in a multimethod (which defaults to syntactical matching) and therefore extensible to new operators.

2.3 Write one, match many

Another situation likely to aries when writing rules for (say) simplification is that you have to duplicate rules with an other operator which behaves the same. Basic example: If you use different implementations for the same function - like clojure.core/+ and an optimized other implementation . you would have to dublicate the rules concerning clojure.core/+ with the other implementation.

Expresso uses clojures ad-hoc hierarchies for this. It matches a pattern against an expression, if the operator of expression is an instance of the operator of the pattern. This enables you to do the following

(derive 'clojure.core/+ e/+)
(derive 'other.ns/+ e/+)

(with-expresso [+ other.ns/+ e/+]
  (def r (rule (e/+ ?x 0) :=> ?x))

  (apply-rule r (+ 3 0)) ;=> 3
  (apply-rule r (other.ns/+ 3 0)) ;=> 3
)

2.4 Going absolutely crazy

This makes it also possible to have very powerful abstract rules. Here is an example for representing mathematical properties of groups. It also shows the function transform-with-rules which recursively applies a vector of rules to the expression


(defmulti group-id identity)
(defmethod group-id :default [_] false)
(defmethod group-id [`+ 0] [_] true)
(defmethod group-id [`* 1] [_] true)

(defn is-group-identityo [op id]
  (project [op id]
           (== true (group-id [op id]))))

(defmulti group-ne identity)
(defmethod group-ne :default [_] nil)
(defmethod group-ne `+ [_] 0)
(defmethod group-ne `* [_] 1)

(defn group-neo [op res]
  (project [op]
           (== res (group-ne op))))

(with-expresso [- /]
(defmulti group-inverse first)
(defmethod group-inverse :default [_] nil)  
(defmethod group-inverse `+ [[_ x]] (- x))
(defmethod group-inverse `* [[_ x]] (/ 1 x))
)
(use 'numeric.expresso.utils)
(defn is-group-inverso [op x y]
  (project [op x]
           (if-let [inv (group-inverse [op x])]
             (== y inv)
             fail)))
(def group-rules
  [(rule (ex ?op ?x ?id) :=> ?x :if (is-group-identityo ?op ?id))
   (rule (ex ?op ?x ?y) :=> (fn [res] (group-neo ?op res)) 
    :if (is-group-inverso ?op ?x ?y))])

(with-expresso [+ * - /]
  (transform-with-rules group-rules (+ 1 0))  ;=> 1
  (transform-with-rules group-rules (* 3 1)) ;=> 3
  ;works because + and * are commutative
  (transform-with-rules group-rules (+ 0 1)) ;=> 1
  (transform-with-rules group-rules (* 1 3)) ;=> 3
  (transform-with-rules group-rules (+ 3 (- 3))) ;=> 0
  (transform-with-rules group-rules (* 3 (/ 1 3))) ;=> 1
  (transform-with-rules group-rules 
    (+ (* 1 (* 3 (/ 1 3))) (+ (* 1 2) (- (* 2 1))))) ;=> 1
)

3 What's next

In the next week I want to work further on the transformation with rules, try different strategies (postwalk vs prewalk) also in a core.logic context, and give proper support for n-ary expressions. I plan to do this by allowing a &* syntax in the rules which matches the rest of the arguments.

Ang again, please comment.

Date: 2013-06-23T13:36+0200

Author: Maik Schünemann

Org version 7.8.09 with Emacs version 23

Validate XHTML 1.0

Freitag, 14. Juni 2013

Constructing Algebraic Expressions

Constructing Expressions

Constructing Expressions


Gsoc finally starts monday. And for the start I want to have a good idea of how the user interface of expresso should look like, for this I want to discuss the best way of aktually constructing expresso expressions :).

1 Representation of expresso expressions

Because core.logic currently doesn't play nicely with custom types and algebraic expressions fit nicely with normal clojure s-expressions I plan to represent algebraic expressions just as that. However, that doesn't mean it is straightforward to construct them - expresso has to know the full qualified function symbol to differentiate between - for example - clojure.core/* and the core.matrix * which behave differently. Also other mathematical properties should be stored about the functions - I plan to use metadata for it.

2 How should using expresso feel like

Hopefully as seamless as possible.

One approach would be a macro - create-expression. It would construct the enhanced form of the s-expression from the s-expression it gets. This, however has some drawbacks. First the user either needs to use ~ to aktually get the data in the expressions. Or you have to have map as argument which would map from symbols to values. Further than that, because it is a macro, it can't be used in higher order functions.

(let [matrix [[1 0 1]
              [0 1 0]
              [1 0 1]]]
  (simplify (construct-expression (* 5 (determinant ~matrix))))
  ;or 
  (simplify (construct-expression (* 5 (determinant x)) {'x matrix})))

The other approach would be to have construction functions in an own namespace, with concise names, just like core.matrix did with the operators namespace.

(ns test
  (:use [expresso.construction])
  (:refer-clojure :exclude [* - + == /]))
(let [matrix [[1 0 1]
              [0 1 0]
              [1 0 1]]]
 (simplify (* 5 (determinant matrix))))

Mike Anderson also posted some interesting usage examples (with a possible syntax) on the clojure mailing list:

; 1. Solving simultaneous equations expressed in arrays:

(solve [x y] (== [x y] (* [[3 0] [0 10]] [y 1])))
=> [30 10]

;2a. Derivatives of array expressions:

(derivative [x] (* [x 2] [3 (* x x)]))
=> [3 (* 4 x)]

;2b. Derivatives that are themselves vectors / arrays:

(derivative [[x y]] (* [x 2] [3 (* x x)]))
=> [[3 (* 4 x)] 0]

;3. Simplification of computations on arrays:

(simplify (trace [[x y] [z (- 5 x)]]))
=> 5

;4. Simplification of array-level expressions

(simplify (* 10 A (some-identity-matrix) (inverse A) B))
=> (* 10 B)

What would be your favorite way of using expresso?

3 expresso on core.matrix expressions

Considering the close relation between expresso and core.matrix it is very likely that expresso (especially the optimizer) will be used on core.matrix expressions. Mike's examples also point in this direction. What about making expresso an implementation of core.matrix ? It would not calculate the results of matrix operations, but create the expressions under the hood. That way one could just switch the implementation of core.matrix to make the matrix expression available to expresso.

For the core.matrix folks: Do you think that is possible? There are certainly a few caveats in it but it seems to be the perfect way of using expresso in a core.matrix context.

Date: 2013-06-14T23:09+0200

Author: Maik Schünemann

Org version 7.8.09 with Emacs version 23

Validate XHTML 1.0