The type database API referred to as mewa.typedb offers you the functions needed to build up the typesystem of your language.
- Create a New Type Database
- Implementing the Concept of Scope
- Scope Bound Objects
- Types
- typedb:def_type
- typedb:def_type_as
- typedb:this_type
- former name typedb:get_type is deprecated
- typedb:this_types
- former name typedb:get_types is deprecated
- Reductions
- Derive and Resolve Types
- Type Attributes
- Introspection for Debugging
mewa = require("mewa")
typedb = mewa.typedb()The variable typedb holds now the type database created.
Get or/and set the current scope. All methods defining objects dependent on a scope like
- typedb:set_instance
- typedb:this_instance
- typedb:def_type
- typedb:def_type_as
- typedb:this_type
- typedb:this_types
- typedb:def_reduction
are referring to the current scope. Without parameter the function just returns the current scope. With a parameter the function sets the current scope to the parameter value and returns the previously defined value for the current scope.
This function was designed to support the mapping of AST nodes to scopes in the tree traversal: You set the current scope when you enter the node and restore the old current scope value when leaving the node.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | scope | table | (optional) pair of integers describing the scope to set as the current one |
| 2nd | step | integer | (optional) integer describing the scope-step to set as the current one, set to scope[2]-1 if not specified |
| Return 1st | table | pair of integers describing the (previously defined) current scope | |
| Return 2nd | integer | integer describing the (previously defined) current scope-step |
Get or/and set the current scope-step. All methods retrieving objects dependent on a scope like typedb:get_instance, typedb:derive_type, typedb:resolve_type, typedb:get_reduction, typedb:get_reductions are referring to the current scope-step. Without parameter the function just returns the current scope-step. With a parameter the function sets the current scope-step to the parameter value and returns the previously defined value for the current scope-step.
This function was designed to support the mapping of AST nodes to scope-steps in the tree traversal in the same way as typedb:scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | step | integer | (optional) integer describing the scope-step |
| Return | integer | integer describing the (previously defined) current scope-step |
The call of typedb:scope with one parameter only sets the scope-step implicitly to the last value inside the scope (end of scope minus 1). If you are not relying on a scope-step different from that, you don't have to call step for every scope-step value provided by the grammar description.
Besides describing the relation to an enclosing scope, scope-step can also be used as a state counter for implementing cleanup in an exit scenario, e.g. return or exception handling.
Set the instance for the object with name name to be object for the current scope (set with typedb::scope).
| # | Name | Type | Description |
|---|---|---|---|
| 1st | name | string | Name of the object we declare an instance of |
| 2nd | instance | any type not nil | The instance of the object |
The object handles are currently not recycled. This means that every object update with set_instance creates a new handle and stores the object passed with this handle as key in a Lua table.
As a consequence, old instances are not freed when overwritten with set_instance. In the example language1 I use this_instance
to get the current object for update and set_instance only if there is no object declared for the current scope and a new one has to be created.
Since version 0.5, Mewa uses the Lua function luaL_ref for getting object handles instead of storing them in a custom table.
This improves the situation in terms of performance. The suggested policy remains the same.
Get the instance for the object with name name for the innermost scope including the current scope-step (set with typedb::scope or typedb::step).
| # | Name | Type | Description |
|---|---|---|---|
| 1st | name | string | Name of the object we are addressing |
| Return | * | The instance of the object we addressed or nil if not defined in an enclosing scope of the current scope-step. |
Implementation of a register allocator for LLVM IR.
mewa = require("mewa")
typedb = mewa.typedb()
-- A register allocator as a generator function counting from 1, returning the LLVM register identifiers:
function register_allocator()
local i = 0
return function ()
i = i + 1
return "%R" .. i
end
end
-- Create a register allocator for the scope [0..1000]:
typedb:scope( {0,1000}); typedb:set_instance( "register", register_allocator())
-- Create a register allocator for the scope [2..300]:
typedb:scope( {2,300}); typedb:set_instance( "register", register_allocator())
-- Allocate a register in the scope-step 45, that is the first register in [2..300]:
typedb:step( 45); print( typedb:get_instance( "register")());
-- Allocate a register in the scope-step 500, that is the first register in [0..1000]:
typedb:step( 500); print( typedb:get_instance( "register")());
-- Allocate a register in the scope-step 49, that is the second register in [2..300]:
typedb:step( 49); print( typedb:get_instance( "register")());
%R1
%R1
%R2
Get the instance for the object with name name assigned to the current scope (set with typedb::scope).
| # | Name | Type | Description |
|---|---|---|---|
| 1st | name | string | Name of the object we are addressing |
| Return | * | The instance of the object we addressed or nil if not defined in the current scope. |
typedb:this_instance is useful to implement the following pattern:
- inherit on read
- copy on first write
- reference on following writes.
For example for the implementation of allocation frames or the implementation of the Pascal "WITH" or the C++ "using".
Define a type and describe how the type is built by assigning a constructor to it. The scope of the newly defined type has been set with the last call of the setter typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | context-type | integer | Type referring to the context of the type or 0 if the type is not a member of some other structure |
| 2nd | name | string | Name of the type defined |
| 3rd | constructor | any type | (optional) Constructor describing how the type is built (nil if undefined) |
| 4th | parameter | table | (optional) Array of type/constructor pair or type handles without constructor. (*) |
| Return | integer | identifier assigned to the type or -1 if the definition is a duplicate |
To put no parameters on the same level as an empty parameter list is as declaring null and empty as equivalent as we do here is dangerous in language design. Be aware of the pitfalls and try to separate the types that can have parameters and the ones that don't by an appropriate naming scheme.
Define a new type representing another type already defined. The newly defined type name can be used as a kind of synonym for the specified type in the current scope. The scope of the newly defined type has been set with the last call of the setter typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | context-type | integer | Type referring to the context of the type or 0 if the type is not a member of some other structure |
| 2nd | name | string | Name of the type defined |
| 3rd | type | any type | Type handle of the type this type definition is a synonym for in the current scope |
| Return | integer | type handle passed as third argument or -1 if the definition is a duplicate |
The type defined like this has the same constructor, therefore it cannot be used as alias for a type with a built constructor.
Get a type definition defined in the current scope, without lookup in enclosing scopes and without any reductions of the context type. The current scope has been set with the last call of the setter typedb::scope. Same as typedb:this_types but filtering the one instance with all parameters matching.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | context-type | integer | Type referring to the context of the type or 0 if the type is not a member of some other structure |
| 2nd | name | string | Name of the type defined |
| 3rd | parameter | table | (optional) Array of type handles (integers) or nil if no parameters defined |
| Return | integer | identifier assigned to the type or nil if not found |
Get all type definitions without matching the parameters defined in the current scope, without lookup in enclosing scopes and without any reductions of the context type. The current scope has been set with the last call of the setter typedb::scope. Same as typedb:this_type but retrieving all instances differing in the parameters attached.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | context-type | integer | Type referring to the context of the type or 0 if the type is not a member of some other structure |
| 2nd | name | string | Name of the type defined |
| Return | table | List of types |
Deprecated function, renamed to typedb:this_type.
Deprecated function, renamed to typedb:this_types.
Define a reduction from a type resulting in another type with a tag to classify it. The scope of the newly defined reduction has been set with the last call of the setter typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | dest-type | integer | Resulting type of the reduction |
| 2nd | src-type | integer | Origin type of the reduction |
| 3rd | constructor | any type | Constructor describing how the type reduction is implemented (nil if undefined ~ identity). |
| 4th | tag | integer 1..32 | Tag assigned to the reduction, used to restrict a type search or derivation to selected classes of reductions. |
| 5th | weight | number | (optional) Weight of the reduction in the calculation of the shortest path when resolving types. Default is 0.0 |
Create a set of tags for selecting a set of reductions valid in the context of a type search.
| # | Name | Type | Description |
|---|---|---|---|
| .... | tag | integer | Element of a list of tags to add to the set |
Get the constructor of a reduction from a type to another if it exists. The current scope-step defining the valid reduction candidates defined in a covering scope has been set with the last call of the setter typedb::step or typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | dest-type | integer | Resulting type to of the reduction. |
| 2nd | src-type | integer | Start type of the reduction. |
| 3rd | tagmask | integer | (optional) Set (bit-set) of tags (*) that selects the reduction classes to consider. No restriction if undefined. |
| Return 1st | number | Weight of the reduction if it exists in a scope and the result is valid or nil if it does not exist. | |
| Return 2nd | any type | Constructor of the reduction if it exists or nil if it is not defined by a scope covering the current scope-step. |
Built with typedb:reduction_tagmask.
Get the list of reductions defined for a type from a list of selected classes defined by tag. The current scope-step defining the valid reduction candidates defined in a covering scope has been set with the last call of the setter typedb::step or typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Start type of the reductions to inspect. |
| 2nd | tagmask | integer | (optional) Set (bit-set) of tags (*) that selects the reduction classes to consider (select all if undefined). |
| 3rd | tagmask | integer | (optional) Set (bit-set) of tags (*) that trigger a flag 'count' to be set in a result if it matches. |
| Return | table | List of type/constructor/weight/count as tables with named members. |
Built with typedb:reduction_tagmask.
typedb:get_reductions is useful to implement the Dijkstra shortest part search used in typedb:derive_type and typedb:resolve_type in plain Lua for debugging and tracing.
Such a parallel implementation is easier to handle than it would be the to offer a mechanism to instrument the original implementation for tracing.
Finds the path of reductions selected by the tagmask parameter with the minimum cost (sum of reduction weights). The current scope-step defining the valid reduction candidates has been set with the last call of the setter typedb::step or typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | dest-type | integer | Resulting type to derive. |
| 2nd | src-type | integer | Start type of the reduction path leading to the result type. |
| 3rd | tagmask | integer | (optional) Set (bit-set) of tags (*) that selects the reductions to use (select all if undefined). |
| 3rd | tagmask_pathlen | integer | (optional) Set (bit-set) of tags (*) that selects the reductions contributing to the length count of a result. (**) |
| 4th | max_pathlen | integer | (optional) maximum length count (number of reductions selected by tagmask_pathlen) of an accepted result. (***) |
| Return 1st | table | List of type/constructor pairs as tables with named members or nil if no result path found. | |
| Return 2nd | number | Weight sum of best solution found | |
| Return 3rd | table | Alternative solution with same weight found. There exists an ambiguus reference if this value is not nil. |
Built with typedb:reduction_tagmask.
Select none if undefined
The tagmask_pathlen, max_pathlen parameters allow to define restrictions on the number of reductions that are implicit value conversions. Most programming languages allow one conversion of a function parameter. 1 is also the default for max_pathlen.
Finds the matching type with the searched name and a context-type to derive from the context-type parameter with the shortest path (sum of reduction weights) of reductions selected by the tagmask parameter. The returned list of reductions (2nd return value) have to be applied on the searched context-type instance to construct the instance of the context-type of the returned candidate types (***). The returned list of candidates (3rd return value) has to be inspected by the client to find the best match. The current scope-step defining the valid reduction candidates has been set with the last call of the setter typedb::step or typedb::scope.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | context-type(s) | integer/table | Single type or array of types or type/constructor pairs referring to the context of the type (*) |
| 2nd | name | string | Name of the type searched |
| 3rd | tagmask | integer | (optional) Set (bit-set) of tags (**) selecting the reduction classes used (select all if undefined). |
| Return 1st | integer | Derived context-type of the results, nil if not found, array with two types in case of ambiguous results. | |
| Return 2nd | table | List of context-type reductions for building the result context, type/constructor pairs as tables with named members. (***) | |
| Return 3rd | table | List of candidates types found, differing in the parameters. The list has to be filtered by the caller (****). |
The context-type 0 is reserved for types that are not a member of some other structure. If passing a list of context types (table), the behavior is slightly different (see (***)).
Built with typedb:reduction_tagmask.
If passing a list of context-types or context-type/constructor pairs as first argument, then the origin of the reduction path to the resulting context-type is returned as first element of the reduction list returned as 2nd return value. So the caller is able to construct the instance of the result context from the second return value only. If passing a single type/constructor pair or type then the returned reduction list has to be applied on this to construct the instance of the result context.
The reason why parameter matching of the results is left to the caller is because there are different ways how to do this depending on the language. In fact, how parameters are matched is a core characteristic of the language and should therefore be implemented in the lua part of the type system.
To inspect the result you first have to look if the 1st return value is nil (meaning that the type could not be resolved). Then you have to check if the first return value is a table (meaning that there are ambiguous results). The table contains two of the conflicting context types. Otherwise the first return value is the context-type of the resuls types and the 2nd and 3rd return value specify how the instances of the resolved types are built.
All programming languages I know follow the policy that a function name in the innermost possible scope is shadowing declarations in the outer scopes, even if these have nearer matches of the arguments. Another behavior would be alien and dangerous from the software engineering point of view. Therefore I consider the restriction that all candidate matches have to share the same context-type as useful.
The following functions are convenient getters for types defined with typedb:def_type.
Get the name of the type as it was specified as name argument (second) of typedb:def_type.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier |
| Return | string | Name of the type without context |
Get the type handle of the type as specified as context-type argument (first) of typedb:def_type.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier |
| Return | string | Handle of the context type of this type or 0 for the global context |
Get the full signature of the type as string. This is the full name of the context type, the name and the full name of all parameters defined.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier |
| 2nd | type | string | (optional) Separator for multipart type name, default is space ' ' |
| Return | string | Full name of the type with context and parameters in oval brackets '(' ')' separated by ',' |
Get the list of parameters defined for a type.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier |
| Return | table | List of type/constructor pairs as tables with named members. |
Get the number of parameters defined for a type.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier |
| Return | integer | Number of parameters defined for this function. |
Get the constructor of a type.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier |
| Return | any type | Constructor of the type or nil if undefined. |
Exits with error if the type passed is not valid. Returns nil if type is 0 or if not constructor is defined for that type.
Get the scope of a type definition.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | type | integer | Type identifier to query the scope |
| Return | integer | the scope of the type or 0 if it was defined without context-type. |
Exits with error if the type passed is not valid.
Used to enforce stricter rules for the visibility of certain objects, e.g. restrict access of variables in locally declared functions to a declared capture, the own stack frame and global variables. Also used for types defined on demand like generics and arrays. To enable reuse, generic and array instances are defined in the scope of their template type definition and not only in the scope where they are used.
Get the tree of scopes with the instances defined.
| # | Name | Type | Description |
|---|---|---|---|
| 1st | name | string | Name of the object we are addressing |
| Return | table | Tree structure with a node for each definition scope |
This is a costly operation and not intended to be used as data structure for the compiler itself. It is thought as help during development.
| Name | Type | Description |
|---|---|---|
| chld | function | Iterator function to iterate on the child nodes (also tree structures like this node). |
| scope | function | Function returning an array (pair of integers) describing the scope of this node. |
| instance | function | Function returning the instance defined for this node. |
Get the tree of scopes with the list of types defined there.
| # | Name | Type | Description |
|---|---|---|---|
| Return | table | Tree structure with a node for each definition scope |
| Name | Type | Description |
|---|---|---|
| chld | function | Iterator function to iterate on the child nodes (also tree structures like this node) |
| scope | function | Function returning an array (pair of integers) describing the scope of this node. |
| list | function | Function returning the list of types (integers) defined in the scope of this node |
This is a costly operation and not intended to be used as data structure for the compiler itself. It is thought as help during development.
Get the tree of scopes with the list of reductions defined there.
| # | Name | Type | Description |
|---|---|---|---|
| Return | table | Tree structure with a node for each definition scope |
| Name | Type | Description |
|---|---|---|
| chld | function | Iterator function to iterate on the child nodes (also tree structures like this node) |
| scope | function | Function returning an array (pair of integers) describing the scope of this node |
| list | function | Function returning the list of reductions (structures) defined in the scope of this node |
| Name | Type | Description |
|---|---|---|
| to | integer | Destination type of the reduction |
| from | integer | Origin type of the reduction |
| constructor | any type not nil | Constructor describing how the type reduction is implemented. |
| tag | integer 1..32 | Tag assigned to the reduction. |
| weight | number | Weight assigned to the reduction. |
This is a costly operation and not intended to be used as data structure for the compiler itself. It is thought as help during development.