为冗长的介绍道歉,不幸的是,我想不出办法让它更短。
问题
我们正在构建一个简单的应用程序,它通过应用模式转换来操作代数表达式 - 目标是能够说“采用 2*x+2
并应用'分解'”。最终目标是能够确定两个表达式在一组模式转换下是否等价(即 2*(x+1)^2
'reachable' from 2x^2+4x+2
)。
我们创建了一组对域进行建模的类并定义了“规范”形式,这基本上意味着(符号上)相同的表达式只有一种构造方式:x+y+z
将始终表示为 Plus(x, y, z
) 并且从不作为 Plus(y, x, z)
或 Plus(x, Plus(y, z))
,即使它是通过调用 Plus(Plus(x, z), y)
创建的.
这些规范变换中的许多都是相应运算符的代数属性的直接结果——关联性允许上面看到的“扁平化”等。这些属性也对模式操作有直接影响——例如,Power(\_, 2)
不可交换,因此它只匹配具有 2
的表达式作为第二个 child (参数),但 Plus(_, 2)
是可交换的,因此它可以匹配具有 2
的表达式就像它的任何一个 child 一样。由于这些原因,我们希望将这些代数属性表示为类上的显式数据,然后在应用程序的各个部分中对其进行解析。
棘手的部分是我们需要这些数据在静态(我们在构造表达式以应用适当的规范转换时需要它,但由于表达式尚未构造,我们不能动态访问它)和动态(在模式期间)都可用匹配,我们必须能够做到 expr.hasAttribute(Associative)
)。由于这些属性对于特定的表达式类型(类)是固定的,我们也试图避免直接在类上定义它,例如
class Plus(children: List<Expression>): Expression(children) {
val attributes = setOf(Associative, Commutative, IdentityElement(Number(0.0)))
...
}
这是因为我们不想要一个新的
Set
每次创建表达式时都会创建 - 我们想要 Set
在类声明期间创建一次,因为这是唯一需要创建它的时间。解决方案
我们决定解决这个问题的方法是创建一个全局
HashMap<KClass<out Expr>, Set<Attribute>>
它将保存属性,然后创建一个 Builder 对象,该对象负责解析属性并在创建表达式时应用适当的规范转换。我包含了我们正在使用的代码的简化版本。一些高层评论:
HashMap
定义于 Expression.Companion
invoke
创建实例。 companion object
上定义的函数.这是因为规范转换可能会产生与正在创建的对象不同的对象,例如 Plus(Symbol(x))
创建 Symbol(x)
. 我的问题是双重的:
Attributes
在 Builder
.这实际上不是我的目标,它只是因为试图使代码更干净。而且我确信可以做更多的事情。 谢谢!
import kotlin.reflect.KClass
/**
* ATTRIBUTES
*/
abstract class Attribute
object Associative: Attribute()
object Commutative: Attribute()
class Identity(val element: Expr) : Attribute()
/**
* END ATTRIBUTES
*/
/**
* BUILDER
*/
// So there are basically two things we can do in canonical form -> we can operate on children (flattening, canonical ordering)
// or we can operate on the final expression as a whole (transforming Plus(x) to x, for example)
// So, every attribute may or may not contribute a functional operator that transforms either the children or the expression
// as a whole. These operators must be composed in a certain order (e.g. flattening must occur before ordering) and then
// applied to the result.
// The operators that change the expressions type short-circuit the function (because there is nothing else to do)
object Builder {
inline fun<reified A: Attribute> Set<Attribute>.withAttribute(block: A.() -> Any?) =
this.filterIsInstance<A>().firstOrNull()?.run(block)
inline fun<reified E: Expr> withAttributes(block: Set<Attribute>.() -> Any?)
= Expr.attributes[E::class]?.run(block)
inline fun<reified E: Expr> canonizeByAttributes(crossinline constructor: (List<Expr>) -> E, children: List<Expr>): Expr {
val childrenOperators = mutableListOf<(List<Expr>) -> List<Expr>>()
withAttributes<E> {
withAttribute<Identity> {
when(children.size) {
0 -> return element
1 -> return children.first()
else -> {}
}
}
withAttribute<Associative> {
childrenOperators.add {
children -> children.flatMap { if(it is E) it.children else listOf(it) }
}
}
withAttribute<Commutative> {
childrenOperators.add {
children -> children.sortedBy { it.toString() }
}
}
}
return constructor(childrenOperators.fold(children) { children, op -> op(children)})
}
}
/**
* END BUILDER
*/
/**
* EXPRESSIONS
*/
abstract class Expr protected constructor(val children: List<Expr>) {
val attributes: Set<Attribute>? get() = Companion.attributes[this::class]
override fun toString(): String = "${this::class.simpleName}(${children.joinToString(", ")})"
companion object {
val attributes: HashMap<KClass<out Expr>, Set<Attribute>> = hashMapOf()
}
}
Expr.attributes[Plus::class] = setOf(Identity(Symbol("0")), Commutative, Associative)
class Plus private constructor(children: List<Expr>): Expr(children) {
companion object {
operator fun invoke(children: List<Expr>) = Builder.canonizeByAttributes(::Plus, children)
operator fun invoke(vararg children: Expr) = invoke(children.toList())
}
}
class Symbol(val name: String): Expr(listOf()) {
override fun toString(): String = "Symbol($name)"
}
/**
* END EXPRESSIONS
*/
/**
* EVALUATION, TESTS
*/
Plus(Symbol("x")).attributes
(Plus(Symbol("x")) as Symbol).name == "x"
(Plus(Symbol("x"), Plus(Symbol("x"), Symbol("y"))))
(Plus() as Symbol).name == "0"
(Plus(Plus()) as Symbol).name == "0"
Plus(Symbol("2"), Symbol("y"), Plus(Symbol("x"), Symbol("1")))
/**
* END EVALUATION, TESTS
*/
最佳答案
您可以拥有一个 set 属性,而无需每次都创建一个新实例,例如:
private val plusAttributes = setOf(Associative, Commutative, IdentityElement(Number(0.0)))
class Plus(children: List<Expression>): Expression(children) {
val attributes = plusAttributes
// ...
}
这样,Plus 的所有实例都引用了同一个集合。每个实例中仍然存在额外引用的开销,但远低于集合(可以有一个大对象树)。
更好的是,制作
attributes
Expression
中的一个抽象属性类,在每个实现类中重写。这样,您可以在不知道表达式类型的情况下访问属性。您可能考虑的另一种方法是使用相关子类实现的标记接口(interface)以及扩展表达式。这完全没有开销,而且测试起来非常简单明了:
if (myExpression is Associative)
,尽管它不会一次性为您提供所有 map 。 (如果有任何与属性相关的行为,您可以向相关接口(interface)添加一个方法,这将朝着更传统的 OO 设计方向发展。)
关于generics - 代数表达式 - Kotlin 建模静态和动态属性的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59036003/