Language Up-Typing
From dis-Emi-A
Up-Typing is the process of working upwards from the leaves of the call graph and assigning possible type scenarios to all of the functions encountered. This process is done on a per function basis and produces a matchable type signature for all encountered functions.
Contents |
Scenario
A scenario for a function is a set of types (for each item) which satisfies the constraints introduced by the code both explicitly and implicitly. Only valid scenarios are actually considered scenarios, invalid scenarios are discarded from the system (should a function have no valid scenarios it is considered an error).
Complete Scenarios
In the normal case up-typing will produce scenarios having all the constraints well defined.
In the theoretical scenario we deal only with complete scenarios, the discussion of partial scenarios only applies to how a compiler may implement such auto typing (which is a vital part of the discussion).
So in theory every function has a well defined set of scenarios. In the case discussed by partial scenarios it is not that the items are "unknown" it is rather that any type available in the system is allowed for the type there -- which means the function has a rather large number of scenarios.
For example a function like
nothing :> ( a -> a );
Has as many scenarios as there are types in the system. This is rather unpractical for a compiler to handle, so our discussions will include how to handle partial scenarios.
Partial Scenarios
For some special cases it will not be possible for the up-typing to produce a complete scenario, yet nonetheless the code is valid.
The basic example is that of the tertiary operator from C, which would have an implementation something like:
tertiary :> ( cond, t, f -> r )
{
[ cond ] { r = t; }
[ otherwise ] { r = f; }
};
There are two distinct subsets of the context here which have no interrelations, the set of { cond } and { t, f, r }. In this case up-typing can determine that "cond" must be boolean, though it can't say anything more about t,f,r other than that they must all be the same type. Thus the typed signature might look like this:
( :Boolean:, :?1:, :?1: -> :?1: )
This concept further applies to types, in that individual parts of the context are definable only by the caller (the clearest example being that of a container class, which the actual item it contains is irrelevant to its controlling code).
Constraints
Explicit
An explicit constraint is one that is written in the source code using the constraint syntax. These must be met in all scenarios for a function.
= Function Call
A function call has a signature which establishes the constraints needed to use the function. Should a function have multiple scenarios, each of these scenarios are imported into the calling function and permuted with the existing set of scenarios in order to find all the possible scenarios.
Signatures may be complete, or partial.
Assignment / Reference
Assignment and reference implies a relationship such that both sides of the equation are valid in the operation. In the minimal case (excluding derived types, interfaces and qualifiers) this means that both sides of these operations must have the same type.
This needs to be explored further to allow for derived types, interfaces, and qualifiers. Though it is known now that an assignment requires the items to be immutable, and a reference requires them to be mutable.
