Keisan

Keisan (計算, to calculate) is a Ruby library for parsing equations into an abstract syntax tree. This allows for safe evaluation of string representations of mathematical/logical expressions. It has support for variables, functions, conditionals, and loops, making it a Turing complete programming language.

Installation

Add this line to your application's Gemfile:

gem 'keisan'

And then execute:

$ bundle

Or install it yourself as:

$ gem install keisan

Usage

REPL

To try keisan out locally, clone this repository and run the executable bin/keisan to open up an interactive REPL. The commands you type in to this REPL are relayed to an internal Keisan::Calculator class and displayed back to you.

Calculator class

This library is interacted with primarily through the Keisan::Calculator class. The evaluate method evaluates an expression by parsing it into an abstract syntax tree (AST), and evaluating it. There is also a simplify method that allows undefined variables and functions to exist, and will just return the simplified AST.

calculator = Keisan::Calculator.new
calculator.evaluate("15 + 2 * (1 + 3)")
#=> 23
calculator.simplify("1*(0*2+x*g(t))").to_s
#=> "x*g(t)"

For users who want access to the parsed abstract syntax tree, you can use the ast method to parse any given expression.

calculator = Keisan::Calculator.new
ast = calculator.ast("x**2+1")
ast.class
#=> Keisan::AST::Plus
ast.to_s
#=> "(x**2)+1"
ast.children.map(&:to_s)
#=> ["x**2", "1"]

Caching AST results

Computing the AST from a string takes some non-zero amount of time. For applications of this gem that evaluate some set of fixed expressions (possibly with different variable values, but with fixed ASTs), it might be worthwhile to cache the ASTs for faster computation. To accomplish this, you can use the Keisan::AST::Cache class. Passing an instance of this class into the Calculator will mean everytime a new expression is encountered it will compute the AST and store it in this cache for retrieval next time the expression is encountered.

cache = Keisan::AST::Cache.new
# Note: if you don't want to create the Cache instance, you can just pass `cache: true` here as well
calculator = Keisan::Calculator.new(cache: cache)
calculator.evaluate("exp(-x/T)", x: 1.0, T: 10)
#=> 0.9048374180359595
# This call will use the cached AST for "exp(-x/T)"
calculator.evaluate("exp(-x/T)", x: 2.0, T: 10)
#=> 0.8187307530779818

If you just want to pre-populate the cache with some predetermined values, you can call #fetch_or_build on the Cache for each instance, freeze the cache, then use this frozen cache in your calculator. A cache that has been frozen will only fetch from the cache, never write new values to it.

cache = Keisan::AST::Cache.new
cache.fetch_or_build("f(x) + diff(g(x), x)")
cache.freeze
# This calculator will never write new values to the cache, but when
# evaluating `"f(x) + diff(g(x), x)"` will fetch this cached AST.
calculator = Keisan::Calculator.new(cache: cache)

Specifying variables

Passing in a hash of variable (name, value) pairs to the evaluate method is one way of defining variables

calculator = Keisan::Calculator.new
calculator.evaluate("3*x + y**2", x: -2.5, y: 3)
#=> 1.5

It is also possible to define variables in the string expression itself using the assignment = operator

calculator = Keisan::Calculator.new
calculator.evaluate("x = 10*n", n: 2)
calculator.evaluate("3*x + 1")
#=> 61

To perform multiple assignments, lists can be used

calculator = Keisan::Calculator.new
calculator.evaluate("x = [1, 2]")
calculator.evaluate("[x[1], y] = [11, 22]")
calculator.evaluate("x")
#=> [1, 11]
calculator.evaluate("y")
#=> 22

Specifying functions

Just like variables, functions can be defined by passing a Proc object as follows

calculator = Keisan::Calculator.new
calculator.evaluate("2*f(1+2) + 4", f: Proc.new {|x| x**2})
#=> 22

Note that functions work in both regular (f(x)) and postfix (x.f()) notation, where for example a.f(b,c) is translated internally to f(a,b,c). The postfix notation requires the function to take at least one argument, and if there is only one argument to the function then the braces can be left off: x.f.

calculator = Keisan::Calculator.new
calculator.evaluate("[1,3,5,7].size")
#=> 4
calculator.define_function!("f", Proc.new {|x| [[x-1,x+1], [x-2,x,x+2]]})
calculator.evaluate("4.f[0]")
#=> [3,5]
calculator.evaluate("4.f[1].size")
#=> 3

Like variables, it is also possible to define functions in the string expression itself using the assignment operator =

