Système d'algèbre informatique (CAS) pour Scala
-
15-11-2019 - |
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
etMutliply
On dirait que ça pourrait devenir désordonné
La solution
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.