Implementing a reducing interpreter

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.

The next table shows the well-known semantics of the and and or boolean binary operators.

*) 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 => { (2)
    // body in listing 7.2
}

export const reduced = (value: Value): Value => { (3)
    if (value instanceof BooleanLiteral) {
        return booleanLiteral(value.value) (4)
    }
    if (value instanceof BinaryOperation) {
        return reducedBinaryOperation(value) (5)
    }
    return deepCloned(value) (6)
}

1. Define a separate function that reduces BinaryOperation. The body of this you’ll find in the next listing.
2. Define the reduced function that reduces an instance of Value, returning a Value.
3. If value is a BooleanLiteral, return a new BooleanLiteral with the same value. We need to instantiate a new BooleanLiteral instance, because any node must in appear in only AST.
4. If value is a BinaryOperation, delegate reduction to the reducedBinaryOperation function.
5. In all other cases, just return the deep-cloned value. Deep-cloning value is necessary because any node must appear in a AST only once. The implementation of the deepCloned function is in listing further below.

The body of the reducedBinaryOperation function:

const reducedLeft = reduced(left) (1)
const leftIsBoolean = reducedLeft instanceof BooleanLiteral (2)
const reducedRight = reduced(right) (3)
const rightIsBoolean = reducedRight instanceof BooleanLiteral

switch (operator) { (4)

    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!`) (5)
}

    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: { (6)
        console.debug(`don’t know how to handle binary operation with operator=${operator}`)
        return binaryOperation(operator, reducedLeft, reducedRight)
    }

}

1. Reduce the left operand as much as possible by calling reduced.
2. Check if the reduced left operand is a boolean literal.
3. Do the same for the right operand.
4. Switch on the operator field of the BinaryOperation instance, with a case for and, for or, and a default case:
5. We actually already handled all cases in the previous if-statements, so we should never reach here.
6. 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 the first two listings 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:

*) 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)

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 type INodeBase), with the ID of each duplicated node computed by the newId function.
• The returned function is then called with the node passed to deepCloned. This returns an array of duplicated nodes that a priori have type INodeBase.
• That array will only contain one node: the deep-cloned node. We get that deep-cloned node out of the array, and cast it to the same type as the given node.

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 * from "./MyFPL.g.js"
export { reduced } from "./reducer.js"
export { Shorthands } from "./shorthands.js"

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" (1)
import { describe } from "mocha"

import { BinaryOperator, BooleanLiteral, reduced, Shorthands, Value } from "my-fpl"

const {binaryOperation, booleanShorthands} = new Shorthands()
const {booleanLiteral, trueLiteral, falseLiteral} = booleanShorthands

describe(`reduction of booleans`, () => {

    const expectBoolean = (value: Value, expected: boolean) => { (2)
        expect(value).to.be.instanceof(BooleanLiteral)
        expect((value as BooleanLiteral).value).to.eq(expected)
    }

    it(`boolean literals`, () => { (3)
        const trueResult = reduced(trueLiteral())
        expectBoolean(trueResult, true)

        const falseResult = reduced(falseLiteral())
        expectBoolean(falseResult, false)
    })

    it(`and/or operators`, () => { (4)
        for (const operator of [BinaryOperator.and, BinaryOperator.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 BinaryOperator.and: return leftOperand && rightOperand
                                case BinaryOperator.or: return leftOperand || rightOperand
                                default: throw new Error(`test can’t handle binary operator: ${operator}`)
                            }
                        })()
                    )
                }
            }
        }
    })

})

1. Import the chai and mocha testing libraries/frameworks as dependencies. This relies on having executed npm add chai and npm add mocha before.
2. Define a helper function that asserts a value is a BooleanLiteral with the indicated value.
3. Assert that a boolean value reduces to the same boolean value.
4. Loop over all cells in the first table above.

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)