RascalTutor
Synopsis

TypePal is a framework for name analysis, type checking and type inference

Description

Many type checkers have already been written in Rascal with good results. However, type checkers for different languages have a lot in common and address similar questions:

  • How to handle declarations of names, in particular their scope and uses?

  • How to distinguish the roles names can play, e.g., names of functions, data types, labels, constants or variables?

  • How to handle imports and multiple name spaces?

  • How to associate requirements/constraints relevant for type checking with the syntax definition of the language being type checked?

  • How to represent the types that occur in a program?

  • How to handle global or local type inference?

  • How to give precise error messages (and avoid spurious messages)?

  • How to extract information that is useful for later compiler stages or the IDE for, e.g., code generation, use-def information or name completion?

TypePal is a declarative framework that operates on a model of the analysed program consisting of

  • facts about source code fragments with known type (e.g., an integer literal is of type integer);

  • requirements that are imposed on a source code fragment by the type system being used; a requirement may need the types of one or more other source code fragments, e.g., if the expression on the right-hand side of an assignment has type integer, then the type of the variable on the left-hand side should be compatible with the type integer;

  • calculators that compute the type of a source code fragment; this computation may also need the types of one or more other source code fragments, e.g., compute the type of the addition operator based on the types of its operands.

We will call this model the TModel (for "Type Model") of the program: facts describe elementary observations, requirements impose restrictions on the types of program fragments, and calculators compute new types. A requirement or calculator may detect a type violation and will then generate an error message. When a requirement is satisfied or a calculator computes a new type, this leads to the creation of new facts that may trigger the computation of other requirements and calculators.

Technically, TypePal uses scope graphs for expressing definition and use of names (including their role, scope, name space, and visibility), and constraints to describe facts, requirements and calculators. These constraints are such that they can express either type checking or type inference, or a mixture thereof. Under the hood, these constraints are solved in an efficient, data-driven, fashion.

The TypePal framework is highly parameterized and can be adapted to specific type checking needs.

1. Concepts and Definitions

Synopsis

The concepts and definitions used in TypePal.

1.1. Identifier

The syntax of a source language may impose various restrictions on the identifiers that can occur in a program. They amount to including or excluding specific characters for various occurrences of names in the program. One example is the requirement in Java that class names start with an upper case letter. TypePal is agnostic of such conventions and represents each name as a string. Qualified names are also supported and are represented by a list of strings.

1.2. Tree

The Rascal data type Tree (REF) is used to represent all parse trees that can be generated for any syntax described in Rascal. Tree is also a super type of any syntactic construct that may occur in a parse tree. In TypePal we interchangeably use Tree and the source area (a source location) from it has been derived to uniquely identify program parts, definitions, uses and scopes.

1.3. Scope

A scope is a region of a program that delimits where the definition of an identifier is applicable. An identifier is defined in the scope where it is defined and in all nested subscopes, unless one of these subscopes redefines that same identifier. In that case, the inner definition applies inside that nested scope (and its subscopes). Scopes are represented by the subtree of the parse tree that corresponds to their textual extent. Examples of scopes are a module or function scope.

1.4. Scope Graph

The scope graph is one of the the oldest method to describe the scope of names in a program. We use a version of scope graphs as described by Kastens & Waite, Name analysis for modern languages: a general solution, SP&E, 2017. This model uses text ranges in the source text (happily represented by Rascal’s loc data type) to identify and define all aspects of names. A scope graph provides lookup operations on names that takes both syntactic nesting and semantic linking (via paths) into account, as well as the specific roles of identifiers and paths (described below).

1.5. Path

TypePal is based on scope graphs that are not only based on syntactic containment of scopes but can also express semantic connections between parse trees. While scopes are strictly determined by the hierarchical structure of a program (= parse tree), paths provide an escape from this restriction and define a semantic connection between syntactic entities that are not hierarchically related and may even be part of different syntax trees. Connections between syntactic entities are labelled path, with user-defined labels. An example is the import of a module M into another module N that makes the entities in M known inside N. Here is an example of a path label to mark an import path between two parse trees.

data PathLabel
    = importsLabel()
    ;

Paths are, amongst others, used in the resolution of qualified names.

1.6. Name Resolution

