> ## Content Index
> Fetch the complete content index at: https://dsl-consultancy.ghost.io/llms.txt
> Use this file to discover other available public pages before exploring further.

# Implementing a reducing interpreter
- URL: https://dsl-consultancy.ghost.io/implementing-a-reducing-interpreter/
- Published: 2026-09-18T07:23:42.000Z
- Updated: 2026-09-24T09:16:26.000Z
- Author: Meinte Boersma

💡

This is post 07 in my blog series on MyFPL — see [the index/table of contents](https://codeberg.org/dslmeinte/my-fpl/src/branch/main/blogs/index.adoc?ref=dsl-consultancy.ghost.io).  
  
The code in this and previous blog posts can also be found [here, on Codeberg](https://codeberg.org/dslmeinte/my-fpl?ref=dsl-consultancy.ghost.io). 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 `Value`s 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**](https://en.wikipedia.org/wiki/Homoiconicity?ref=dsl-consultancy.ghost.io). Homoiconic reduction fits entirely with my goals, and it also avoids that we have to decide how to translate MyFPL `Value`s to appropriate runtime representations.

We’ll call this **reducing interpreter** the ***reducer***, from now on.

💡

****Native runtime representations vs. homoiconicity**  
  
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.

__Semantics of and and or binary operations__
| 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 => { (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 `BooleanLiteral`s. 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:

__Semantics of and and or binary operations, with operands reduced to booleans and not reducible to booleans__
| 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)
```

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.

💡

We didn’t use the `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.

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.

💡

In this blog post, we’ve implemented a **reducing interpreter*. In the next blog post, I’ll explain how we’re going to cater for the **notation* or **syntax* aspect of MyFPL.

© 2026 Meinte Boersma (DSL Consultancy)