Functional Languages and Implementation Reuse

The Hindley-Milner style types [92] which are used in functional languages such as Haskell are particularly convenient for giving examples of signatures where dierent argument and result types may be chosen rather freely but only in ways

9.3. VIRTUAL OBJECTS 189 which exhibit certain patterns of relations between the types. For example, consider the standard function ^map which takes a function f and a list l as arguments and returns another list containing the images by f of the elements in l. This function has the following type:

8; :(^!)^![]^![]

This type species that^mapcan be applied to any functionf and listlfor which there exists a choice of values for the type variables and such that f is a function fromto andlis a list of values of type; the result is then known to be a list of values of type . Wherever ^mapis used, the type analysis will combine the above type of ^mapwith the types of nearby expressions by means of a unication process which determines how (and if) it is possible to consistently choose values for all the type variables [92].

This approach enables a type safe reuse of a given function implementation for all those types of arguments where a choice of values for type variables is possible, i.e., for all those types of arguments which are known to have a certain minimal top-down structure. The implementation of ^mapwill work correctly no matter what structure the elements in the list have, it just has to be a list of something, and the function argument can be called on arbitrary values as far as^mapis concerned. There are some internal relations between the arguments that the function argument typemust be the same as the type of the elements in the list, and that the result type [] can be computed from the function type ^!. These internal relations are irrelevant for the implementation of ^map, but the consistent use of such internal relations in composite types allow for very well-studied and solid type correctness properties for programs as a whole.

In this tradition, the highest priority is given to reusing function implemen-tations as widely as possible. For example, there should only be one^mapfunction which would then be reused for all the possible choices of values for type vari-ables. The^mapfunction will actually work just ne in all those cases, and having several structurally identical implementations of the^mapfunctionalitye.g. one for each choice of type variableswould be confusing and redundant. The ideal is that programming language entities such as functions should be pure struc-ture, purely transparent, carrying no other properties than the minimum which is derived from the language semantics. So for example, the meaning of ^map is just to apply a function to all elements in a list, no less and in particular no more.

The natural consequence is that structural type equivalence is considered correct in the functional language community, and anything else is seen as a compromise which must be rooted in performance considerations or sheer bad judgment; types should be computable (if we have a function type and a list type then we can take them apart and recombine the elements to make another list type); and the structure of composite values should not be taken to mean anything but that structure, and we can of course take composite values apart and recombine them any way we like. We might use the phrase `no nonsense' to describe this mindset, noting that the nonsense is everything beyond the

operational semantics of the language. Functional languages are really very well optimized along these lines, and the topic of virtual objects is all about obtaining some of the benets of this approach.

However,gbetahas grown out of an entirely dierent mindset. In the gbeta approach the highest priority is given to how well the programming language will support programmers in the construction of complex systems. We are less concerned with the fact that a given implementation may be redundant in a purely operational, semantic sensethe implementation should not play such a dominant role. In contrast, we nd it important to support programmers in the construction and use of program entities based on an understanding of the role and purpose of those program entities which goes far beyond the narrow semantic properties and into the minds of people. Hence, a composite entity is more than the sum of its parts. The programming language should support programmers in thinking about composite entities as meaningful in and of themselves and containing parts that make sense in their context, rather than thinking about composite entities as arbitrary conglomerates whose parts may be repackaged freely into other conglomerates.

Consequently, languages like ^Beta andgbeta are actually quite poorly op-timized for a consistent and ubiquitous exploitation of opportunities for im-plementation reuse based on purely structural and operational similarities. A typical example where this seems to create problems is with container data structures such as^lists and^sets. The problem is that these languages insist that a ^list-of-^integer pattern must have its own unique identity, dierent from any other^list-of-^integerpattern which happens to be dened by some other possibly syntactically identical declaration. As far as both are simply con-sidered as lists of ^integerobjects without any further meaning, this is a clear example of harmful and confusing redundancy, and it is inconvenient in large projects to have to standardize on using one particular declaration in order to avoid having several type-incompatible^list-of-^integerpatterns.

However, in practice this does not seem to be a problem, because the generic

listfunctionality can be implemented as methods on the generic^listpattern and the concrete lists tend to be used only very locally in the implementation of other patterns which do actually carry a meaning of their own. It seems that meaningless concepts such as^list-of-^integershould preferably be kept hid-den inside the implementation of meaningful patterns, because the requirement that an entity be meaningful becomes ever more urgent the larger the universe is where it is intended to be known and used. This means that it is not a problem in practice that two ^list-of-^integerpatterns are distinct, because there will not be any source code which uses both of them. Hence, we do not intend to change or complicate the design of gbetain any profound way in order to pro-vide structural equivalence between (some) patterns. Besides, container data structures seem to be an exception where structural equivalence is obviously desirable, other examples come up rather seldom and seem less compelling.

There is another case where the need to improve on the support for imple-mentation reuse in gbeta is more acute. This case is in some sense inverse to the problem of excessive uniqueness of container data structureswe might say

9.3. VIRTUAL OBJECTS 191 that a structural equivalence on container data structures would allow us to use many dierent entities in the same context, but this improvement is about al-lowing one entity to be used in many dierent contexts. The problem is that the static analysis and the run-time semantics of ^Beta and gbetado not support the capture of regularities such as the multiple occurrences of a type variable in a Hindley-Milner style polymorphic type, and hence it is hard to write routines which are parametrically polymorphic in the same sense as the^mapfunction in a functional language. The next section will detail why this is a hard problem in ^Betaandgbetaand outline some partial solutions.