Symbolic Algebra using Scala

Hi Martin

Interesting project! I think Scala's implicit conversions is an important tool for a project like this, although it won't be teh answer to all of your questions. Google "scala implicit conversions".

Cheers,
Daniel



On Mon, Jun 28, 2010 at 10:59 AM, Martin Baker <scala9256 [at] martinb [dot] com> wrote:

I would like to build a open source computer algebra program using Scala. That
is a program which can work with mathematical structures like complex numbers,
vectors, matrices, quaterenions, tensors, Clifford algebras, polynomials...
this list goes on. Then to be able to do symbolic computations using these.
There is already an open source program called Axiom, written in a different
language, that does exactly what I want:

http://en.wikipedia.org/wiki/Axiom_%28computer_algebra_system%29

The problem with this is that it has a poor development infrastructure: no
IDE, poor error messages, no access to the java/scalar library.

So what I would like is a program with the mathematical power of Axiom but the
programming environment of Scala.

I have seen a program called 'scalala' (http://code.google.com/p/scalala/) but
this seems to concentrate on numeric computing for linear algebra rather than
the type of symbolic algebra that Axiom can handle.

Although Axiom is written in Lisp, this is used to create a user language
called SPAD (and a derivation called Aldor), SPAD is remarkably similar to
Scala in that it has a similar combination of OO and Functional programming,
strong typing and so on.

So at first sight it would seem very easy to do what I want, just create
classes for complex, vectors, matrices, quaterenions .. and so on. However
when I think about this I cant work how to get them to interact with each
other and the language in the ways that's needed.

This is where it gets complicated to explain, so rather than write a long
explanation here I though it better to put the issues on this page:

http://www.euclideanspace.com/maths/standards/program/language/

If anyone, with a better understanding of Scala than me, could have a quick
look at this and give me any thoughts about whether Scala can do the sorts of
things I would appreciate your comments.

Thanks,

Martin

I wrote this little bit of code sometime ago, is it the kind of thing you are
after?

sealed abstract class Tree

case class Sum(l: Tree, r: Tree) extends Tree {
override def toString():String =
"(" + l.toString() + "+" + r.toString() + ")"
}
case class Var(n: String) extends Tree {
override def toString() = n
}
case class Const(v: Double) extends Tree {
override def toString() = v.toString
}
case class Power(x:Var, y:Const) extends Tree {
override def toString() = x + "^" + y
}
case class Product(x:Tree, y:Tree) extends Tree {
override def toString() = x + "*" + y
}

object Math {
type Environment = String => Double

def eval(t: Tree, env: Environment): Double = t match {
case Sum(l, r) => eval(l, env) + eval(r, env)
case Product(l, r) => eval(l, env) * eval(r, env)
case Power(x, y) => java.lang.Math.pow(eval(x, env), eval(y, env))
case Var(n) => env(n)
case Const(v) => v
}

def simplify(t: Tree): Tree = t match {
case Power(l, Const(y)) if (y == 1) => l
case Product(l,r) if (r==Const(1)) => simplify(l)
case Product(l,r) if (l==Const(1)) => simplify(r)
case Product(l,r) => Product(simplify(l), simplify(r))
case Sum(Const(a), Const(b)) => Const(a + b)
case Sum(l, r) if (l==r) => Product(Const(2), l)
case Sum(l, r) => Sum(simplify(l), simplify(r))
case _ => t
}

def derive(t: Tree, v: String): Tree = t match {
case Power(Var(n), Const(y)) if (v == n) => Product(Const(y),
Power(Var(n), Const(y - 1)))
case Sum(l, r) => Sum(derive(l, v), derive(r, v))
case Var(n) if (v == n) => Const(1)
case _ => Const(0)
}

def main(args: Array[String]):Unit= {
val exp: Tree = Power(Var("x"), Const(2))
println("Expression: " + exp + "=" + simplify(exp))

println("Derivative relative to x:\n " + derive(exp, "x") + " = " +
simplify(derive(exp, "x")))
println("Derivative relative to y:\n " + derive(exp, "y") + " = " +
simplify(derive(exp, "y")))

val env: Environment = { case "x" => 5 case "y" => 7 }
println("Evaluation with x=5, y=7: " + eval(exp, env))

}

}

Kiama [1] might be useful for symbolic manipulation of your constructs.

You've already found Scalala, which is a great example of embedding a
DSL in Scala.

-jason

[1] http://code.google.com/p/kiama/wiki/Lambda2

On Mon, Jun 28, 2010 at 10:59 AM, Martin Baker wrote:
> I would like to build a open source computer algebra program using Scala. That
> is a program which can work with mathematical structures like complex numbers,
> vectors, matrices, quaterenions, tensors, Clifford algebras, polynomials...
> this list goes on. Then to be able to do symbolic computations using these.
> There is already an open source program called Axiom, written in a different
> language, that does exactly what I want:
>
> http://en.wikipedia.org/wiki/Axiom_%28computer_algebra_system%29
>
> The problem with this is that it has a poor development infrastructure: no
> IDE, poor error messages, no access to the java/scalar library.
>
> So what I would like is a program with the mathematical power of Axiom but the
> programming environment of Scala.
>
> I have seen a program called 'scalala' (http://code.google.com/p/scalala/) but
> this seems to concentrate on numeric computing for linear algebra rather than
> the type of symbolic algebra that Axiom can handle.
>
> Although Axiom is written in Lisp, this is used to create a user language
> called SPAD (and a derivation called Aldor), SPAD is remarkably similar to
> Scala in that it has a similar combination of OO and Functional programming,
> strong typing and so on.
>
> So at first sight it would seem very easy to do what I want, just create
> classes for complex, vectors, matrices, quaterenions .. and so on. However
> when I think about this I cant work how to get them to interact with each
> other and the language in the ways that's needed.
>
> This is where it gets complicated to explain, so rather than write a long
> explanation here I though it better to put the issues on this page:
>
> http://www.euclideanspace.com/maths/standards/program/language/
>
> If anyone, with a better understanding of Scala than me, could have a quick
> look at this and give me any thoughts about whether Scala can do the sorts of
> things I would appreciate your comments.
>
> Thanks,
>
> Martin
>

Dear Martin,
i like your thinking. i'm sure you're aware of this list of symbolic algebra packages. i've never played with either, however, Java Algebra System and SymJA can -- in principle -- both be used with Scala straight away.
If you're intent on rolling your own, you might look to DoCon to see how they've used a pure functional substrate to express the vagaries of Symbolic Algebra.
Best wishes,
--greg

On Mon, Jun 28, 2010 at 3:07 PM, Channing Walton <channingwalton [at] mac [dot] com> wrote:

I wrote this little bit of code sometime ago, is it the kind of thing you are
after?

sealed abstract class Tree

case class Sum(l: Tree, r: Tree) extends Tree {
 override def toString():String =
   "(" + l.toString() + "+" + r.toString() + ")"
}
case class Var(n: String) extends Tree {
 override def toString() = n
}
case class Const(v: Double) extends Tree {
 override def toString() = v.toString
}
case class Power(x:Var, y:Const) extends Tree {
 override def toString() = x + "^" + y
}
case class Product(x:Tree, y:Tree) extends Tree {
 override def toString() = x + "*" + y
}

object Math {
 type Environment = String => Double

 def eval(t: Tree, env: Environment): Double = t match {
   case Sum(l, r) => eval(l, env) + eval(r, env)
   case Product(l, r) => eval(l, env) * eval(r, env)
   case Power(x, y) => java.lang.Math.pow(eval(x, env), eval(y, env))
   case Var(n) => env(n)
   case Const(v) => v
 }

 def simplify(t: Tree): Tree = t match {
   case Power(l, Const(y)) if (y == 1) => l
   case Product(l,r) if (r==Const(1)) => simplify(l)
   case Product(l,r) if (l==Const(1)) => simplify(r)
   case Product(l,r) => Product(simplify(l), simplify(r))
   case Sum(Const(a), Const(b)) => Const(a + b)
   case Sum(l, r) if (l==r) => Product(Const(2), l)
   case Sum(l, r) => Sum(simplify(l), simplify(r))
   case _ => t
 }

 def derive(t: Tree, v: String): Tree = t match {
   case Power(Var(n), Const(y)) if (v == n) => Product(Const(y),
Power(Var(n), Const(y - 1)))
   case Sum(l, r) => Sum(derive(l, v), derive(r, v))
   case Var(n) if (v == n) => Const(1)
   case _ => Const(0)
 }

 def main(args: Array[String]):Unit= {
   val exp: Tree = Power(Var("x"), Const(2))
   println("Expression: " + exp + "=" + simplify(exp))

   println("Derivative relative to x:\n " + derive(exp, "x") + " = " +
simplify(derive(exp, "x")))
   println("Derivative relative to y:\n " + derive(exp, "y") + " = " +
simplify(derive(exp, "y")))

   val env: Environment = { case "x" => 5 case "y" => 7 }
   println("Evaluation with x=5, y=7: " + eval(exp, env))

 }

}
--
View this message in context: http://scala-programming-language.1934581.n4.nabble.com/Symbolic-Algebra-using-Scala-tp2270633p2271523.html
Sent from the Scala - User mailing list archive at Nabble.com.

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com

Thank you very much for the replies on this thread, you have given me a lot of
things to read and try to understand in more detail.

I think there is a fundamental issue that I sort of implied but did not state
explicitly in my original post, should I:

1) Use Scala to parse and run a custom mathematics specific language.
2) Use Scala itself as the language with mathematics types added and tweak
Scala to work with these types.

