Implementing a type system

Share
đź’ˇ
This is post 11 in my blog series on MyFPL — see the index/table of contents.

The code in this and previous blog posts can also be found here, on Codeberg. 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 simplistic â€“ 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.

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)