Name resolution is based on the principle: syntactic resolution first, semantic resolution second. This means that we first search for a definition in the current parse tree and only when that fails we follow semantic path to other trees (either in the current tree or in other trees):

  • First the current scope in which the name is used is searched for a definition.

  • If this fails surrounding scopes are searched.

  • If this fails semantic paths in the same parse tree or to other parse trees are searched, such as, for instance, provided by an import statement.

This is illustrated below, where a name occurrence O can be resolved to definitions D1 (syntactic resolution), D2 (semantic resolution) and/or D3 (semantic resolution).

400
Name resolution need not have a unique solution. Therefore the author can extend TypePal by writing functions to (a) filter valid solutions; (b) determine which identifiers may be overloaded.

1.7. Role

Identifiers, scopes and path can play different roles that determine how they will be handled.

1.7.1. Identifier Role

Identifier roles are modelled by the data type IdRole that has to be extended by the author of the typechecker. Here is an example where roles are introduced for constants, variables, formal parameters and functions:

data IdRole
    = constantId()
    | variableId()
    | formalId()
    | functionId()
    ;

When defining an identifier, the specific role of that identifier has to be given, e.g. as constantId(). When using an identifier, the set of acceptables roles has to be given. For instance, an identifier used in an expression may accept the roles { constantId(), variableId(), formalId() }.

1.7.2. Scope Role

Scope roles are modelled by the data type ScopeRole and are used to distinguish different kinds of scopes. Later (REF) we will see that this can be used, for instance, to search for the innermost scope with a specific role, say the innermost function scope. Here is an example that introduces scopes for functions and loops:

data ScopeRole
    = functionScope()
    | loopScope()
    ;

1.7.3. Path Role

Path roles are modelled by the data type PathRole:

data PathRole
    = importPath()
    | extendPath()
    ;

1.8. Types

The type to be associated with names varies widely for different programming languages and has to be provided by the typechecker author. TypePal provides the data type AType that has to be extended for the language to be defined:

data AType
   = tvar(loc name)                                (1)
   | atypeList(list[AType] atypes)                 (2)
   | overloadedAType(rel[Key, AType] overloads)    (3)
   | lazyLub(list[AType] atypes)                   (4)
   ;
1 tvar represents a type variable (used for type inference) and is only used internally.
2 atypeList represents a list of `AType`s and is used both internally in TypePal but can also be used in typechecker definitions.
3 overloadedAType represents overloaded types.
4 lazyLub represents a lazily computed LUB of a list of types.

The typechecker author has to provide a function to convert `AType`s to string (it is used create readable error messages):

str prettyPrintAType(AType atype);

1.9. DefInfo

When defining a name, we usually want to associate information with it such as the type of the defined name. TypePal provides the data type DefInfo for this purpose:

data DefInfo
    = noDefInfo()                                       (1)
    | defInfo(AType atype)                              (2)
    | defInfo(list[Tree] dependsOn, AType() getAType)   (3)
    ;
1 No information associated with definition.
2 Explicitly given AType associated with definition.
3 Type of definition depends on the type of the entities given in dependsOn, when those are known, getAType can construct the type of this definition. getAType will only be called by TypePal during constraint solving.

2. Architecture of TypePal

Synopsis

Architectural overview of TypePal

Description

Type checking using TypePal proceeds in the following stages:

  • Parse the program to be analyzed using its syntax definition, the result is a a parse tree;

  • Collect constraints (facts, requirements and calculators) from the parsed program and build an initial TModel using these collected constraints; this also involves resolving the semantic links between program parts as introduced by, e.g., import statements;

  • Solve the constraints, the result is a validated and further enriched TModel.

This approach is very flexible, since each of the stages can be called separately, enabeling a pipeline with user-defined model transformations inbetween.

800

This whole process starts with a syntax for the language we want to analyze (let’s call that language L for now). The L syntax is used to parse the L program we want to type check. The result is a parse tree.

Collecting constraints from the resulting parse tree is based on the builder pattern: first a new Collector is created (using newCollector) and that enables the author of the type checker to add facts, requirements and calculators to the TModel depending on the specific input program. The Collector calls user-defined collect functions for each language construct. This collection process is strictly local and based on the nested structure of the parse tree and the result is an initial TModel.

In order to add non-local information that crosscuts the tree structure (e.g., an import statement that uses another module), non-local, semantic paths are also resolved at the end of the collection phase.

