> ## 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 type system
- URL: https://dsl-consultancy.ghost.io/implementing-a-type-system/
- Published: 2026-10-30T09:57:10.000Z
- Updated: 2026-11-17T10:07:20.000Z
- Author: Meinte Boersma

💡

This is post 11 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 11”.

Across the next blog posts, we’re going to implement a *type system*. “What’s that?” I hear you ask. Well, glad you did. This question can – and has been – answered in a multitude of ways. I tend towards a rather simple – some would even say simpl**istic** – one.

**A type system is a something that associates parts of your program with a range of types, and checks whether your program is *consistent* in terms of those types.**

In our context, “part of a program” translates to “AST node”. A type system then consists of the following moving parts:

1. A *range of types* to describe types with.
2. A *type computer* that computes a type from that range for any AST node in our programs that we deem useful to associate with a type.
3. A set of *type constraints* that determine for any AST node in our program whether that AST node makes sense type-wise. A *constraint* consists of the following things:
  1. A *reference* to one of the classifiers in MyFPL’s structure.
  2. A *logical condition* that a(ny) node that’s compatible with the classifier from item 1, has to conform to.
  3. A *function* to compute a *violation message* to report on a node if the condition from item 2 is not met by that node.

💡

Not all constraints are type constraints. Other kinds of constraints check for other kinds of consistency than type-consistency.

A *constraints checker* is a separate component – that we get to in a separate blog post – that’s responsible for checking every AST node against every constraint, and reporting violations to the user. Because computed types serve as input for the constraints checker, we’re going to implement the type computer first.

For us, the type computer is essentially a function that returns a `Type` node given an AST node that we think should be associated to a type. MyFPL’s structure currently is very limited: every value in our program is either a `BooleanLiteral` or a `BinaryOperation` with boolean operator `and` or `or`. This makes the type computer *a priori* a bit trivial: every value is `BooleanType`\-d. (`BooleanType` is also the only subtype of `Type`, anyway.)

💡

A type system is a **design space* in the sense that we can make a lot of design choices — even if it doesn’t feel that way yet, because MyFPL is still so tiny.

This simplicity/triviality allows us to spend some thinking time and code on how we’re going to implement the type computer on. Some questions shaping that:

- Compute a type for what AST nodes? Not every concept in MyFPL’s structure admits a sensible type for its instances — e.g.: what would be a sensible type of a `Program` node?
- How to trigger type computation? Do we compute types on the fly, whenever requested? Do we pre-compute them like we did with the reductions to visualize? Can we compute them *reactively*, i.e. compute them on-demand, but recompute them whenever AST nodes change?
- How to deal with *type interdependencies*?Most AST nodes are dependent on their children and/or other nodes they reference for their exact meaning. That also means that the type computation of most AST nodes is going to depend on the types computed for their children and/or nodes they reference. We could’ve already seen this, had MyFPL had integers, including corresponding integer operators for `BinaryOperation`\-s. Another example would be constructs like references to other things that have a type – such as variables/constants, or function parameters.

The last two questions really are different sides of the same coin, because the order in which type computation can/should be triggered depends heavily on the possible type interdependencies. Initially, we’re going to answer these last two questions in a blissfully stupid fashion, because even then, we already have enough machinery to implement — meaning code to write and explain. (Rest assured: we’ll better our lives along the course of this blog series.)

Essentially, I want to reach a point where we covered all four key aspects – structure, notation, constraints, meaning – of MyFPL as quickly as possible, and constraints is the missing one. Once we’ve reached that point, we can continue with:

1. Expanding the structure with more language constructs.
2. Expanding the projection, type system, constraints, and reducer – i.e.: the notation, constraints, and meaning aspects – accordingly.
3. Making the projection interactive and editable.
4. Improving the implementation of all these aspects — e.g.: their performance.

## What to compute a type for

Right now, any AST node is either a `Value` or a `Program`. (The “standalone, concrete” classifiers comment in the `packages/my-fpl/src/reflection.g.ts` file only mentions `Program` and the `Reduction` annotation, which we’re not going to assign a type.) So, it’s pretty obvious that we should compute types for all values, but nothing else. This means we shouldn’t compute types for `Program`, nor for any of the concrete concepts inheriting from `Type`.

This definitely *will* change in the future, and we don’t have to consult a crystal ball to see that. As an example: consider a parameter of a function definition, that consists of a name and a (declared) type. Such a parameter isn’t itself a value, since what would it evaluate to? But it can be associated with a type in an obvious way, through its declared type.

From now on, we’ll call something “*typable*” if it can be associated with a type. It makes sense to have a way to “flag” typable classifiers in MyFPL’s structure.

Let’s introduce yet another interface for that: the `Typable` interface.