calculator = Keisan::Calculator.new
calculator.evaluate("f(x) = n*x", n: 10) # n is local to this definition only
calculator.evaluate("f(3)")
#=> 30
calculator.evaluate("f(0-a)", a: 2)
#=> -20
calculator.evaluate("n") # n only exists in the definition of f(x)
#=> Keisan::Exceptions::UndefinedVariableError: n
calculator.evaluate("includes(a, element) = a.reduce(false, found, x, found || (x == element))")
calculator.evaluate("[3, 9].map(x, [1, 3, 5].includes(x))").value
#=> [true, false]

This form even supports recursion, but you must explicitly allow it.

calculator = Keisan::Calculator.new
calculator = Keisan::Calculator.new(allow_recursive: false)
calculator.evaluate("my_fact(n) = if (n > 1, n*my_fact(n-1), 1)")
#=> Keisan::Exceptions::InvalidExpression: Unbound function definitions are not allowed by current context

calculator = Keisan::Calculator.new(allow_recursive: true)
calculator.evaluate("my_fact(n) = if (n > 1, n*my_fact(n-1), 1)")
calculator.evaluate("my_fact(4)")
#=> 24
calculator.evaluate("my_fact(5)")
#=> 120

Multiple lines and blocks

Keisan understands strings which contain multiple lines. It will evaluate each line separately, and the last line will be the the result of the total evaluation. Lines can be separated by newlines or semi-colons.

calculator = Keisan::Calculator.new
calculator.evaluate("x = 2; y = 5\n x+y")
#=> 7

The use of curly braces {} can be used to create block which has a new closure where variable definitions are local to the block itself. Inside a block, external variables are still visible and re-assignable, but new variable definitions remain local.

calculator = Keisan::Calculator.new
calculator.evaluate("x = 10; y = 20")
calculator.evaluate("{a = 100; x = 15; a+x+y}")
#=> 135
calculator.evaluate("x")
#=> 15
calculator.evaluate("a")
#=> Keisan::Exceptions::UndefinedVariableError: a

By default assigning to a variable or function will bubble up to the first definition available in the parent scopes. To assign to a local variable instead of modifying an existing variable out of the closure, you can use the let keyword. The difference is illustrated below.

calculator = Keisan::Calculator.new
calculator.evaluate("x = 1; {x = 2}; x")
#=> 2
calculator.evaluate("x = 11; {let x = 12}; x")
#=> 11

Comments

When working with multi-line blocks of code, sometimes comments are useful to include. Comments are parts of a string from the # character to the end of a line (indicated by a newline character "\n").

calculator = Keisan::Calculator.new
calculator.evaluate("""
  # This is a comment
  x = 'foo'
  x += '#bar' # Notice that `#` inside strings is not part of the comment
  x # Should print 'foo#bar'
""")
#=> "foo#bar"

Lists

Just like in Ruby, lists can be defined using square brackets, and indexed using square brackets

calculator = Keisan::Calculator.new
calculator.evaluate("[2, 3, 5, 8]")
#=> [2, 3, 5, 8]
calculator.evaluate("[[1,2,3],[4,5,6],[7,8,9]][1][2]")
#=> 6
calculator.evaluate("a = [1,2,3]")
calculator.evaluate("a[1] += 10*a[2]")
calculator.evaluate("a")
#=> [1, 32, 3]

They can also be concatenated using the + operator

calculator = Keisan::Calculator.new
calculator.evaluate("[3, 5] + [x, x+1]", x: 10)
#=> [3, 5, 10, 11]

Keisan also supports the following useful list methods,

calculator = Keisan::Calculator.new
calculator.evaluate("[1,3,5].size")
#=> 3
calculator.evaluate("[1,3,5].max")
#=> 5
calculator.evaluate("[1,3,5].min")
#=> 1
calculator.evaluate("[1,3,5].reverse")
#=> [5,3,1]
calculator.evaluate("[[1,2],[3,4]].flatten")
#=> [1,2,3,4]
calculator.evaluate("range(5)")
#=> [0,1,2,3,4]
calculator.evaluate("range(5,10)")
#=> [5,6,7,8,9]
calculator.evaluate("range(0,10,2)")
#=> [0,2,4,6,8]
calculator.evaluate("[1, 2, 2, 3].uniq")
#=> [1,2,3]
calculator.evaluate("[1, 2, 3].difference([2, 3, 4])")
#=> [1]
calculator.evaluate("[1, 2, 3].intersection([2, 3, 4])")
#=> [2, 3]
calculator.evaluate("[1, 2, 3].union([2, 3, 4])")
#=> [1, 2, 3, 4]

Hashes

Keisan also supports associative arrays (hashes), which maps keys to values.

calculator = Keisan::Calculator.new
calculator.evaluate("my_hash =