Système d'algèbre informatique (CAS) pour Scala

Question

Je recherche un système CAS simple pour Scala.

Il devrait avoir les fonctionnalités suivantes:

• donner accès à l'arbre de syntaxe abstrait (de préférence via des classes de cas pour une correspondance facile)
• analyse String pain grillé
• Simplifier les expressions

---

Si personne n'existe et que je dois écrire quelque chose de basique moi-même, quelle est la meilleure représentation?

Je pense à quelque chose comme ça:

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

J'implémenterais le Algorithme de simplification décrit ici, ce qui semble fastidieux. (Mais peut-être que l'ennui est inévitable lorsqu'il s'agit de simplifier les expressions algébriques?)

Certaines critiques de cette implémentation spécifique sont:

• J'appellerai récursivement simplify Partout sur les arguments des classes de cas (semble être centralisé d'une manière ou d'une autre)
• Traitant des varargs / List arguments à Add et Mutliply On dirait que ça pourrait devenir désordonné

Answer 1

Je ne connais pas un CAS existant pour Scala.

Lorsque je fais le traitement du langage, je trouve normalement beaucoup plus agréable d'utiliser la correspondance de motifs sur une hiérarchie scellée plutôt que le polymorphisme de style OO. Étant donné que l'ajout de nouveaux types de termes est rare (cela signifie un changement de langue) et l'ajout de nouvelles opérations communes, ce côté du problème d'expression semble mieux s'adapter.

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 morceau de technologie que je voulais apprendre, mais je n'ai pas, ce sont des grammaires d'attribut. Ils sont censés retirer une grande partie de l'ennui de ce type de traitement AST. Voir Kiama http://code.google.com/p/kiama/ Pour une implémentation Scala

Soit dit en passant, bien que j'utilise des doubles ici pour votre domaine, vous pourriez mieux utiliser un "Big Rational" - une paire de grands Integers. Ils sont lents mais très précis.