Scala的计算机代数系统(CAS)

发布时间：2020-12-16 18:37:36 所属栏目：安全来源：网络整理

导读：我正在为 scala寻找一个简单的CAS系统. 它应该具有以下功能：允许访问抽象语法树(最好通过案例类以便于匹配) 将字符串解析为AST 简化表达如果不存在并且我必须自己写一些基本的东西,那么最好的代表是什么？我在想这样的事情： abstract trait Term{ def s

我正在为 scala寻找一个简单的CAS系统.

它应该具有以下功能：

>允许访问抽象语法树(最好通过案例类以便于匹配)
>将字符串解析为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,这似乎很乏味. (但是在简化代数表达式时,可能乏味不可避免？)

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

>我会在case类的参数上递归地调用简化(看起来它可能以某种方式集中)
>处理Add和Mutliply的varargs / List参数似乎可能会变得混乱

解决方法

我不知道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处理中汲取大量的乏味.有关Scala实现,请参阅kiama http://code.google.com/p/kiama/

顺便说一句,虽然我在这里使用双打为你的域名,你可能最好使用“大理性” – 一对BigIntegers.它们很慢但很精确.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!