In a language that allows defining types in-language, how to store type computation results?

[haukepribnow]

I'm working on a language in which the user can define their own types. Now I wonder: At what point should I run the type inference and what is the "right" place to store the type inference information that is most in line with the Langium architecture?

At this point, I'm primarily interested in making the inferred types available to the ScopeProvider so that it can provide a scope containing the members of a defined type in an expression. For example, my language supports the dot notation for accessing members like in person.city.name.length. Here, I would like to for example enable the ScopeProvider to provide the members of person's type or of person.city's type etc..

With regards to implementing a type system in Langium, the documentation available on https://langium.org/docs/reference/document-lifecycle/ tells me:

In languages with a type system, you would typically implement computation of types in an additional pre-processing step in order to make type information available in the document. This additional step can be registered to run after scope computation with the onBuildPhase method of DocumentBuilder. How types are computed heavily depends on the kind of type system, so there is no default implementation for it.

So this does answer the "what point" part of my question already. But just to go sure, I would love to get feedback whether I got the documentation right. Here's how I interpreted the documentation:

export const Hfunct02Module: Module<Hfunct02Services, PartialLangiumServices & Hfunct02AddedServices> = {
    validation: {
        Hfunct02Validator: () => new Hfunct02Validator()
    },
    references: {
        ScopeProvider: (services) => new Hfunct02ScopeProvider(services)
    },
    ///////////////// <new>
    types: {
        Hfunct02TypeComputer: (services) => new Hfunct02TypeComputer(services)
    }
    ///////////////// </new>
};


export function createHfunct02Services(context: DefaultSharedModuleContext): {
    shared: LangiumSharedServices,
    Hfunct02: Hfunct02Services
} {
    const shared = inject(
        createDefaultSharedModule(context),
        Hfunct02GeneratedSharedModule
    );
    const Hfunct02 = inject(
        createDefaultModule({ shared }),
        Hfunct02GeneratedModule,
        Hfunct02Module
    );
    shared.ServiceRegistry.register(Hfunct02);
    registerValidationChecks(Hfunct02);

    ///////////////// <new>
    const typeComputer = Hfunct02.types.Hfunct02TypeComputer;
    shared.workspace.DocumentBuilder.onBuildPhase(DocumentState.ComputedScopes, (documents, cancelToken) => {
        for (const document of documents) {
            if (cancelToken?.isCancellationRequested) {
                break;
            }
            typeComputer.compute(document);
        }
    });
    ///////////////// </new>

    if (!context.connection) {
        // We don't run inside a language server
        // Therefore, initialize the configuration provider instantly
        shared.workspace.ConfigurationProvider.initialized({});
    }
    return { shared, Hfunct02 };
}

I feel this might work. But is there any advise that I should consider before I commit to this approach?

---

Moving on to the "where to store" question:

I haven't found any documentation that explains how a program that uses Langium is supposed to "attach" information to AST nodes for later use. The only documentation that deals with storing data while processing is the one about caches.

Because using a cache for the use case of storing type data feels not quite right, I looked into Langium's codebase and explored the default implementations for some of the services. I found that the DefaultIndexManager has its own Map that stores the relationship between strings and AST nodes. To mirror that approach, I could also add a similar Map as a field to my Hfunct02TypeComputer for storing the type of each AST node. I would have this Map get reset whenever the registered onBuildPhase callback fires. However, I wonder if the usage of onBuildPhase would suffice: Will the build phase be restarted also after a document got removed from the workspace? And will the callback therefore be called also in this case? (Because if it does not get fired in this case, then my Map would contain incorrect information.)

But taking a step back: Is this an approach that is really in line with Langium's architecture? Or does the architecture encourage users to store type information somewhere/somehow else?

[msujew]

Hey @haukepribnow,

Ideally, you would not eagerly compute the types of your documents. Instead, you can compute the types on the fly when they're needed. See as a larger example how it's implemented in the langium-lox example (without caching though). I'll think about creating a PR that adds caching soon, when I have some time this week.

With regards to implementing a type system in Langium, the documentation available on https://langium.org/docs/reference/document-lifecycle/ tells me:

I believe the documentation is a bit outdated there. However, what we often do is that we use the onBuildPhase or onDocumentPhase callbacks to search for additional data that needs to be stored in order to quickly infer the type information. But that really depends on the language. Often times, that is not really necessary.

I haven't found any documentation that explains how a program that uses Langium is supposed to "attach" information to AST nodes for later use. The only documentation that deals with storing data while processing is the one about caches.

The builtin caches are generally very useful when it comes to building (and caching) type system data. In our production grade projects, we usually build our type systems on a large DocumentCache<AstNode, TypeInfo>. Note that you generally don't need to worry about cache invalidation when using these caches, because they take care of it by themselves. I would recommend to supply the DocumentState.ComputedScopes argument for the state for this to work best.

[haukepribnow]

Thanks a lot.

you [...] compute the types on the fly when they're needed
That's actually what I've started with. However, my language requires a context-dependent type inference approach. In this approach, you need to have done the type inference work for specific containers before you can work on the children. And when going child-to-parent with this methodology, it's not trivial to know on what level it is sufficient to terminate.

To give a flavor, here's an example of what my language can currently support:

type int32 {
    gt : fn(other : int32) : bool;
}

type bool {
}
type string{
}
type Collection<T> {
}

type mapFuncType : <T,U>fn(coll : Collection<T>, mapper : fn(item : T) : U) : Collection<U>;

type Person {
    age : int32;
    city : string;
}

global persons : Collection<Person>;
global map : mapFuncType;

result = map(persons, [p => p.age.gt(18).ifElse("adult", "child")])

My challenge is this: For determining the scope for the members of p within the body of the inline function [p => p.age.gt(18)], the system must infer the type of that inline function first. This is possible by determining the type of the first argument persons and thereby finding out that T is of type Person. Only with this knowledge, the scope for what can follow after p. becomes known. So in order to determine the scope for the "inner" items, knowledge collected by running the inference on the outer items is required and needs to be passed down.

And as established: When the system would just get asked to provide the scope for a random "inner" element, it would not be trivial to determine from there "how far out" it needs to go to parent and parent-parents etc.

With this being written, what's your advice for a language with such type inference requirements? Should I still try whatever I can to do type inference "on the fly" as far as I can achieve it? Or would this complexity call for another approach?

[msujew]

Thanks for outlining the complexity of the language! In the end, the on-the-fly approach has the benefit of being able to resolve types on the spot. I.e. you can just ask arbitrary AST nodes for their types, and the type inference will resolve references, compute other types, etc. as required. The top-down approach does not have this benefit, since not all types are computed until the end, which means that you likely cannot follow cross references all the way (which requires scoping, which requires the type system).

In our experience, the back and forth between scoping and type system is often times required to fully model the capabilities of the type system. I expect both approaches to be equally as powerful, but the on-the-fly approach is likely more ergonomic, meaning it requires less code/complexity.