NaiveExpr

A naive expression

Nov 29, 2018

见习魔法师

NaiveExpr

NaiveExpr

NaiveJSON 之后,naive系列又出了一位新成员——NaiveExpr,是一个朴素的数学表达式求解器。

关于为什么要写这个,主要是为了应付课程设计,NaiveExpr是我的期末大作业,我负责编写protocolcore部分(即CLI部分)。

原课题是实现一个能计算带变量的表达式,当然通常做法是将中缀表达式转换为后缀表达式,然后通过类似栈的结构进行在线计算,这样当然十分简单,而且应当是数据结构的基本功, 但是,NaiveExpr却不是这么计算的,而是将其转换为一个AST(抽象语法树),就是将其编译,然后进行计算。(当然,只是有了eval,apply还没写好)

Why compile?

为什么不用后缀表达式,而使用效率更低的AST呢?理由很简单,我们平时书写算式的时候其实并不十分规整,比如我们要表达x * 3的时候,往往会写成3x,而这时候中缀表达式分析起来就比较麻烦了,而且我们不能简单地在两个标识符直接添加乘号来解决,因为我们表达sin(x)的时候还会写成sinx,此时我们不能将其理解成sin * x或者(sinx),通过通常的循环进行分析就比较麻烦。所以我通过解析器来进行分析语法,像这种分析器,函数式语言是比较能胜任的,于是和Naive JSON一样,这里也使用了Scala,而且整个项目也是函数式的。

基本元素

数学中,表达式由数字,变量和符号组成,这也是NaiveExpr的基本元素。

数字(数值)

字面量就是值的就是数值,主要分为三种:

  • 有理数
  • 浮点数
  • 布尔值

鉴于时间比较紧迫,这里无理数用浮点数表示。

同时也有两个数学常数,用浮点数表示:

pi | π 表示圆周率

e 表示 e

这三者可以被隐式转换,其中布尔值会被隐式转换成1(true)和0(false),同时和C系语言相似,非零值被视为true,所以不建议将浮点数变成bool,可能会遇到精度问题。

变量

变量必须是合法的C标识符,不能出现保留关键字(比如说pi等常数)含有自由变量的表达式被视为函数(这个设计是要求,没有办法)

遗憾的是,目前还不能递归

运算

NaiveExpr支持的运算有

  • 四则运算
  • 三角函数
  • 指数/对数运算
  • 符号化/数值化求导
  • 方程求解
  • 简单的表达式化简

在进行运算的时候,如果是有理数之间的四则运算,则结果就是有理数,否则会化为浮点数。

简单的四则运算和对数,三角函数求导是符号化的,会直接出现结果。

方程求解只能解一元方程,方法是牛顿法,如果是有理数的一次方程,就会有解析解,否则为浮点数的近似解。

语法

和你平时书写的习惯类似,下面给出几个示例:

3 - 1/3 返回有理数,为8/3

2x 这个结果是一个函数,给定x,返回x的两倍

x - x 这在我们看来明显是0,在NaiveExpr看来也是如此,结果是有理数0

x + x - y 返回一个函数 (x, y) => 2 * x - y

若要调用一个函数,有两种办法:

(x + x - y)(y = 2x)

x + x - y where y = 2x where 从句可以让你少打一对括号。

(expression)(var1=v1, var2=v2, ..., varn=vn)expression where var1=v1 and var2=v2expression where var1=v1, var2=v2

这两者结果是一致的,就是计算 x + x - 2x的结果,显而易见是0

sinx where x=pi/2 | sin(pi/2) 三角函数运算,结果为浮点数1.0

solve(3x + 2y = 9x, x) | 3x + 2y ?x= 9x 解方程,求解 (3x + 2y = 9x)中x为多少

为了求解,我们需要给定x的初始值,因此解方程实质上被视为函数。如果我们给定

(3x + 2y ?x= 9x)(x=2, y=1) 就会给出结果:1/3

另外,如果方程中自由变量只有一个,则无需给定需要求解的变量。

[expression] | int(expression) 取整

|x| | absx 求绝对值

科里化

当你的没有给定所有的变量时,这个表达式仍然是函数,这是自动currying。

REPL

在REPL中有特殊语法,输入:help有惊喜(

在REPL中,_指代上一个结果

def <标识符> = <表达式> 定义一个绑定

undef <标识符> 取消一个绑定

Frontend

NaiveExpr现在已经利用Scala.js编译到了JavaScript,也就是说,我利用了原有的库写了一个前端, 在使用Scala.js编译做跨平台项目的时候碰到了不少坑,也许会在将来的某一天写一篇关于Scala跨平台多项目交叉编译的采坑手记。 目前临时地将丑到爆的前端放在了NaiveExpr,因为是纯前端计算,卡爆警告。 (用回了MaterializeCSS绝对不是我的恶趣味)

GitHub

_______ .__ ___________ \ \ _____ |__|__ __ ____ \_ _____/__ ________________ / | \\__ \ | \ \/ // __ \ | __)_\ \/ /\____ \_ __ \ / | \/ __ \| |\ /\ ___/ | \> < | |_> > | \/ \____|__ (____ /__| \_/ \___ >_______ /__/\_ \| __/|__| \/ \/ \/ \/ \/|__|