I've started developing SymbolicNim the past few weeks so it's still just in its youth and lacks a lot of features. Right now it can create symbolic variables and combine them with +, -, *, /, ^ as well as sin, cos, tan, exp and ln. It does do some simplifications automatically (x + x -> 2*x etc) but the plan is that in the future all non-obvious simplifications will have to be done manually by the user (expand, factor, etc). As far as more advanced functionality goes I've implemented differentiation of expressions. Here is an example of how you could use it right now:
let x = newVariable("x")
let y = newVariable("y")
let expr1 = 2*x + y^3
let expr2 = -2*x + 3*y^3
echo expr1 + expr2 # 4*y^3
echo diff(expr1, x) # 2
echo diff(expr1, y) # 3*y^2
echo diff(expr1, y, 2) # d^2/dy^2(expr1) = 6*y
echo diff(expr1, x, y) # d/dy(d/dx(expr1)) = 0
let expr3 = sin(x^2)
echo diff(expr3, x) # 2*x*cos(x^2)
It's tested against both ARC and ORC but you must use a recent version of nim devel (Nim 1.2 doesn't work!). This is because of a problem with a collision between ^ in SymbolicNim and the stdlib that got fixed recently.
I'm not much of a symbolic algebra user myself really (I just got feeling when I wrote this, really xD) so I'm asking you all what kind of features you would like to be added for you to consider using this? I need a carrot (someone else's needs) basically :-D
Yes, I looked at symengine before I started but I got a bit intimidated by all the dependencies (I'm a Windows guy, don't really know for example how to get the libgmp-dev things installed) so I thought this could be a learning opportunity how symbolic libraries work. And I feel like I've learnt a lot since then :) But you are absolutely right that a wrapper around it would make for a much quicker development.
Interesting use cases! :D I've only done a bit of robot mechanics and it was a thrill! Matrices sound like it could be a quite hefty undertaking but it definitely goes on the TODO-list for the future. What operations do you perform on the matrices? Just matrix-multiplications and additions? Quaternions, on the other hand, should be easier as they are more vector-like (symbolic Vectors goes on the list as well). And reference frames could go into a Physics submodule perhaps?
This is thrilling! :D Now I've got a huge carrot to hunt!
Usually the most complicated and most visible and useful feature is simplification, for example: https://github.com/calyau/maxima/blob/master/src/simp.lisp
I guess it entirely depends on what your goal is.
Calculus has many applications. ;-) One thing people might be able to use this for is algebraically derived first or second derivatives (or their matrix forms gradients and Jacobians, Hessians). While few statements can be absolute, typically algebraic forms are both faster to evaluate and more accurate than numerical derivatives. That can help things like numerical minimization (eg. for non-linear least squares, etc.) and equation solving.
There are also things like Complex Step Differentiation, of course, with its own peculiar needs. Arraymancer probably has some autograd stuff in it as well, but I don't know how tangled up that is in the highly idiosyncratic backprop algorithm.
I'm not much of a symbolic algebra user myself really (I just got feeling when I wrote this, really xD) so I'm asking you all what kind of features you would like to be added for you to consider using this? I need a carrot (someone else's needs) basically :-D
The #1 problem with symbolic computation is that most of the obvious / easy algorithms suffer from intermediate expression swell, to the order of exponential space and time requirements. I'm not exaggerating; in my field, Gröbner bases, it's been proven that in general you need *doubly* exponential space and time.
Matrix computation is not that bad, but even there the polynomial complexity is enough that people do funny things for sufficiently large matrices, such as black box computation or even Monte Carlo methods.
My point is, if you want to implement this in pure Nim, OK, fine, but unless you're willing to engage in cutting edge research, or you decide to re-implement things that already exist in C, C++, LISP, etc., you won't come anywhere near the performance of packages such as Macaulay, Maple, Mathematica, Maxima, etc. Especially Maxima, which comes from research done at MIT's Artificial Intelligence Lab in the 1950s.
You would do better to build an interface to pre-existing packages, as someone else pointed out. GMP in particular seems to be a gold standard for arbitrary-size integers in the open-source world. I saw where you said above that you're a little apprehensive about doing that, and I can understand; a PhD student of mine had a devil of a time getting some of these things to compile in Windows 4 or 5 years ago, and the Sage project spent more than a year getting Singular 4.x to work with it. Still, it's doable in principle.
Please don't misunderstand; the project is great idea, and if it really interests you I can point you to some PhD programs in Canada, the US, and Europe. :-) I just want you to know what you're getting into before you find yourself drifting away from a project that turned out to be harder than you first thought, and it becomes abandonware. Probably be best to decide in advance what you can implement and what compromises you're willing to settle for, so, inquiring here is a very good idea.
That's some really interesting use cases :D Yes especially when accuracy is important I can imagine that the analytic solution is more efficient. Complex step diff blew my mind first time I heard about it, it seemed too good to be true :O
@cantanima you are bringing a lot of good points to the table :) Most of this is probably outside my abilities but implementing a few of them at least could be an interesting experience. Cutting-edge performence isn't really any ambition I have but something that's faster than doing it by hand is a win in my eyes.
I have discovered something very exciting though! It seems BinaryBuilder has support for symengine so if I can get it to work with Nimterop there's a chance I won't have to battle against dependecy hell... And then we could have a working, fast library that people can use. And I can fiddle with my own pure Nim implementation in my spare time :-)
1. Mathematical functions such as exp and sin. We need the deep embedding to do simplifications like exp(ln(x)) = x but that limits us to the functions hardcoded in the code. Or perhaps we could use something like this to let the user define their own types along with a seq of simplification rules. Let's say someone created a library with a lot of functions this way for the symbolic library. Could the end-user then import the function-library and use the function-kinds defined there along with the default ones? Say someone writes a library with Bessel functions and they want to use them along with the sin and cos that comes by default.
This is a simplification pass in a compiler. You take the AST and if it matches a simplification that the compiler recognized you merge the nodes.
Yes but the problem is that the compiler doesn't know about the simplifications for Besselfunctions because it is defined by a user.
Perhaps the easiest way to solve this problem is for them to make a PR to the symbolic compiler and add it in the deep embedding instead of creating their own? 🤷
They can also define term-rewriting templates to catch that:
template simplifyExpLn{ln(exp(x))}(x: untyped): untyped = x
And now this simplifies ln(exp(x)) but this is limited to direct calls, if the ln or exp are hidden in other functions this won't work.
Ergo, you might need a extension system for your passes so that people can add new simplification passes.
You might want to look into some example simplification passes used in DaCe (a compiler for linear algebra): https://github.com/spcl/dace/tree/de7deaee/dace/transformation/dataflow
The problem I've had with Term rewriting macros is that they can only be used a certain number of times before it is ignored. So any code that contains more than a few of these simplifications will only be partially simplified (ex: up to line 20 and not below that). But your point about it not recognizing hidden occurrences is good so it wouldn't have been a viable solution either way.
Will take a look at DaCe and see if I can understand enough to implement it myself :D thank you!
Just an idea: we create a pragma for the different passes and then you add a simplification proc by adding the correct pragma to it. The code then get's added to a global "simplification database" that is executed when compiling or calling simplify() on a symbolic expression. For example:
proc simplifyBessel(node: SymNode): SymNode {.simplifyPass.} =
# add simplification code here
I have started rewriting my AST to work both at compile time and runtime, and I stole a concept from SymEngine to represent addition and multiplication using a table instead of a seq. So perhaps that could yield a bit better performance as well. I have also started to add support for compiling a symbolic expression to one (or several) procs: in the compileTime branch
The code isn't as clean as @mratsim's but it does have more of a focus on being usable at runtime so there is a few eager simplifications I'm doing. For example when you add two sums, they get merged, not just put into a binary "Add operator".
Next up is making it a bit more extensible!
The lastest release of SymbolicNim (0.2.1) uses the new AST now. In my microbenchmarks I've seen a big improvement in performance compared to the old AST (it's faster than sympy for this benchmark as well fwiw). This new AST is inspired by @mratsim's in Lux but simpler in some senses and more compilcated in others. It represents sums and products with tables for example. Hashing and caching hashes is the current way I'm trying to speed it up. This should make them roughly O(N) in complexity instead of O(N^2) as the old seq version offered. The big difference between the old and the new version is that the new one works at compile time (mark variables with {.compileTime.}). This means that we can compile a symbolic expression (sin(x + y^2) for example) into efficient pure Nim code. In this case it would be transformed into a proc like this:
proc f(x, y: float): float =
sin(x + pow(y, 2))
The second thing that the new version offers is better extensibility. At the moment custom mathematical functions can be used (ex: exp, sin, cos, tan) if registered. The function must have two functions defined: a diff proc that differentiates the function and a compile proc which returns the NimNode representation of the function. Here is how exp is implemented:
proc exp*(symNode: SymNode): SymNode =
if symNode.kind == symFunc and symNode.funcName == "ln":
return symNode.children[0]
if symNode.kind == symNumber and symNode.lit == 0 // 1:
return newSymNumber(1 // 1)
result = newSymNode(symFunc)
result.funcName = "exp"
result.nargs = 1
result.children.add symNode
proc diffExp(symNode: SymNode, dVar: SymNode): SymNode =
assert symNode.kind == symFunc and symNode.funcName == "exp"
# calculate d/dx(exp(f(x))) = d/dx(f(x)) * exp(f(x))
let child = symNode.children[0]
result = diff_internal(child, dVar) * symNode
proc compileExp(symNode: SymNode): NimNode =
assert symNode.kind == symFunc and symNode.funcName == "exp"
# generate the code `exp(compile(symNode.children[0]))`
let childNimNode = compileSymNode(symNode.children[0])
result = quote do:
exp(`childNimNode`)
registerSymFunc("exp", diffExp, compileExp) # this adds it to SymbolicNim's list of known functions
You could also want to defined your own custom type that contains symbolic expression, like a symbolic matrix. If you only want to use it at runtime, then you can go ahead and just do like you would usually have done. But if you want to be able to compile it into a proc, you have to provide a compile macro. You also need a target type that your symbolic type get's transformed into. In the case of a symbolic matrix I turn it into an Arraymancer Tensor. Here is my matrix type and the compile macro:
type SymMatrix* = ref object
data*: seq[SymExpr]
rows*, cols*: Natural
macro compile*(matrix: static SymMatrix): untyped =
var elems = nnkBracket.newTree()
for i in 0 .. matrix.data.high:
elems.add compileSymExpr(matrix.data[i])
# constructs the @[...] expression
let seqExpression = nnkPrefix.newTree(
newIdentNode("@"),
elems
)
let rows = newLit matrix.rows
let cols = newLit matrix.cols
result = quote do:
result = `seqExpression`.toTensor
result = result.reshape(`rows`, `cols`)
There are still some rough edges but it's starting to be usable for basic tasks at least now. So feel free to test it out. All feedback is welcomed! :D
Symbolicnim is now on Nimble: nimble install symbolicnim
And to celebrate it I bring you subs so you can fullfill all your substitution needs. It's what you could expect:
echo subs(sin(x + y)^z, x + y, z) # sin(z)^z
var taylorSeries = taylor(sin(x), x, 0, 6)
Performance-wise I'm just confused. A simple microbenchmark for subs against Sympy said SymbolicNim was 100-1000x slower. But when I instead did the Taylor expansion, Nim was 1000 times faster 🤷♀️ There are still a lot of possible optimizations in memory-use I guess.