Как заменить объекты в древовидном экземпляре класса случая Scala производными объектами? - PullRequest
Новая
       42

Как заменить объекты в древовидном экземпляре класса случая Scala производными объектами?

0 голосов
/ 22 октября 2019

Предположим, у меня есть набор классов наблюдений, которые представляют константы, переменные и унарные и двоичные операции над ними, аналогично одному из главы "Классы наблюдений и сопоставление с образцом" в Программировании в Scala: 

abstract class Value {
    def basicEvaluate(varArray: Array[Double]): Double
    def evaluate(varArray: Array[Double]) = basicEvaluate(varArray)
}

case class Constant(d: Double) extends Value {
    override def basicEvaluate(varArray: Array[Double]) = d
}

case class Variable(i: Int) extends Value {    
    override def basicEvaluate(varArray: Array[Double]) = varArray(i)
}

case class Add(v1: Value, v2: Value) extends Value {
    override def basicEvaluate(varArray: Array[Double]) = v1.evaluate(varArray) + v2.evaluate(varArray)
}

...

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

trait UsingCache extends Value {
    var cached: Option[Double] = None
    override def evaluate(varArray: Array[Double]) = {
        if (cached == None) {
            cached = Some(basicEvaluate(varArray))
        }
        cached.get
    }
}

Затем я могу сделать следующее: 

val expr = new Variable(0) with UsingCache
val expr2 = new Add(expr, expr) with UsingCache
expr2.evaluate(Array(5.0))

и это работает.

Мой вопрос - какреализовать функцию def extend(value: Value): UsingCache, которая бы рекурсивно заменяла каждый Value в дереве соответствующим .. with UsingCache объектом? Я хочу, чтобы эта логика была отделена от отдельных подклассов Value (например, когда я добавляю новую операцию, она не должна содержать какой-либо код, специфичный для кэширования). Есть ли способ сделать это с помощью неявного преобразования? Или какие-то идеи, как использовать отражение Scala (я использую Scala 2.12)?

Ответы [ 2 ]

0 голосов
/ 23 октября 2019

Вот решение, которое использует стек для прохождения в глубину. Он оптимизирован для хвостового вызова, поэтому не будет страдать от переполнения стека. ОП также попросил повторно использовать старые кэшированные значения, чтобы карта использовалась для запоминания. 

object CachedValueTest2 {

  def main(args: Array[String]) = {
    val expr1 = Add(Add(Constant(1), Add(Variable(1), Constant(1))), Add(Constant(2), Constant(2)))
    println(extend(expr1))

    val expr2 = Add(Add(Constant(1), Add(Add(Variable(2), Constant(1)), Constant(1))), Add(Constant(2), Add(Variable(1), Constant(2))))
    println(extend(expr2))
  }

  def extend(value: Value): UsingCache = {
    def replace(input: Value, stack: List[(Add, Option[UsingCache], Option[UsingCache])], map: Map[Value, UsingCache]): UsingCache = {
      input match {
        case in @ Constant(d) =>
          val (v, newMap) = map.get(in) match {
            case Some(entry) => (entry, map)
            case None =>
              val entry = new Constant(d) with UsingCache
              (entry, map + (in -> entry))
          }
          popStack(v, stack, newMap)
        case in @ Variable(i) =>
          val (v, newMap) = map.get(in) match {
            case Some(entry) => (entry, map)
            case None =>
              val entry = new Variable(i) with UsingCache
              (entry, map + (in -> entry))
          }
          popStack(v, stack, newMap)
        case in @ Add(v1, v2) =>
          map.get(in) match {
            case Some(entry) => entry
            case None => replace(v1, (in, None, None) :: stack, map)
          }

      }
    }

    def popStack(input: UsingCache, stack: List[(Add, Option[UsingCache], Option[UsingCache])], map: Map[Value, UsingCache]): UsingCache = {
      stack match {
        case head :: tail =>
          head match {
            case (add, None, None) =>
              replace(add.v2, (add, Some(input), None) :: tail, map)
            case (add, Some(v1), None) =>
              val v = new Add(v1, input) with UsingCache
              val newMap = map + (add -> v)
              popStack(v, tail, newMap)
          }
        case Nil => input
      }
    }

    replace(value, List(), Map())
  }

  abstract class Value {
    def basicEvaluate(varArray: Array[Double]): Double

    def evaluate(varArray: Array[Double]) = basicEvaluate(varArray)
  }

  case class Constant(d: Double) extends Value {
    override def basicEvaluate(varArray: Array[Double]) = d
  }

  case class Variable(i: Int) extends Value {
    override def basicEvaluate(varArray: Array[Double]) = varArray(i)
  }

  case class Add(v1: Value, v2: Value) extends Value {
    override def basicEvaluate(varArray: Array[Double]) = v1.evaluate(varArray) + v2.evaluate(varArray)
  }

  trait UsingCache extends Value {
    var caches : Map[Array[Double], Double] = Map()

    override def evaluate(varArray: Array[Double]) = {
      caches.get(varArray) match {
        case Some(result) =>
          result
        case None =>
          val result = basicEvaluate(varArray)
          caches = caches + (varArray -> result)
          result
      }

    }
  }

}
0 голосов
/ 22 октября 2019

Попробуйте макрос 

def extend(value: Value): UsingCache = macro extendImpl

def extendImpl(c: blackbox.Context)(value: c.Tree): c.Tree = {
  import c.universe._

  def transformExprss(exprss: Seq[Seq[Tree]]): Seq[Seq[Tree]] =
    exprss.map(_.map(expr => if (expr.tpe <:< typeOf[Value]) q"extend($expr)" else expr))

  value match {
    case q"$expr.$tname.apply(...$exprss)" =>
      val exprss1 = transformExprss(exprss)
      q"new $expr.${tname.toTypeName}(...$exprss1) with UsingCache"
    case q"${tname: TermName}.apply(...$exprss)" =>
      val exprss1 = transformExprss(exprss)
      q"new ${tname.toTypeName}(...$exprss1) with UsingCache"
  }
}

extend(Add(Constant(1.0), Variable(2)))

//Warning:scalac: performing macro expansion App.extend(App.Add.apply(App.Constant.apply(1.0), App.Variable.apply(2))) at ...
//Warning:scalac: {
//  final class $anon extends App.Add(extend(App.Constant.apply(1.0)), extend(App.Variable.apply(2))) with UsingCache {
//    def <init>() = {
//      super.<init>();
//      ()
//    }
//  };
//  new $anon()
//}
//Warning:scalac: performing macro expansion App.extend(App.Constant.apply(1.0)) at ...
//Warning:scalac: {
//  final class $anon extends App.Constant(1.0) with UsingCache {
//    def <init>() = {
//      super.<init>();
//      ()
//    }
//  };
//  new $anon()
//}
//Warning:scalac: performing macro expansion App.extend(App.Variable.apply(2)) at ...
//Warning:scalac: {
//  final class $anon extends App.Variable(2) with UsingCache {
//    def <init>() = {
//      super.<init>();
//      ()
//    }
//  };
//  new $anon()
//}
...