After the Collector phase, a TModel is available whose constraints can be solved (or not). This is done by creating a new Solver (using newSolver) and running it on the given TModel.

TypePal can configured using a TypePal Configuration.

3. Reporting

Synopsis

How to format and report errors, warnings and info messages.

4. Collector

Synopsis

A Collector collects constraints from source code and produces an initial TModel.

Description

A Collector is a statefull object that provides all the functions described below to access and change its internal state. The global services provided by a Collector are:

  • Register facts, requirements and calculators as collected from the source program.

  • Maintain a global (key,value) store to store global information relevant for the collection process. Typical examples are:

    • Configuration information.

    • The files that have been imported.

  • Maintain scopes. Typically, scopes of functions and blocks.

  • Maintain a single value per scope. This enables decoupling the collection of information from separate but related language constructs. Typical examples are:

    • While collecting information from a function declaration: associate the required return type with a new function scope so that return statements in the function body can check that (a) they occur inside a function; (b) that the type of their returned value is compatible with the required return type.

    • While collecting information from an optionally labelled loop statement: associate the label with a new loop scope so that break/continue statements can check that: (a) they occur inside a loop statement; (b) which loop statement they should (dis)continue.

  • Reporting.

The functions provided by a Collector are summarized below:

800

Technically, Collector is a datatype with a single constructur and with a number of functions as fields, For instance, given a Collector named c, calling the define function amounts to: c.define(the-arguments-of-define). All Collector functions are prefixed with /* Collector field */ to emphasize that they are a field of the Collector datatype.

Two dozen functions are available that fall into the following categories:

  • Create: create Collector, collect information from source program, and build initial TModel.

  • Define & Use: define and use identifiers in various ways.

  • Calculate. Require & Facts: define requirements and calculators and establish facts.

  • Inference: create new type variables for type inference.

  • Scoping: enter and leave a scope, ask for current scope.

  • Scope Info: add information to the current scope or retrieve that information.

  • Global Info: add global information or retrieve that information; this is available during collection and solving.

  • Nested Info: maintain nested information during collection; this is only available during collection.

  • Reporting: report errors, warnings and info messages.

  • Composition: add another TModel to the current one.

The builder functions are applied repeatedly until all information has been collected from the source program.

Finally, run creates the desired TModel that will be used by the Solver.

4.1. Create

A Collector is created using the function newCollector. By way of run it is converted into a TModel.

Collector newCollector(Tree pt, TypePalConfig config = tconfig(), bool debug = true);
/* Collector field */ TModel () run;

Given a parse tree pt of the program to be checked, a typical scenario is:

c = newCollector();
collect(pt, c);
model = c.run();
... continue with Solver ...
The collect function has to be supplied by the author of the type checker and looks like this:
void collect(LanguageConstruct lc, Collector c){ ... }

where:

  • lc is a syntactic type from the language under consideration.

  • c is a Collector.

Each collect function is responsible for visiting its subtrees.

4.2. Define & Use

4.2.1. Define a name

The function define is used to add in the current scope the definition of a name to the TModel:

/* Collector field */  void (str id, IdRole idRole, Tree def, DefInfo info) define;

where:

  • id is the textual appearance of the name.

  • idRole is the role played by the name.

  • def is the part of the parse tree that corresponds to the definition of the name.

  • info is information to be associated with this definition.

4.2.2. Use an unqualified name

There are four functions to describe the occurrence of a name in a parse tree as a use. The most elementary use of a name is described by:

/* Collector field */ void (Tree occ, set[IdRole] idRoles) use,

The parse tree occ is a use to be resolved in the current scope in one of the given roles idRoles. The use of a variable in an expression is typically modelled with this use function.

4.2.3. Use an unqualified name via a path

The next version of use, represents a use that refers to another tree using a specific path label:

/* Collector field */ void (Tree occ, set[IdRole] idRoles, PathRole pathRole) useViaPath;

4.2.4. Use a qualified name

Next we consider the use of qualified names, i.e., a list of identifiers that will be resolved from left to right. We will call these identifiers (except the last one) qualifiers and the last one the qualified identifier.

/* Collector field */ void (list[str] ids, Tree occ, set[IdRole] idRoles, set[IdRole] qualifierRoles) useQualified;

