Система компьютерной алгебры (CAS) для Scala

Я ищу простую систему CAS для scala.

Он должен иметь следующие особенности:

  • предоставить доступ к абстрактному синтаксическому дереву (предпочтительно через классы case для легкого сопоставления)
  • разобрать String в 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 повсюду в аргументах классов case (похоже, это можно как-то централизованно)
  • Работа с аргументами varargs / List для Add и Mutliply может привести к путанице.

scala cas implementation computer-algebra-systems
person dsg    schedule 18.05.2011    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Я не знаю о существующей CAS для Scala.

При обработке языка мне обычно гораздо приятнее использовать сопоставление с образцом в закрытой иерархии, а не полиморфизм в стиле объектно-ориентированного программирования. Поскольку добавление новых типов терминов происходит редко (это означает смену языка), а добавление новых операций является распространенным явлением, эта сторона проблемы выражения кажется более подходящей.

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.

Между прочим, хотя я использую здесь двойные числа для вашего домена, вам, возможно, лучше использовать «большой рациональный» — пару BigIntegers. Они медленные, но очень точные.

person James Iry    schedule 18.05.2011
comment
Спасибо! Любые советы о том, как упростить выражения формы: ((a * c * x^2) + (b * x^2)) быть (a*c + b) * x^2? Аналогию было легко сделать с Power, но списки для Multiply и Add усложняют мне задачу. - person dsg; 19.05.2011
comment
В документе, на который вы ссылаетесь, описывается аналогичное преобразование из (x ^ a * y ^ b * x ^ c) в (x ^ (a + c) * y ^ b). Подход, который они используют, прост: убедившись, что все дочерние узлы умножения имеют одинаковую каноническую форму, они извлекают первый элемент из списка и смотрят, имеют ли какие-либо другие узлы такое же основание. Если это так, они объединяют два. Затем то же самое делают с остатком. Списки Scala имеют удобную функцию, называемую разделением, которая позволяет вам разделить список в соответствии с произвольными критериями, которые должны позволить вам сделать именно это. - person James Iry; 19.05.2011