Computer algebra in ML
Jon Harrop
I would like to learn more about the design and implementation of computer
algebra systems, particularly using the ML family of languages. I have
looked at the source code to Maxima but its lack of typeful programming and
pattern matching make it seriously tedious. I also stumbled upon a very
elegant symbolic integrator called the "Poor Man's Integrator" by Manuel
Bronstein that implements the parallel Risch algorithm in only 95 lines of
Maple code:
http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/index.html
However, that Maple source code relies upon non-trivial CA functions that I
not only do not know how to implement in ML but cannot even guess the
structure of the types they act upon.
Has anyone implemented any simple CA systems in ML? What are the basic
datatypes used to represent mathematical expressions?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
> I also stumbled upon a very elegant symbolic integrator called the
> "Poor Man's Integrator" by Manuel Bronstein that implements the
> parallel Risch algorithm in only 95 lines of Maple code:
Conventional wisdom is that the Risch algorithm is a beautiful
theoretical accomplishment but doesn't give very usable results in
practice. Maybe I'm behind the times.
> Has anyone implemented any simple CA systems in ML? What are the basic
> datatypes used to represent mathematical expressions?
Based on what little I know about Macsyma and Mathematica, the
corresponding ML datatypes would just be the obvious ones. The
algorithms themselves are a lot more interesting/difficult than the
datatypes. There is a pretty good book by Buchberger called "Computer
Algebra" or something like that, though it is probably outdated by now.
Jon Harrop
> Based on what little I know about Macsyma and Mathematica, the
> corresponding ML datatypes would just be the obvious ones.
I thought the obvious data type was:
type t =
| Num of BigRational
| Add of t * t
| Mul of t * t
| Pow of t * t
but I get the impression most CASs use (multivariate?) polynomials as their
primitives.
> The
> algorithms themselves are a lot more interesting/difficult than the
> datatypes. There is a pretty good book by Buchberger called "Computer
> Algebra" or something like that, though it is probably outdated by now.
I'll check it out, thanks.
Paul Rubin
> but I get the impression most CASs use (multivariate?) polynomials as their
> primitives.
Yes, there are a lot of fancy algorithms (beyond my math level) for
dealing with multivariate factoring, etc. Also things like formal power
series. You've used Mathematica so I'm pretty sure it should be fairly
obvious to you what kinds of datatypes occur in the expression nodes.
Jon Harrop
Not at all, no. My first thought is that they were using the data type I
just described and doing some non-trivial simplifications on it but more
experience suggests that it is using a far more sophisticated primitive
representation and what I perceived to be symbolic simplifications were
actually nothing more than canonicalization in a more expressive
representation.
Waldek Hebisch
>
> I would like to learn more about the design and implementation of computer
> algebra systems, particularly using the ML family of languages. I have
> looked at the source code to Maxima but its lack of typeful programming and
> pattern matching make it seriously tedious.
You should look at FriCAS or Axiom or OpenAxiom. They build on
code of commercial Axiom released by NAG. This code originated as
Scratchpad II at IBM and was effort to build fully typed computer
algebra system. The type system is based on system F, main
features are types as values and parametrized types. There is
a type hierarchy modeling large part of computer algebra.
--
Waldek Hebisch
heb...@math.uni.wroc.pl