(I guess that is what meant by External Vs. Internal DSLs ?)

What I was hoping for was the second because then all the control structures,
IDE, error messages and so on are all provided by the Scala infrastructure.

It would be nice if I could do this by just adding a java library such as Java
Algebra System and SymJA, it looks like there is some good stuff there but its
hard to know how extensible a pure object oriented approach like this would
be. To find out I guess I would need to take time to evaluate them.

Would I be right in thinking that, of all the examples given 'scalala' is
perhaps the example that has gone furthest down this second route? So perhaps
I should investigate 'scalala' first (even though it seems to be aimed more at
numeric applications).

Thanks,

Martin

You are correct that that is what is meant by internal vs. external DSLs.It's often possible to wrap an existing Java library with an internal scala DSL. But it depends how custom you want your language to be. If Scala syntax, as flexible as it is, is not flexible enough for what you envision, Scala's parsing library is quite powerful too.

On Tue, Jun 29, 2010 at 5:31 AM, Martin Baker <scala9256 [at] martinb [dot] com> wrote:

Thank you very much for the replies on this thread, you have given me a lot of
things to read and try to understand in more detail.

I think there is a fundamental issue that I sort of implied but did not state
explicitly in my original post, should I:

1) Use Scala to parse and run a custom mathematics specific language.
2) Use Scala itself as the language with mathematics types added and tweak
Scala to work with these types.

(I guess that is what meant by External Vs. Internal DSLs ?)

What I was hoping for was the second because then all the control structures,
IDE, error messages and so on are all provided by the Scala infrastructure.

It would be nice if I could do this by just adding a java library such as Java
Algebra System and SymJA, it looks like there is some good stuff there but its
hard to know how extensible a pure object oriented approach like this would
be. To find out I guess I would need to take time to evaluate them.

Would I be right in thinking that, of all the examples given 'scalala' is
perhaps the example that has gone furthest down this second route? So perhaps
I should investigate 'scalala' first (even though it seems to be aimed more at
numeric applications).

Thanks,

Martin