Niklaus Haldiman

Marcus Denker

Oscar Nierstrasz

Practical, Pluggable Types ⋆

Most languages fall into one of two camps: either they adopt a unique, static type system, or they abandon static type-checks for runtime checks. Pluggable types blur this division by (i) making static type systems optional, and (ii) supporting a choice of type systems for reasoning about different kinds of static properties. Dynamic languages can then benefit from static-checking without sacrificing dynamic features or committing to a unique, static type system. But the overhead of adopting pluggable types can be very high, especially if all existing code must be decorated with type annotations before any type-checking can be performed. We propose a practical and pragmatic approach to introduce pluggable type systems to dynamic languages. First of all, only annotated code is type-checked. Second, limited type inference is performed on unannotated code to reduce the number of reported errors. Finally, external annotations can be used to type third-party code. We present TypePlug, a Smalltalk implementation of our framework, and report on experience applying the framework to three different pluggable type systems.

Introduction

Any static type system attempts to reduce the number of errors that may occur at run-time by restricting the programs that one is allowed to write. Staticallytyped programming languages implicitly take the position that this is a good deal. In return for the minor inconvenience of not being able to write certain kinds of relatively uncommon programs, we obtain guarantees that no catastrophic run-time errors will occur.

Dynamically-typed languages assume the opposing standpoint. Precisely those interesting programs -for example, those exploiting behavioural reflectionwould be rejected. Furthermore, although there are many different approaches to static typing, a statically-typed programming language must commit to one. Dynamic languages do not need to make this kind of premature commitment. Finally, there is the argument that static type systems are responsible for generating a false sense of security. Certain catastrophic errors can certainly be detected, but others cannot.

Gilad Bracha has argued that it is possible to have one's cake and eat it too [START_REF] Bracha | Pluggable type systems[END_REF]. Instead of static type systems being mandatory, they should be optional. This means that a type system should neither require syntactic annotations in the program source, nor should it affect the run-time semantics of the language. An optional type system would report possible errors, but would not prevent the program from being run (and possibly failing at run-time). In addition, type systems should be pluggable, that is, one should be able to choose the kind of static checks one would like to perform. This is especially interesting given the relatively recent emergence of more exotic type systems for reasoning about confinement [START_REF] Grothoff | Encapsulating objects with confined types[END_REF], aliasing [START_REF] Smith | Alias types[END_REF], scopes [START_REF] Zhao | Scoped types for real-time Java[END_REF] and so on.

A number of pluggable type systems have been proposed over the last years [START_REF] Ekman | Pluggable non-null types for Java[END_REF][START_REF] Allwood | Fleece, pluggable type checking for dynamic programming languages[END_REF][START_REF] Andreae | A framework for implementing pluggable type systems[END_REF]. The key difficulty with pluggable types, however, is a practical one: In the presence of a large, existing software base, how can one benefit from a pluggable type system without annotating the legacy code?

We present a practical and pragmatic approach to pluggable types that significantly reduces the overhead of adopting a new type system. TypePlug is a framework supporting pluggable types implemented in Squeak Smalltalk. Type systems are defined by specializing the framework. Types are declared using an annotation framework. TypePlug reduces the cost of adopting a type system by means of the following techniques:

1. Only annotated code is type-checked. 2. Type inference is applied to unannotated code to reduce propagation of errors. 3. Explicit type casts shortcut type-checking. [START_REF] Zhao | Scoped types for real-time Java[END_REF]. External annotations are supported to declare types for third-party code.

Section 2 provides a brief introduction to TypePlug using an example of a non-nil type system. In Section 3 the TypePlug framework is described in some detail. Section 4 discusses experience using TypePlug to define a class-based type system and a confinement type system. Section 5 discusses the results obtained in the context of related work. We conclude in Section 6 with some remarks on future work.

TypePlug in a Nutshell

TypePlug provides a framework to optionally annotate code with type declarations and to type-check annotated code. We will demonstrate how optional types and type checking can be used in a typical coding session.

To keep the presentation as simple as possible, we use the example of a nonnil type system. This type system has exactly one type, the nonNil type. If a variable has the nonNil type it cannot hold the value nil. Anything not typed nonNil is considered to potentially evaluate to nil (there is no explicit nil type).

To declare a variable to be of type nonNil we add the annotation <:nonNil :> to it. In the following class definition of a two-dimensional line we declare the instance variable endPoint to be nonNil: Object subclass: #Line uses: TReflectiveMethods typedInstanceVariables: 'startPoint endPoint <:nonNil :>' typedClassVariables: ''

Notice the trait 1 TReflectiveMethods that we use in this class. It pulls in the annotation framework that we need to annotate its methods. We assume that we have not added any other annotations yet to the methods of this Line class. If we now browse the source of one of the methods we can experience type checking in action. Here is a method of a line that moves it horizontally by a number of units:

moveHorizontally: anInteger startPoint := self movePoint: startPoint horizontally: anInteger. endPoint := self movePoint: endPoint horizontally: anInteger <-type 'TopType' of expression is not compatible with type 'nonNil' of variable 'endPoint'.

When the source of a method is displayed it is type-checked and type errors are shown inline. The type error found in the above method is highlighted. What it says is that the expression self movePoint: endPoint horizontally: anInteger was found to have the top type which means that its type is unknown. Since the instance variable endPoint requires the type nonNil, this results in a type error.

To fix this error we have to look into the method movePoint:horizontally: and declare its return type to be nonNil. This is what it looks like: movePoint: aPoint <:nonNil :> horizontally: anInteger ↑ (aPoint addX: anInteger y: 0) <:nonNil :>

A return type annotation must be added to the return statement expression. Notice how parentheses are needed here to apply the annotation to the whole expression. Adding a return type to a method has two repercussions: in call sites of the method the message send expression will be typed accordingly and within the method its return statements will be type-checked. Here this means that the expression aPoint addX: anInteger y: 0 must be of type nonNil (assume we annotated the addX:y: method with a nonNil return type already, so no type error occurs here).

To show an example of an argument type we annotated the first argument of movePoint:horizontally: with a nonNil type as well. Adding an argument type declares the argument to be of that type within the method, and it is also a requirement to arguments passed when the method is used. Because of this requirement we now get a different type error when we look at moveHorizontally: again: moveHorizontally: anInteger startPoint := self movePoint: startPoint horizontally: anInteger <-in message 'movePoint:horizontally:' of class 'Line' argument 'TopType' is not compatible with expected type 'nonNil'. endPoint := self movePoint: endPoint horizontally: anInteger.

The startPoint instance variable does not have an annotation so its type is the default, the top type, which is not what is required for the first argument to movePoint:horizontally:. The obvious fix to this type error is to declare startPoint to be nonNil as well. A different strategy that TypePlug offers is to cast an expression to an arbitrary type, in this example by adding the annotation <:castNonNil :>. moveHorizontally: anInteger startPoint := self movePoint: startPoint <:castNonNil :> horizontally: anInteger. endPoint := self movePoint: endPoint horizontally: anInteger.

With a cast a programmer asserts to the type checker that the type of a given expression is known. Casts are useful for one-off resolutions of type errors where more type annotations would be overkill or impossible, for example because the cast expression uses untyped third-party code.

Let's annotate one more method of Line with a return type:

hasStartPoint ↑ (startPoint notNil) <:nonNil :>
We are still operating under the assumption that no other type annotations have been made than those previously discussed. We surely have not annotated any notNil method with types, so how come we don't get a type error here because the expression startPoint notNil can't be proven to be nonNil? The reason is that the type checker tries to infer return types of methods if they are not explicitly annotated. The notNil method has two implementations, one in the base class Object -simply returning false -and one in UndefinedObject -simply returning true. So obviously invocations of notNil will always return a nonNil boolean value, which is what the type checker figured out in this case, sparing us from explicitly annotating the notNil method with a return type.

