They are "just" a JSON form of an Abstract Syntax Tree, so you can write your own executor. In particular it seems they follow the following convention, according to their own docs:
- Arrays are expressions, while all other JSON types are literals (curiously this implies no array literals directly! I'll elaborate a fix later)
- The first item of an array is the function to be executed, while the rest of the items are parameters to that function.
- The root object is not necessarily relevant to the expression syntax, just where they happen use it.
- The only "stateful" thing is the
let/var functions, which allow you to create variables, scoped to the enclosing let expression, which suggests they have some way to pass a context to functions.
So, let's build one! I'll try to go over the code line by line below, but you can also just look at the snippet source at the end of the question if you prefer the formatting there.
Here we will later define all functions available for the expression language
const OPERATIONS = {};
Now, let's set up the evaluator function. It obviously must receive the expression it will evaluate, but also a context that can be modified by operations.
const evaluate = (expression, context = {}) => {
First, we deal with literals by evaluating them as themselves
if (!(expression instanceof Array)) {
return expression;
}
Right, now to the real deal:
let's find out what operation to run and its parameters.
const [operationKey, ...rawParameters] = expression;
const operation = OPERATIONS[operationKey];
We handle unknown operations by panicking! AAAH!
if (operation == null) {
throw new Error(`Unknown operation ${operationKey}!`);
}
Oh nice, we know this operation! Now, how should we call it?
It obviously needs to receive its parameters, as well as the context,
in case it is one of those pesky stateful operations. Plus, as we
have seen with Mapbox's let, operations can create new contexts!
I propose the following signature, though you can change it for your
particular preference and use-cases:
First parameter:
Current context
Second parameter:
Array of all of the operation's parameters. This makes for
easy iteration if the operation is variadic, and simpler stuff
can still just use deconstruction to have a "fixed" signature.
We will pass the parameters "raw", not evaluated, so that the
operation can do whatever evil things it wants to do to them.
Return value:
Whatever the operation wants to evaluate to!
return operation(context, rawParameters);
};
Right, right, we have set up the evaluator, but how do we actually use it?
We need some operations, let's start with the easy ones to wet our feet:
Remember how I said above that the parameters array comes in raw? We'll need to evaluate them manually inside our operation functions.
OPERATIONS["-"] = (context, [a, b]) => evaluate(a, context) - evaluate(b, context);
OPERATIONS["+"] = (context, [a, b]) => evaluate(a, context) + evaluate(b, context);
Okay, that was easy, but what if we want to accept an arbitrary amount of arguments?
OPERATIONS["*"] = (context, parameters) => parameters
.map(p => evaluate(p, context))
.reduce((accumulator, x) => accumulator * x);
Right, now let's implement those arrays we spoke of. The solution is simple, have an operation that creates the array from its parameters!
OPERATIONS["array"] = (context, parameters) => parameters
.map(p => evaluate(p, context));
Cool, cool, but what about the evil spawns of Satan himself? let and var?
Let's start with the lesser of them: Easy, we just read whatever was stored in the context for that variable name!
OPERATIONS["var"] = (context, [variable]) => context[variable];
Now, the "tricky" one, let, which is both variadic AND changes the context!
I'll pull out my braces here because it's gonna be a bit bigger than the previous beautiful one-line operations!
OPERATIONS["let"] = (context, [...definitions]) => {
Right, we have A context, but we don't want to pollute it outside the let block! So let's copy it to a new temporary one:
const innerContext = { ...context };
Now we need to loop the definitions, remember, they are 2 elements each:
A variable name, and its value expression! But first, we need to pick out the last argument which is the expression to be executed in the resulting context:
const body = definitions.pop()
Let's get the obvious stuff out of the way, if we have an odd number of things in our definitions, the user is wrong! Let's throw it on their ugly face! Let's use a cryptic error message just to be evil...
if (definitions.length % 2 === 1) {
throw new Error("Unmatched definitions!");
}
Cool, now we get to do the cool stuff which is create those variables:
for (let i = 0; i < definitions.length - 1; i += 2) {
const name = definitions[i];
const value = definitions[i + 1];
Here I made the choice that variables in the same block can depend
on previous variables, if that's not to your liking, use the parent
context instead of the one we're modifying at the moment.
innerContext[name] = evaluate(value, innerContext);
}
Variables are done, now let's evaluate the body!
return evaluate(body, innerContext);
};
And we're done! That is the basic of evaluating a syntax tree!
You might want to go on and add your own domain-specific operations now.
I made this snippet for demonstrating how this ends up working, and using code comments instead of literate-coding if that's your style. The HTML and CSS are irrelevant, just some lipstick to make it look a bit more presentable.
// Here we will later define all functions available for the expression language
const OPERATIONS = {};
// Now, let's set up the evaluator function.
// It obviously must receive the expression it will evaluate,
// but also a context that can be modified by operations.
const evaluate = (expression, context = {}) => {
// First, we deal with literals by evaluating them as themselves
if (!(expression instanceof Array)) {
return expression;
}
// Right, now to the real deal:
// let's find out what operation to run and its parameters.
const [operationKey, ...rawParameters] = expression;
const operation = OPERATIONS[operationKey];
// We handle unknown operations by panicking! AAAH!
if (operation == null) {
throw new Error(`Unknown operation ${operationKey}!`);
}
// Oh nice, we know this operation! Now, how should we call it?
// It obviously needs to receive its parameters, as well as the context,
// in case it is one of those pesky stateful operations. Plus, as we
// have seen with Mapbox's `let`, operations can create new contexts!
//
// I propose the following signature, though you can change it for your
// particular preference and use-cases:
//
// First parameter:
// Current context
// Second parameter:
// Array of all of the operation's parameters. This makes for
// easy iteration if the operation is variadic, and simpler stuff
// can still just use deconstruction to have a "fixed" signature.
// We will pass the parameters "raw", not evaluated, so that the
// operation can do whatever evil things it wants to do to them.
// Return value:
// Whatever the operation wants to evaluate to!
return operation(context, rawParameters);
};
// Right, right, we have set up the evaluator, but how do we actually use it?
// We need some operations, let's start with the easy ones to wet our feet:
// Remember how I said above that the parameters array comes in raw?
// We'll need to evaluate them manually inside our operation functions.
OPERATIONS["-"] = (context, [a, b]) => evaluate(a, context) - evaluate(b, context);
OPERATIONS["+"] = (context, [a, b]) => evaluate(a, context) + evaluate(b, context);
// Okay, that was easy, but what if we want
// to accept an arbitrary amount of arguments?
OPERATIONS["*"] = (context, parameters) => parameters
.map(p => evaluate(p, context))
.reduce((accumulator, x) => accumulator * x);
// Right, now let's implement those arrays we spoke of.
// The solution is simple, have an operation that
// creates the array from its parameters!
OPERATIONS["array"] = (context, parameters) => parameters
.map(p => evaluate(p, context));
// Cool, cool, but what about the evil spawns of Satan himself? Let and Var?
// Let's start with the lesser of them:
// Easy, we just read whatever was stored in the context for that variable name!
OPERATIONS["var"] = (context, [variable]) => context[variable];
// Now, the "tricky" one, Let, which is both variadic AND changes the context!
// I'll pull out my braces here because it's gonna be a bit bigger than the
// previous beautiful one-line operations!
OPERATIONS["let"] = (context, [...definitions]) => {
// Right, we have A context, but we don't want to pollute it outside
// the Let block! So let's copy it to a new temporary one:
const innerContext = { ...context
};
// Now we need to loop the definitions, remember, they are 2 elements each:
// A variable name, and its value expression! But first, we need to pick
// out the last argument which is the expression to be executed in the
// resulting context:
const body = definitions.pop()
// Let's get the obvious stuff out of the way, if we have an odd number of
// things in our definitions, the user is wrong! Let's throw it on their
// ugly face! Let's use a cryptic error message just to be evil...
if (definitions.length % 2 === 1) {
throw new Error("Unmatched definitions!");
}
// Cool, now we get to do the cool stuff which is create those variables:
for (let i = 0; i < definitions.length - 1; i += 2) {
const name = definitions[i];
const value = definitions[i + 1];
// Here I made the choice that variables in the same block can depend
// on previous variables, if that's not to your liking, use the parent
// context instead of the one we're modifying at the moment.
innerContext[name] = evaluate(value, innerContext);
}
// Variables are DONE, now let's evaluate the body!
return evaluate(body, innerContext);
};
// Bonus points for reading the snippet code:
// Remember that we are not limited to numeric values,
// anything that JSON accepts we accept too!
// So here's some simple string manipulation.
OPERATIONS["join"] = (context, [separator, things]) => evaluate(things, context)
.flat()
.join(separator);
// And we're done! That is the basic of evaluating a syntax tree!
// Not really relevant to the question itself, just a quick and dirty REPL
(() => {
const input = document.getElementById("input");
const output = document.getElementById("output");
const runSnippet = () => {
let expression;
try {
expression = JSON.parse(input.value);
} catch (e) {
// Let the user type at peace by not spamming errors on partial JSON
return;
}
const result = evaluate(expression);
output.innerText = JSON.stringify(result, null, 2);
}
input.addEventListener("input", runSnippet);
runSnippet();
})();
html {
display: flex;
align-items: stretch;
justify-content: stretch;
height: 100vh;
background: beige;
}
body {
flex: 1;
display: grid;
grid-template-rows: 1fr auto;
grid-gap: 1em;
}
textarea {
padding: 0.5em;
border: none;
background: rgba(0, 0, 0, 0.8);
color: white;
resize: none;
}
<textarea id="input">
[
"let",
"pi", 3.14159,
"radius", 5,
[
"join",
" ",
[
"array",
"a circle with radius",
["var", "radius"],
"has a perimeter of",
[
"*",
2,
["var", "pi"],
["var", "radius"]
]
]
]
]
</textarea>
<pre id="output">
</pre>