![](https://storage.ghost.io/c/eb/4d/eb4df6b9-0e4f-4d29-b975-4075848c0001/content/images/2026/10/code-Listing-11_1-structure-changes.png)

Listing 11\. 1\. Extending MyFPL’s structure with a `Typable` interface (in the `packages/build/src/structure.ts` file)

1. Define the `Typable` interface, *before* the definition of the `Value` interface.
2. Extend the existing `Value` interface from the newly-defined interface. This makes all values typable.

Code typeset in **bold** indicates an addition to existing code.

(We leave `Program` and `Type` as they are.)

## Implement the type computation

After running the `generate` NPM task in the `build` package, we can implement the type computer, in the form of a `typeOf` type computation function in the new `packages/my-fpl/src/type-computer.ts` file. Because MyFPL is still so tiny and extremely simple, the function is very simple as well — for now, at least.

```
import { BinaryOperation, BooleanLiteral, Typable, Type } from "./MyFPL.g.js"
import { Shorthands } from "./shorthands.js"

const { typeShorthands } = new Shorthands()
const { booleanType } = typeShorthands

export const typeOf = (typable: Typable): Type => { ❶
    if (typable instanceof BooleanLiteral) { ❷
        return booleanType()
    }
    if (typable instanceof BinaryOperation) { ❸
        return booleanType()
    }
    throw new Error(`concept not handled by typeOf: ${typable.classifier.name}`) ❹
}
```

Listing 11\. 2\. Implementing the type computer (in the new `packages/my-fpl/src/type-computer.ts` file)

1. Define the `typeOf` type computation function that takes a `Typeable` (node) and returns a `Type` (node).
2. If the `typable` is a `BooleanLiteral`, return a newly-minted `BooleanType` node.
3. Do the same if `typable` is a `BinaryOperation`, since all our current binary operations – `and` and `or` – are boolean operators that evaluate to a boolean. Obviously, this will change in the future, after the introduction of other types, and other corresponding binary operators — e.g., integers and the standard arithmetic operators.
4. Throw a “not handled”-`Error` in case we forget to handle a value `Concept` through a corresponding `if (typable if <concept>) { … }` statement.

### Testing the type computation

We also want to write some unit tests for this, so we have to expose the `typeOf` function to the `test` package, by adding the following line of code to the `packages/my-fpl/src/index.ts` file:

Listing 11\. 3\. Export the`typeOf`function from the`my-fpl`package (in the`packages/my-fpl/src/index.ts`file)

```
export { typeOf } from "./type-computer.js"
```

Now, we can write unit tests in the new `packages/test/src/type-computer.tests.ts` file:

```
import { expect } from "chai"

import { myFPL, Shorthands, typeOf } from "my-fpl"

const { binaryOperation, booleanShorthands } = new Shorthands()
const { trueLiteral, falseLiteral } = booleanShorthands
const { and, or } = myFPL.BinaryOperator

describe(`(naive) typeOf`, () => {

    it(`literals`, () => { ❶
        expect(typeOf(trueLiteral())).to.be.instanceof(myFPL.BooleanType)
        expect(typeOf(falseLiteral())).to.be.instanceof(myFPL.BooleanType)
    })

    it(`binary operations`, () => { ❷
        const andOperation = binaryOperation(
            and,
            trueLiteral(),
            falseLiteral()
        )
        expect(typeOf(andOperation)).to.be.instanceof(myFPL.BooleanType)

        const orOperation = binaryOperation(
            or,
            trueLiteral(),
            trueLiteral()
        )
        expect(typeOf(orOperation)).to.be.instanceof(myFPL.BooleanType)

        const nestedBinaryOperation = binaryOperation(
            and,
            binaryOperation(or, trueLiteral(), falseLiteral()),
            trueLiteral()
        )
        expect(typeOf(nestedBinaryOperation)).to.be.instanceof(myFPL.BooleanType)
    })

    it(`throws error for unhandled Typable concept`, () => {
        const program = myFPL.Program.create("test-id")
        expect(() => typeOf(program as unknown as myFPL.Typable))   ❸
            .to.throw(Error, /concept not handled by typeOf: Program/)
    })

})
```

Listing 11\. 4\. Unit testing the `typeOf` function (in the new `packages/test/src/type-computer.tests.ts` file)

1. Check what `typeOf` does on literals in one `it`\-section.
2. Check what `typeOf` does on binary operations in another `it`\-section.
3. Ensure that the “not handled”-`Error` gets thrown. Because I don’t want to make the effort to create an extra, “bogus” typable concept, I test this by passing a `Program` node, “disguised” as a `Typable` through an `as`\-typecase, into `typeOf`.

💡

In this blog post, we started with the implementation of MyFPL’s **type system*. We got as far as implementing a “naive” type computer function. In the next blog post, we’re going to trigger type computation on our programs, and visualize the computed types.

© 2026 Meinte Boersma (DSL Consultancy)