sicmutils.expression.analyze — sicmutils 0.20.0

This namespace defines an API for working with 'expression analyzers' and the ICanonicalize protocol.

Expression analyzers find canonical forms of inputs over limited vocabularies of operations. For example, a polynomial analyzer will expose operations like addition, subtraction, multiplication, and exponentiation by positive integers (but not division).

An expression containing only these operations and symbols can then be converted to and from a polynomial canonical form, which in this example would have the effect of grouping like terms; a rational function backend would include the division operation and be capable of cancellation. Canonicalizing an expression with respect to an analyzer is therefore effected by a round-trip to and from the canonical form.

*inhibit-expt-simplify* clj/s

Exponential expressions with non-integer exponents must become kernels, because they cannot become polynomial exponentials.

To disable this guard, bind this variable to false.

auxiliary-variable-fetcher clj/s

(auxiliary-variable-fetcher analyzer)

Given an analyzer instance created with make-analyzer, returns a function of no arguments that, when called, will return the analyzer's current map of generated symbol => subexpression.

Call the no-argument function returned by passing analyzer to initializer to reset the table.

For example:

(def a (poly-analyzer))
(def ea (expression-analyzer a))

(def get-tables (auxiliary-variable-fetcher a))
(def reset-tables! (initializer a))

(ea '(+ x x x (sin x) (sin x)))
;;=> (+ (* 3 x) (* 2 -s-0000000000000000))

(get-tables)
;;=> {'-s-0000000000000000 '(sin x)}

(reset-tables!)
(get-tables)
;;=> {}

default-simplifier clj/s

(default-simplifier analyzer)

Given an analyzer instance created with make-analyzer, returns a simplifier (a function of S-expression => simplified S-expression) that will reset its internal symbolic bindings at every invocation.

Equivalent to:

(let [new-analysis! (initializer analyzer)
      simplify (expression-simplifier analyzer)]
  (fn [expr]
    (new-analysis!)
    (simplify expr)))

See expression-simplifier for a version that will assign the same symbol to every expression it sees more than once.

expression-analyzer clj/s

(expression-analyzer analyzer)

Given an analyzer instance created with make-analyzer, returns a function that will take a symbolic expression, and return a simplified expression with any subexpression NOT supported by the analyzer backend replaced by a generated symbol.

Any replaced subexpression will map to the SAME symbol over repeated invocations, unless you call the resetting function generated by passing analyzer to initializer.

For example:

(let [a  (poly-analyzer)
      ea (expression-analyzer a)]
  (ea '(+ x x x (sin x) (sin x))))
;;=> (+ (* 3 x) (* 2 -s-0000000000000000))

expression-simplifier clj/s

(expression-simplifier analyzer)

Given an analyzer instance created with make-analyzer, returns a simplifier (a function of S-expression => simplified S-expression) that will NOT reset its internal symbolic bindings across invocations.

This can be useful if the analyzer backend has any sort of memoization or caching of expressions.

Pass analyzer to initializer to create a function that, when called, will explicitly reset the internal cache:

(def reset-analyzer! (initializer analyzer))
(def simplify (expression-simplifier analyzer))

(reset-analyzer!)
(simplify <expr>)

See default-simplifier for a version that will reset its internal variable assignment cache at each invocation.

ICanonicalize clj/s protocol

ICanonicalize captures the methods exposed by a SICMUtils analyzer backend.

->expression clj/s

(->expression analyzer b variables)

Convert a canonical form b back to S-expression form.

Each ICanonicalize instance uses variables in different ways. The variables sequence is typically obtained from the continuation invoked by [[expression->]], so these functions are complementary.

expression-> clj/s

(expression-> analyzer x continue)

(expression-> analyzer x continue compare-fn)

Invokes continue with two arguments:

• A version of x converted to the canonical form represented by analyzer
• A (sorted by compare-fn) sequence of variables found in x.

compare-fn is used to sort variables. Defaults to [[clojure.core/compare]].

known-operation? clj/s

(known-operation? analyzer x)

Returns true if the symbolic operation x is considered fundamental by analyzer, false otherwise.

initializer clj/s

(initializer analyzer)

Given an analyzer instance created with make-analyzer, returns a function of no arguments that, when called, will reset the analyzer's internal caches of symbol => subexpression and subexpression => symbol.

make-analyzer clj/s

(make-analyzer backend)

(make-analyzer backend symbol-generator)

Make-analyzer takes an analyzer backend (which implements ICanonicalize) and returns a dictionary with the apparatus necessary to prepare expressions for analysis by replacing subexpressions formed from operations unknown to the analyzer with generated symbols, and backsubstituting after analysis is complete.

For example, in the case of polynomial canonical form, we would replace a subexpression like (sin x) with a gensym, before entry, since the sin operation is not available to the polynomial canonicalizer, and restore it afterwards.

monotonic-symbol-generator clj/s

(monotonic-symbol-generator prefix)

Returns a function which generates a sequence of symbols with the given prefix with the property that later symbols will sort after earlier symbols.

This is important for the stability of the simplifier. (If we just used clojure.core/gensym, then a temporary symbol like G__1000 will sort earlier than G__999. This will trigger errors at unpredictable times, whenever clojure.core/gensym returns two symbols that cross an order-of-magnitude boundary.)