5

私はscala用のシンプルなCASシステムを探しています。

次の機能が必要です。

  • 抽象構文ツリーへのアクセスを許可します（一致を容易にするために、できればケースクラスを介して）
  • StringASTに解析する
  • 式を簡略化する

何も存在せず、自分で基本的なことを書かなければならない場合、最良の表現は何ですか？

私はこのようなことを考えています：

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ます（どういうわけか一元化できるようです）
  • varargs /List引数を処理するAddと、Mutliply厄介になる可能性があるようです
4

1 に答える 1

4

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)
}

私が学ぶことを意味していたが、まだ理解していないテクノロジーの1つは、属性文法です。彼らは、この種のAST処理から退屈な作業の多くを取り除くことになっています。Scalaの実装については、kiamahttp://code.google.com/p/kiama/を参照してください。

ちなみに、ここではドメインにdoubleを使用していますが、「大きな有理数」（BigIntegerのペア）を使用した方がよい場合があります。それらは遅いですが、非常に正確です。

于 2011-05-18T15:38:18.893 に答える