Here ids is the qualified name, occ is the actual occurrence, and there are two sets of roles: idRoles are the possible roles for the qualified identifier iself and `qualifierRolesa are the possible roles for the qualifiers.

4.2.5. Use a qualified name via a path

/* Collector field */ void (list[str] ids, Tree occ, set[IdRole] idRoles, set[IdRole] qualifierRoles, PathRole pathRole) useQualifiedViaPath;

4.2.6. Use a name via another type

/* Collector field */ void (Tree container, Tree selector, set[IdRole] idRolesSel) useViaType

4.3. Require, Calculate & Facts

4.3.1. Define a fact

A fact is known type information for a program fragment and is defined using:

/* Collector field */ void (Tree target, value src) fact;

src can be either an AType or Tree. In the latter case its type is retrieved using getType.

4.3.2. Define a requirement

A requirement is a predicate regarding the type or properties of a source tree fragment src. A requirement has a name (for reporting purposes) and a list of dependencies whose types have to be known before this requirement can be computed.

/* Collector field */ void (str name, Tree src, list[value] dependencies, void() preds) require;
/* Collector field */ void (str name, Tree src, list[value] dependencies, void() preds) requireEager;

More specific requiremens can be expressed for checking that two subtrees or types are equal or comparable, can ne unified, or that the one is a subtype of the other:

/* Collector field */ void (value l, value r, FailMessage fmsg) requireEqual;
/* Collector field */ void (value l, value r, FailMessage fmsg) requireComparable;
/* Collector field */ void (value l, value r, FailMessage fmsg) requireSubtype;
/* Collector field */ void (value l, value r, FailMessage fmsg) requireUnify;

The arguments l and r should either be an AType or a subtree whose type can be determined using getType.

4.3.3. Define a calculator

A calculator computes the type of a subtree src by way of an AType-returning function calculator. A list of dependenciesis given whose types have to be known before this calculator can be computed.

/* Collector field */ void (str name, Tree src, list[value] dependencies, AType() calculator) calculate;
/* Collector field */ void (str name, Tree src, list[value] dependencies, AType() calculator) calculateEager;

4.4. Inference

/* Collector field */ AType (value src) newTypeVar;

4.5. Scoping

/* Collector field */ void (Tree inner) enterScope;
/* Collector field */ void (Tree inner) leaveScope;
/* Collector field */ loc () getScope,

4.6. Scope Info

/* Collector field */ void (Key scope, ScopeRole scopeRole, value info) setScopeInfo;
/* Collector field */ lrel[Key scope, value scopeInfo]  (ScopeRole scopeRole) getScopeInfo;

4.7. Global Info

/* Collector field */ void (str key, value val) store;
/* Collector field */ set[value] (str key) getStored;

4.8. Nested Info

/* Collector field */ void (str key, value val) push
/* Collector field */ value (str key) pop,
/* Collector field */ value (str key) top,
/* Collector field */ list[value] (str key) getStack,
/* Collector field */ void (str key) clearStack,

4.9. Composition

/* Collector field */ void (TModel tm) addTModel;

4.10. Reporting

/* Collector field */ void (FailMessage fmsg) report;
/* Collector field */ void (list[FailMessage] fmgs) reports;

See Reporting for a description of FailMessage.

5. Solver

Synopsis

A Solver tries to solve the constraints in a TModel; unsolved constraints produce error messages

Description

Recall that requirements and calculators use function parameters of the respective types void(Solver s) predicates and AType(Solver s) calculator. Although this are ordinary Rascal functions it is useful to summarize the TypePal-specific functions that can be used inside these functions:

800

In identical style as used for <Collector>>, Solver is a datatype with a single constructur and with a number of functions as fields, For instance, given a Solver named s, calling the getType function amounts to: s.getType(argument-of-getType). All Solver functions are prefixed with /* Solver field */ to emphasize that they are a field of the Solver datatype.

The result of the Solver is an enriched TModel that contains, amongst others, messages regarding violated requirements or types that could not be computed. It can also be used to generate other usefull information about the program such as a use-def relation and the used vocabulary (used for name completion).

5.1. Types

The workhorse of TypePal is the function getType that determines the type of given tree or source location. When that is known, it is returned as value. If it is not known, the internal exception TypeUnavailable() is thrown which will abort the execution of the current requirement or calculator which will be tried later again.

/* Solver field */ AType(value) getType
/* Solver field */ AType (str id, loc scope, set[IdRole] idRoles) getTypeInScope
/* Solver field */ AType (AType containerType, Tree selector, set[IdRole] idRolesSel, loc scope) getTypeInType
/* Solver field */ set[AType] (AType containerType, loc scope) getAllTypesInType

For convenience, onError is available both for Tree and loc arguments;

5.2. Require & Calculate

5.2.1. equal and requireEqual

The function equal determines whether t1 and t2 are equal, the result is a Boolean value. The function requireEqual just returns when the outcome is true, otherwise the FailMessage is generated.

/* Solver field */ bool (value, value) equal
/* Solver field */ void (value, value, FailMessage) requireEqual

5.2.2. subtype and requireSubtype

The function subtype determines whether t1 is a subtype of t2. Under the hood, the user-provided function getSubType is called, see [Typepal Configuration]. The function requireSubtype just returns when the outcome is true, otherwise the FailMessage is generated.

/* Solver field */ bool (value, value) subtype
/* Solver field */ void (value, value, FailMessage) requireSubtype

5.2.3. comparable and requireCompare

The function comparable determines whether t1 is comparable with t2. Under the hood, the user-provided function getSubType is called twice, see [Typepal Configuration]. The function requireComparable just returns when the outcome is true, otherwise the FailMessage is generated.

/* Solver field */ bool (value, value) comparable
/* Solver field */ void (value, value, FailMessage) requireComparable

5.2.4. unify and requireUnify

The function unify determines whether t1 can be unified with t2. Under the hood, the user-provided functions getSubType and getLub are used, see [Typepal Configuration]. The function `requireUnify just returns when the outcome is true, otherwise the FailMessage is generated. The bindings that may result from unification are effectutated when the enclosing calculate or require succeeds.