While this preceding coding session serves as a lightweight introduction to TypePlug, it also illustrates an important issue when programming with optional types. Once one adds just one type to previously untyped code the need for more type annotations usually arises to type-check other parts of the code. Most likely, these additional types prompt for even more type annotations. This means that quite a bit of work is usually required from a programmer if he introduces types in a section of his code. A framework for optional typing should be aware of this problem and minimize the work required by the programmer. As demonstrated in the coding session, two of our strategies in this area are type inference and casts, reducing the need for explicit type annotations.

The TypePlug Framework

A type system in TypePlug is specified by first defining the types of the system and then the properties of the types. This mainly consists of defining mappings from Smalltalk elements to types as well as operations on types. Since a key goal of TypePlug is to enable the creation of new type systems without much effort, the number of properties that have to be defined is kept to a minimum while retaining considerable flexibility.

Concretely, a new type system is created by subclassing the TPTypeSystem class and overriding some of its methods. As a quick reference and overview, Table 1 lists all of the methods of TPTypeSystem that can be overridden when implementing a new type system. In the following discussion we will touch on the details of the most important of these methods. Persephone enhances Squeak with a model for methods based on an abstract syntax tree (AST). Any entity of the AST can be annotated with metadata. Annotations can be visible in the source code, they can be added in various places in a method, namely to instance and class variables, method arguments, return statements, local variables and block variables. For example, the expression anExpression <:aSelector: anArgument:> attaches an annotation with one argument to the expression anExpression.

The argument of an annotation can be any Smalltalk expression. In the simplest case, when the argument is just a literal object, the value of the annotation is set to this literal object. When the argument is an expression, the value of the annotation is the AST of this expression. We can specify when this AST is evaluated, either at compile time or later at run-time. In addition we provide a reflective interface to query and set annotations at runtime.

Annotations, Types and Their Representation. TypePlug gathers type information from annotations made in Squeak source using the Persephone framework. Such an annotation places the requirement that the annotated subexpression should have the given type.

In addition to type annotations TypePlug supports cast annotations. Casts are unchecked -they always succeed, regardless of whether they can statically be proven type safe. Cast annotations are formed by preceding a type annotation with cast and capitalizing its first character, e.g.,<:castNonNil :> is a cast to type nonNil.

Since TypePlug supports an arbitrary number of coexisting pluggable type systems, any expression can have several annotations, one per type system. In the source code, annotations are simply added one after the other. For this to work we need a way to distinguish annotations for different type systems. Every type system defines a unique system key that is used to identify its annotations. The system key is a symbol returned from the class method systemKey.

For the non-nil type system, the key is nonNil, thus an annotation for the unique type in the system is <:nonNil :>. This is a special case -usually a type system will have more than one single type, and keys will usually have a colon at the end to signal that. For example, the confinement type system discussed in Section 4.2 has the key confine:. In an annotation for that system, the actual type appears as the annotation value after the key, e.g.,<:confine: toClass :>.

The type system must define its valid annotation values and thus its valid types. It does so by defining a method annotationValueToType:inContext: which returns instances of its types (types in TypePlug are instances of subclasses of the class TPType). The annotationValueToType:inContext: method takes as the first argument an abstract syntax tree (utilizing the Refactoring Browser AST nodes) of such an expression. This is a great help for type systems which might have complex annotation values, so they do not need to do their own parsing. The second argument is an instance of TPContext which describes the context of the annotation, i.e., in which method the annotation at hand is located. In a type system, the interpretation of an annotation might depend on where it is found.

The Top Type. One type is predefined and shared by all type systems: the top type. It is assumed to be a supertype of every other type in a type system. Within the TypePlug framework, the top type can appear in many places where a type is expected, and if it does it means one of two things:

1. This can be any type. 2. Nothing is known about this type.

An example of the first meaning is the default argument type for methods: by default, if a method argument is not explicitly annotated with a type, it is assumed to have the top type. The second meaning can be observed in the typing methods discussed in the next section: all of these by default return the top type to state that, e.g., the type of literals (defined by typeForLiteral:) is unknownunless, of course, defined differently by the type system.

Generally speaking, every typed thing has the top type if it is unannotated or has an unknown type. This may seem like an insignificant implementation detail but the top type is an important device to usefully type check only partially annotated source. With its property of being a supertype of every other type it guarantees that, e.g., unannotated source code type-checks safely.

Typing Elements of Smalltalk Syntax. Type systems can define the types of a range of basic constructs of Smalltalk syntax: types for literals, global variables, primitives, arrays, blocks and pseudo-variables such as self and super. This is achieved by implementing any of the typeFor* family of methods defined on type systems, as listed in Table 1. By default all of these methods return the top type.

In the non-nil type system, the implementation of the typing methods is very simple. Here are two of the more interesting ones:

typeForLiteral: aValue ↑ aValue ifNotNil: [self singleType] ifNil: [self topType] typeForSelfInClass: aClass ↑ (UndefinedObject includesBehavior: aClass) ifTrue: [self topType] ifFalse: [self singleType]
Obviously, the type for a literal is always nonNil except when the value is nil. To assess the type of self we need to be slightly cautious since within nil's class, UndefinedObject, we cannot say that self is nonNil. But the same is true for all superclasses of UndefinedObject since their methods could be called from the nil instance (the includesBehavior: method returns true if the argument is the receiver or a superclass of the receiver).

Subtyping and Unification. The two most important operations a type system must define in our model are a subtyping relation and a type unification operation. Each of these is heavily used at the core of the type-checking algorithm as described in Section 3.2. Responsibilities for subtyping and unification are assigned to the type system rather than to types, though the implementation of a particular type system may delegate these responsibilities to the types themselves.

The subtyping relation is defined by implementing the is:subtypeOf: method which takes two types as arguments. It should return true if the first type is a subtype of the second in the context of this type system, false otherwise. While type systems are free to define whatever subtyping relation they please, it should usually be reflexive and transitive to be of practical use. The second argument may be the top type, representing an unknown type. The top type is considered to be a supertype of every other type of any type system by definition, so is:subtypeOf: is never called with the first argument being the top type.

The unification operation creates a type that represents the union of two types. Again, type systems are completely free to define this in any way that is appropriate. Generally, the union of two types should be the most specific common supertype, but a type system can also work with an explicit union type that it defines. In code, the unification operation is defined by implementing the unifyType:with: method which should return the result of unifying the two types passed as arguments.

Since the non-nil type system only knows a single type, subtyping and unification are absolutely trivial. The nonNil type is a subtype of itself and the nonNil type unified with itself gives the nonNil type again: The Built-in Static Type System. Although Smalltalk is dynamically typed, its source code nevertheless contains some inherent static type information. For example, the class of an object is statically known if it appears as a literal in the source code. Static type information such as this can be very valuable to the type-checking algorithm and to any given pluggable type system. It is therefore important to capture this information and make it available in a convenient form. TypePlug achieves this with a built-in static type system which is itself implemented as an ordinary pluggable type system. Every expression is assigned one of the following static types:

-The self type, the type of the pseudo-variable self.

-The super type, the type for the pseudo-variable super.

-Class types, the types for objects whose class is known.

-Object types, the types for objects whose exact value is known, e.g., literals and globals. -Block types, the type for literal blocks.

-The top type, meaning that nothing is known about the static type of that expression.

