5.2 Overload resolution

The Expression module uses a two-pass algorithm to resolve overloading: Starting with the leaves of an expression tree and working towards the root, it determines a possible type set for each node. Each possible type set has an associated cost, which is the sum of the costs associated with all of the operators in the expression tree rooted at that node. Operators introduced by PreDefOpr have cost 1; arbitrary costs can be assigned to operators by declaring them in OIL (see Operator definition).

Every type in the possible type set is either a leaf type or is associated with an operator whose result is that type, and whose operands are elements of the possible type sets of the node's children. If there is more than one operator having these properties, the one of lowest cost is chosen. An arbitrary choice is made if several such operators have the same cost.

If the Required attribute of an expression is NoKey, then the type module chooses the lowest-cost element of the root's possible type set as the result type of the expression. Otherwise, the Required attribute is taken as the result type whether or not it appears in the possible type set of the root.

The second pass starts with the root of the tree and works towards the leaves. At each node, the chosen result type determines an operator (possibly the illegal operator). Given an operator, the operand types are fixed (the operand types of the illegal operator are NoKey by definition). Thus the module must choose those types as the result types of the children.

Notice that this algorithm makes use of the result type of an operator to resolve overloading. Many languages require that overloading be resolved solely on the basis of operand types. That constraint can't be enforced by the type module, but must be implemented as part of the code that builds the type module's database: When adding a relationship between an operator and an indication, report an error if the indication is already associated with an operator having the same result type. (In order to prevent superfluous error reports during type analysis, the offending operator should actually be added to the database.)