Implementing a reducing interpreter
The code in this and previous blog posts can also be found here, on Codeberg. Check out the repo at the commit marked “blog 07”.
In the previous blog post, we created meta-types for booleans, and constructed ASTs from those. Of course, we also would like to run such programs. To do that, we’re going to build an interpreter. An interpreter takes an MyFPL program and “some data”, and returns “the result” of this program. (We’ll make the “some data” part more explicit a couple of blog posts later on.) Often, this result consists of data, and possibly some side effects.
The interpreter that we’ll be building, is a little bit different from usual interpreters. It interprets the MyFPL program by reducing it as much as possible but not more. That means (among other things) that we won’t be throwing exceptions whenever we find during reduction that some constraint gets violated. An example of a violated constraint is: some piece of data is missing, or we divided by zero. Instead of throwing an exception, we just return a new MyFPL program that’s the reduction of the MyFPL program we were running, up to the point that the constraint turned out to be violated. (In fact, it’s quite likely we can even reduce the MyFPL program beyond that point — we’ll demonstrate this later, along the course of this blog series.) This coincidentally means that all data that the program operates on, or returns, has the form of (or should be representable as) MyFPL Values as well.
The principle of programs, data they operate on, as well as the result of running/interpreting programs having the same format, is called homoiconicity. Homoiconic reduction fits entirely with my goals, and it also avoids that we have to decide how to translate MyFPL Values to appropriate runtime representations.
We’ll call this reducing interpreter the reducer, from now on.
A “typical” interpreter tends to evaluate to values whose types are native to the programming language that the interpreter is implemented in. E.g.: in our case, a boolean-typed value would evaluate to a JavaScript
Boolean value.This has several advantages: If the runtime representations are nimble – such as JavaScript’s primitive types:
Boolean, Number, etc. – a minimum of memory is allocated for such values. Using native types also makes for faster and easier to read code.Homoiconic reduction means that the reducer has to spend more time and memory constructing the node objects that make up the AST of the reduction of a MyFPL program. Because MyFPL is not meant for high-performance computing purposes, this is OK.
The next table shows the well-known semantics of the and and or boolean binary operators.
| left operand* | right operand* | and |
or |
|---|---|---|---|
false |
false |
false |
false |
true |
false |
false |
true |
false |
true |
false |
true |
true |
true |
true |
true |
*) Actually: the reduction of those operands, so we can use boolean binary operators within boolean binary operators.
We’ll implement these semantics as follows, in the new packages/my-fpl/src/reducer.ts file.
import { BinaryOperation, BinaryOperator, BooleanLiteral, Value } from "../MyFPL.g.js"
import { Shorthands } from "../shorthands.js"
const { binaryOperation, booleanLiteral } = new Shorthands()
const reducedBinaryOperation = ({ operator, left, right }: BinaryOperation): Value => { âť¶
// body in listing 7.2
}
export const reduced = (value: Value): Value => { âť·
if (value instanceof BinaryOperation) {
return reducedBinaryOperation(value) ❸
}
return deepCloned(value) âťą
}Listing 7. 1. Implementation of a reducer AKA an interpreter (in the packages/my-fpl/src/reducer.ts file)
- Define a separate function that reduces
BinaryOperation. The body of this you’ll find in the listing 7.2. - Define the
reducedfunction that reduces an instance ofValue, returning aValue. - If
valueis aBinaryOperation, delegate reduction to thereducedBinaryOperationfunction. - In all other cases, just return the deep-cloned
value. Deep-cloningvalueis necessary because any node can appear in an AST only once. The implementation of thedeepClonedfunction is in listing 7.3 (further below).
BooleanLiteral in listing 7.1 above. But this is covered by the final return-statement, that deep-clones value, which we’d have to do for a BooleanLiteral anyway. You’re free to choose to handle BooleanLiteral explicitly, of course.The body of the reducedBinaryOperation function:
const reducedLeft = reduced(left) âť¶
const leftIsBoolean = reducedLeft instanceof BooleanLiteral âť·
const reducedRight = reduced(right) ❸
const rightIsBoolean = reducedRight instanceof BooleanLiteral
switch (operator) { âťą
case BinaryOperator.and: {
if (leftIsBoolean && rightIsBoolean) {
return booleanLiteral(reducedLeft.value && reducedRight.value)
}
if (!leftIsBoolean && !rightIsBoolean) {
return binaryOperation(operator, reducedLeft, reducedRight)
}
if (leftIsBoolean) { // ==> !rightIsBoolean
return reducedLeft.value
? reducedRight
: booleanLiteral(false)
}
if (rightIsBoolean) { // ==> !leftIsBoolean
return reducedRight.value
? reducedLeft
: booleanLiteral(false)
}
throw new Error(`shouldn’t be able to reach here!`) ❺
}
case BinaryOperator.or: {
if (leftIsBoolean && rightIsBoolean) {
return booleanLiteral(reducedLeft.value || reducedRight.value)
}
if (!leftIsBoolean && !rightIsBoolean) {
return binaryOperation(operator, reducedLeft, reducedRight)
}
if (leftIsBoolean) { // ==> !rightIsBoolean
return reducedLeft.value
? booleanLiteral(true)
: reducedRight
}
if (rightIsBoolean) { // ==> !leftIsBoolean
return reducedRight.value
? booleanLiteral(true)
: reducedLeft
}
throw new Error(`shouldn’t be able to reach here!`)
}
default: { âť»
console.debug(`don’t know how to handle binary operation with operator=${operator}`)
return binaryOperation(operator, reducedLeft, reducedRight)
}
}Listing 7. 2. Body of the reducedBinaryOperation function
- Reduce the left operand as much as possible by calling
reduced. - Check if the reduced left operand is a boolean literal.
- Do the same for the right operand.
- Switch on the
operatorfield of theBinaryOperationinstance, with a case forand, foror, and a default case: - We actually already handled all cases in the previous
if-statements, so we should never reach here. - If we happen to have stumbled upon an unknown binary operator, we print a helpful debug message on the JS console for ourselves, and return a newly-minted binary operation with that operator and the reduced left and right operands.
Even though we can only have values that are instances of BooleanLiteral and BinaryOperation with operator and/or at this point, the code in listings 7.1 and 7.2 above doesn’t rely on that knowledge. Instead, it explicitly checks whether the left and right operands reduced to BooleanLiterals. If they don’t, or if the Value to reduce is neither a BooleanLiteral nor a BinaryOperation, it returns a version of it that’s reduced as much as possible — which sometimes is not at all.
We’ve effectively implemented the following semantics:
| left operand* | right operand* | and |
or |
|---|---|---|---|
false |
false |
false |
false |
true |
false |
false |
true |
| <left operand> | false |
false |
<left operand> |
false |
true |
false |
true |
true |
true |
true |
true |
| <left operand> | true |
<left operand> | true |
false |
<right operand> | false |
<right operand> |
true |
<right operand> | <right operand> | true |
| <left operand> | <right operand> | <left operand> and <right operand> |
<left operand> or <right operand> |
*) Again: the reduced operands, really.
For any other operator than and and or, a BinaryOperation is reduced to: <reduced left operand> <operator> <reduced right operand>.
Finally, we implement the deepCloned function, in a separate new packages/my-fpl/src/lionweb-utils.ts file:
import { deepDuplicatorFor, INodeBase } from "@lionweb/class-core"
import { newId } from "./ids.js"
import { MyFPLBase } from "./MyFPL.g.js"
const deepCloned = <NT extends INodeBase>(node: NT): NT =>
deepDuplicatorFor([MyFPLBase.INSTANCE], newId)(node)[0] as NT (1)Listing 7. 3. Implementation of a deep-cloner (in a new packages/my-fpl/src/lionweb-utils.ts file)
I realize that final line of code might look like an incantation of a magic spell, so I’ll unpack it:
deepDuplicatorFor([MyFPLBase.INSTANCE], newId)returns a function that duplicates a given node (of typeINodeBase), with the ID of each duplicated node computed by thenewIdfunction.- The returned function is then called with the
nodepassed todeepCloned. This returns an array of duplicated nodes that a priori have typeINodeBase. - That array will only contain one node: the deep-cloned
node. We get that deep-clonednodeout of the array, and cast it to the same type as the givennode.
Testing the reducer
The implementation of the reducer is pretty straightforward, but it would nevertheless behoove us to test it. We implement (unit) tests in the separate test package next to the build and my-fpl packages, using the Mocha and Chai frameworks.
To be able to access the “stuff” to test, we first expose it from (a new index.ts file in) the my-fpl package, as follows:
export * as myFPL from "./MyFPL.g.js" âť¶
export { reduced } from "./reducer.js"
export { Shorthands } from "./shorthands.js"Listing 7. 4. Exposing the MyFPL language from the my-fpl package from an index.ts file
- Export everything from the file generated from MyFPL’s structure, grouped together as a
myFPLconstant. This constant serves as a “namespace” of-sorts, and is useful to shortenimport-statements a bit, as well as to avoid potential name collisions.
After building the my-fpl package, we can write unit tests, which we’ll do in the new packages/test/src/reducer.tests.ts file:
import { expect } from "chai" âť¶
import { describe } from "mocha"
import { myFPL, reduced, Shorthands } from "my-fpl"
const { binaryOperation, booleanShorthands } = new Shorthands()
const { booleanLiteral, trueLiteral, falseLiteral } = booleanShorthands
const { and, or } = myFPL.BinaryOperator âť·
const expectBoolean = (value: myFPL.Value, expected: boolean) => { ❸
expect(value).to.be.instanceof(myFPL.BooleanLiteral)
expect((value as myFPL.BooleanLiteral).value).to.equal(expected)
}
describe(`reduction of literals`, () => {
it(`booleans`, () => { âťą
const trueResult = reduced(trueLiteral())
expectBoolean(trueResult, true)
const falseResult = reduced(falseLiteral())
expectBoolean(falseResult, false)
})
})Listing 7. 5. Unit testing the reduction of boolean literals (in the new packages/test/src/reducer.tests.ts file)
- Import the
chaiandmochatesting libraries/frameworks as dependencies. This relies on having executednpm add chaiandnpm add mochabefore. - Destructure the literals from the
BinaryOperatorenumeration, just to avoid that we have to typemyFPL.BinaryOperator.so often, in listing 7.6 (and later). - Define a helper function that asserts a value is a
BooleanLiteralwith the indicated value. - Assert that a boolean value reduces to the same boolean value.
Finally, we’re going to add a unit test that checks the reduction of binary operations with all combinations of boolean operands and and/or operators. It’s easy to check those because we can – so far – only instantiate two boolean values: the true and false literals.
describe(`reduction of binary operations`, () => {
it(`boolean operands with and/or operators`, () => { âť¶
for (const operator of [and, or]) {
for (const leftOperand of [true, false]) {
for (const rightOperand of [true, false]) {
const result = reduced(binaryOperation(operator, booleanLiteral(leftOperand), booleanLiteral(rightOperand)))
expectBoolean(
result,
(() => {
switch (operator) {
case and: return leftOperand && rightOperand
case or: return leftOperand || rightOperand
default: throw new Error(`test can’t handle binary operator: ${operator}`)
}
})()
)
}
}
}
})
})Listing 7. 6. Unit testing the reduction of binary operations with booleans operator and operands (in the new packages/test/src/reducer.tests.ts file)
- Loop over all cells in table 7.1.
BooleanType concept at all, yet. That’s because we neither implemented a type system yet, nor type declarations. This’ll change along the course of this blog series — from blog post 11 onwards.This blog post is somewhat “code-heavy”. That’s partly due to a certain amount of boilerplate necessary, and partly because the semantics of the and and or operators in MyFPL simply require a certain amount of code — both for their logic, as for their unit tests.
© 2026 Meinte Boersma (DSL Consultancy)