斯卡拉计算机代数系统（CAS）

Question

我正在寻找一个简单的CAS系统的斯卡拉。

它应具有以下特征：

• 给访问抽象语法树（优选经由case类，便于匹配）
• 解析String到AST
• 简化表达式

---

如果不存在，我必须自己写一些基本的东西，什么是最好的表示？

我想是这样的：

abstract trait Term 
{ 
    def simplify:Term 
    def evaluate(assignment:Var => Double):Double 
    def derivative:Term 
} 

case class Const(c:Int) extends Term 
case class Var(x:String) extends Term 

case class Negate(x:Term) extends Term 
case class Subtract(x:Term, y:Term) extends Term 
case class Divide(x:Term, y:Term) extends Term 


object Add { def apply(x:Term*):Add = Add(x.toList) } 
case class Add(xs : List[Term]) extends Term 

object Multiply { def apply(x:Term*):Multiply = Multiply(x.toList) } 
case class Multiply(xs:List[Term]) extends Term 

case class Power(x:Term, y:Term) extends Term 
case class Exp(x:Term) extends Term 

我实现simplification algorithm described here，这似乎有些单调乏味。 （但也许单调乏味是不可避免的，当涉及到简化代数表达式？）

这种具体实施的一些批评是：

• 我会递归调用simplify各地对参数的情况下的地方类（似乎是它可以以某种方式集中）
• 与可变参数/ List参数Add和Mutliply处理似乎是它可以变得混乱

Answer 1

我不知道现有的Scala CAS。

在进行语言处理时，我通常会发现使用模式匹配而不是OO风格的多态性会更令人愉快。由于添加新的术语类型很少（这意味着语言的改变）并且添加新的术语常常表达问题的这一方似乎更适合。

sealed trait Term 
case class Const(c : Double) extends Term 
case class Var(x : String) extends Term 
case class Negate(x : Term) extends Term 
case class Multiply(xs : List[Term]) extends Term 
// etc 

object CAS { 

    // I assume that the assignment map may be incomplete, thus 
    // evaluation is really a partial substitution and then simplification 
    def evaluate(t : Term, assignment : Var => Option[Double]) : Term = t match { 
    case _ : Const => t 
    case v : Var => assignment(v) map Const getOrElse v 
    case Negate(x) => evaluate(Multiply(Const(-1) :: evaluate(x, assignment) :: Nil), assignment) 
    case Multiply(ts) => { 
     val evalTs = ts map { t => evaluate(t, assignment) } 
     val flattened = evalTs flatMap { 
     case Multiply(subs) => subs 
     case t => List(t) 
     } 
     val constTotal = Const((flattened collect { case Const(c) => c }).product) 
     val otherTerms = flattened filter { case t : Const => false; case _ => true } 
     (constTotal, otherTerms) match { 
     case (Const(0), _) => Const(0) 
     case (Const(1), Nil) => Const(1) 
     case (Const(1), _) => Multiply(otherTerms) 
     case _ => Multiply(constTotal +: otherTerms) 
     } 
    } 
    // etc 

    } 

    private val emptyAssignment : (Var => Option[Double]) = { x : Var => None } 

    // simplfication is just evaluation with an empty assignment 
    def simplify(t : Term) : Term = evaluate(t, emptyAssignment) 
} 

一点技术我一直想要了解，但没有是属性语法。他们应该从这种AST处理中获取许多枯燥乏味的东西。另请参阅kiama http://code.google.com/p/kiama/以获得Scala实现

顺便说一下，虽然我在这里为您的域使用双打，但您最好使用“大理性” - 一对BigIntegers。他们很慢但非常精确。