Interrelated Types In a Method Signature

The^mapfunction mentioned in the previous section is actually a good example of interrelated types in a signature, but the creation of a list of elements of type (which was the result type for the function argument) requires structural type equivalence in order to be useful; otherwise the returned list could not be ac-cessed as a list of elements of type, only as a ^listof bare^objects, because the actual pattern of the result would be known only inside the implementation of ^map. Hence, we will consider an example which does not repackage compos-ite entities into other composcompos-ite entities. As explained, this is something that gbetais not optimized for.

Let us assume that we want a generally applicable procedure which can extract an element from a list. This problem is simple and still requires the handling of polymorphically interrelated types which is hard in^Betaandgbeta. We can easily create a partial solution to this problem with a procedure which uses subpattern polymorphism to handle all kinds of ^lists:

getElement:

(# theList: ^{^}list;

theElement: ^{^}object enter theList[]

do theList.first.elm[]->theElement[]

exit theElement[]

#) ^Ex.

9-13

This procedure receives ^theList as an argument and then uses the method

first to extract the rst element from the list. In the standard ^{Beta list} we have to access the^elmattribute of the result returned by ^firstto get hold of the element itself, so we do that; the element is then reference assigned to

theElementso that we can deliver it as the result of ^getElement.

This design is type safe and it will actually deliver an element from the list as desired (ignoring possible errors such as `List is empty'). The problem with this design is that it needlessly throws away static information about the properties of the element: If we use ^getElementto extract an element from a list of ^integer objects then the result will certainly be an ^integer, but the static analysis will claim that we only know that it is an instance of ^objector a subpattern. Since statically provable information about run-time entities is a valuable resource it is important to try to avoid such a loss.

One way to do this is to have a separate copy of ^getElementfor each spe-cialization of ^list. Note that this is exactly what we doeven though there is only one copy of the syntaxif we change^getElementfrom a (stand-alone) procedure to a method of ^list:

list:

(# element:< object;

:::

getElement:

(# theElement: ^{^}element do first.elm[]->theElement[]

exit theElement[]

#)

#) ^Ex.

9-14

Since a method of a^listobject depends on that^listit is possible for the static analysis to retain the information about the qualication of elements in that particular ^list, so^getElementon a ^listwhose ^element attribute is known to be ^integerwould be known to deliver an^integer, not just an^object.

This technique uses contextuality to remove the need for the equivalent of call-site instantiations of parametrically polymorphic functional types like

8:[]^!, and it may be applicable in many cases. It is also specically ob-ject oriented because it builds on context dependency as opposed to parameter-ization. However, it does not provide us with genuine parametric polymorphism because all those^getElementmethods, one in each^list, would be distinct and non-interchangeable both in the static analysis and in the dynamic semantics.

In a functional language we could actually have one single function with the type⁸:[]^!, and that function could be used for all choices of. For sim-ple calls it makes little dierence whether we have many distinct ^getElement methods or just one^getElementprocedure, but if we wanted to get an element from many^lists and^getElementwere a method then we could not obtain one single^getElementrun-time entity and reuse it with all of those lists.

There is a profound reason why such a polymorphic entity could not be created in an imperative language such as^Beta orgbeta. The reason is that functional languages use immutable bindings of names to values whereas^Beta and gbeta use destructive assignments to variable entities. Because of this, it is actually possible to view the type analysis and type inference of functional languages as a ubiquitous data ow analysis which delivers the results in the form of types of functions. It does not exactly determine the ow of data, but it does establish some connections between the types in type variable expressions which can only be proved because the ow of data is so restricted.

In the functional equivalent to our^getElementprocedure the type system knows that the returned element is of typefor such anthat the argument is of type [], which almost amounts to knowing that the element actually came from that list; in the^Betaandgbetaapproach it is only known that every operation respects all safety invariants (in particular that a variable object conforms to its qualication). Hence, as far as the type checker is concerned there is absolutely no way we could use knowledge about the object referred by^theListto conclude