Example:Need for Global Function Name Lookup
From dis-Emi-A
This section is to show, by means of a simple example, why global namespace lookup of functions is required for auto-typing. It shall also explore the alternatives and indicate why they are not being considered (or rather, why they were considered and rejected).
Example
A simple example using financial numbers and a simple function.
namespace finance
{
Currency = class { ... }
OP(<) :> Currency a, Currency b -> Boolean c { ... }
OP(+) :> Currency a, Currency b -> Currency c { ... }
}
namespace math
{
max :> a, b -> c
{
[ a < b ]
c = b;
||
c = a;
}
}
large_sum :> cur, n1, n2 -> result
{
result = cur + max( n1, n2 );
}
Up-Typing
To get the possible types for large_sum we use bottom-up typing
- starting at the leaf nodes:
- OP(+) and OP(<), which are both available in Currency (and the standard types, consider only Float here). So we have for OP(<)
- OP(<) :> Currency, Currency -> Currency
- OP(<) :> Float, Float -> Float
- then max which uses the OP(<), which gives us:
- max :> Currency, Currecny -> Currency
- max :> Float, Float -> Float
- Then onto large_sum which again has both a Float and Currency version
Looking closely at the bottom-up typing of max however you notice that it included the functions from the finance namespace. It did this automatically, since given how such packages would be structured, math is the common package, and finance is the extension package, therefore the math namespace would never actually have a reference to the finance package. So it has to automatically consider all namepsaces in order to get at the Currency definition.
Okay, but in C++ this doesn't happen. Why not? Because the up-typing is not done. The max function remains as a template until it is actually instantiated in the large_sum function. At which point the type of n1 and n2 are considered to produce the code for max. In C++ the type of n1,n2 have to of course then be known, but for our language they aren't.
Thus we need to do up-typing first to figure out the types, and if we had left out the finance namespace max would not have been available for the Currency type (and could never be since as assume we cannot modify the math package to reference the namespace). This would make introducing new types into existing libraries impossible. So either we do up-typing and consider all namespaces, or we don't do auto-typing -- and obviously we don't intend on dropping the auto-typing.
Down Typing
It is tempting from this example to want to say that both up-typing and the C++ style templates should be done and the most correct solution is just chosen. In this example it is possible, there aren't that many constraints that need to be held. It would also allow the higher most functions to explicitly indicate which namespaces they are using and we would never have any namespace confusion.
The idea would be to start at large_sum and find all immediate functions which have some kind of matching signature and then in turn expand those, producing a possibility tree of compilations for the function large_sum. Most combinations would eventually rule themselves out as they would not have a matching leaf-node for a function they need to call.
This has two major drawbacks. If we start at large_sum we have to assume that its parameters are wildcard types and blindly match all functions until we get a contradiction in types. Or, you could rather state that we start with the complete list of all types in the system and eliminate them as appropriate leaf-nodes for functions are not found. In this case we only need to consider types explicitly included in the scope (if finance was not included then Currency will not be used).
The other major drawback is that the distance between a first-level evaluation and the elimination of possibilities at leaf-nodes could be very large and similar functions cannot be reduced to the same function until nearly the end. That is, if max is used in many places, every place max is used requires a complete new possibility tree since in each instance its possibilities may collapse in a slightly different fashion. While for very-close to leaf functions like max this is manageable, it becomes nightmare as you call many high-level functions (and becomes impossible if you consider recursion -- that is, impossible without a clever optimization).
So, at quick glance, to give an idea of complexity, a function Q has
- K parameters
- T imported types in its scope
- F function calls
Without optimization, Q has T^K * F possible function calls (permute all the signature variants for Q and then apply that to each function it calls).
Add further to this that a typical program P has an average stack depth of S. Since each branch of a function must be evaluated independently (in the worst case) we have a simple recursive formula: Q(S) = T^K * F * Q(S-1) with Q(1) = 1. This gives us a hefty exponential formular which would clearly violate our requirement for polynomial compilation (see Language Requirements).
With a little bit more thinking you can see how most of the possibilities at each branch can be removed, but that doesn't really matter. At the heart of the problem is still this horrible exponential possibility tree which completely rules out making all but the smallest of programs compilable.
Thus we have to try and deal with automatic namespace inclusion in the up-typing system.
