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 handle overloading?
-
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 Rascal framework that addresses the above questions and we describe here all its concepts, architecture and features and also show some examples:
-
Overview: An overview of TypePal.
-
A Calculator Language: Calc illustraties the basic facilities of TypePal.
-
Concepts and Definitions: The concepts and definitions used in TypePal.
-
Architecture of TypePal: Architectural overview of TypePal.
-
Reporting: How to format and report errors, warnings and info messages.
-
Collector: A
Collectorcollects constraints from source code and produces an initialTModel. -
Solver: A
Solvertries to solve the constraints in aTModel; unsolved constraints produce error messages. -
TypePal Configuration: Configuration options for TypePal.
-
Utilities: Some utility functions.
-
Examples of Typecheckers: Examples of type checkers built with TypePal.
1. Overview
An overview of TypePal
TypePal is a declarative framework that operates on a model of the program to be type checked that consisting of
-
facts that some source code fragment has a known type, e.g., an integer literal is of type integer, or that its type is equal to the type of another source code fragment, e.g., the type of the expression in parentheses
( e )is equal to the type ofe. -
calculators that compute the type of a source code fragment and create new facts; this computation may also need the types of one or more other source code fragments, e.g., computing the type of the addition operator is based on the types of its operands.
-
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.
We call this model the TModel (for "Type Model") of the program: facts describe elementary observations and equalities between types, calculators compute new type facts, and requirements impose restrictions on the types of program fragments. 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.
TypePal is highly parameterized and can be adapted to specific type checking needs.
2. A Calculator Language
Calc illustraties the basic facilities of TypePal
By developing a type checker for Calc, a tiny pocket calculator language, we illustrate elementary usage of TypePal. The full source code of Calc can be found at https://github.com/cwi-swat/typepal/tree/master/src/examples/calc. See Examples of Typecheckers for a list of all available type checker examples.
2.1. Syntax of Calc
module lang::calc::Syntax
extend lang::CommonLex; (1)
start syntax Calc
= Decl+ (2)
;
syntax Decl
= "var" Id "=" Exp ";" (3)
;
syntax Exp
= Id (4)
| Integer (5)
| Boolean (6)
| bracket "(" Exp ")" (7)
> left Exp "*" Exp (8)
> left Exp "+" Exp (9)
> "if" Exp "then" Exp "else" Exp (10)
;
keyword Reserved
= "var" | "if" | "then" | "else"
;
| 1 | For brevity we use some common lexical definitions in lang::CommonLex. They take, amongst others, care of whitespace, comments and
definitions for integer and Boolean constants (Integer and Boolean) as well as identifiers (Id). |
| 2 | A Calc program consists of one or more declarations (Decl). |
| 3 | Each declaration introduces a new variable and binds it to the value of an expression. |
| 4 | An expression can be an identifier (that should have been introduced in a preceding declaration), or |
| 5 | an integer constant, or |
| 6 | a Boolean constant, or |
| 7 | be surrounded by parentheses, or |
| 8 | a multiplication (arguments should have the same type), or |
| 9 | an addition (arguments should have the same type), or |
| 10 | a conditional expression (the first expression should have type Boolean, the other two should have the same type). |
2.2. Typechecking Calc
Type checking Calc amounts to checking the following:
-
Every name that is used in an expression should have been defined in a declaration and has the type of the expression in that declaration.
-
Addition or multiplication on integers yields an integer type.
-
Addition or multiplication on Booleans yields a Boolean type.
-
The condition in a condional expression should be Boolean.
-
The then and else part of a conditional expression should have the same type; that type becomes the type of the conditional expression.
Let’s now move to the Calc type checker described in lang::calc::Checker. We break it up in parts
and describe the parts as we go. You should be explicitly aware of the fact that type checking consists of two phases:
-
Collecting facts and constraints: this is all about formulating constraints and attaching them to parts of the source program. In this phase types are unknown and constraints can only be created but not yet solved. All computations on types have therefore to be postponed until the solving phase. We will see how in a minute.
-
Solving constraints: constraints are solved (if possible) and types are assigned to parts of the source program.
2.2.1. Begin of type checker module for Calc
module lang::calc::Checker
import lang::calc::Syntax; // The Calc syntax
extend analysis::typepal::TypePal; // TypePal
We import the Calc syntax lang::calc::Syntax and then we extend the TypePal analysis::typepal::TypePal.
There is a technical reason why we have to extend TypePal rather than import it. Some data types (e.g., AType)
and functions (e.g., collect) are already defined in TypePal itself and they are being extended in each type checker.
|
2.2.2. Extend AType
TypePal has a built-in data type to represent types: AType. This data type can be extended to represent language-specific types.
data AType
= boolType()
| intType()
;
str prettyAType(boolType()) = "bool";
str prettyAType(intType()) = "int";
The values in Calc are Booleans and integers and we create two AType constants boolType() and intType() to represent these types.
prettyAType converts them back to a string representation; this is used in error reporting.
2.2.3. Collecting facts and constraints
Writing a type checker in TypePal amounts to collecting facts and constaints from a source program to be checked.
This is achieved by the collect function that has the form
void collect(current: syntactic pattern, Collector c){ ... }`
where syntactic pattern corresponds with a rule from the language syntax, in this case lang::calc::Syntax.
The Collector argument provides methods to add facts and constraints.
One collect declaration is needed per alternative in the syntax but some rules (i.e., chain rules) are handled automatically.
|
By convention the syntactic pattern is named current and the Collector is named c.
|
Each collect declaration is responsible for calling collect on relevant subparts (a run-time error is given for a missing collect).
|
Check Declaration
A declaration introduces a new name and associates the type of the righthand side expression with it.
void collect(current: (Decl) `var <Id name> = <Exp exp> ;`, Collector c){
c.define("<name>", variableId(), current, defType(exp));
collect(exp, c);
}
Here we define name as a variable and define its type as the same type as exp. Let’s digest this:
-
c.define(…)calls thedefinefunction in theCollectorand adds this definition to the internal state of the Collector. -
nameis a parse tree for the lexical syntax ruleId."<name>"reduces this tree to a string and this is how the variable can be used later on. -
variableId()defines that the role of this name (IdRole) is a variable.variableIdis a built-in roleIdRole. -
currentis the parse tree of the whole declaration, we use it as unique identification of the definition ofname. -
defTypeis used to define the type ofnameand it comes in several flavours. Here, we use another parse tree fragmentexpas argument.defType(exp)should be read as the same type asexpand the effect is thatnameis defined having the same type asexp. This implies that the type ofnamecan only be known when the type ofexpis known.
Check Exp: Id
An expression consisting of a single identifier, refers to a name introduced in another declaration and gets the type introduced in that declaration.
void collect(current: (Exp) `<Id name>`, Collector c){
c.use(name, {variableId()});
}
An expression consisting of a single identifier represents a use of that identifier.
c.use(name, roles) records this. There are then two possibilities:
-
a matching define is found for one of the given roles: use and definition are connected to each other.
-
no matching define is found and an error is reported.
| In larger languages names may be defined in different scopes. Scopes do not play a role in Cal. |
| We do not enforce define-before-use in this example, but see [XXX] how to achieve this. |
Check Exp: Boolean and Integer constants
void collect(current: (Exp) `<Boolean boolean>`, Collector c){
c.fact(current, boolType());
}
void collect(current: (Exp) `<Integer integer>`, Collector c){
c.fact(current, intType());
}
When encountering a Boolean or integer constant we record their type using c.fact(current, its type).
The second argument of fact maybe an AType, an arbitrary parse tree (in which case the type of that tree will be used),
or a function that returns a type.
|
Check Exp: parentheses
void collect(current: (Exp) `( <Exp e> )`, Collector c){
c.fact(current, e);
collect(e, c);
}
The type of an expression enclosed by parentheses is the same as the same of the enclosed expression.
A final, essential, step is to collect constraints from the subpart e.
Check Exp: addition
Addition of integers given an integer result and addition of Booleans gives a Boolean result.
void collect(current: (Exp) `<Exp e1> + <Exp e2>`, Collector c){
c.calculate("addition", current, [e1, e2],
AType (Solver s) {
switch(<s.getType(e1), s.getType(e2)>){
case <intType(), intType()>: return intType();
case <boolType(), boolType()>: return boolType();
default:
s.report(error(current, "`+` not defined for %t and %t", e1, e2));
}
});
collect(e1, e2, c);
}
Checking addition is more complex since we need the type of sub expressions e1 and e2 in order to do our job.
The type of an arbitrary parse tree can be computed using
c.calculate(informative label, current, list of dependencies, AType(Solver s) { … }.
where
-
informative label is a label that can be used in error messages and log files.
-
currentis the parse tree for which we are computing a type. -
list of dependencies is a list of other parse trees whose type is needed in the computation of the type of
current. -
AType(Solver s) { … }performs the type computation:-
it is only called when the types of all dependencies are known.
-
it has a
Solveras argument: aSolvermanages the constraint solving process and is aware of all facts and solved constraints so far and knows, for instance, about the existence of type information for some parse tree. -
it either returns an
ATypeor reports an error.
-
The above code could be paraphrased as follows:
The type of current can only be computed when the types of e1 and e2 are known. When known,
get their types (using s.getType) and distinguish cases: two integer arguments give an integer result type and two Boolean arguments a Boolean result type;
otherwise report an error.
A final, essential, step is to collect constraints from the subparts e1 and e2.
Check Exp: multiplication
void collect(current: (Exp) `<Exp e1> * <Exp e2>`, Collector c){
c.calculate("multiplication", current, [e1, e2],
AType (Solver s) {
switch(<s.getType(e1), s.getType(e2)>){
case <intType(), intType()>: return intType();
case <boolType(), boolType()>: return boolType();
default:
s.report(error(current, "`*` not defined for %t and %t", e1, e2));
}
});
collect(e1, e2, c);
}
Checking multiplication follows exactly the same pattern as checking addition. Even in this simple example we see repetition of code that could be factored out.
Check Exp: conditional expression
void collect(current: (Exp) `if <Exp cond> then <Exp e1> else <Exp e2>`, Collector c){
c.calculate("if Exp", current, [cond, e1, e2],
AType(Solver s){
s.requireEqual(cond, boolType(),
error(cond, "Condition should be Boolean, found %t", cond));
s.requireEqual(e1, e2,
error(current, "Equal types required, found %t and %t", e1, e2));
return s.getType(e1);
});
collect(cond, e1, e2, c);
}
Checking a conditional expression amounts to checking that the condition has type Boolean and
that the then and else branch have the same type (which also becomes the type of the conditional expression as a whole).
In the above code we see s.requireEqual(arg1, arg2, message).
Here arg1 and arg2 may either be a subtree (in which case its type is used) or an AType.
requireEqual requires that both types are equal or reports an error.
A final, essential, step is to collect constraints from the subparts cond, e1 and e2.
2.3. Testing the Calc typechecker
2.3.1. Getting started
module lang::calc::Test
extend lang::calc::Checker;
extend analysis::typepal::TestFramework; // TypePal test utilities
import ParseTree; // In order to parse tests
We need three ingredients for testing:
-
lang::calc::Checker, the Calc type checker we have just completed. -
analysis::typepal::TestFramework, the TypePal test framework which enables test automation. -
ParseTreethat provides parsing functionality that is needed to parse Calc source text.
2.3.2. Manual testing
TModel calcTModelFromTree(Tree pt){
return collectAndSolve(pt);
}
Given a parse tree pt for a Calc program, we apply collectAndSolve to it. This creates a Collector, uses it to collect constraints from pt and then creates a Solver
to solve all constraints. The result is a TModel. calcTModelFromTree will also be used during automated testing.
TModel calcTModelFromStr(str text){
pt = parse(#start[Calc], text).top;
return calcTModelFromTree(pt);
}
In order to obtain a parse tree, we need to parse it as shown above.
TModels contain much information but here we are only interested in the messages that have been generated during constraint solving.
They are contained in the messsages field of a TModel.
With the above machinery in place we can perform some experiments:
-
calcTModelFromStr("var x = 3;"),messagesgives no messages. -
calcTModelFromStr("var x = 3+true;").messsagesreports that addition of integer and Boolean is illegal.
2.3.3. Automated testing
bool calcTests() {
return runTests([|project://typepal-examples/src/lang/calc/tests.ttl|],
#Calc, calcTModelFromTree);
}
TypePal’s testing framework enables scripting of tests. Each script is written in TTL (TypePal Testing Language).
Use runtests(list of TTL files, start non-terminal, function to create a TModel) to execute the scripts.
Here is a sample script:
test Ok1 [[ var x = 1; ]]
test Ok2 [[ var x = 1; var y = x + 2; ]]
test Undef1 [[ var x = y; ]]
expect { "Undefined variable `y`" }
test Add1 [[ var x = 1 + 2; ]]
test Add2 [[ var x = true + false; ]]
test Add3 [[ var x = 1 + true; ]]
expect { "`+` not defined for `int` and `bool`" }
test If1 [[ var x = if true then 1 else 2;
var y = x + 1;]]
test If2 [[ var x = if true then 1 else false; ]]
expect { "Equal types required, found `int` and `bool`" }
test If3 [[ var x = if 1 then 2 else 3; ]]
expect { "Condition should be Boolean, found `int`" }
and here is the produced output:
Test Ok1: true
Test Ok2: true
Test Undef1: true
Test Add1: true
Test Add2: true
Test Add3: true
Test If1: true
Test If2: true
Test If3: true
Test summary: 9 tests executed, 9 succeeded, 0 failed
3. Concepts and Definitions
The concepts and definitions used in TypePal.
3.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.
3.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) associated with it to uniquely
identify program parts, definitions, uses and scopes.
3.3. Scope
A scope is a region of a program that delimits where definitions of identifier are 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 identified by the subtree of the parse tree that introduces them such as, for instance, a module, a function declaration or a block. Special rules may apply such as define-before-use or scopes-with-holes.
3.4. Scope Graph
The scope graph is one of the the oldest methods 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 take both syntactic nesting and semantic linking (via paths) into account,
as well as the specific roles of identifiers and paths (described below).
3.5. Identifier definition
The definition of an identifier is inside TypePal characterized by a Define:
alias Define = tuple[loc scope, str id, IdRole idRole, loc defined, DefInfo defInfo];
where
-
scopeis the scope in which the definition occurs; -
idis the text representation of the identifier; -
idRoleis the role in which the identifier is defined, see Identifier Role; -
definedis source code area of the definition; -
defInfois any additional information associated with this definition, see DefInfo,
3.6. Identifier Use
The use of an identifier is characterized by a Use:
data Use
= use(str id, loc occ, loc scope, set[IdRole] idRoles)
| useq(list[str] ids, loc occ, loc scope, set[IdRole] idRoles, set[IdRole] qualifierRoles)
;
where use represents the use of a simple name and useq that of a qualified name.
In the latter case, a list of strings is given; the last string is a simple name in given idRoles and the preceeding strings are its qualifiers in qualifierRoles.
3.7. 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 (i.e., its 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 paths labelled with user-defined roles.
Paths are represented by the Rascal datatype PathRole.
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 role to mark an import path between two parse trees.
data PathRole
= importPath()
;
Paths are, amongst others, used in the resolution of qualified names.
3.8. 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 of a TypePal-based type checker can provide functions to (a) filter valid solutions; (b) determine which identifiers may be overloaded. |
3.9. Role
Identifiers, scopes and path can play different roles that determine how they will be handled. They are represented by various Rascal datatypes that can be extended by the author of a typechecker.
3.9.1. Identifier Role
Identifier roles are modelled by the data type IdRole.
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() }.
3.9.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()
;
3.9.3. Path Role
Path roles are modelled by the data type PathRole:
data PathRole
= importPath()
| extendPath()
;
3.10. 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 provides already some built-in constructors:
data AType
= tvar(loc tname) (1)
| atypeList(list[AType] atypes) (2)
| overloadedAType(rel[loc, IdRole, 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. |
AType that has to be extended with language-specific types.
The typechecker author also has to provide a function to convert AType to string (it is used create readable error messages):
str prettyAType(AType atype);
3.11. 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)
| defType(value contrib) (2)
| defTypeCall(list[loc] dependsOn, AType(Solver s) getAType) (3)
| defTypeLub(list[loc] dependsOn, list[loc] defines, list[AType(Solver s)] getATypes) (4)
;
| 1 | No information associated with this definition. |
| 2 | Explicitly given AType contribution associated with this definition. contrib can either be an AType, or a Tree.
In the latter case, the type of that tree is used (when it becomes available) for the current definition. |
| 3 | Type of this 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. |
| 4 | Refine a set of definitions by taking their LUB, mostly used for local type inference. |
The Solver argument of getAType and getATypes is the current constraint solver being used.
| noDefInfo may be removed. |
4. 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 parse tree;
-
Collect constraints (facts, calculators, and requirements) from the parsed program and build an initial
TModelusing these collected constraints; -
Solve the constraints, the result is a validated and further enriched
TModel. This amounts to executing calculators and requirements when the types on which they depend become available. This also involves resolving the semantic links between program parts as introduced by, e.g., import statements.
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 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.
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 be configured using a TypePal Configuration.
5. Reporting
How to format and report errors, warnings and info messages.
Reporting may be done both in the Collector and the Solver.
It uses values of the datatype FailMessage that can be created as follows:
FailMessage error(value src, str msg, value args...);
FailMessage warning(value src, str msg, value args...);
FailMessage info(value src, str msg, value args...);
Here,
-
srcis aTreeorlocthat is the subject of the report. -
msgis an informative string to be printed. It may contain insertion directives. -
argsare zero or more values to be inserted in the insertion directives inmsg.
The following insertion directives are supported:
-
%t: insert the type of the next element ofargs. -
%v: insert the value of the next element ofargs. -
%q: quote and insert the type or value of the next element ofargs. -
%%: insert the character%.
6. Collector
A Collector collects constraints from source code and produces an initial TModel.
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, calculators, and requirements 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.
-
-
Manage scopes.
-
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: create a new function scope and associate the required return type with it 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: create a new loop scope and associate the label with it 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:
Three dozen functions are available that fall into the following categories:
-
Lifecycle of Collector: create a new
Collector, use it tocollectinformation from a source program, and produce a TModel. -
Configuration: retrieve or modify configuration settings.
-
Scoping: enter or leave a scope, ask for current scope.
-
Scope Info: add information to the current scope or retrieve that information.
-
Nested Info: maintain nested information during collection; this is only available during collection.
-
Composition: add another TModel to the current one.
-
Reporting: report errors, warnings and info messages.
-
Add Path: add paths to the scope graph.
-
Define: define identifiers in various ways.
-
Use: use identifiers in various ways.
-
Inference: create new type variables for type inference.
-
Facts: establish facts.
-
Calculate: define calculators.
-
Require: define requirements.
Technically, Collector is a datatype with a single constructur and 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.
6.1. LifeCycle of Collector
A new Collector is created using the function newCollector.
Collector newCollector(str modelName, Tree pt, TypePalConfig config = tconfig());
where
-
modelNameis the name of the TModel to be created (used for logging); -
ptis the parse tree of the source program to be type checked; -
configis a TypePal Configuration.
Once a Collector has been created, the user-defined collect function is invoked
with the current parse tree of a source program and the Collector as arguments.
The collect function is applied recursively until all
information has been collected from the source program.
Finally, run creates the desired TModel that will be used by the Solver:
/* Collector field */ TModel () run;
A typical scenario is (for a given a parse tree pt of the program to be checked):
c = newCollector("my_model", pt); // create Collector
collect(pt, c); // collect constraints
model = c.run(); // create initial TModel to be handled by the 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:
-
lcis a syntactic type from the language under consideration. -
cis aCollector.
Each collect function is responsible for collecting constraints from its subtrees.
|
6.2. Configuration
The TypePal Configuration can be retrieved or adjusted by the following two functions:
/* Collector field */ TypePalConfig () getConfig;
/* Collector field */ void (TypePalConfig cfg) setConfig;
The former returns the current TypePal configuration, the latter sets the current configuration to a new configuration.
6.3. Scoping
Scope management amounts to entering a new scope, leave the current scope and retrieving the current scope:
/* Collector field */ void (Tree inner) enterScope;
/* Collector field */ void (Tree inner) leaveScope;
/* Collector field */ loc () getScope,
In order to check consistency, leaveScope has the inner scope that it is supposed to be leaving as argument.
Here is an example how the let expression in Fun handles subscopes:
void collect(current: (Expression) `let <Id name> : <Type tp> = <Expression exp1> in <Expression exp2> end`, Collector c) {
c.enterScope(current);
c.define("<name>", variableId(), name, defType(tp));
c.calculate("let", current, [exp2], AType(Solver s) { return s.getType(exp2); } );
collect(tp, exp1, exp2, c);
c.leaveScope(current);
}
6.4. Scope Info
It is possible to associate auxiliary information with each scope.
This enables the downward propagation of information during the topdown traversal of the source program by collect.
Typical use cases are:
-
recording the return type of a function declaration and checking that all return statements in the body of that function have a type that is compatible with the declared return type.
-
recording the label of a loop statement for the benefit of nested break or continue statements.
Scopes are identified by their source location and ScopeRole: a user-defined data type that distinsguishes possible
roles such as functionScope() or labelScope().
setScopeInfo sets the information for a scope:
/* Collector field */ void (loc scope, ScopeRole scopeRole, value info) setScopeInfo;
where
-
scopeis the scope for which information is to be set. -
scopeRoleis the role of that scope. -
infois the associated information.
getScopeInfo retrieves associated scope information:
/* Collector field */ lrel[loc scope, value scopeInfo] (ScopeRole scopeRole) getScopeInfo;
where
-
scopeRoleis the role of the scope we are looking for.
getScopeInfo returns a list relation containing scope/scopeInfo pairs (ordered from innermost to outermost scope).
Let’s illustrate ScopeInfo with a stripped down version of how the Rascal type checker handles while and break statements:
data LoopInfo = loopInfo(str name); (1)
void collect(current: (Statement) `<Label label> while( <{Expression ","}+ conditions> ) <Statement body>`, Collector c){
c.enterScope(current);
...
loopName = "<label.name>";
c.setScopeInfo(c.getScope(), loopScope(), loopInfo(loopName)); (2)
...
c.leaveScope(current);
}
void collect(current:(Statement) `break <Target target>;`, Collector c){
...
loopName = "<target.name>"
for(<scope, scopeInfo> <- c.getScopeInfo(loopScope())){ (3)
if(loopInfo(loopName1) := scopeInfo){
if(loopName == "" || loopName == loopName1){
collect(target, c);
return;
}
} else {
throw rascalCheckerInternalError(getLoc(current), "Inconsistent info from loop scope: <scopeInfo>");
}
}
c.report(error(current, "Break outside a while/do/for statement"));
}
| 1 | Introduces a data type to represent loop information. |
| 2 | When handling a while statement, the current scope is marked as loopScope and loopInfo is associated with it. |
| 3 | When handling a break statement, we get all available ScopeInfo for loopScopes (innermost first) and check the associated loopInfo. |
6.5. Nested Info
An arbitrary number of push down stacks can be maintained during the topdown traversal of the source code that is being type checked. A use case is recording that a certain syntax type is encountered and make children aware of this, e.g. "we are inside a parameter list".
Each stack has a string name (key) and is created on demand.
/* 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,
push, pop, and top perform standard stack operations. push creates a stack when needed, while top and pop require
the existence of the named stack. getStack returns all values in the named stack, while clearStack resets it to empty.
6.6. Composition
TModels can be composed by adding the information from one TModel to the other. A use case is module compoisition.
/* Collector field */ void (TModel tm) addTModel;
addTModel adds the information in tm to the current Collector.
6.7. Reporting
One or more reports can be added by report and reports:
/* Collector field */ void (FailMessage fmsg) report;
/* Collector field */ void (list[FailMessage] fmgs) reports;
See Reporting for a description of FailMessage.
If one of the messages is error the execution of the current calculator or requirement is immediately terminated.
|
6.8. Add Path
TypePal is based on nested scopes and path between scopes. The former represent textual nesting as present in block structure and function scopes. The latter represent non-local semantic links between program parts as present in import statements between modules or Pascal’s with statement. The following functions add to the scope graph a path from the current scope to another scope.
6.8.1. Add a path to a definition
/* Collector field */ void (Tree occ, set[IdRole] idRoles, PathRole pathRole) addPathToDef;
addPathToDef is typically used to create an import or extend path between program parts.
occ is an occurence of a name that should be defined elsewhere in one of the given roles.
The effect is to add a pathRole path between the current scope and the definition.
Here is an example taken from ModFun:
void collect(current: (ImportDecl) `import <ModId mid> ;`, Collector c){
c.addPathToDef(mid, {moduleId()}, importPath());
}
6.8.2. Add a path to a qualified definition
/* Collector field */ void (list[str] ids, Tree occ, set[IdRole] idRoles, set[IdRole] qualifierRoles, PathRole pathRole) addPathToQualifiedDef;
Similar to addPathToDef for the occurrence of a qualified names rather than a simple name.
6.8.3. Add a path to a type
/* Collector field */ void (Tree occ, PathRole pathRole) addPathToType
occ is a parse tree with has a certain type.
The effect is to add a pathRole path between the current scope and the definition of that type.
A prime example is type checking of Pascal's with statement which opens the definition
of a record type and makes all defined fields available in the body of the with statement.
Here we create a withPath between the scope of the with statement and all definitions
of the record types of the given record variables:
void collect(current: (WithStatement) `with <{RecordVariable ","}+ recordVars> do <Statement withStat>`, Collector c){
c.enterScope(current);
for(rv <- recordVars){
c.addPathToType(rv, withPath());
}
collect(recordVars, withStat, c);
c.leaveScope(current);
}
6.9. Define
The function define adds the definition of a name in the current scope:
/* Collector field */ void (str id, IdRole idRole, value def, DefInfo info) define;
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 the definition information DefInfo to be associated with this definition.
The function defineInScope adds the definition of a name in a given scope:
/* Collector field */ void (value scope, str id, IdRole idRole, value def, DefInfo info) defineInScope
6.10. Use
6.10.1. Use an unqualified name
There are three 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.
Here is an example from Calc:
void collect(current: (Exp) `<Id name>`, Collector c){
c.use(name, {variableId()});
}
6.10.2. 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 list of strings that form the qualified name, occ is the actual occurrence, and there are two sets of roles:
idRoles are the possible roles for the qualified identifier itself and `qualifierRoles are the possible roles for the qualifiers.
6.10.3. Use a name via another type
Many languages support named types and names that can be defined inside such a named type.
Examples are field names in records or method names in classes. useViaType handles the use of names defined in a named type:
/* Collector field */ void (Tree container, Tree selector, set[IdRole] idRolesSel) useViaType
where
-
container: has a named type as type. -
selector: is the name to be selected from that named type. -
idRolesSel: are the IdRoles allowed for the selector.
Here is an example of field selection from a record in Struct:
void collect(current:(Expression)`<Expression lhs> . <Id fieldName>`, Collector c) {
c.useViaType(lhs, fieldName, {fieldId()}); (1)
c.fact(current, fieldName); (2)
collect(lhs, c);
}
| 1 | Determine the type of lhs, say T. Now look for a definition of fieldName (as fieldId) in the definition of T. |
| 2 | The type of the whole expressions becomes the type of fieldId. |
useViaType can be configured with getTypeNamesAndRole and getTypeInNamelessType that
determine the precise mapping between a named or unnamed type and its fields.
6.10.4. UseLub
In some languages (think Rascal) local type inference and subtyping are needed to determine the type
of variables: when no explicit definition is present, the type of these variables is inferred from their use and
the least-upper-bound (LUB) of all the uses of a variable is taken as its type.
useLub marks variable uses for which this regime has to be applied:
/* Collector field */ void (Tree occ, set[IdRole] idRoles) useLub
See the Rascal type checker for examples.
6.11. Inference
ATypes may contain type variables and new type variables can be created using newTypeVar:
/* Collector field */ AType (value src) newTypeVar;
Type variables can be bound via unification.
Here is an example of a call expression taken from UntypedFun:
void collect(current: (Expression) `<Expression exp1>(<Expression exp2>)`, Collector c) {
tau1 = c.newTypeVar(exp1);
tau2 = c.newTypeVar(exp2);
c.calculateEager("application", current, [exp1, exp2],
AType (Solver s) {
s.requireUnify(functionType(tau1, tau2), exp1, error(exp1, "Function type expected, found %t", exp1));
s.requireUnify(tau1, exp2, error(exp2, "Incorrect type of actual parameter"));
return tau2;
});
collect(exp1, exp2, c);
}
calculate and require are only evaluated when all their dependencies are
available and they are fully instantiated, i.e., do not contain type variables.
calculateEager and requireEager are also only evaluated when all their dependencies
are available but those may contain type variables.
The bindings that are accumulated during calculateEager or requireEager
are effectuated upon successfull completion of that calculateEager or requireEager.
6.12. Fact
The function fact registers known type information for a program fragment src:
/* Collector field */ void (Tree src, value atype) fact;
where atype can be either an AType or a Tree. In the latter case the type of that Tree is used when available.
Here are two examples from Calc:
void collect(current: (Exp) `<Integer integer>`, Collector c){
c.fact(current, intType()); (1)
}
void collect(current: (Exp) `( <Exp e> )`, Collector c){
c.fact(current, e); (2)
collect(e, c);
}
| 1 | Registers the fact that the current expression has type intType. |
| 2 | Registers the fact that the current expression has the same type as the embedded expression e. |
6.13. Calculate
A calculator computes the type of a subtree src by way of an AType-returning function calculator.
A list of dependencies is given whose types have to be known before this calculator can be computed.
There are two versions: for calculate all dependencies should be fully resolved and instantiated,
while calculateEager can also handle dependencies that still contain type variables.
/* Collector field */ void (str name, Tree src, list[value] dependencies, AType(Solver s) calculator) calculate;
/* Collector field */ void (str name, Tree src, list[value] dependencies, AType(Solver s) calculator) calculateEager;
See A Calculator Language and Examples of Typecheckers for examples of calculator definitions.
See Inference for details about type variables.
6.14. Require
A requirement is a predicate regarding the type or properties of a source tree fragment src.
There are two versions: for require all dependencies should be fully resolved and instantiated,
while requireEager can also handle dependencies that still contain type variables.
/* Collector field */ void (str name, Tree src, list[value] dependencies, void(Solver s) pred) require;
/* Collector field */ void (str name, Tree src, list[value] dependencies, void(Solver s) pred) requireEager;
where
-
nameis the name of the requirement (for reporting purposes). -
dependenciesis a list of dependencies whose types have to be known before this requirement can be computed. -
predis a function that actually checks the requirement; when it is violated this will be reported via its Solver argument.
More specific requiremens can be expressed for checking that two subtrees or types are equal, comparable, that the one is a subtype of the other, or that they can be unified:
/* 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 is known.
See A Calculator Language and Examples of Typecheckers for examples of requirement definitions. See Inference for details about type variables.
7. Solver
A Solver tries to solve the constraints in a TModel; unsolved constraints produce error messages
The purpose of a Solver is to solve the constraints that have been gathered by the Collector and to produce a TModel. The functions provided by a Solver are summarized below:
Two dozen functions (some very similar to the ones provided for Collector) are available that fall into the following categories:
-
Lifecycle of Solver: create a new Solver and use it to solve the constraints in a given TModel.
-
Fact: establish facts.
-
Calculate: calculate types.
-
Require: check requirements.
-
Types: retrieve the type of a program fragment in various ways, if that type is available.
-
Inference: create new type variables for type inference.
-
Reporting: report errors, warnings and info messages.
-
Global Info: access global information such as the current TypePal Configuration, available type facts, and the global store (EXPLAIN).
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).
7.1. Lifecycle of Solver
Once, an initial TModel has been created by a Collector, a Solver takes over to solve constraints
and produce a final TModel. A new Solver can be created by newSolver that comes in two flavours:
Solver newSolver(Tree pt, TModel tm)
Solver newSolver(map[str,Tree] namedTrees, TModel tm){
The former takes a parse tree and an initial TModel and is intended to solve the constraints for a single parse tree. The latter takes a map of named parse trees and an initial TModel and can handle the situation of multiple trees with mutual dependencies.
Finally, run creates the final TModel by solving the constraints in the initial TModel:
/* Solver field */ TModel () run
A complete type checking scenario (for a given a parse tree pt of the program to be checked) is:
c = newCollector("my_model", pt); // create Collector
collect(pt, c); // collect constraints
initial_model = c.run(); // create initial TModel
s = newSolver(pt, initial_model); // create Solver
final_model = s.run(); // solve constraints and produce final TModel
The final TModel contains valuable information such as
-
messages (errors, warnings, info);
-
type facts for subtrees of the given parse tree;
-
use/def relations.
7.2. Fact
The function fact registers known type information for a program fragment src:
/* Solver field */ void (value src, AType atype) fact
Here
-
srcmay either be aTree(i.e., a parse tree fragment) or aloc(the source location of a parse tree fragment). -
atypeis the AType to be associated withsrc.
7.3. Calculate
All calculate (and require) functions use the following typing convention: an argument of type value can either be:
-
an
AType, or -
a
Tree.
In the former case, the AType is used as is.
In the latter case, the type of the tree is used provided that it exists.
Otherwise a TypeUnavailable() exception is generated and the calculator or requirement
in which the predicate occurs is re-evaluated at a later time.
7.3.1. equal
/* Solver field */ bool (value l, value r) equal
The function equal determines whether the types of l and r are equal, the result is a Boolean value.
7.3.2. subtype
/* Solver field */ bool (value l, value r) subtype
The function subtype determines whether the type of l is a subtype of the type of r;
it calls the user-provided function getSubType, see TypePal Configuration.
7.3.3. comparable
/* Solver field */ bool (value l, value r) comparable
The function comparable determines whether the type of l is comparable with the type of r;
it calls the user-provided function getSubType twice, see TypePal Configuration.
7.3.4. unify
/* Solver field */ bool (value l, value r) unify
The function unify determines whether the type of l can be unified with the type of r
it calls the user-provided functions getSubType and getLub, see TypePal Configuration.
The bindings that may result from unification are effectuated when the enclosing calculate succeeds.
7.3.5. lub
/* Solver field */ AType (value l, value r) lub
The function lub return the least upper bound of the types of l and r;
it calls the user-provided function getLub, see TypePal Configuration.
7.4. Require
7.4.1. requireEqual
/* Solver field */ void (value l, value r, FailMessage fmsg) requireEqual
The function requireEqual returns when the types of l and r are equal, otherwise a FailMessage is reported.
7.4.2. requireSubType
/* Solver field */ void (value l, value r, FailMessage fmsg) requireSubType
The function requireSubtype returns when the type of l is a subtype of r, otherwise the FailMessage is reported;
it calls the user-provided function getSubType, see TypePal Configuration.
7.4.3. requireCompare
/* Solver field */ void (value l, value r, FailMessage fmsg) requireComparable
The function requireComparable returns when the type of l is comparable with the type of r, otherwise the FailMessage is generated;
it calls the user-provided function `getSubType`twice, see TypePal Configuration.
7.4.4. requireUnify
/* Solver field */ void (value l, value r, FailMessage fmsg) requireUnify
The function requireUnify just returns when the type of `l can be unified with the type of r, otherwise the FailMessage is reported;
it calls the user-provided functions getSubType and getLub, see TypePal Configuration.
The bindings that may result from unification are effectuated when the enclosing require succeeds.
7.4.5. requireTrue and requireFalse
/* Solver field */ void (bool b, FailMessage fmsg) requireTrue
/* Solver field */ void (bool b, FailMessage fmsg) requireFalse
The function requireTrue returns when its condition is true, otherwise the FailMessage is reported.
The function requireFalse returns when its condition is false, otherwise the FailMessage is reported.
7.5. Types
Type-related functions try to retrieve various forms of type information from parts of the source program.
When that information is available, it is returned as result.
When it is not available, the internal exception TypeUnavailable() is thrown.
This will abort the execution of the current requirement or calculator which will then be tried later again.
7.5.1. getType
The workhorse of TypePal is the function getType that determines
the type of a given source code fragment in the current scope:
/* Solver field */ AType(value src) getType
src may either be a Tree (i.e., a parse tree fragment) or a loc (the source location of a parse tree fragment).
Here is how getType is used in Pico to check the addition operator:
-
two integer arguments give an integer result;
-
two string arguments give a string result;
-
other combinations are incorrect.
void collect(current: (Expression) `<Expression lhs> + <Expression rhs>`, Collector c){
c.calculate("addition", current, [lhs, rhs],
AType (Solver s) { switch([s.getType(lhs), s.getType(rhs)]){
case [intType(), intType()]: return intType();
case [strType(), strType()]: return strType();
default:
s.report(error(current, "Operator `+` cannot be applied to %t and %t", lhs, rhs));
}
});
collect(lhs, rhs, c);
}
7.5.2. getTypeInScope
The function getTypeInScope determines
the type of a given source code fragment in a given scope and given roles:
/* Solver field */ AType (Tree occ, loc scope, set[IdRole] idRoles) getTypeInScope
Here
-
occis a parse tree fragment; -
scopeis the desired scope; -
idRolesis a set of allowed identifier roles.
7.5.3. getTypeInScopeFromName
The function getTypeInScopeFromName determines the type of a given name that has been bound via given identifier roles
in a given scope.
It is typically used to map a name of a type to its actual type, e.g.,
mapping the name POINT as it occurs in a declaration to the actual record type of POINT.
/* Solver field */ AType (str name, loc scope, set[IdRole] idRoles) getTypeInScopeFromName
Here:
-
nameis the name of the desired element; -
scopeis the desired scope; -
idRolesis a set of allowed identifier roles.
7.5.4. getTypeInType
The function getTypeInType is typically used to determine parts of a container type such as, e.g.,
the fields in a named record type or the methods in a named class type.
/* Solver field */ AType (AType containerType, Tree selector, set[IdRole] idRolesSel, loc scope) getTypeInType
Here:
-
containerTypeis a given container type; -
selectoris a parse tree fragment to select a part from the container type (e.g., a field or method name); -
idRolesSelis a set of allowed identifier roles for the selector (e.g.,fieldId()ormethodId()); -
scopeis the desired scope.
7.5.5. getAllDefinedInType
The function getAllDefinedInType is typically used to determine all named types that are defined in a container type,
e.g., all fields in a record type or all methods in a class type.
/* Solver field */ rel[str id, AType atype] (AType containerType, loc scope, set[IdRole] idRoles) getAllDefinedInType
Here:
-
containerTypeis a given container type; -
scopeis the desired scope; -
idRolesis a set of allowed identifier roles for the selectoed types.
7.6. Inference
Type inference is supported by the introduction of type variables
using newTypeVar in combination with unification primitives
inside calculateEager Calculate and requireEager Require
such as requireUnify and unify. The following functions support the computation
with types possibly containing type variables.
7.6.1. instantiate
/* Solver field */ AType (AType atype) instantiate
replaces all type variables occurring in atype by their binding (when present).
7.6.2. isFullyInstantiated
/* Solver field */ bool (AType atype) isFullyInstantiated
checks whether atype contains any occurrences of type variables.
7.7. Reporting
/* Solver field */ bool(FailMessage fmsg) report
/* Solver field */ bool (list[FailMessage] fmsgs) reports
7.8. Global Info
7.8.1. getConfig
/* Solver field */ TypePalConfig () getConfig
Returns the current TypePal Configuration.
7.8.2. getFacts
/* Solver field */ map[loc, AType]() getFacts
Returns the type facts known to the Solver as mapping from source location to AType.
7.8.3. getStore
/* Solver field */ map[str,value]() getStore
Returns the global store of the Solver. The following elements may occur in the store:
-
Remaining Nested Info from the collect phase. For instance, a single
pushto a stack during the collect phase will be visible during the solve phase and can me (mis)used to communicate information between the two phases.
8. TypePal Configuration
Configuration options for TypePal
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.
-
Verbosity: configures the verbosity of TypePal.
Here is an overview:
8.1. Name Resolution & Overloading
8.1.1. isAcceptableSimple
/* Configuration field */ Accept (TModel tm, loc def, Use use) isAcceptableSimple
Here
-
tmis a given TModel -
defis a proposed definition -
useis the use (characterized by theUsedata type that contains, name, occurrence, scope and identifier roles of the use, see Identifier Use) for which the definition is proposed.
isAcceptableSimple accepts or rejects a proposed definition for the use of a simple name in a particular role.
The returned Accept data type is defined as:
data Accept
= acceptBinding()
| ignoreContinue()
| ignoreSkipPath()
;
The default isAcceptableSimple returns acceptBinding()`.
Typical concerns addressed by isAcceptableSimple are:
-
enforce definition before use;
-
check access rights, e.g. visibility.
By comparing the offset of the source locations of definition, respectively, the use, we enforce definition before use:
Accept myIsAcceptableSimple(TModel tm, loc def, Use use)
= use.occ.offset > def.offset ? acceptBinding() : ignoreContinue();
8.1.2. isAcceptableQualified
/* Configuration field */ Accept (TModel tm, loc def, Use use) isAcceptableQualified
Here
-
tmis a given TModel -
defis a proposed definition -
useis the use for which the definition is proposed.
isAcceptableQualified accepts or rejects a proposed definition for the use of a qualified name in a particular role.
8.1.3. isAcceptablePath
/* Configuration field */
Accept (TModel tm, loc defScope, loc def, Use use, PathRole pathRole) isAcceptablePath
Here
-
tmis a given TModel; -
defScopeis the scope in which the proposed definition occurs; -
defis a proposed definition; -
useis the use for which the definition is proposed; -
pathRoleis the role of the semantic path.
isAcceptablePath accepts or rejects a proposed access path between use and definition.
To illustrate this, assume a language with modules and imports. A module may contain variable definitions but these are not visible from outside the module. This can be enforced as follows:
Accept myIsAcceptablePath(TModel tm, loc def, Use use, PathRole pathRole) {
return variableId() in use.idRoles ? ignoreContinue() : acceptBinding();
}
8.1.4. mayOverload
/* Configuration field */ bool (set[loc] defs, map[loc, Define] defines) mayOverload
mayOverload determines whether a set of definitions (defs) are allowed to be overloaded,
given their definitions (defines).
In FWJava the only allowed overloading is between class names and constructor names.
bool fwjMayOverload (set[loc] defs, map[loc, Define] defines) {
roles = {defines[def].idRole | def <- defs}; (1)
return roles == {classId(), constructorId()}; (2)
}
| 1 | First collect all the roles in which the overloaded names have been defined. |
| 2 | Only allow the combination of class name and constructor name. |
8.2. Operations on Types
Various operations on types can be configured by way of user-defined functions.
8.2.1. isSubType
/* Configuration field */ bool (AType l, AType r) isSubType
Function that checks whether l is a subtype of r.
8.2.2. getLub
/* Configuration field */ AType (AType l, AType r) getLub
Function that computes the least upperbound of two types and l and r.
8.2.3. getMinAType
/* Configuration field */ AType() getMinAType
Function that returns the smallest type of the type lattice.
8.2.4. getMaxAType
/* Configuration field */ AType() getMaxAType
Function that returns the largest type of the type lattice.
8.2.5. instantiateTypeParameters
/* Configuration field */ AType (Tree current, AType def, AType ins, AType act, Solver s) instantiateTypeParameters
The function instantiateTypeParameters defines instantiation of language-specific type parameters, where:
-
currentis a source code fragment for which typeacthas already been determined, but any language-specific type parameters inactmay still need to be instantiated. -
defis the parameterized type ofact. -
insis an instantiated version of the type ofact(i.e., with bound type parameters). -
actis the actual type found forcurrentthat needs to be instantiated.
instantiateTypeParameters will match def with ins and the resulting bindings will be used to instantiate act.
The instantiated version of act is returned.
In StructParameters parameterized structs (records) are defined.
The formal type of such a struct is structDef(str name, list[str] formals),
i.e., a struct has a name and a list of named formal type parameters.
The actual type of a struct is structType(str name, list[AType] actuals),
i.e., a struct name followed by actual types for the parameters.
The definition of instantiateTypeParameters for this example is as follows:
AType structParametersInstantiateTypeParameters(Tree current, structDef(str name1, list[str] formals), structType(str name2, list[AType] actuals), AType t, Solver s){
if(size(formals) != size(actuals)) throw checkFailed([]);
bindings = (formals[i] : actuals [i] | int i <- index(formals));
return visit(t) { case typeFormal(str x) => bindings[x] };
}
default AType structParametersInstantiateTypeParameters(Tree current, AType def, AType ins, AType act, Solver s) = act;
8.3. Retrieval of Types
8.3.1. getTypeNamesAndRole
/* Configuration field */ tuple[list[str] typeNames, set[IdRole] idRoles] (AType atype) getTypeNamesAndRole
This function determines whether a given atype is a named type or not. This is needed for the customization
of indirect type computations such as [useViaType] and getTypeInType. When atype is a named type
getTypeNamesAndRole returns:
-
A list of names that may be associated with it. In most languages this will contain just a single element, the name of the type. In more sophisticated cases the list may contain a list of named types to be considered.
-
A list of roles in which the type name can be bound.
Here are the definitions for <<Struct>:
tuple[list[str] typeNames, set[IdRole] idRoles] structGetTypeNamesAndRole(structType(str name)){
return <[name], {structId()}>; (1)
}
default tuple[list[str] typeNames, set[IdRole] idRoles] structGetTypeNamesAndRole(AType t){
return <[], {}>; (2)
}
| 1 | A structType(name) has a name that is bound in the role structId(). Return the name and role. |
| 2 | Any other type is unnamed; return an empty list of type names. |
Another example is the Rascal type checker, where we need to model the case that all abstract data types are a subtype of Tree.
In that case getTypeNamesAndRole will return <["A", "Tree"], roles> for an abstract data type A. The net effect
is that when the search for a name in A fails, the search is continued in Tree.
8.3.2. getTypeInTypeFromDefine
/* Configuration field */ AType (Define containerDef, str selectorName, set[IdRole] idRolesSel, Solver s) getTypeInTypeFromDefine
In some extreme cases (think Rascal) the type of a field selection cannot be determined by considering all the fields
defined in a container type and as a last resort one needs to fall back to information that has been associated with the original definition
of the container type. getTypeInTypeFromDefine is called as a last resort from getTypeInType.
In the Rascal type checker common keyword parameters of data declarations are handled using getTypeInTypeFromDefine.
8.3.3. getTypeInNamelessType
/* Configuration field */ AType(AType containerType, Tree selector, loc scope, Solver s) getTypeInNamelessType
getTypeInNamelessType describes field selection on built-types that have not been explicitly declared with a name.
A case in point is a length field on a built-in string type.
In StaticFields this is done as follows:
AType staticFieldsGetTypeInNamelessType(AType containerType, Tree selector, loc scope, Solver s){
if(containerType == strType() && "<selector>" == "length") return intType();
s.report(error(selector, "Undefined field %q on %t", selector, containerType));
}
8.4. Extension Points
8.4.1. preSolver
/* Configuration field */ TModel(map[str,Tree] namedTrees, TModel tm) preSolver
A function preSolver that can enrich or transform the TModel before the Solver is applied to it.
8.4.2. postSolver
/* Configuration field */ void (map[str,Tree] namedTrees, Solver s) postSolver
A function postSolver that can enrich or transform the TModel after constraint solving is complete.
8.5. Miscellaneous
8.5.1. unescapeName
/* Configuration field */ str(str) unescapeName
A function unescapeName to define language-specific escape rules for names. By default, all backslashes are removed from names.
8.5.2. validateConstraints
/* Configuration field */ bool validateConstraints = true
When validateConstraints is true, the validity of all constraints is checked before solving starts.
For all dependencies (in facts, calculators and requirements) a calculator needs to be present to solve that dependency.
8.6. Verbosity
The verbosity of TypePal can be controlled with several configurations settings.
8.6.1. showTimes
/* Configuration field */ bool showTimes = false
When showTimes is true, the time of the Collector and Solver phases is printed.
8.6.2. showSolverSteps
/* Configuration field */ bool showSolverSteps = false
When showSolverSteps is true, each step of the Solver is printed.
8.6.3. showSolverIterations
/* Configuration field */ bool showSolverIterations = false
When showSolverIterations is true, information is printed about each iteration of the Solver.
8.6.4. showAttempts
/* Configuration field */ bool showAttempts = false
When showAttempts is true, the number of evaluation attempts per calculator or requirement is printed when solving is complete.
8.6.5. showTModel
/* Configuration field */ bool showTModel = false
When showTModel is true, the resulting TModel is printed when solving is complete.
9. Utilities
Some utility functions.
TypePal provides some utility functions to address common scenarios.
9.1. collectAndSolve
TModel collectAndSolve(Tree pt, TypePalConfig config = tconfig(), bool debug = false)
collectAndSolve implements the most simple type checking scenario without any customization.
For a given parse tree pt:
-
Create a Collector and use it to create a TModel by applying
collectto parse treept. -
Create a Solver and solve the constraints in that TModel.
-
Return the extended TModel.
9.2. getUseDef
rel[loc, loc] getUseDef(TModel tm)
Get all use-def relations in a given TModel. This may be used in an IDE for creating hyperlinks between use locations and definitions.
9.3. getVocabulary
set[str] getVocabulary(TModel tm)
Get all defined names in a given TModel. This may be used in an IDE for text completion.
9.4. getFacts
map[loc, AType] getFacts(TModel tm)
Get all the locations and their type in a given TModel.
9.5. getMessages
list[Message] getMessages(TModel tm)
Get all the messages in a TModel (as added by the Solver).
10. Examples of Typecheckers
Examples of type checkers built with TypePal.
TypePal is used in a new type checker for the Rascal meta-programming language and also in type checkers for half a dozen domain-specific languages created by http://swat.engineering in the domains finance, forensics and privacy.
To get you started more quickly, we give below a list of complete TypePal-based type checkers ranging from very simple (intended only to illustrate specific TypePal features) to type checkers for FeatherweightJava and the complete Pascal programming language. For each example we give a description, the most distinctive TypePal features that are used, and its source at GitHub. Each example has the same structure:
-
Syntax.rscthe syntax of the example language. -
Checker.rscthe type checker for the language. -
Test.rscfunctions to call the type checker and test framework. -
tests.ttltest cases for the type checker. -
examples(optionally) a directory with example.
10.1. Calc
What |
The pocket calculator language Calc; we already covered it [A simple pocket calculator language] |
Illustrates |
fact, define, use, requireEqual, calculate, getType, report |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/calc |
10.2. Pico
What |
Toy language with declared variables in single scope, assignment, if and while statement |
Illustrates |
fact, define, use, enterScope, leaveScope, requireEqual, calculate, getType, report |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/pico |
10.3. QL
What |
A questionnaire language, for describing forms with text entry fields and computed values |
Illustrates |
fact, define, use, requireEqual, requireTrue, calculate, getType, report |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/ql |
10.4. Fun
What |
Functional language with explicit types, function declarations and calls, let and if expressions |
Illustrates |
fact, define, use, enterScope, leaveScope, requireEqual, calculate, getType, report |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/fun |
10.5. ModFun
What |
Extension of Fun with modules |
Illustrates |
PathRole, addPathToDef |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/modfun |
10.6. Struct
What |
Simple named records |
Illustrates |
useViaType, TypePalConfig, getTypeNamesAndRole |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/struct |
10.7. Aliases
What |
Struct extended with type aliases |
Illustrates |
useViaType, TypePalConfig, getTypeNamesAndRole |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/aliases |
10.8. StaticFields
What |
Struct extended with fields on non-record type |
Illustrates |
useViaType, TypePalConfig, getTypeNamesAndRole, getTypeInNamelessType |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/staticFields |
10.9. StructParameters
What |
Struct with parameterized records |
Illustrates |
useViaType, TypePalConfig, getTypeNamesAndRole, getTypeInNamelessType, instantiateTypeParameters |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/structParameters |
10.10. SmallOO
What |
Small OO language without inheritance |
Illustrates |
useViaType, TypePalConfig, getTypeNamesAndRole |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/smallOO |
10.11. FWJava
What |
FeatherWeight Java, a minimal, Java-like, language with inheritance and constructors |
Illustrates |
useViaType, addPathToDef, isSubType, TypePalConfig, getTypeNamesAndRole, mayOverload, preSolver, setScopeInfo, getScopeInfo |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/fwjava |
10.12. Pascal
What |
The Pascal language (Second Edition, 1978) |
Illustrates |
useViaType, addPathToType, PathRole, isSubType, TypePalConfig, preCollectInitialization getTypeNamesAndRole |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/pascal |
10.13. UntypedFun
What |
Functional language with implicit (inferred) types, function declarations and calls, let and if expressions |
Illustrates |
fact, define, use, enterScope, leaveScope, requireEqual, calculate, getType, report, newTypeVar, calculateEager, requireUnify, unify |
Source |
https://github.com/cwi-swat/typepal/tree/master/src/examples/untypedFun |