/* Solver field */ bool (value, value) unify
/* Solver field */ void (value, value, FailMessage) requireUnify

5.2.5. requireTrue and requireFalse

The function requireTrue returns when its condition is true, otherwise the FailMessage is generated. The function requireFalse returns when its condition is false, otherwise the FailMessage is generated.

/* Solver field */ void (bool, FailMessage) requireTrue
/* Solver field */ void (bool, FailMessage) requireFalse

5.2.6. lub

The function lub return the least upper bound of two types. Under the hood, the user-provided function getLub is called, see [Typepal Configuration].

/* Solver field */ AType lub(AType t1, AType t2);

5.3. Inference

5.3.1. instantiate

5.3.2. isFullyInstantiated

5.4. Reporting

/* Solver field */ bool(FailMessage fm) report
/* Solver field */ bool (list[FailMessage]) reports

5.5. Global Info

5.5.1. getConfig

5.5.2. getFacts

6. TypePal Configuration

Synopsis

Configuration options for TypePal

Description

TypePal provides configuration options for

  • Name Resolution & Overloading: configures how names are resolved and which overloading is allowed.

  • Operations on Types: configures how operations like subtype and least-upper-bound (lub) are defined.

  • Retrieval of Types: configures how named and structured types are handled.

  • Extension Points: configures operations before an after solving.

  • Miscellaneous: utility functions that can be configured.

Here is an overview:

800

The TypePal configuration can provide additional declarations for:

  • Name Resolution & Overloading:

    • isAcceptableSimple: accepts or rejects a proposed definition for the use of a simple name in a particular role. Typical concerns are:

      • enforce definition before use;

      • check access rights, e.g. visibility.

    • isAcceptableQualified: accepts or rejects a proposed definition for the use of a qualified name in a particular role.

    • isAcceptablePath: accepts or rejects an proposed access path between use and definition.

    • mayOverload: determines whether two names are allowed to be overloaded.

  • Operations on Types:

    • Functions to check subtype (isSubType) and least upperbound (getLub) of two types.

    • Functions that given the smallest (getMinAType) and largest (getMaxAType) element of the type lattice.

    • The function instantiateTypeParameters defines language-specific instantiation of type parameters.

  • Retrieval of Types:

  • Miscellaneous:

    • A function unescapeName to define language-specific escape rules for names.

  • Extension Points:

    • A function preSolver that can enrich or transform the TModel before the Solver is applied to it.

    • A function postSolver that can enrich or transform the TModel after constraint solving is complete.