expreduce, 在围棋中,一个实验计算机代数系统

分享于 

11分钟阅读

GitHub

  繁體 雙語
An experimental computer algebra system written in Go
  • 源代码名称:expreduce
  • 源代码网址:http://www.github.com/corywalker/expreduce
  • expreduce源代码文档
  • expreduce源代码下载
  • Git URL:
    git://www.github.com/corywalker/expreduce.git
    Git Clone代码到本地:
    git clone http://www.github.com/corywalker/expreduce
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/corywalker/expreduce
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    
    Expreduce

    Build Status

    本软件是实验质量,目前不打算用于认真使用。 有很多成熟的开源计算机代数系统可以使用。

    Expreduce实现了一种用于术语重写的特殊构造。 对于计算机代数系统来说,它是一种简洁的语言,因为它能够表达与标准数学方程非常相似的表达式操作步骤。 例如微积分中的产品规则可以表示为:

    
    D[a_*b_,x_] := D[a,x]*b + a*D[b,x]
    
    
    
    

    既然内核理解了产品规则,当以后遇到与上述LHS匹配的Pattern 时,它将递归应用产品规则,直到表达式稳定为止。

    术语重写系统和 Pattern 匹配引擎是相当先进的。 这个阶段的计算机代数系统非常有限,但简单的演算和代数操作确实支持( 请参阅下面的示例)。 如果你寻找更成熟的计算机代数系统,请考虑使用 Mathematica ( 专用的) 或者 Mathics (。开源,sympy支持)。

    安装和运行

    这里是下载。

    如果你只需要开始,你可以下载二进制版本并运行无下载或者编译的软件。 前往最新版本,并下载你的操作系统的正确软件包。

    来自源的

    
    go get github.com/corywalker/expreduce
    
    
    expreduce
    
    
    
    

    文档

    Expreduce为支持的每个函数都提供了文档。 链接到文档

    示例
    
    Welcome to Expreduce!
    
    
    
    In[1]:= D[Cos[Log[Sin[x]]+x]+x,x]
    
    
    
    Out[1]= 1 + -(1 + Cot[x])*Sin[x + Log[Sin[x]]]
    
    
    
    In[2]:= Integrate[5*E^(3*x),{x,2,a}]//Expand
    
    
    
    Out[2]= -5/3*E^6 + 5/3*E^(3*a)
    
    
    
    In[3]:= FactorSquareFree[1 - 2*x^2 + x^4]
    
    
    
    Out[3]= (-1 + x^2)^2
    
    
    
    In[4]:= Sum[i, {i, 1, n}]
    
    
    
    Out[4]= 1/2*n*(1 + n)
    
    
    
    In[5]:= Together[(1/2 + 3/a)^2+b/c]
    
    
    
    Out[5]= 1/4*a^-2*c^-1*(4*a^2*b + 36*c + 12*a*c + a^2*c)
    
    
    
    In[6]:= 40!
    
    
    
    Out[6]= 815915283247897734345611269596115894272000000000
    
    
    
    In[7]:= Solve[x^2-x-2.5==0,x]
    
    
    
    Out[7]= {{x -> -1.15831}, {x -> 2.15831}}
    
    
    
    
    Rubi集成规则

    Expreduce使用了Albert的Rubi集成套件。 这些规则可以通过运行 LoadRubi[] 加载,然后就可以调用 Int[Sin[a + b*Log[c*x^n]], x] 这些规则比 Integrate[] 中的那些简单的规则要强大得多。

    http://www.apmaths.uwo.ca/~arich/

    集成示例

    
    In[1]:= Int[((A + C*Sin[e + f*x]^2)*(a + a*Sin[e + f*x])^m*(c + -c*Sin[e + f*x])^(-1/2)), x]
    
    
    
    Out[1]= (f^-1*Cos[e + f*x]*Hypergeometric2F1[1, 1/2 + m, 3/2 + m, 1/2*(1 + Sin[e + f*x])]*(1 + 2*m)^-1*(A + C)*(a + a*Sin[e + f*x])^m*(c + -c*Sin[e + f*x])^(-1/2) + -2*C*a^-1*f^-1*Cos[e + f*x]*(3 + 2*m)^-1*(a + a*Sin[e + f*x])^(1 + m)*(c + -c*Sin[e + f*x])^(-1/2))
    
    
    
    In[2]:= Int[(x^-5*(a*x)^(-1/2)*(1 + -a*x)^(-1/2)*(1 + a*x)), x]
    
    
    
    Out[1]= (-2/9*a^4*(a*x)^(-9/2)*(1 + -a*x)^(1/2) + -34/63*a^4*(a*x)^(-7/2)*(1 + -a*x)^(1/2) + -68/105*a^4*(a*x)^(-5/2)*(1 + -a*x)^(1/2) + -272/315*a^4*(a*x)^(-3/2)*(1 + -a*x)^(1/2) + -544/315*a^4*(a*x)^(-1/2)*(1 + -a*x)^(1/2))
    
    
    
    
    技术说明

    在Expreduce中,一切都是表达式,可以是原子值,如整数或者符号,也可以是子表达式的有序列表。 在子表达式的有序列表中,第一个元素被称为头。 它指定了以下类型的数据。 例如 a + 1 表示为 Plus[a, 1]。 头部是 Plus,后面的两个子表达式是符号 a 和整数 1

    当解释器遇到还没有计算的表达式时,它将检查带有规则内部数据库的MATCH。 内部规则集合在表达式的头上被键控。 一个例子是 Cos[n_Integer?EvenQ*Pi] := 1,这意味着采用一个甚至多倍的弦的余弦应该计算为 1.

    Pattern 匹配必须快速进行评估。 在内部,所有表达式都保持一个对应的树。 每个表达式和子表达式都常常知道它的内容的哈希,而无需进行任何计算。 这使得检查表达式相同性就像检查两个int64值的相等性一样。 当 MATCH的模式中存在模式时,我们不再依赖于哈希,但Expreduce有一个大多数有效的MATCH 迭代器。

    值得注意的是,表达式可以多种方式 MATCH的Pattern。 一个简单的例子是 MatchQ[x + y, a_ + b_] 在这里,a 可以保持x,b 可以保持y 或者a 可以保持y,b 可以保持x。 MATCH 迭代器迭代所有可能的分配(。Pattern 将使用多少表达式进行 MATCH 处理)。 MATCH 迭代器还将遍历每个分配的所有可能分配。 指定指定哪些子表达式将 MATCH 转换为 Pattern,而不仅仅是多少。

    其他项目

    Expreduce实际上非常类似于 Mathics,类似的术语重写系统使用Sympy作为for操作的后端。 我创建expreduce有几个原因。 第一个是我想学习所有关于术语重写系统的知识。 其次,我相信在这里实现的语法比使用 python 来处理表达式( 作为 Sympy,因此 Mathics ) 更适合于构建计算机代数系统。 在表达式树中使用第一类支持 Pattern 匹配和替换的语言是编写计算机代数系统的理想方法。 这与一个优化的核心结合可以能导致有效和通知的评估,没有多少翻译程序员翻译方程式。

    当前限制

    引擎为给定的符号应用规则时,它会首先尝试使用最多的规则。 目前的特殊性定义是基本的,但当然可以改进。 大多数情况下都是这样,但我可以预见到错误的情况。 现在没有办法覆盖规则应用程序的顺序,但是将来很容易添加。

    Pattern 匹配系统可以能非常慢,尤它的是在使用多个术语的Orderless 表达式时。 因为正确匹配这些术语常常需要检查 Pattern的许多不同排列,直到找到一个 MATCH。 我现在的理论是,当前匹配系统正常运行,并且可以修改它以加速事件。

    未来方向

    我希望尝试将golang范例的并发性应用到评估序列中。 一些低悬挂果将对纯函数映射纯函数的列表或者它的他表达式(。计算列表表达式的导数) 进行并行计算。 类似地,支持Listable函数的自动线程是很好的( 计算大型 array的sin(x) )。 表达式的计算通常从开始计算每个参数开始。 这可能同时成为并发的。 一个更加复杂但非常有趣的应用程序是将 Pattern 匹配引擎分解为并发组件。 我们必须非常小心地对副作用,所以我们可以能需要修改我们的范围构造或者限制访问 EvalState。 另一种方法是创建一个函数来预测另一个函数是否具有副作用( 这是否可行)。 一个 true 预测可以让系统回到非并发评估。

    因为至少还有两个替代引擎实现与( 另一个在这里。 ) 相同的语法,所以决定使用标准链接协议,这样替换引擎独立于运行在上面的规则是非常有用的。 另一层抽象是前端。 真正的层次结构如下所示: 核心 <- 规则 <- 前端。 将所有这些函数分解为可以互换和可以互换会很好。

    也有兴趣的是建立一些形式的规则定义。 关于这一点,应该有一些预先已有的文献,因为术语重写是。 要回答的一些有趣问题是:

    • 给出符号( 或者规则的宇宙)的一组规则,我们可以找到重复或者减少最基本的规则集。 回答这样的问题将提高系统的效率和清晰性。
    • 给定一组符号( 或者规则的宇宙) 规则,我们可以证明递归重写将终止? 编写一个与自身或者与其他规则协作的规则是相当容易的。 当然,我们应该去掉一些命令性的符号,比如 WhileFor。 即使删除了这些命令功能,这个问题仍然是停止问题? 我们能否限制我们的考虑,使问题不再是停止问题? 回答这个问题将提高系统的稳定性。
    • 插件开发

    非常标准的工作流程请记住 go generate

    
    # To update any. m changes or changes to the parser:
    
    
    go generate./...
    
    
    # To run the test suite:
    
    
    go test./...
    
    
    
    

    使用 go generate 可能需要下载额外的依赖项。


    COM  EXP  SYS  系统  Algebra  
    相关文章