algebra system & core.logic

[Brent Millare]

Is there work towards building an algebra system with core.logic? So one could analyze mathematical expressions: compute symbolic derivatives, simplify expressions, determine undefined variables, and other forms of analysis.

If there isn't, I have a good starting problem that I need help on.

Lets say I have a bunch of equations, with the left hand side a single variable, and the right is some expression. They are not ordered in any way but I would like to order them, (if possible, otherwise throw useful error), such that there isn't any dependency problems. Is there a good way to do this with core.logic? And is the performance comparable to a hand coded solution. Or put another way, can it do this in seconds for 500 equations?

[David Nolen]

On Fri, May 18, 2012 at 8:31 PM, Brent Millare <brent....@gmail.com> wrote:

Is there work towards building an algebra system with core.logic? So one could analyze mathematical expressions: compute symbolic derivatives, simplify expressions, determine undefined variables, and other forms of analysis.

 Not that I'm aware of.

 

are not ordered in any way but I would like to order them, (if possible, otherwise throw useful error), such that there isn't any dependency problems. Is there a good way to do this with core.logic? And is the performance comparable to a hand coded solution. Or put another way, can it do this in seconds for 500 equations?

Unknown :) I do know that The Art of Prolog does cover a simple system based on the Prolog Equation Solving System. You might want to start research there.

David 

[Brent Millare]

I'm working through "The Art of Prolog" at the moment, we'll see where it takes me.

[David Nolen]

It might also be interesting to pursue a hybrid system - that's the whole point of core.logic - being able to mix functional and relational programming with minimal hassle.

David

--

You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Brent Millare]

That's more or less what I'm going to have to do anyways. It's great that clojure + core.logic make that as easy as possible.

[Julian]

Core.logic isn't the only way to approach this problem. In Peter Norvig's PAIP he included a simple algebra system, macsyma http://norvig.com/paip/macsyma.lisp (in common lisp).

JG

[Martin Jul]

Symbolic computation sounds like a really great project! 

For your specific problem of sorting the dependencies, you can do a "topological sort" of the dependency graph of your equations in linear time (given there are no cyclic dependencies, otherwise it would detect the failure). There are standard algorithms to do that.

It would be interesting to compare to core.logic's performance. Modelling the dependencies in core.logic is straightforward, but ordering them in linear time is not obvious to me - but I would love to see the code if you do it.

All the best, 

Martin

[Brent Millare]

On Monday, May 21, 2012 7:11:01 AM UTC-4, Martin Jul wrote:

Symbolic computation sounds like a really great project! 

For your specific problem of sorting the dependencies, you can do a "topological sort" of the dependency graph of your equations in linear time (given there are no cyclic dependencies, otherwise it would detect the failure). There are standard algorithms to do that.

I ended up coding my own hand solution but I started from the leaves and worked towards the root nodes. I'll try the topological sort + reverse list approach and then compare performances. The topological sort code looks much simpler.

[Brent Millare]

Actually, after working through the algorithm presented in the wiki, I think my implementation is basically equivalent given the data structures I'm using. :|

[Alex Gian]

No, there isn't a system based on core.logic, AFAIK, but Gerry Sussmans scmutils has had an succesful initial port.
I am sure that core.logic and many other Clojure facilities could be used to improve the symbolic logic, enable better algorithms etc, and I certainly hope this will happen.

Here's a little plug I made about it, I hope it's not too Off-topic

===================================

It may be of interest to readers of this thread that Gerry Sussman's scmutils system is being ported to Clojure.
This is a very advanced CAS, offering things like automatic differentiation, literal functions, etc, much in the style of Maple.
It is used at MIT for advanced programs on dynamics and differential geometry, and a fair bit of electrical engineering stuff.  It is also the system used in Sussman&Wisdom's "sequel" (LOL) to SICP, SICM (Structure and Interpretation of Classical Mechanics).
Although originally a Scheme program, this is not a direct translation, but a ground-up rewrite to take advantage of the best features of Clojure.  It's been named sicmutils, both in honour of the original and of the book
This superb effort is the work of Colin Smith and you can find it at https://github.com/littleredcomputer/sicmutils .

I believe that this could form the basis of an amazing Computer Algebra System for Clojure, competitive with anything else available.  Although it is a pretty huge beast, as you can imagine, and tons of stuff remains to be ported, the basics are pretty much there, the system will differentiate, and handle literals and literal functions pretty well.  It is a work in progress.  The system also uses the "generic" approach advocated by Sussman, whereby operations can be applied to functions, creating a great abstraction that simplifies notation no end.

Here's a taster:

> (def unity (+ (square sin) (square cos)))
> (unity 2.0)  ==>  1.0
> (unity 'x)   ==> 1 ;; yes we can deal with symbols
> (def zero (D unity))  ;; Let's differentiate
> (zero 2.0)   ==> 0

SicmUtils introduces two new vector types “up” and “down” (called “structures”), they work pretty much as you would expect vectors to, but have some special mathematical (covariant, contravariant) applications, and also some programming properties in that they are executable!

> (def fnvec (up sin cos tan))  => fnvec
> (fnvec 1)   ==> (up 0.8414709848078965 0.5403023058681398 1.5574077246549023)
> ;; differentiated
> ((D fnvec) 1)  ==>  (up 0.5403023058681398 -0.8414709848078965 3.425518820814759)
> ;; derivative with symbolic argument
> ((D fnvec) 'θ) ==> (up (cos θ) (* -1 (sin θ)) (/ 1 (expt (cos θ) 2))) 

Partial differentiation is fully 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

The system also supports TeX output, polynomial factorization, and a host of other goodies.  Lots of stuff, however, that could be easily implemented has not been done purely out of lack of human resources.  Graphic output and a "notepad/worksheet" interface (using Clojure's Gorilla) are also being worked on.

I hope this has gone some way towards whetting your appetite enough to visit the site and give it a whirl.  You don't even need Clojure, you could run it off the provided jar file.

===================================