Object types of a given class are all subtypes of the corresponding class type, e.g., the object type for the integer literal 42 is a subtype of the class type for SmallInteger.

The block type is a class type, since the class of a literal block is obviously known. The same goes for the super type. The self type, however, is not a class type -in class hierarchies the pseudo-variable self can refer to any of the subclasses of the class it appears in.

In contrast to user-defined pluggable type systems, the static type system is always present underneath every other type system. The built-in static types are available to implementors of pluggable type systems, and can be exploited when defining subtyping and unification for those systems. As a general principle, whenever an implementation gets hold of a type of some expression (e.g., the two types passed as arguments into the unification operation) it can also access the static type of that same expression.

Type Checking

The heart of TypePlug is its approach to type-checking. The type-checking algorithm has been designed to make it easy to plug in a new type system. Furthermore, since type annotations in pluggable type systems are optional, the algorithm must deliver useful results in the face of an only partly annotated codebase. As a consequence of these considerations we established two guiding principles for the approach to type checking:

1. Only code that contains type annotations or uses annotated methods will be type-checked. 2. Where code to be type-checked refers to unannotated code, static types and type inference will be used to infer as much type information as is practical.

The combination of these two principles makes it possible to deal well with a mix of typed and untyped code.

Ensuring Type Safety. Type checking in TypePlug is applied per method and per type system. The type checker takes a type system and a method as input, statically checks the method for type safety and returns detailed results about a type error if there is one.

Source code is analyzed by traversing its abstract syntax tree (AST) representation. A type is assigned to every expression node in the AST. The type of an expression is determined by the typing methods of the type system and -where possible -by type inference, taking into account the type and cast annotations in the source.

While the type checker traverses the AST, at certain points type safety is ensured by doing subtyping checks. The three points are assignments, return statements and message sends. Type safety checks for assignments and return statements are trivial, but message sends deserve an extended discussion.

Checking Message Sends. Ensuring the type safety of message sends is the most difficult problem in type checking Smalltalk. In general, the class of a receiver of a message is not statically known, so there is usually no way to statically determine which method will be invoked at runtime or if a matching method even exists. Clearly, any static type-checking algorithm relying on partial type annotations must be pragmatic here and make some compromises.

One possible solution to improve the situation is to extensively use type inference to determine the class of message receivers. We do utilize some simple forms of type inference but in the context of a specific pluggable type system, not to determine the class of expressions.

We use a simple scheme that nevertheless yields useful results. Our approach tries to look up the set of methods that could be invoked for a specific message send and involve the whole set during type checking. The static type system is used to make this set as small as possible. Thus our approach is similar to standard type inference techniques [START_REF] Palsberg | Object-oriented type inference[END_REF], but with a far simpler reduction strategy.

Three cases are distinguished based on the static type of the receiver:

1. If the receiver class is statically known, i.e., the receiver has a static class type, the method invoked at runtime can be looked up precisely and the set consists of that one method. Note that object types, block types and super types all fall under this case since they are class types. 2. If the receiver has a self type we need to consider the class the method being type-checked belongs to. The set consists of all implementors of the message in this class and its subclasses. It is necessary to include subclasses because the self pseudo-variable can refer to an instance of a subclass if the method is called from a subclass. 3. If the receiver does not have a static type, i.e., its static type is the top type, we have to resort to a very broad strategy: the set consists of all implementors of a message, i.e., all methods of the message's name implemented in the whole system. This case is the most common, unfortunately. A pluggable type system might carry information that can be used to further reduce the set of methods in this case. That is why type systems get the chance to implement their own strategy for this third case (by overriding the methodsForMessage method).

Once the set of methods to be considered has been fixed, the actual type check of the message send consists of asserting that the types of the arguments are subtypes of the respective types of the methods parameters. If a method parameter does not have a type it is assumed to have the top type which means that untyped parameters effectively are not type-checked. If the set of methods is empty a type error is raised.

This approach as a whole has the desirable property of catching most type errors. But it has the undesirable property of possible raising too many type errors. When unrelated classes have methods with the same name but with different parameter types, the "all implementors" strategy might label a message send as a type error even though at runtime the error would never occur. This drawback becomes less problematic when one considers what actually happens when type checking arguments in a message sends. If a method does not have any type annotations argument type checking is always successful. Only methods that declare types on their arguments can provoke type errors. Since we do not expect to operate in a fully annotated code base these questionable type errors should not occur often.

One problem remains: This approach cannot guarantee that a receiver actually responds to a message at runtime, i.e., that a receiver actually implements a method of that name. We only guarantee type safety for the case that a receiver actually responds to a message.

Type Inference

We treat type inference as a crucial tool to enhance the user experience of Type-Plug. It spares a programmer from exhaustively annotating source code with types.

Our type checker has two specific limited forms of type inference built in, for local variable types and for method return types. Both of those are optional, insofar as the type checker just tries to infer types but does not depend on a conclusive result. What is more, the pluggable type systems themselves do not have to care about type inference -it emerges from our model of type systems and does not restrict expressiveness within that model.

Type inference for local variables is not particularly novel or interesting, so we will only discuss our approach to return type inference here.

Return Type Inference. When the returned result of a message send is used, the type checker needs to make a useful assumption about the return type of the message. Again, Smalltalk's dynamic properties make it impossible to know which method will actually be invoked at runtime. So we use the same rules as with argument type checking described in Section 3.2 to get a set of methods to be considered. The return type of the message is then the union of all return types of those methods.

If a method was not annotated with a return type, its return type is by default considered to be the top type. But to improve the quality of type checking and comply with the requirement to infer as many types as possible, the type checker will try to infer the return type of an unannotated method. Inference basically works the same way as type checking (implementation-wise it is in fact identical): we walk the AST of the method and keep track of the types of AST nodes. The inferred return type simply becomes the union of the types of all return statements in the method. If the method's last statement is not a return statement, the type defined by the type system for self is also part of this union since by default Smalltalk methods return self.

When inferring the return type of a method the result can obviously be improved by inferring the return types of message sends within that method as well. In fact the inferencer could drill even deeper and walk the whole graph of method calls to make the result as precise as possible. This is not realistic for performance reasons, so we limit the inferencer to an inference depth. It defines how deep the inferencer looks into the call graph.

Increasing the inference depth is very costly in terms of performance, since the total number of methods considered grows very fast. While using TypePlug with real world code we discovered that 3 is about the highest tolerable inference depth. We use various caching strategies to improve performance, but in general inferred return types can't be kept in a cache very long because the conditions that lead to a cache invalidation are very costly to detect, especially with a high inference depth (i.e., when the the return type annotation of a method changes, the inferred return types of all its callers might change).

The Impact of Return Type Inference. To assess the impact of return type inference, we carried out the following experiment. In a stock Squeak image without any explicit type annotations we tried to infer the return type of all methods of classes in the category Files-Directories. This category contains Squeak's abstraction of file system directories, with a total of 8 classes with 210 methods. This serves as an example of a typical small package of user code that one would want to type check.

In the second stage of the experiment, we added as many return type annotations to methods of the Object class as possible. Object is the base class for almost all other classes in Smalltalk; it implements some heavily used methods such as = (equality), class and copy, so annotating those should improve return type inference (because overridden methods inherit types from superclasses). With this small set of type annotations we again tried to infer all return types in the Files-Directories class category We used an inference depth of 1, meaning that the type inferencer is allowed to dive one level deep into messages used in an examined method, but not further. We ran this experiment for both the non-nil and the class-based type system (discussed in Section 4.1). The results are summarized in Table 2.

