用 Julia 实现一个 CAS


#1

数学上的变量类型为 Variable <: Expression,使用 name 字段唯一区分;常数为抽象类型 Constant <: Expression。表达式为抽象类型 Expression,不含分支、循环等结构,使用类型及类型参数来区分不同类型的表达式。例如,二元运算表达式的类型为 BinaryOpExpr{op <: Function, T <: Expression, S <: Expression},其中 op 为二元运算对应的 Julia 函数,TS 分别为参数的类型;设变量 x、常数 a,则 a^x 的类型可以是 BinaryOpExpr{typeof(^), Constant, Variable},也可以是 BinaryOpExpr{typeof(^), Expression, Expression},前者提供了更多关于表达式的信息,根据此信息可以其化简为 exp(log(a) * x),不过也更消耗资源。

通过重载函数,让一个不含分支、循环等结构的 Julia 函数作用在变量或表达式上生成一个 Expression、作用在常数上生成一个 Constant、作用在普通的 Julia 变量就照常运行。例如,设变量 x,则 exp(x) 返回一个 Expressionexp(Constant(1)) 返回一个 Constantexp(1) 返回一个 Float64

等式、不等式、微分式、积分式等皆应作为 Expression 的子类型,在添加新的数学对象时除了要实现对应的函数和类型,还应实现对应的 Expression 子类型并重载运算规则。


#2

我觉得不要做成严格subtype,做成trait更好,因为我发现很多package或多或少会需要一些符号计算的功能。

这样当别的package想做customize的时候只要用trait标记自己的object就可以利用这些已有的工具。


#3

trait 虽然在文档上有看到过,不过是什么东东呀,可以给些例子或资料吗?


#4

Julia里用的是holy trait,因为Julia是duck type,所以一个object能做什么取决于它有什么方法,我们可以定义一些property来在编译时期确定这个object是否有某种功能。

abstract type VariableType end
struct Variable <: VariableType end
struct Constant <: VariableType end


VariableType(x::Foo) = Variable()
VariableType(x::Goo) = Constant()

some_operation(x::Foo, y::Goo) = some_operation(VariableType(x), x, VariableType(y), y)

# implementation
some_operation(::Constant, x, ::Constant, y) = #blabla
some_operation(::Variable, x, ::Constant, y) = #blabla
# etc.

这个会让实现复杂一些,但是好处就是可以扩展到其它package自己定义的类型里面去。


#5

特征是不是还可以有类似继承的关系,例如:

abstract type VariableType end
abstract type Constant <: VariableType end
struct ZZ <: Constant end

然后具有 ZZ 这个 trait 的变量也具有 Constant


#6

是的,原理和功能和subtype能实现的差不多,但是能方便加到别的对象上去。

否则类似的东西已经有人写过了。


#7

#8

我其实是想说另外一个:

功能上这些都已经完善了,不过都没法直接利用duck typing拓展到一个以及定义好的 Expression 类里去。我觉得在一些数值库里提供一定的符号计算功能还是很方便的。


#9

下面简单介绍几点设计思路,并没有完全实现,希望各位可以指出不足之处。

约定:下文中提及的「变量」、「函数」和「表达式」指的是数学意义上的,若需要表示 Julia 中的则用「Julia 变量」、「Julia 函数」和「Julia 表达式」指代。

抽象类型 MathStruct 指代所有要支持的数学结构,如实数、有理数等。若一个类型 TMathStruct 的直接子类型,则说明 T 对应一个数学结构,比如表示全体复数可用 CC <: MathStruct 表示。若有 T <: S <: MathStruct,则 T 对应的数学结构为 S 的子集,比如 NN <: ZZ <: QQ <: RR <: CC <: MathStruct。可以自定义新的数学结构,但应定义为抽象类型,以便其他人复用代码。

所有变量 x 属于某个 MathStruct,其可在声明时指定,例如 @var x::CC 会定义一个 CC 上的变量。函数的定义域和值域与之类似,例如 @func f(::ZZ)::ZZ 会定义一个定义域为 ZZ 的、值域为 ZZ 的函数。

函数可以计算,比如 (f + g)(x) = f(x) + g(x)(f ∘ g)(x) = f(g(x))。微分视为函数,(D ∘ sin)(x) = D(sin(x)) = cos(x) * D(x) 意味着 (D ∘ sin) = cos * D。若将关于不同变量 x_1, x_2, \dots , x_n 的微分记为 d_1, d_2, \dots , d_n ,则以其为基底,在 + 以及下可张成一个交换环。


#10

然后有没有专门用于转换(as…)/代入(subs)和运行(eval)的Julia函数?


#11

代入肯定是要有的,转换我觉得不需要有,每个符号表达式应该有字段来表示其所属 Mathstruct。执行根本就没有对应的语义,符号表达式的任何处理不会改变系统状态。