Implementing a JavaScript expression engine

The target audience of this post are JavaScript developers of any level.

Recently I started working on an expression engine in JavaScript.

Our application allows administrators to configure some expressions to show or hide some sections on the page. Those expressions are small code snippets written using a homemade syntax. The expression is capable of doing simple operations on numbers, boolean, date, and some proprietary data types. For example

min(objectA.value, objectB.value) + 3;

Traditionally, expressions are evaluated in the server side only. When user change some fields on a form (for example, objectA.value in the expression above), in order to plug them into an expression for evaluation, we need to send user's input to the server side and wait for the response to come back. This server round trip is unnecessary because the expression doesn't change, what do change are the fields on a form, and all of them are available on the client side.

To increase performance, I embarked on a journey to create an evaluation engine on the client side. Parsing of the expression will still happen on the server side. By processing evaluation on the client side, we can respond to user's input in a form and pump them into the evaluation engine to get the result on the fly.

This is an exciting opportunity for me. It's a rare chance that I can actually use things I learned from college!

When the server finishes parsing an expression, it comes back as an abstract syntax tree. The job of the engine's job is to walk through the tree and calculate the value of each node recursively until it reaches the root node, at which it will calculate the result of the whole expression.

The concept is straightforward, it is basically a recursive call.

function evaluate(astNode) {
    const resolvedChildren = astNode.children.map(evaluate);
    switch (astNode.type) {
        case 'literal': return astNode.value;
        case 'identifier': return resolveIdentifier(astNode);
        case 'function':
            return resolveFunction(astNode)(resolvedChildren);
        case 'operator':
            return resolveOperator(astNode)(resolvedChildren);
        default:
            throw new Error('we got a node we don't understand');
    }
}

If a node has children, we evaluate the children first before evaluating the node.

As I dug deeper, I found some interesting issues.

First we need a type system

JavaScript has some quirks, one of them is how it deals with numbers:

0.1 + 0.2; // 0.30000000000000004

JavaScript is also notoriously bad when dealing with date and time.

Due to all these issues, we are creating our own types to wrap native JavaScript types. Wrapping native types also provide flexibility on the internal representation. If we want to use emojis to represent number internally, we can easily make the switch in one place.

How do we define functions

The engine will support a set of core functions. A major part of the engine is to implement the standard library the includes the implementations of core functions. We need a way to go from a function name, such as "add" to the implementation of add function.

We are going with simple JavaScript functions.

function addHandler(arg1, arg2) {
  // both arg1 and arg2 are our own number types
  return arg1.add(arg2);
}

All functions are bundled into a simple JavaScript map, with function name being the key, and implementation being the value.

dealing with short-circuiting

It is an unusual requirement, that some of the functions need to support short-circuiting. For example, an if then else ternary function to calculate how much it would a meal cost

if(isSunny, costOfEatingOut, costOfOrderingTakeout)

If isSunny evaluates to true, then we only need to evaluate costOfEatingOut and totally skip the evaluation for costOfOrderingTakeout. Vice versa, if isSunny evaluates to false, we only need to evaluate costOfOrderingTakeout. This small optimization might look trivial, it can save a lot of time when one of the arguments are very complicated.

However, with our evaluatefunction above, we always resolve all the arguments before passing into a function.

We decide to use a special flag on some function that needs access to unresolved Abstract Syntax Tree nodes.

function ifHandler(conditionNode, thenNode, elseNode) { ... }
isHandler._takesASTNodes = true;

Before the engine calls a function, it will check if the function has the special property to decide whether to preresolve all the arguments or let the function handle them.

Now the function needs to evaluate the arguments.

function ifHandler(conditionNode, thenNode, elseNode) {
  const condition = evaluate(conditionNode);
  if (condition.isTrue()) {
    return evaluate(thenNode);
  }
  return evaluate(elseNode);
}

evaluate function is used as a dependency of ifHandler, while ifHandler is also a dependency of evaluate. We have a circular dependency here. One way to break the dependency is to let evaluate pass itself to ifHandler as an argument. But we would like the function interface to be simpler.

What I proposed was writing ifHandler as a generator.

function* ifHandler(conditionNode, thenNode, elseNode) {
  const condition = yield conditionNode;
  if (condition.isTrue()) {
    return yield thenNode;
  }
  return yield elseNode;
}

JavaScript generator is something I never get a chance to use (I have seen some usage in redux-saga). IMO it's a pretty neat way of delegate responsibility back to the caller.

Logging

In case an error occurs during runtime, we would like a way to run the same evaluation locally to diagnose errors. The ability to take a snapshot of evaluation and run it locally is helpful. We are going to do that with the help of Redux DevTools. The creator of Redux DevTools wrote a post on using Redux DevTools without Redux. We are already using Redux DevTools for debugging redux, so there will be no additional dependencies to add.

Testing

During the process of designing the engine, we try to stay functional. Most of the components we come up with are pure functions. Pure functions are a type of functions that don't cause side effects. Given the same inputs, they will always produce the same outputs. Pure functions are great for testing because they don't have global dependencies and their outputs are predictable.

The system is under development. I am sure we will encounter more interesting problems. It is one of the bigger projects for me, and most importantly, it is a brand new project. Who doesn't like writing new codes 😏?