symbolic expression manipulation with expresso

---

It is now half way through the google summer of code project and I will do a quick showoff in this post about what is supported in expresso right now and what will come in the near future.

Table of Contents

• 1 Constructing expressions
• 2 Basic manipulations of expressions
• 3 A semantic rule based translator on top of core.logic
• 4 algebraic expression manipulation algorithms
• 5 optimizing expressions

1 Constructing expressions

Expresso expressions are clojure s-expressions. Even if expresso can use custom types to better represent for example poynomials internally they will implement ISeq so that they can be used like regular s-expressions in every regard. Expresso provides a few convenient methods to help you construct expressions:

(use 'numeric.expresso.core)

;; the ex macro is convenient for quickly constructing expressions. variables 
;; are automatically quoted and the function symbols are automatically namespace 
;; qualified, which is important because clojure.core/* behaves different than 
;; core.matrix.operators/*

(ex (+ x y (* x 2 z))) ;=> (clojure.core/+ x y (clojure.core/* x 2 z))

;;If you have a local named x and would like to have the value of x in the 
;;expression you need to unquote it
(let [x 3]
  (ex (+ 1 ~x))) ;=> (clojure.core/+ 1 3)

;;If you have more symbols for which you want the actual values (for example if
;; the constants aren't primitive) Ther is the ex' macro. You have to explicitly 
;; ' (quote) the arguments with it therefore the name :)
(let [x 3]
  (ex' (+ x 'x))) ;=> (clojure.core/+ 3 x)
;; It also takes an optional symbol vector as first argument. The variables in it
;; will be implicitly quoted
(ex' [x] (* 3 x)) ;=> (clojure.core/* 3 x)

;; these macros compile down to calls the the more fundamental ce function 
;; (construct expression) which
;; creates an expression from the symbol and arguments.
(ce `+ [1 2 3]) ;=> (clojure.core/+ [1 2 3])
;;you can think of it like list* + adding information expresso uses in the 
;;algebraic manipulation.

;;construct-with lets you transform your normal heavy number crunshing code to
;; clean symbolic expression generating code. In its body it replaces all the
;; symbols contained in the symbol vector with the equivalent expresso construcing 
;;functions. Is is especially convenient for writing rules.
(construct-with [+ - * /]
  (defn create-silly-expression [x]
    (+ 1 (* 2 (- 3 (/ 4 x))))))

(create-silly-expression 5)
;=>(clojure.core/+ 1 (clojure.core/* 2 (clojure.core/- 3 (clojure.core// 4 5))))

2 Basic manipulations of expressions

You can evaluate an expression providing a symbol map for the symbols in it and you can substitute partsof the expression

(evaluate (ex (+ (* 2 x) (* x 2))) {'x 2}) ;=> 8
(eval (substitute (ex (+ (* 2 x) (* x 2))) {'x 2})) ;=> 8

(substitute (ex (+ (* 1 0) 4)) {(ex (* 1 0)) 0}) ;=> (clojure.core/+ 0 4)

3 A semantic rule based translator on top of core.logic

Term rewriting through rule application is a - or 'the' - fundamental technique for all sorts of expression manipulation. Therfore, expresso would not live up to its aim to be a general clojure library for manipulating expressions without a powerful rule based translator. Here is what the rule based translator looks like:

(use 'numeric.expresso.core)

;;rules are constructed with the rule macro. Rules in expresso are semantic by 
;;default, that means commutative expression match regardlessy of their order of 
;;arguments for example. The syntax is (rule pat :=> trans) where pat is an 
;;expression which can contain variables and trans can be an expression or a core.logic
;;relation which will be called upon succesful matching. An optional guard relation can
;;be specified at the end whith :if guard. See my previous posts for more examples

(construct-with [+ - * /]

(def rules [(rule (+ 0 ?x) :=> ?x)
            (rule (+ 0 ?&*) :=> (+ ?&*))])

(apply-rule (first rules) (+ 0 1)) ;=> 1
(apply-rule (first rules) (+ 1 0)) ;=> 1
(apply-rule (first rules) (+ 0 1 2)) ;=> nil
(apply-rule (second rules) (+ 0 1 2)) ;=>(clojure.core/+ 1 2)
(apply-rule (second rules) (+ 1 0 3 4 2)) ;=> (clojure.core/+ 1 3 4 2)

;;apply-rule tries to apply the given rule. apply-rules tries to apply a whole 
;;vector of rules and transform-expression transforms a given expression according
;;to a rule vector to a normal form on which no rules can be applied anymore.
;;the ?&* represents a sequence-matcher, which matches a subexpression and spits 
;;it in after matching. This allows powerful transformations to be represented as rules
;;advanced rules:
;;The rule macro also supports to define a transformation function inline,
;; with the ;==> syntax and extractors, which can take apart an expression 
;;using a custom extracting function. Together they enable really powerful 
;;translations. For example the following could be part of a function which 
;;rearranges an expression in regard to a variable v using the rule based 
;;translator like this
(with-expresso [+ cons? = - / * ]
(def rearrange-rules
  [(rule [(cons? ?p ?ps) (= (+ ?&+) ?rhs)]
         :==> (let [[left x right] (split-in-pos-sm ?&+ ?p)]
                [?ps (= x (- ?rhs left right))]))
   (rule [(cons? ?p ?ps) (= (* ?&+) ?rhs)]
         :==> (let [[left x right] (split-in-pos-sm ?&+ ?p)]
                [?ps (= x (/ ?rhs (* left right)))]))]))

;;cons? is an extractor which matches a vector and binds ?p to the first and ?ps to
;; the rest of it the part after the :==> is normal cojure code!
;;it is also possible to define custom extractors

4 algebraic expression manipulation algorithms

This is the second big part of expresso which contains functions to solve and rearrange an expression, to simplify it etc. The range of expressions these functions can handle will be greatly enhanced in the second part of gsoc

(simplify (ex (+ (* x 0) (* x (- x x))))) ;=> 0
(simplify (ex (+ (* 2 x) 4 5 (* 3 x)))) ;=> (clojure.core/+ (clojure.core/* 5 x) 9)

;;differentiate takes the derivative of the given expression regarding the
;;variable v
(differentiate 'x (ex (+ (* 3 (** x 2)) (* -2 x))))
;=>(clojure.core/+ (clojure.core/* 6 x) -2)
(differentiate 'y (ex (+ (* 3 (** x 2)) (* -2 x))))
;=> 0

;;rearrange rearranges an expression containing one occurrence of the specified 
;;variable to the form (= v rhs)
(rearrange 'x (ex (= (+ 1 x) 4))) ;=> (clojure.core/= x (clojure.core/- 4 1))
(rearrange 'x (ex (= (+ 1 (* 2 (+ 3 (* 4 x)))) 10)))
;=> (clojure.core/= x (clojure.core// (clojure.core/- 
;   (clojure.core// (clojure.core/- 10 1) (clojure.core/* 2)) 3) (clojure.core/* 4)))

;;solve tries to simplify the expression so that it contains only one occurrence of 
;;the variable, rearranges it then and simplifies the rhs
(solve 'x (ex (= (+ 1 x) 3))) ;=> (clojure.core/= x 2)
(solve 'x (ex (= x (+ x 1)))) ;=> () ;no solution found
(solve 'x (ex (= x x))) ;=> _0 ; x undetermined
(solve 'x (ex (= (* 3 x) (+ (* 4 x)  4)))) ;=> (clojure.core/= x -4)

5 optimizing expressions

Like the solving part above this is in focus for the second part of gsoc.

;;optimize takes an expression optimizes it and returns a function which can be 
;;called with the symbols in the expression.

(def compiled-expr (optimize (+ (* 1 x) (* x 1))))

(compiled-expr {'x 2}) ;=> 4

;;optimize doesn't do very much by now but it recognises common subexpressions
;; and only executes them once to see what optimize has done lets check the result
;; of optimize* which doesn't return a callable function but the optimized expression


(def optimized (optimize* (ex (+ (* 1 x) (* x 1)))))

optimized ;=> (let [local50510 (clojure.core/* 1 x)] 
               ;(clojure.core/+ local50510 local50510))

(evaluate optimized {'x 2}) ;=> 4

all the code you see here is working in the current master branch of expresso. As always comments/critique/thoughts welcome.

Date: 2013-07-29T14:43+0200

Author: Maik Schünemann

Org version 7.8.09 with Emacs version 23

Validate XHTML 1.0