Computer Algebra System (CAS) para Scala

Question

Estoy buscando un sistema CAS simple para scala.

Se debe tener las siguientes características:

• dar acceso al árbol de sintaxis abstracta (preferiblemente a través de clases de casos para una fácil adaptación)
• de análisis String a AST
• simplificar las expresiones

---

Si no existe ninguno y tengo que escribir algo básico, ¿cuál es el la mejor representación?

estoy pensando algo como esto:

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 

me gustaría poner en práctica el simplification algorithm described here, que parece tedioso. (Pero tal vez el tedio es inevitable cuando se trata de simplificar las expresiones algebraicas?)

Algunas críticas de esta aplicación específica son:

• voy a estar llamando de forma recursiva simplify por todo el lugar en los argumentos al caso clases (parece que podría ser centralizada de alguna manera)
• Tratar con los varargs/List argumentos a Add y Mutliply parece que podría causar problemas

Answer 1

No sé de un CAS existente para Scala.

Al hacer el procesamiento del lenguaje, normalmente me resulta mucho más agradable utilizar la coincidencia de patrones sobre una jerarquía sellada en lugar de un polimorfismo de estilo OO. Dado que agregar nuevos tipos de términos es raro (eso significa un cambio de idioma) y agregar nuevas operaciones comunes, este lado del problema de expresión parece encajar mejor.

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) 
} 

Un poco de la tecnología que he querido aprender pero no tengo las gramáticas de atributos. Se supone que deben sacar gran parte del tedio de este tipo de procesamiento de AST. Ver kiama http://code.google.com/p/kiama/ para una aplicación Scala

Por cierto, mientras que yo utilizo dobles aquí para su dominio que puede ser mejor usar un "gran racional" - un par de BigIntegers. Son lentos pero muy precisos.