TypePal is a framework for name analysis, type checking and type inference
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.
This is called 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 as we will see below.
1. Architecture of TypePal
Architectural overview of TypePal
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 facts, requirements and calculators from the parsed program.
-
Build an initial
TModelusing these collected facts, requirements and calculators. -
Resolve Path, resolves the semantic links between program parts (as introduced by, e.g., import statements), the result is an enriched
TModel; -
Validate the enriched
TModel, the result is a validated and further enrichedTModel.
This approach is very flexible, since each of the stages can be called separately, enabeling a pipeline with user-defined model transformations inbetween.
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 facts, requirements and calculators from the resulting parse tree is based on the builder pattern:
first a new TBuilder (an TModel builder) is created and that enables the author of the type checker
to add facts and requirements to the TModel depending on the specific input program.
Collection uses the parse tree, the TBuilder, and user-supplied declarations for the types in L
(user-defined extensions of TypePal’s built-in AType data type)
as well as rules for collecting facts, requirements and calculators (user-defined collect functions). 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), such non-local, semantic paths are resolved in a separate path resolution phase.
After path resolution, an TModel is available that can be validated.
The validation phase can be further specialized by providing additional declarations for:
-
When the language L uses subtyping:
-
Functions to check subtype (
myIsSubType) and least upperbound (myLUB) of two types. -
Functions that given the smallest (
myATypeMin) and largest (myATypeMax) element of the type lattice.
-
-
Functions to filter the results of name resolution:
-
myMayOverload: determines whether two names are allowed to be overloaded. -
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.
-
The result of validation 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).
2. Concepts and Definitions
The concepts and definitions used in TypePal.
2.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.
2.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 use Tree to uniquely
identify program parts, definitions, uses and scopes.
2.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.
2.4. 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.
2.5. 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).
2.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).
| 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. |
2.7. Role
Identifiers, scopes and path can play different roles that determine how they will be handled.
2.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() }.
2.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()
;
2.7.3. Path Role
Path roles are modelled by the data type PathRole:
data PathRole
= importPath()
| extendPath()
;
2.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 AType2String(AType atype);
2.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. |
3. Build a TModel
A TBuilder enables the incremental addition of facts, requirements and calculators to a TModel.
A TBuilder is a statefull functional object that provides all the functions described below
to access and change its internal state. The global services provided by a TBuilder 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 TBuilder and its lifecycle looks like this:
The TBuilder is represented as a data type with a single constructor
that has fields that correspond to the functions provided by the builder.
For instance, calling the define function on a TBuilder named tb amounts to: tb.define(the-arguments-of-define).
Two dozen functions are available that fall into the following categories:
-
Create, Collect & Build: create
TBuilder, collect information from source program, and build theTModel. -
Define & Use: define and use identifiers in various ways.
-
Facts, Requirements & Calculators: establish facts, define requirements and calculators.
-
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.
-
Reporting: report errors and warnings.
The builder functions are applied repeatedly until all information has been collected from the source program.
Finally, build creates the desired TModel that will be used for validation.
3.1. Create, Collect & Build
A TBuilder is created using the function newTBuilder. By way of build it is converted into a TModel.
TBuilder newTBuilder();
TModel build();
Given a parse tree pt of the program to be checked, a typical scenario is:
tb = newTBuilder();
collect(pt, tb);
model = tb.build();
... continue with validation ...
The collect function has to be supplied by the author of the type checker and looks like this:
|
void collect(LanguageConstruct lc, TBuilder tb){ ... }
where:
-
lcis a syntactic type from the language under consideration. -
tbis aTBuilder.
Each collect function is responsible for visiting its subtrees. This achieved by the following mandatory call
at the end of each collect function:
|
collectParts(lc, tb);
3.2. Define & Use
3.2.1. Define a name
The function define is used to add in the current scope the definition of a name to the TModel:
void define(str id, IdRole idRole, Tree def, DefInfo info);
where:
-
idis the textual appearance of the name. -
idRoleis the role played by the name. -
defis the part of the parse tree that corresponds to the definition of the name. -
infois information to be associated with this definition.
3.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:
void use(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.
3.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:
void useViaPath(Tree occ, set[IdRole] idRoles, PathRole pathRole);
3.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.
void useQualified(list[str] ids, Tree occ, set[IdRole] idRoles, set[IdRole] qualifierRoles);
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.
3.2.5. Use a qualified name via a path
void useQualifiedViaPath(list[str] ids, Tree occ, set[IdRole] idRoles, set[IdRole] qualifierRoles, PathRole pathRole);
3.3. Facts, Requirements & Calculators
3.3.1. Define a fact
A fact is known type information for a program fragment and is defined using:
void fact(Tree src, AType tp);
3.3.2. Define a requirement
void require(str name, Tree src, list[value] dependencies, void() preds) require;
void requireEager(str name, Tree src, list[value] dependencies, void() preds);
3.3.3. Define a calculator
void calculate(str name, Tree src, list[value] dependencies, AType() calculator);
void calculateEager(str name, Tree src, list[value] dependencies, AType() calculator);
3.4. Inference
AType newTypeVar();
3.5. Scoping
void enterScope(Tree inner);
void leaveScope(Tree inner);
loc () getScope,
3.6. Scope Info
void setScopeInfo(Key scope, ScopeRole scopeRole, value info);
lrel[Key scope, value scopeInfo] getScopeInfo(ScopeRole scopeRole);
3.7. Global Info
void store(str key, value val);
set[value] getStored(str key);
3.8. Error reporting
void reportError(Tree src, str msg);
void reportWarning(Tree src, str msg);
void reportInfo(Tree src, str msg);
4. Validate a TModel
The functions available during validation
Recall that requirements and calculators use function parameters of the respective types void() predicates and
AType() calculator. Although this are ordinary Rascal functions it is useful to summarize the TypePal-specific
functions that can be used inside these functions:
4.1. getType
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.
AType getType(Tree tree);
AType getType(loc src);
AType getType(str id, Key scope, set[IdRole] idRoles);
4.2. getDefinitions
In order to get the definition information associated with a name in a given role and scope, getDefinitions returns
a set of `Define`s (since multiple definitions may apply).
Define is defined as:
alias Define = tuple[Key scope, str id, IdRole idRole, Key defined, DefInfo defInfo];
and getDefinitions is defined as:
set[Define] getDefinitions(str id, Key scope, set[IdRole] idRoles){
4.3. onError
Several of the available functions express their failure by way of an ErrorHandler defined as:
data ErrorHandler
= onError(loc where, str msg)
| noError()
;
ErrorHandler onError(Tree t, str msg);
For convenience, onError is available both for Tree and loc arguments;
4.4. subtype
The function subtype determines whether t1 is a subtype of t2.
Under the hood, the user-provided function myIsSubType is called.
When the outcome is true, subtype just returns, otherwise the error handler is invoked.
void subtype(AType t1, AType t2, ErrorHandler handler);
4.5. lub
The function lub return the least upper bound of two types.
Under the hood, the user-provided function myLUB is called.
AType lub(AType t1, AType t2);
4.6. unify
The function unify tries to unify two types.
When successful, this may lead to the binding of type variables occurring in these types.
When unsuccessful, the error handler is called.
void unify(AType t1, AType t2, ErrorHandler handler);