Symbolic mathematical calculations in Clojure vs. F#

Question

I have come across the following F# sample and found it intriguing.

http://www.codeproject.com/KB/net-languages/SymbolicCalcInFS.aspx

Does Clojure have language/library facilities for doing something like this with ease? It is ok to force Polish notation for formulas, if that makes things easier.

Thanks, and let me know if there are questions.

Ankylostomiasis

Answer 1

I don't know much about Clojure, but here are, at least, some pointers.

The key feature that makes the F# code nice is pattern matching on algebraic data types. An algebraic data type is for example the declaration of the Expression type (that is used to represent mathematical expressions) and pattern matching is the match construct that is used to check for various known cases when implementing simplification or differentiation.

I don't think that Clojure has any built-in support for pattern matching, but it can be implemented as a library. One library that looks quite interesting is the patter-match module (in Clojars). Here is an example that uses it to implement algebraic evaluator (which is quite close to the F# article).

Another thing that appears in the F# article is active patterns (which allow you to declare and reuse patterns). I don't think that there is a Clojure library for that, but given the flexibility of the language, it should be possible to implement them too (however, they are not really that necessary in the F# article)

Conflagrant

Answer 2

Lisp has long history in symbolic computing. See the AI case study book by Peter Norvig. Lisp provides a lot of great language features to abstract the common operations on the symbols. Sometimes you can write really concise code (more concise/short than F#).

Static languages like F# have strong type systems and convenient pattern matching on the data types. The compiler could find errors that are caught by the type system, e.g. lack of considering one special case. Thinking about types with your data could also reduce the chances for runtime error. The type inference in F# also makes F# code very concise.

Unroof

+1 for PAIP, been reading it past two weeks and it's great so far – Bischoff

Answer 3

Symbolic differentiation was one of the first applications of lisp!

I made a blogpost about a simple symbolic differentiator. It only deals with + and *, but it is easily extended.

It was part of a series I wrote to introduce beginners to clojure at a conference in London, to show how easy it is for clojure to manipulate its own code.

Of course the cute thing is that having done the differentiation, the code can then be compiled! So you can produce differentiated versions of user input, or macros that produce functions and their derivatives, etc.

The original's here, and nicely syntax highlighted:

http://www.learningclojure.com/2010/02/clojure-dojo-4-symbolic-differentiation.html

But I've posted the code here so you can have a look:

;; The simplest possible symbolic differentiator

;; Functions to create and unpack additions like (+ 1 2)
(defn make-add [ a b ] (list '+ a b))
(defn addition? [x] (and (=(count x) 3) (= (first x) '+)))
(defn add1   [x] (second x))
(defn add2   [x] (second (rest x)))


;; Similar for multiplications (* 1 2)
(defn make-mul [ a b ] (list '* a b))
(defn multiplication? [x] (and (=(count x) 3) (= (first x) '*)))
(defn mul1   [x] (second x))
(defn mul2   [x] (second (rest x)))


;; Differentiation. 
(defn deriv [exp var]
  (cond (number? exp) 0                                                              ;; d/dx c -> 0
        (symbol? exp) (if (= exp var) 1 0)                                           ;; d/dx x -> 1, d/dx y -> 0

        (addition? exp) (make-add (deriv (add1 exp) var) (deriv (add2 exp) var))     ;; d/dx a+b -> d/dx a + d/dx b
        (multiplication? exp) (make-add (make-mul (deriv (mul1 exp) var) (mul2 exp)) ;; d/dx a*b -> d/dx a * b + a * d/dx b
                                        (make-mul (mul1 exp) (deriv (mul2 exp) var)))
        :else :error))


;;an example of use: create the function x -> x^3 + 2x^2 + 1 and its derivative 
(def poly '(+ (+ (* x (* x x)) (* 2 (* x x))) 1))

(defn poly->fnform [poly] (list 'fn '[x] poly))

(def polyfn  (eval (poly->fnform poly)))
(def dpolyfn (eval (poly->fnform (deriv poly 'x))))



;;tests

(use 'clojure.test)

(deftest deriv-test
  (testing "binary operators"
    (is (= (let [m '(* a b)] [(multiplication? m) (make-mul (mul1 m) (mul2 m))]) [true  '(* a b)]))
    (is (= (let [m '(* a b)] [(addition? m)       (make-add (add1 m) (add2 m))]) [false '(+ a b)])))
  (testing "derivative function"

    (is (= (deriv '0 'x)               '0))
    (is (= (deriv '1 'x)               '0))
    (is (= (deriv 'x 'x)               '1))
    (is (= (deriv 'y 'x)               '0))
    (is (= (deriv '(+ x x) 'x)         '(+ 1 1)))
    (is (= (deriv '(* x x) 'x)         '(+ (* 1 x) (* x 1))))
    (is (= (deriv '(* x x) 'y)         '(+ (* 0 x) (* x 0))))
    (is (= (deriv '(* x (* x x)) 'x)   '(+ (* 1 (* x x)) (* x (+ (* 1 x) (* x 1)))))))
  (testing "function creation: d/dx (x^3 + 2x^2 + 1) = 3x^2 + 4x "
    (let [poly '(+ (+ (* x (* x x)) (* 2 (* x x))) 1)]
      (is (= ((eval (poly->fnform poly)) 3) 46))
      (is (= ((eval (poly->fnform (deriv poly 'x))) 3)))))) 

Dishabille

Answer 4

I haven't tried it, but Clojuratica looks very interesting.

Stefansson

Answer 5

Well, now Clojure offer powerful pattern matching libraries :

1. matchure : https://github.com/dcolthorp/matchure
2. match : https://github.com/swannodette/match

Ribbentrop

Answer 6

Yes, a system such as you describe now exists on Clojure! It is none other than Gerry Sussman's companion system to his -and Wisdom's- SICM (Structure and Interpretation of Classical Mechanics) book. For Clojure it's been named sicmutils, and ported by Colin Smith.

I've described it briefly elsewhere - https://mcmap.net/q/786186/-computer-algebra-for-clojure - but in short yes, it definitely does the four things you F# article mentions, viz.

1. Differentiation:
2. Simplification of algebraic expressions
3. Formatting
4. Parsing of expressions

and much, much more...

1) Differentiation (full partial differentiation supported)

> (defn ff [x y] (* (expt x 3)(expt y 5)))
> ((D ff) 'x 'y) ==> (down (* 3 (expt x 2) (expt y 5)) (* 5 (expt x 3) (expt y 4))) 
> ;; i.e. vector of results wrt to both variables

NB. Two types of vectors are supported, "up" and "down" to accomodate covariant and contravariant expressions

2) Simplification of expressions: Oh, yes...

> (def unity (+ (square sin) (square cos)))
> (unity 'x)   ==> 1 ;; yes we can deal with symbols

3) Formatting: Expressions can be rendered in TeX for beautiful display. I can't show this easily here, but currently a Maple-style notebook/workshhet is under development, using Clojure's "Gorilla"

4) Parsing: Obviously. Converting between expressions and functions is a core part of the system.

Have a look at https://github.com/littleredcomputer/sicmutils . you don't even need Clojure to run it, you can use the supplied Java jar file.

Eighty