In both type systems, for about 31% of all methods the return type could be inferred even without any type annotations present in the image. This shows that return type inference does add significant value to the system as a whole, since in this package for more than 30% of methods explicit return type annotations are not even needed. 39 methods (19% of all methods) do not contain a return statement, so their return type is trivially inferred to be the type of self.

With type annotations for Object, inferred return types are about 3% more for the non-nil type system and 5% more for the class-based type system. This improvement is quite impressive considering that only a few annotations were added to Object. These results suggest that the cumulative effect of additional annotations to other commonly used classes such as numbers, strings and collections should be good.

Programming Environment Integration

In Smalltalk IDEs, browsers are traditionally used to navigate and modify the source code in an image. Part of TypePlug is a type browser for Squeak, a browser that enhances a standard browser with some type-specific behavior. The type browser has three main features: it integrates type checking, it provides an alternative way of introducing type annotations without changing source code (external type annotations) and it exports types to a distributable form.

Fig. 1. The Type Browser

Figure 1 shows the type browser in action. Compared to a standard browser, the type browser has an extra panel to the right of the list of methods. This panel shows the method type of the currently selected method, i.e., its argument and an up arrow (↑) to represent the return statement, including types if there are type annotations. Selecting one of these types brings up the type in the bottom (source code) area of the browser where it can be edited.

External Type Annotations. For a type system to support useful type checking it is often necessary to annotate at least a minimal set of methods of the standard Smalltalk classes with types. For example, you may want to annotate the return type of the hash method of Object with a nonNil type. But normally it is not a good idea to add such an annotation by modifying the source of a method. Redefining methods in standard classes such as Object works well locally in an image, but problems arise when the code or the types should be packaged up for distribution, reside in a version control system, or undergo any other form of migration between images.

To address these issues, the type browser offers a way to add external type annotations which are separate from the source code of a method. External types can simply be added and modified through the extra types panel of the browser, which registers types with an external cache but does not change the source code of a method. Additionally, the type browser offers the option to export the types of all methods of a class, including both external and in-source types. Exported types of several classes can easily be bundled, distributed and imported into any image.

The external type annotation support of the type browser is an important tool for the development and use of pluggable type systems. It allows developers of a type system to distribute a set of types for a Squeak base image, but it also allows other parties to create and distribute type packages for arbitrary type systems.

Case Studies

In addition to the non-nil type system presented in Section 2, we used TypePlug to implement a class-based type system and a confinement type system. We present in some detail the first of these, and briefly summarize our experience with the second.

A Class-Based Type System

We use TypePlug to implement an expressive class-based type system, sporting many features of modern statically typed languages. It supports generic types, polymorphic methods, type unions and typed blocks. The syntax for type annotations in this system is summarized in Table 3. This is expressive enough to meaningfully annotate most Smalltalk code with class-based types. Table 3. Grammar for class-based types

The type of instances of a class is simply the name of that class, e.g., booleans and integers have the types Boolean and Integer respectively. Classes themselves (as opposed to their instances) have a type, too. Such a class type is formed by appending class to the name of the class, e.g.,Boolean class for the type of the class Boolean.

We will not discuss all other kinds of types in detail. Instead we will look closely at the important subtyping relation and the polymorphism features of the type system.

Subtyping. The usefulness of a class-based type system such as this one depends largely on the definition of subtyping. Smalltalk code in general is not well suited to be typed using classes. For example, classes might override methods while breaking assumptions about types made in the superclass, and other classes might "delete" methods defined in superclasses. All of these things function well considering Smalltalk's dynamic properties, but are not readily compatible with the notion of subtyping.

