Scala的计算机代数系统（CAS）

Question

Scala的计算机代数系统（CAS）

scalaimplementationcascomputer-algebra-systems

5

我正在寻找一个适用于Scala的简单的CAS系统。

它应该具备以下功能：

- 通过case类（便于匹配）提供对抽象语法树的访问权限 - 将字符串解析为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

我会实现这里描述的简化算法，看起来很繁琐。（但也许在简化代数表达式时无法避免繁琐？）

一些对此特定实现的批评是：

我将在各个地方递归调用simplify，对于案例类的参数（似乎可以以某种方式集中处理）
处理Add和Multiply的可变参数/ List参数似乎会变得混乱

- dsg

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James Iry · Accepted Answer

我不知道是否存在适用于Scala的现有CAS。

在进行语言处理时，我通常更喜欢使用密封层次结构上的模式匹配，而不是面向对象的多态性。由于添加新的术语类型很少（这意味着语言的变化），而添加新操作很常见，因此表达问题的这一方面似乎更加适合。

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实现。

顺便说一句，虽然我在这里使用double，但你最好使用“big rational”，即两个BigIntegers。它们比较慢，但非常精确。