On the basis of these considerations we define a subtyping relation that is based on the type interface of a class. We define this to be the set of class method types that have some type annotation (a method type is a method's name with its argument and return types). Table 4 demonstrates this with an example. The type interface of the type Fruit is the method type of mixWith: (with argument Fruit and return type Array E: Fruit) plus of course any method types inherited from superclasses. isVegetable is not part of the type interface since it does not have any type annotations.

The definition of our subtyping relation consists of two clauses. The first clause forms the basis for the relation with a standard contravariant definition for structural subtyping:

1. Type A is a subtype of type B if the type interface of B is a subset of the type interface of A and for all method types mB of the interface B and the corresponding method type mA of the interface A it is true that: the argument types of mB are subtypes of the respective argument types of mA and the return type of mA is a subtype of the return type of mB.

Taken in isolation, this is a standard subtyping relation from the literature (e.g., [12, page 182]) based on structural interfaces, using the usual contravariant subtyping rule for arguments.

According to this first clause, in the fruit example from Table 4 it is clear that both types Apple and Orange are subtypes of the type Fruit; their type interface contains the (inherited) mixWith: method with types. Also, more surprisingly, the Apple and Orange types are both subtypes of each other -their type interfaces are identical since they both implement an annotated color method.

There is one obvious problem with subtyping based only on the above first clause: if this were the complete subtyping rule then every simple type would be a subtype of every other simple type in a codebase without any type annotations. This would not be useful, which motivates the second clause of our definition: 2. We consider the type B of the class B which is a subclass of A. If the type interface of B is identical with the type interface of A (i.e., the methods of class B do not add or change any type annotations compared to A), then the type B has no subtypes except itself.

This means that for types based on classes that do not define any typed methods, subtyping is based on type identity only.

This rather unusual subtyping definition has some interesting implications. First, thanks to the second clause, it works well with untyped classes. Second, it puts a lot of responsibility into the hands of the programmer who makes type annotations. For example, a newly created class is not a subtype of its superclass. The programmer must add at least one method with a type annotation to 4. Fruit bowl code the new class (while not violating subtyping rules) to make the new class a subtype of its superclass. In general, to get subtyping relations in a class hierarchy, type annotations must be added to all the classes in the hierarchy that should participate in the subtyping relation.

Genericity. Generic types are types parameterized by at least one named type parameter. A generic type parameter consists of a name followed by a colon and the type it should be bound to. A typical example of generic types are collections, e.g., the type of an OrderedCollection. This type has a single parameter E referring to the type of the elements of the collection. An OrderedCollection of integers then has the type OrderedCollection E: Integer.

In the context of a class with a generic type, type parameters can be used just like any other type: the type Param E refers to the type that the parameter E takes in a generic type. By using a type parameter in any method a type implicitly becomes generic, i.e., there is no explicit declaration of type parameters. For example, the type of an OrderedCollection is generic because the parameter Param E appears in the methods of the class OrderedCollection, e.g., as the argument type of the add: method.

Apart from type parameters with class scope as used in generic types, our class-based type system also supports type parameters with method scope. Methods making use of such type parameters are polymorphic methods. The quintessential and most simple example of a polymorphic method is the id: method which takes an argument and does nothing but return that argument again. To type id: we can give its argument the type MethodParam A, a type parameter named A with method scope. As the return type of id: we use the same type parameter again, MethodParam A. This expresses that we expect the return type of id: to be the type of its argument.

During type checking of code invoking a polymorphic message, the type checker infers the value of all type parameters from the type of the concrete arguments passed (in the type system implementation, this is achieved via the hook method transformMethodType:...).

An interesting example of a polymorphic method is ifTrue:ifFalse: in the class This example demonstrates that polymorphic methods are needed to type some crucial innards of Smalltalk and also illustrates block types.

A Confinement Type System

As an example very different from the non-nil and class-based type systems we defined a confinement type system. This type system implements a very specific kind of confinement: confined instance variables. References to mutable objects such as a collection are often considered to be private to a class when they are stored in an instance variable; these references should not be shared with other classes. The confinement type system can guarantee that such confined instance variables do not leak from their class and thus are not modified outside their class. In Smalltalk, all instance variables are always private, encapsulated by the instance. In a way, this type system expresses an extended form of privateness for instance variables.

The confinement type system demonstrates how TypePlug enables type systems with fairly complex semantics to be implemented succinctly. The implementation consist of only 4 classes with a total of about 110 lines of code.

This type system exploits TypePlug's type inference in an unusual way: whether a method possibly returns a confined reference is determined only by return type inference, not by explicit return type annotation. Confined type annotations are added only to instance variables. During type checking, type inference automatically takes care of analyzing the flow of these confined references through methods.

A further interesting aspect concerns the unconfined types supported by our confinement system. Unconfined annotations are a pragmatic tool for a programmer to signal to the type checker that he knows the annotated expression does not evaluate to a confined value. The confinement type system is conservative in that it considers the result of any message sent to a confined reference to be confined as well. But some methods (such as copy to copy an object) will always return new and thus unconfined references. The return types of such methods can be annotated with an unconfined type. Unconfined types effectively "override" the effect of confined types-this use of overriding could be a pattern useful in other type systems.

For further details, consult the full report on TypePlug [START_REF] Haldimann | TypePlug -pluggable type systems for Smalltalk[END_REF].

5 Discussion and Related Work

Reflection and Exceptions

In a dynamically-typed language like Smalltalk there are programming idioms that our type checker simply is not capable of handling. We discuss two problems of our approach: typing code that uses the reflective features of Smalltalk and exception handling.

Reflection. Static type checking is about deducing static properties of a system before it is run, whereas reflection (not just introspection) means changing the structure and behavior of a system at runtime. Typing reflective systems thus poses many problems [START_REF] Alanko | Types and Reflection[END_REF].

The perform: method is used to send a message to an object with the message name determined at runtime. It takes a message name as its argument and sends that message to the receiver. The return type depends on the value of the argument which in general is not known statically, so there is no way to reasonably type check a perform: message, its arguments and its return value. However, in many cases we can add an explicit type cast to a perform expression, thus providing the type checker with the information needed to check a perform expression.

The doesNotUnderstand: idiom poses a more severe problem for our type checking algorithm. The doesNotUnderstand: method allows classes to intercept runtime errors occurring when a message was sent that is not understood by the receiver. This means any object possibly accepts a message sent to it even though its class does not explicitly implement a method of the same name. This is a problem because type checking by default assumes that it can find all implementors of a given message name. To avoid false positives when type-checking, the only recommendation we can make is to avoid this idiom in areas of code that should be type safe.

Exceptions. TypePlug currently does not model exceptions. In general, every message send in Smalltalk could result in an exception being signaled. The concept of exceptions is fortunately orthogonal to our notion of type safety. For our purposes, if an exception is signaled it simply means that the execution of a method stops at that point; it does not in any way affect the types of variables or other expressions. TypePlug simply does not deal with exceptions at the moment, not diminishing the usefulness of type checking.

Related Work

In the following, we give an overview of related work. After a short presentation on relevant general work on type systems and type inference in the context of Smalltalk, we focus on related work on pluggable type systems.

Type Systems and Type Inference for Smalltalk. Smalltalk as a practical dynamically typed system has seen many proposals for adding static type systems [START_REF] Borning | A type declaration and inference system for Smalltalk[END_REF][START_REF] Johnson | Type-checking Smalltalk[END_REF][START_REF] Graver | Type-Checking and Type-Inference for Object-Oriented Programming Languages[END_REF][START_REF] Palsberg | Object-Oriented Type Systems[END_REF]. The most recent effort at conceiving and implementing a practical type system for Smalltalk was Strongtalk [START_REF] Bracha | Strongtalk: Typechecking Smalltalk in a production environment[END_REF]. Some of these type systems support optional typing, but they provide just a single type system, not addressing pluggability.

Type Inference was originally researched in the context of functional languages [START_REF] Milner | A theory of type polymorphism in programming[END_REF]. Type inference then was applied to Smalltalk [START_REF] Suzuki | Inferring types in smalltalk[END_REF]. Palsberg and Schwartzbach presented the first algorithm that can type check completely untyped Smalltalk code [START_REF] Palsberg | Object-oriented type inference[END_REF]. The Cartesian product algorithm (CPA) by Agesen [START_REF] Agesen | Concrete Type Inference: Delivering Object-Oriented Applications[END_REF] provides a substantial improvement in both precision and efficiency. Even with this advanced algorithm, type inference does not scale to larger programs. Efficiency and scalability thus is a focus of current research. Demand-driven type inference (DDP) [START_REF] Spoon | Demand-driven type inference with subgoal pruning: Trading precision for scalability[END_REF] provides scalability by analyzing type information on demand and selectively reducing precision. RoelTyper [START_REF] Wuyts | RoelTyper, a fast type reconstructor for Smalltalk[END_REF] uses heuristics for providing type information of instance variables. RoelTyper, like DDP, provides high performance at the cost of reduced precision.

Pluggable Type Systems. Pluggable type systems were originally proposed by Gilad Bracha [START_REF] Bracha | Pluggable type systems[END_REF]. A number of implementations of pluggable type systems have been published.

JavaCOP [START_REF] Andreae | A framework for implementing pluggable type systems[END_REF] is a program constraint system for implementing practical pluggable type systems for Java. The authors present a framework that allows additional types to be added to Java source code, based on Java's annotation facilities. They then define a declarative, rule-based language that can express rules as constraints on AST nodes, making use of the information from annotations as well as from Java's static type system. These rules form the semantics of pluggable type systems and can be enforced by a type checker that hooks into the compile process.

Annotations in JavaCOP are similar to TypePlug's, but are restricted to class and variable declarations by the Java language, so something like our casts on arbitrary expressions cannot be supported. The way type systems are implemented with rules in a domain-specific language is very different from TypePlug's type system model. The rule language enables very fine grained control over type checking. The authors prove the validity and versatility of this approach by implementing an impressive number of pluggable type systems, ranging from confined types to reference immutability and checks of the kind usually done by coding style analyzers. On the other hand, our approach with a rather fixed type checking algorithm and customization is arguably a bit simpler and results in simpler implementations at least for some applications. For example, our nonnil type system is extremely simple with about 30 (mostly very trivial) lines of code while JavaCOP's equivalent presumably needs several non-trivial rules. JavaCOP does not provide any special support for working with untyped legacy code.

Fleece [START_REF] Allwood | Fleece, pluggable type checking for dynamic programming languages[END_REF] also explores the notion of pluggable type systems, but explicitly for dynamically typed languages. As an example of a dynamically typed language the report introduces and defines R sub , a subset of the Ruby programming language, which is then used throughout the report. It develops the notion of annotators that automatically add and propagate annotations (types) on nodes of the AST of a program. A special case of an annotator is the programmer who can manually add annotations to a program. Fleece's handling of annotations correspond in many aspects to TypePlug's. Automatic annotators play the role of the inference part of TypePlug's type checking.

Compared to TypePlug, Fleece is both more general and more restricted. It is more general, because it is independent of the language R sub ; it copes with any other language that can be expressed in the grammar form that it expects. However, it is more restricted because it has not been shown to handle a real dynamically typed language. R sub is a very restricted form of Ruby with, e.g., no inheritance or support of the standard library. The feature that distinguishes TypePlug is the ability to pragmatically work with an actual full implementation of Smalltalk, thus supporting type-checking of legacy code.

JastAdd, an extensible Java Compiler, has been extended with a pluggable type system by Ekman and Hedin [START_REF] Ekman | Pluggable non-null types for Java[END_REF]. The paper presents only one type system, a non-nil type system similar to that of TypePlug. Of all three discussed other frameworks, it is the only one which provides support for reducing the number of annotations needed when dealing with untyped legacy code. It supports inference of non-null types, but it does not allow for type annotations without changing the source code.

Conclusion and Future Work

TypePlug is intended to offer a very pragmatic framework for implementing pluggable type systems. New type systems are defined by specializing the TP- TypeSystem class and overriding the methods for subtyping and type unification. TypePlug makes it relatively easy to obtain the benefits of a pluggable type system even if the underlying legacy code base remains largely free of type annotations. This is achieved by (i) only type-checking annotated code, (ii) using static type information and limited type inference to reason about unannotated code, and (iii) externally annotating third party code. Explicit type casts can also be used to avoid annotating code that is known to be safe.

We have made experience with three very different kinds of type systems, including a classical class-based type system, a non-nil type systems and a type system for confined types.

There are numerous further directions to explore. Presently TypePlug does not take exceptions into account. Type inferencing is quite slow, and inferencing beyond a depth of 3 levels is unpractical. We plan to integrate modern type inference algorithms and a heuristical type analysis system in the spirit of Roel-Typer.

An interesting field for future research is to explore type checking in the presence of reflection, especially how to type check a system that can be changed reflectively at runtime. It would also be interesting to explore ways of adding optional run-time type checks by making further use of the Persephone framework for sub-method reflection, thus complementing TypePlug's static type checking. Pluggable type systems might be able to benefit from information provided by any other pluggable type system, rather than just the built-in static type system. This sharing of type information is another direction to consider.

  is: aType subtypeOf: anotherType ↑ (self isNilType: aType) and: [self isNilType: anotherType] unifyType: aType with: anotherType ↑ ((self isNilType: aType) and: [self isNilType: anotherType]) ifTrue: [self singleType] ifFalse: [self topType]

  Class class (Class-side type) Type | Type (Union type) Block args: {Type*} return: Type (Block type) Class (ParamName: Type)+ (Generic type) Param ParamName (Type parameter) MethodParam ParamName (Type parameter)

class

  Fruit subclassing: Object mixWith: aFruit <:type: Fruit :> ↑ (Array with: self with: aFruit) <:type: Array E: Fruit :> isVegetable ↑ false class Apple subclassing: Fruit color ↑ (Color red) <:type: Color :> class Orange subclassing: Fruit color ↑ (Color orange) <:type: Color :> Table

  <:type: Block args: {} return: MethodParam R :> ifFalse: anotherBlock <:type: Block args: {} return: MethodParam R :> ... ↑ (...) <:type: MethodParam R :>

Table 1 .

 1 Methods of TPTypeSystem to override in subclasses

	systemKey	unique key for this system. Defined as class
		method.
	annotationValueToType:inContext: converts annotations to types. Abstract, must
		be overridden.
	is:subtypeOf:	defines the subtyping relation. Abstract, must
		be overridden.
	unifyType:with:	defines the type unification operation. Ab-
		stract, must be overridden.
	typeForArray:	maps arrays to types.
	typeForBlock:	maps blocks to types.
	typeForGlobal:value:	maps global variables to types.
	typeForLiteral:	maps literals to types.
	typeForPrimitive:	maps primitives to types.
	typeForPrimitiveNamed:module: maps named primitives to types.
	typeForSelfInClass:	maps self pseudo-variables to types.
	typeForSuperInClass:	maps super pseudo-variables to types.
	methodsForMessage:...	customizes the set of methods to be considered
		when type checking message sends.
	transformMethodType:...	transforms methods type before they are used
		in the type checker.
	transformType:...	transforms types before they are used in the
		type checker.
	assignmentTo:...	customizes type checking for assignments
	displayClass:	creates a custom string version of classes.
	displayMethod:in:	creates a custom string version of methods.
	3.1 Defining a Type System
	Persephone. Persephone [9, 10] brings sub-method reflection to Squeak. The
	standard model of Squeak and generally any Smalltalk system does not provide

Table 2 .

 2 Return type inference for class category Files-Directories in a stock Squeak image, version 3.9 final

A trait is a set of methods that can be included in the definition of a class[START_REF] Ducasse | Traits: A mechanism for fine-grained reuse[END_REF].

Acknowledgements

We gratefully acknowledge the financial support of the Swiss National Science Foundation for the project "Analyzing, capturing and taming software change" (SNF Project No. 200020-113342, Oct. 2006 -Sept. 2008).


Marcus Denker
email: denker@iam.unibe.ch

Stéphane Ducasse

Software Evolution from the Field: An Experience Report from the Squeak Maintainers

Keywords: Squeak, open-source, Maintenance, Software Evolution, Tool support

Over the last few years, we actively participated in the maintenance and evolution of Squeak, an open-source Smalltalk. The community is constantly faced with the problem of enabling changes while at the same time preserving compatibility. In this paper we describe the current situation, the problems that faced the community and we outline the improvements that have been introduced. We also identify some areas where problems continue to exist and propose these as potential problems to addressed by the research community.

Introduction

Over the few last years, we actively participated in the development and maintenance of the Squeak open-source project [START_REF] Ingalls | Back to the future: The story of Squeak, A practical Smalltalk written in itself[END_REF]. We were responsible for the the 3.7 and 3.9 official releases and participated in the releases 3.6 and 3.8. During this activity we faced the typical situations that developers are facing daily: bloated code, lack of documentation, tension between the desire of improving the code and providing an unchanging basis for all developers. Furthermore, Squeak suffers from some of the problems of a real open-source project: lack of man-power, distributed development with contributors at multiple locations and lack of long term commitment.

In this paper we present the problems that the Squeak community has been facing and describe the improvements that have been introduced. Moreover we sketch future approaches we would like to put in place. Finally we analyze the open problems and propose these as future research topics that may be of interest to the research community on software evolution. Some researchers analyzed software evolution and its challenges and proposed taxonomy of changes [START_REF] Buckley | Towards a taxonomy of software change[END_REF][START_REF] Mens | Analyzing the evolution of largescale software: Issue overview[END_REF][START_REF] Mens | Challenges in software evolution[END_REF]. There has been other research into open source development and evolution [START_REF] Mockus | Two case studies of open source software development: Apache and mozilla[END_REF]. In this paper we want to give a summary of our own experiences as developers and researchers maintaining a large and complex open-source environment.

First we present Squeak [START_REF] Ingalls | Back to the future: The story of Squeak, A practical Smalltalk written in itself[END_REF] by providing some measurements that characterize it and its evolution. Then we shed some light on the philosophy of Squeak by describing the current forces in the Squeak community and we present the overall development process. We outline the common problems the community has been faced with and the improvements it has adopted both from an implementation and from a more process oriented point of view. Subsequently we present the open problems that still exist. We analyze the opportunities we missed retrospectively and sketch the approach we envision to improve the situation.

Squeak

While the appearance of Squeak may mislead a novice user, Squeak is a really large and complex system containing more than 1600 classes and 32,000 methods in its latest public release (3.8 basic). Squeak includes support for different application domains:

• two large graphical user-interface frameworks, Morphic and MVC,

• an IDE, including an incremental compiler, debugger and several advanced development tools,

• a language core and all the libraries enabling it (both simple and complex) including concurrency abstractions,

• multimedia support including: images, video, sound, voice generation,

• eToy [START_REF] Allen-Conn | Powerful Ideas in the Classroom[END_REF], an advanced scripting programming environment for children,

• various libraries such as compression, encryption, networking, XML support. All this code is part of the main Squeak distribution. In addition to that, there is a growing number of external packages available on the SqueakMap repository (over 600 packages), thus showing the vitality of the Squeak community.

Measurable Facts

The table 1 shows some metrics to give an idea of the size and growth of Squeak. The Squeak community realized that the system is beginning to contain too much unneeded functionality. Hence, in Squeak 3.6 certain functionality such as the web browser and email clients was externalized. In Squeak 3.9, an extensive amount of infrastructural work has been introduced: new language feature (Traits) [START_REF] Schärli | Traits: Composable units of behavior[END_REF], a versioning system (Monticello), a registration mechanism (Services), an abstraction layer for the UI framework (ToolBuilder).

To understand the Squeak development dynamics we have to consider its opensource nature and also to analyze not only its growth, but the actual changes taking place. Indeed some actions (addition and removal of functionality) may result in the numbers of methods and classes remaining constant. One good starting point when considering the evolution of Squeak is to consider the approximate number of patches that have been integrated between releases. These patches vary in size and complexity, so the number can only be taken as a hint of the change that is done:

Communities and Different Agendas

The Squeak.org distribution is used by a wide range of diverse projects. Some of them have their own open-source communities, other are closed research or commercial projects. Here we list the most important projects that are based on the common distribution.

Squeakland. The main focus of this distribution is educators of primary schools.

The main interface is the Etoy system [START_REF] Allen-Conn | Powerful Ideas in the Classroom[END_REF]. Squeakland is widely distributed in Japan and US. The end user does not interact directly with Squeak but the Etoy layer. Code quality, ease of extension, untangling and tested code are not the main focus of development.

SmallLand. It is a community similar in scope to Squeakland: the children are older, and the project directly manages an installed base of its own squeak distribution on 80,000 PCs in schools in Spain. SmallLand has been completely localized in Spanish: one of the largest contributions of this work was the framework for translating Squeak to other european languages, a change that affected a large percentage of the code base. Lot of changes to the graphical user interface were made to support a better desktop. They are concerned with the code quality. Seaside. It is a framework for developing sophisticated dynamic web applications.

Seaside combines an object-oriented approach with a continuation-based one [START_REF] Ducasse | Seaside -a multiple control flow web application framework[END_REF].

Seaside offers a unique way to have multiple control flows on a page, one for each component. This community is concerned with the robustness and scalability of the libraries and the tool support. The design and ease to extend the system is also one of their concerns. This community developed a package and version control system (Monticello), that is used in the latest version of Squeak. This enables the developer to write components that are highly reusable and that can be used to compose complex web applications. Seaside is used by a number of companies for commercial development. Croquet. It is a 3D shared multi-user environment. Users on different machines can use Croquet to explore a three dimensional space together, collaborate and share. Croquet uses a new Peer-to-Peer model for synchronization, allowing the system to function without needing central servers. Tweak. Tweak is a next generation implementation of a UI and scripting system based on the lessons learned with both Morphic and EToys. Tweakers are concerned with code quality but in general are building layers on top or besides the base system.

We have learnt while maintaining Squeak that there are two main driving forces, and this has lead us to coin the phrase 'egocentric syndrome': frequently one group of developers within the community wants to have problems that affect its interests fixed but at the same time demands that no other changes should be made for fear of breaking existing code.

The Squeak Development Process

As with a number of open-source projects, the Squeak community is an opensource movement that lacks real financial support or a sponsoring organization. From its inception to the release 3.4, Squeak was mainly developed by Squeak-Central, a single group of researchers around Alan Kay. From 3.4 to 3.8, the development community grew and became geographically distributed with many developers and small teams.

The general process is the following: the developers produce fixes or enhancements that are sent to the mailing-list and are collected in a central database. Then, the group of maintainers responsible for a given release look at the changes and decide whether to integrate them in the current release.

Common Problems

In this section, we elaborate on some code level problems that face the Squeak community. We are aware that such problems are neither exceptional nor specific to Squeak. Our goal is to document them for researchers who focus on the area of software evolution. The following section shows the improvements that have been applied and an evaluation of the obtained results.

Tangled Code. Historically, and as with any original Smalltalk implementation, Squeak was developed as one single system. The fact that subsystem boundaries were not explicit (for example by means of a package system) leads to a system with a lot of unneeded (and often surprising) dependencies. For example, the compiler depends on the GUI. These dependencies hamper modularisation and evolution: there is a high risk of introducing bugs, as a change in one part of the system can break another unrelated part. Dead Code and Prototype Code. Squeak was originally intended as an environment for prototyping new ideas. Very little effort was spent on refactoring [START_REF] Fowler | Refactoring: Improving the Design of Existing Code[END_REF] and it was never systematically cleaned. Often the experiments and their extensions have remained in the system resulting in dead code and often incomplete functionalities. Evolution Dilemma. The previous problems are minor compared to the evolution dilemma. As multiple stakeholders exist for Squeak, they require that it is a stable basis for development. However at the same time, those same projects also carry out refactorings to improve and bugfix the base system, and by doing they generate instability.

Thus the evolution dilemma is to preserve stability, while at the same time ensuring that it is possible to make changes.

The first two items are what Lehman [START_REF] Lehman | Program Evolution: Processes of Software Change[END_REF] called entropy: The entropy of a system increases with time, unless specific work is executed to maintain or reduce it. The dilemma comes from the fact that reducing the entropy will have impact on the clients using the system.

Language-Level Improvements

One way to address the problem of evolution is by using well-known software engineering techniques and object-oriented design heuristics. [START_REF] Alpert | The Design Patterns Smalltalk Companion[END_REF]. In this section, we give examples of how these techniques were advantageous for Squeak. A challenging problem with most software engineering improvements is that they imply refactoring the system towards a better, more evolvable architecture. Hence we need to change the system to facilitate future changes.

Deprecation

Deprecation mechanisms are a well known technique to allow for gradual adoption of new interfaces. The idea is that all public methods that are no longer needed (e.g., because of adopting a new, different API) are not deleted immediately. Instead, a call to the deprecation method is added with the indication to the user that another method should be used:

Month>>eachWeekDo: aBlock self deprecated: 'Use #weeksDo:'. self weeksDo: aBlock

This method raises a warning in debug mode by calling the #deprecated: method, but allows the original method to execute when in production. In Squeak, deprecated methods are retained for one major release: methods that were deprecated in the development of 3.8 will be removed in 3.9. The usage of the deprecation mechanism decreased over time (Table 3). This could indicate one of two things: it may be an indication that a better mechanism is needed or that the system is in fact stabilizing.

Next Steps. It is not possible to tag an entire class as deprecated. Another disadvantage is that the mechanism as a whole is very course grained: evolution is happening all the time and is not restricted to major releases. Deprecation does not scale towards short cycles of change.

In the future, the authors would like to explore how refactorings could be stored and then be available for automatic replay when a deprecated method is called. We also want to address the issue of deprecation of classes.

Divide and Conquer: Modularizing the System

A large effort is underway to modularize the system. The latest 3.9 beta version is composed of 49 packages excluding tests with an average of 40 classes per package.

Next Steps. The modularization was not driven by advanced analysis [START_REF] Vainsencher | Mudpie: layers in the ball of mud[END_REF]. Having additional tool support to analyze existing dependencies is a first important step.

Registration Mechanisms

Modularization requires that a system be divided into units to be able to be built from a subset of its actual components. In earlier versions of Squeak there were many cases where simple configuration required that the code be changed: for example, when adding a tool, the code that built the menu needed to be extended to handle the new tool. The community successfully applied Transform Conditional to Registration [START_REF] Demeyer | Object-Oriented Reengineering Patterns[END_REF] i.e., registration mechanisms were introduced allowing for registration of new services without having to modify code. This reduced considerably the friction between different tools and facilitated the dynamic loading and unloading of tools.

New Abstractions

Squeak's multiple GUI frameworks proved to overcomplicate the building and maintaining of tools. There were interdependencies between MVC/Morphic and some features are only available in one framework. The solution the community adopted was to build an abstraction layer, named ToolBuilder, representing the common framework elements and to rewrite the tools to use the ToolBuilder framework, which encapsulates the GUI framework used.

Refactorings

A lot of small refactorings were carried out over the recent years, leading to iterative improvements. Some large refactorings were supported such as a complete rewrite of the network subsystem. Large refactorings were possible when the changes did not cross-cut a lot of packages but were localized in one package.

Enabling Changes: Tests

Over the last years unit testing has gained a lot of recognition, as it facilitates change [START_REF] Beck | Extreme Programming Explained: Embrace Change[END_REF]. Tests support the developers ability to change code as they can quickly identify the code that they broke as a result of their changes. Squeak has for a long time contained SUnit, a testing framework. However, it took time for developers to recognize the importance of tests and adopt the practice of writing unit tests. To increase the awareness of unit testing, the distribution of Squeak 3.7 included not only the framework, but the tests themselves. This increased the general awareness among Squeak developers. Over the last releases, test coverage increased, with over 6 times more tests in 3.7 than in 3.6, and nearly doubling in later versions (see Table 4).

Next Steps.

Having tests is a first step towards enabling changes and documenting the system in a synchronized way. The next step is to assess the quality of tests using test coverage tools. We plan to use tests to support the development by having a test server providing continuous feedback on the state of the latest versions [START_REF] Beck | Planning Extreme Programming[END_REF].

Process Improvements

Besides strictly technical improvements on the code level, process-oriented approaches have been adopted. The community started to adopt a number of process improvements such as better tools and real bug tracking. Other promising improvements, for example an automated build system, will be implemented in the future.

Better Packaging Tools

Squeak development used to be based on change sets: simple lists of modified or added methods and class definitions. Changesets can be saved into text files and send around (i.e., via email). However, as soon as multiple developers are involved and are required to get synchronized, changesets do not scale: resolving conflicts is very tedious and turnaround time for integration is very large.

In contrast many of todays development systems use elaborate versioning systems like CVS [START_REF] Fogel | Open Source Development with CVS[END_REF]. This inspired the commercial sub community around Seaside to develop a versioning system called Monticello that uses a powerful merge algorithm, and a server, SqueakSource, that projects can use for managing and storing their code base in a distributed setting.

SqueakSource and Monticello have been proven to be very successful. Squeak-Source counts over 420 registered projects and 480 developers. Several sub communities started to have their own SqueakSource servers to manage their projects. Starting with the development cycle for 3.9, Squeak uses a dedicated SqueakSource installation and Monticello for managing the complete squeak code base.

Next Steps. Having packages that are first class entities and better tool support for packages is desirable.

Bug tracking

Earlier releases of Squeak were developed without any provision for bug-tracking. Naturally the Squeak community were faced with the problem of managing bugs: users did discover bugs, developers offered fixes, some of which were included in the next release. But there was no control over how many bugs had been identified, or to monitor whether or not they had been fixed, or in fact what the general overall state of Squeak was. This situation has been improved with huge success: Over 2500 bugs have been reported using Mantis [START_REF] Mantis | [END_REF], a web-based bug tracking system.

Future improvements

We have learned from experience that we should have invested more time and effort in tools that would support the development process of Squeak. Our goal now is to actively address this. Automatic Build tools. Currently, the task of merging changes is labor-intensive and time-consuming. A goal is to leverage an automatic build system to eliminate all the tedious work that currently face maintainers. Automatic build systems are a well known technique and will be a valuable addition to the set of tools for Squeak development. Integration with an automatic test server is another major aspect of the build system that will have to be tackled. Automatic test runs. Unless tests are run frequently, they are not very useful. Currently executing the entire testsuite takes well over 10 minutes, thus discouraging developers from running tests. We propose to solve this with a server that runs all the tests automatically, at least once a day, and sends reporst to the developers. Such a server is currently in development. Even better tools. The current tools represent improvement in the development process of Squeak, but they need to be improved even further: e.g., the response time of Monticello is slow for large code bases.

Language Design Dreams

Apart from our involvement in the maintenance and evolution of Squeak, we are primarily language design researchers. We try to step back from our research background and avoid to mix experiment in language design with robust, scalable solutions.

While we are skeptical that the complex problem of enabling smooth but fast evolution of a large system can be solved by just adding a couple of new language features, we think that new language features are a very promising field for future research on software evolution: How can a language [START_REF] Nierstrasz | Supporting software change in the programming language[END_REF] support change and evolution?

Here is a list of challenges for the software evolution researchers.

Better support for modularity. While Squeak now has a package mechanism, it does not have a real module system. Packages are only deployment time and code management artefacts. Squeak packages do not include any notion of visibility (contrary to Java packages) [START_REF] Bergel | Analyzing module diversity[END_REF]. It would be interesting to evaluate how a module system, by providing a scoping mechanism, could help to better structure the system. History as a first class objects. Squeak is a reflective language [START_REF] Foote | Reflective facilities in Smalltalk-80[END_REF]: e.g., classes and methods are objects, the system has a complete, object-oriented description of its own structure, available for introspection and change.

We would like to understand the costs of extending this reflective model to take into consideration the data that is important for evolution: the history of the system should be represented as a first class entitiy [START_REF] Gîrba | Modeling History to Understand Software Evolution[END_REF]. Having first class history should support the possibility to express the following questions: Why was this method changed? What else has changed when this method was changed? When did this test break for the first time? Which change affected the performance of the system? Beyond Deprecation. Deprecation, as described earlier, does not really help with the evolution problems the Squeak community faces: the problems is that some clients may want to migrate to a new release but only incrementally for certain parts of their applications. If we have the complete history of the system available, do we really need to force clients to use the latest version only? Would it be possible to have different clients using at the same time different versions of the same components? The operating systems offer the possibility to specify which library version to use. Can such a model be realized at the level of a programming language so that multiple versions are able to co-exist?

Conclusion

The evolution of Squeak with its diverse community of developers and open issues ( i.e., decentralized development, modularization need) is a challenging task. The Squeak community achieved lot of progress over the last years such as a first cut at modularizing the system and the increase of unit tests. However, apart from environment enhancements such as Monticello few tools have been built to analyze the code base of Squeak. We have identified the need for them to help improving the system. In addition, over the last few years, we have experienced the problems of having to introduce changes while at the same time supporting stability for existing users. We highlight the fact that there is no language support for the notion of evolution in todays programming languages. Current languages are only capable of describing one version of the system. Scoping changes and allowing multiple versions while retaining a simple language is an open challenge that the research community is facing.

Acknowledgments.

We gratefully acknowledge the financial support of the Swiss National Science Foundation for the project Recast: Evolution of Object-Oriented Applications (SNF 2000-061655.00/1) and french ANR for the Cook: rearchitecturing object-oriented applications. The authors would like to thank all the Squeak developers and Orla Greevy and Adrian Lienhard for the reviews on the early versions of this paper.

" (SNF Project No. 2000-067855" (SNF Project No. 620-066077, Sept. 2002 -Aug. 2006). 4 Ducasse gratefully acknowledges the financial support of the French National Recherche Agency (ANR) the project "Cook: Rearchitecturing Object-Oriented Application 2005-2008".