Alexandre Bergel

Christophe Dony

Stéphane Ducasse

Prototalk : an Environment for Teaching, Understanding, Designing and Prototyping Object-Oriented Languages

With prototype-based languages, concretization and abstraction are unified into a single concept a prototype. Prototype-based languages are based on a simple set of principles: object-centered representation, dynamic reshape of objects, cloning and possibly message delegation. However, they all differ in the interpretation and combination of these principles. Therefore there is a need to compare and understand.

In this paper we present Prototalk, a research and teaching vehicle to understand, implement and compare prototype-based languages. Prototalk is a framework that offers a predefined set of language data structures and mechanisms that can be composed and extended to generate various prototype-based language interpreters. It presents a classification of languages based on different mechanisms in an operational manner.

Introduction

Born at the end of the eighties [START_REF] Borning | Classes versus prototypes in object-oriented languages[END_REF][2][3] [START_REF] Lalonde | Designing families of data types using exemplars[END_REF], and influenced by frame and actors languages, prototype-based languages propose an object-oriented model based on the object as the sole entity of structure and computation. The prototype paradigm and the semantics of its main aspects have been declined into several variations. In the first age of prototype-based languages, research languages such as Self [START_REF] Ungar | Self: The power of simplicity[END_REF] [START_REF] Ungar | Organizing Programs without Classes[END_REF], Agora [START_REF] Steyaert | A marriage of class-and object-based inheritance without unwanted children[END_REF] [START_REF] Meuter | Agora: The story of the simplest MOP in the world -orthe sche me of object-orientation[END_REF], Kevo [START_REF] Taivalsaari | Delegation versus concatenation or cloning is inheritance too[END_REF], Obliq [START_REF] Cardelli | A language with distributed scope[END_REF], Garnet [START_REF] Myers | Garnet: Comprehensive support for graphical highlyinteractive user interfaces[END_REF], Moostrap [START_REF] Mulet | Towards a methodology for explicit composition of metaobjects[END_REF],

Email addresses: bergel@iam.unibe.ch (Alexandre Bergel), dony@lirmm.fr (Christophe Dony), ducasse@iam.unibe.ch (Stéphane Ducasse). [START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF] and ACT-1 [START_REF] Lieberman | Using prototypical objects to implement shared behavior in object oriented systems[END_REF] [START_REF] Lieberman | Delegation and inheritance: Two mechanisms for sharing knowledge in object-oriented systems[END_REF] have been developed and others such as NewtonScript [START_REF] Smith | The newton application architecture[END_REF] [14] and GlyphicScript have been used in industrial setting.

While the concept of prototype which results from a desire for simplification and unification seems simple at first glance, prototype-based languages come with different models and mechanisms in key language aspects: knowledge representation, object creation and modification, information sharing, message delegation, method lookup. The Treaty of Orlando was the first attempt at defining more clearly the notion of prototypes and as such acknowledged that understanding the differences and grouping was needed [START_REF] Stein | A shared view of sharing: The treaty of orlando[END_REF]. Later on, various studies have proposed taxonomies and analyses to explain and compare the mechanisms and bring to the fore problems [START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF] [8] [START_REF] Steyaert | A marriage of class-and object-based inheritance without unwanted children[END_REF] [17] [START_REF] Bardou | Split objects: a disciplined use of delegation within objects[END_REF] [START_REF] Dony | Classification of object-centered languages[END_REF]. Figure 1 presents a first taxonomy based on five basic criteria [START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF]. Most of the languages mentioned in the taxonomy are implemented in Prototalk. Along this paper references to languages named like L1 or L5 refer to the one classified in Figure 1.

Today new prototype-based languages are continuously appearing. Lua [START_REF] Ierusalimschy | Lua -an extensible extension language[END_REF] is used as a light scripting language. JavaScript with its prototypical instance is still the web-client programming language [START_REF]ECMAScript Language Specification[END_REF] [START_REF] Flanagan | JavaScript: The Definitive Guide, 2nd Edition[END_REF]. More recently IO, a new and extremely compact language with NewtonScript's double inheritance [START_REF]Io home page[END_REF], Pic% [START_REF] Wolfgang De Meuter | hondt, Pic% intersecting classes and prototypes[END_REF] a new prototype language with mixins, Slate a mix between Smalltalk and Self [START_REF] Ungar | Self: The power of simplicity[END_REF] and Prothon [START_REF]Prothon home page[END_REF] a mix between Python and Self have been released. New areas such as mobile and distributed applications [START_REF] Dedecker | Using the prototype-based programming paradigm for structuring mobile applications[END_REF] are discovering the potential benefits of prototype-based languages or of some of the mechanisms or aspects they advocate. Therefore the diversity of prototypebased languages has been and is again quite real. Comparing these languages, being able to design alternative ones, by plugging together adequate aspects, being able to check how far some aspects are compatible is a challenging and useful task since language facets can interact.

The paper presents Prototalk, a framework for implementing interpreters for various prototype-based languages by specializing and composing existing components. The goal of Prototalk is twofold: Firstly, it supports the understanding, classification or teaching of existing languages in a syntactically uniform environment. Second it helps designing and testing new languages.

Prototalk follows the approach "by construction" promoted by Actalk [START_REF] Briot | Programming with explicit metaclasses in Smalltalk-80[END_REF] and ObjVLisp [START_REF] Cointe | Metaclasses are first class: the objvlisp model[END_REF] where concurrent languages or reflective class-based ones are decomposed and built from scratch. Like ObjVLisp and Actalk, Prototalk is also an open pedagogical laboratory used to teach object-oriented development. Enabling students compose or design their own language in a concrete way and get an executable language is a pedagogical advantage. This article is structured as follows. Section 2 presents the goal and the design decision, from the research and pedagogic point of views, that motivated the initial need of a platform to model prototypes-based languages [START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF]. Section 3 describes the architecture of the framework and shows how the Self and NewtonScript language can be simulated. Section 4 presents the bases for programs interpretation. Section 5 details the step to integrate a new interpreter in the platform. An interpreter for NewtonScript is presented. This language introduced the idea of having two inheritance hierarchies based on two kinds of parent links. Section 6 presents an evaluation of the use of Prototalk.

Goals and Design Decisions

While designing the Prototalk platform we had the following goals in mind:

(1) Uniformity: The first objective has been to establish an operational semantics for the basic primitives of the basic prototype-based languages and to to unify the languages description to achieve easy comparisons. (2) Minimality: In the tradition of ObjVLisp, Classtalk and Actalk, we wanted through a minimal kernel to express the most general semantics of prototype-based languages, (3) Extensibility: We wanted Prototalk to be a framework so that new lan-guages simulation can be integrated efficiently and easily. (4) Usability: We didn't want to restrict our system to a semantic model and a raw implementation but we wanted it to be a fully usable environment, including dedicated browsers and inspectors, to achieve actual experiments with prototype-oriented programming.

Prototalk has been initially conceived and used for research purposes but has rapidly been used for pedagogical purposes to teach object-orientation and program interpretation. Its implementation uses all important objectoriented concepts and techniques. It is a framework composed of three main class hierarchies that also uses the Interpreter design pattern. Besides, one of the most interesting points is that it is not so obvious for a student to understand how a class can describe the structure and behavior of objects of a classless world or what distinguishes primitive methods from user-defined methods.

The Prototalk Architecture

In Prototalk, a prototype language is represented by an object model class which implements all the language primitives and prototype internal representation (See Section 4.2). In addition, the object model class related to a dedicated program node builder which is responsible for emitting the abstract syntax tree of the program (see Figure 2). Programs written in Prototalk are parsed by the Smalltalk parser that generates an abstract syntax tree (AST). The nodes composing this tree are specified by the program node builder associated with the object model. The resulting abstract syntax tree is used to interpret a program following the Interpreter Design Pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF].

Prototalk is a framework that can be used at different levels: At the most basic level a user can experiment with languages by combining existing object models provide by Prototalk and existing interpreters. For example, a language L1 making a distinction between the variable and method representation and supporting encapsulation of the variables is created by executing the following expression: to the taxonomy presented in [START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF] and in Figure 1. We illustrate these steps in Section 5. Now we present the core elements of the Prototalk architecture.

Object Model Class

For a given prototype language, the object model class has the following responsibilities: (i) it executes programs written in this language by invoking an interpreter on the program nodes, (ii) implements new concepts of the prototype language such as methods or variables lookup, (iii) represents in the Smalltalk memory prototypes created at runtime within a program, and (iv) provides predefined objects such as the empty prototype PRoot or namespace for prototypes.

Executing. A program written in a prototype language is executed by invoking the method evaluate: sourceCode implemented on the class side of the object model class implementing the corresponding language. This method is the starting point of the program interpretation which is based on the Interpreter design pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]. The argument passed to this message is the source code of the program to be executed. The return value of this method execution is the result of the very last statement specified in the program.

The object model class defines all the concepts for a specific prototype language. However, it delegates to the program node builder the responsibility to assemble a program representation that will then be interpreted (see Section 3.2). A dedicated program node builder is associated with an object model class by the method nodeBuilder. Figure 3 shows a part of the program node builder hierarchy defined in Prototalk.

Prototype Language

Primitives. An object model class gathers the different concepts defining the prototype language by implementing primitives related to the following aspects:

• Object variable and method management. An object model class has to provide the necessary primitives (i) to add or retrieve methods or variables (e.g., addMethod: code, addVar: name, or addSlot: name) and (ii) to perform some basic object creation operations (e.g., clone or newEmtpy). These primitives are implemented as instances methods defined on the object model class.

• Method Lookup and Delegation. Primitives related to message sending and delegation have to be implemented by the object class model through the method methodOwner: name. This method returns the prototype owner of the method name. It defines the lookup semantics. Traditionally it follows the chain of parents objects. This method can be specialized in order to simulate other behaviors such as multiple-parents or double inheritance (Section 5.1).

The method AbstractProto class addPrimitivesOn: defines the primitives that are shared by all the prototype languages. By default any prototype can be cloned, printed and saved in textual format. The method #clone is defined when the structure of the prototype is defined. For example the class SlotProto which unifies variables and methods into slots redefines the primitive #clone.

The language L7AndImplicitDelegation which introduces the concept of parent adds two primitives #newSon and #parent.

AbstractProto class addPrimitivesOn: aRoot aRoot addPrimitiveNamed: #clone. aRoot addPrimitiveNamed: #printOn:. aRoot addPrimitiveNamed: #fileIn:. ˆaRoot Predefined Prototypes. Often predefined objects such as the default object to be cloned have to be provided to properly build programs. Usually such a root object offers primitives (cloning, adding variables or methods, . . . ) accessible to all of its children. For instance the PRoot object is created by the method createRoot defined on the class AbstractProto.

For a given language, PRoot is contained in the global environment and it provides a prototype normally intended to be the root of the object hierarchy.

Abstract Syntax Tree and Program Node Builder

The method evaluate: sourceCode implemented on the object model class calls the Visualworks Smalltalk parser to generate the abstract syntax tree (AST) of the program source code passed as argument. This AST is composed of nodes obtained from the program node builder associated with object model class. Each language L in our platform is associated with program node builder class that determines, via a set of methods, which kind of interpreter program nodes represent an L expression. This is a hook offered by the Smalltalk compilation framework to specialize the generated AST. The class ProgramNode-Builder is implemented by the Smalltalk compilation framework. This class emits specific AST nodes when the parser requests it. It offers a common protocol that can be specialized to get different ASTs from the same or different source code. For example, the ProgramNodeBuilder defines the following methods: declareVariableName:, newCascadeReceiver:messages:, newAssignmentVariable:value:, newMessageReceiver:selector:arguments: or newSelfMessageSelector:. Syntax. In Prototalk, programs are written using a Smalltalk syntax (cf. Section 6). Therefore syntactically, a Prototalk program is a valid Smalltalk one. However, the semantics are different, variable accesses and method invocations depend on the semantics of the language implemented. Most of the nodes composing a prototalk program AST are the Smalltalk ones, except for a few of them that need to be specialized to reflect prototype languages features such as MessageNode and SuperMessageNode for method lookup and VariableNode and AssignmentNode that represent variables.

Object Model Class Hierarchies

Prototalk heavily uses inheritance to structure and reuse the various aspects of prototype-based languages. Figure 4 gives the hierarchy of object model classes representing languages in which prototype objects are defined by a set of slots. For example, the class SlotProto has an instance variable slots and some primitive methods to add new slots (addSlot: name), and to retrieve slots values (slotNamed: name).

Having a class hierarchy for the object models facilitates the extensibility. The definition of a new language is done by simply defining the differences with a previous language. For example the class L11 is a refinement of the class SlotProto that allows prototypes to be created and initialized with a set of slots (method newInitials: slots). The language L11 is refined to the language L11AndImplicitDelegation. The object model class adds an instance variable parent and implements methodOwner: name, parent and newSon. This language is specified by defining the differences with L11.

The object model class hierarchy that defines languages having variables and methods is shown in Figure 5. The class VariableMethodProto defines two instance variables: variables and methods. These variables are initialized in the constructor of this class to an empty set. It also contains all the necessary primitives to manipulate them properly (e.g., addVar: name and addMethod: code to add a variable or a methods). Each prototype objects of this language has its own set of variables and methods.

Basics for Language Interpretation

In Prototalk programs are not compiled, instead interpreted directly from the AST. This AST implements the Interpreter design pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]: each node of the hierarchy is evaluated (through a method eval: context). The interpretation (i.e., execution of a program) starts in its root node. This method is triggered by the object model class when the method evaluate: sourceCode is invoked. Evaluating a node requires a context containing information related to the action performed. The context refers to the receiver of the message currently sent (self), possibly the super one, the variables passed as argument within a method. Access to the self reference is necessary when new variables are defined (i.e., method eval: context of class VariableNode and its subclasses), when new slots are added (methods addSlot: code in the class SelfLike), or when message are sent (method eval: context class MessageNode and its subclasses).

Variable and Message Nodes

Modeling prototype-based languages has to deal with object representation and message lookup semantics. This means that embedding a prototype language within a class-based language requires the redefinition of the semantics of messages passing and variables lookup. In Prototalk, the AST used to represent prototype program is quite similar to the one offered by Smalltalk except that the nodes MessageNode, AssignmentNode and VariableNode have several subclasses to represent the different semantics for sending messages and manipulating a prototype state. Four different message send semantics are implemented in Prototalk: (i) explicit delegation to represent languages like ACT-1 where the delegation has to be done manually (no parent relationship), (ii) implicit delegation to the parents for messages that are not understood by the receiver (e.g., Self), (iii) invocation of a message by invoking the function ask(receiver, messageName, arguments) (à la ObjectLisp) and (iv) super call used to explicitly forward a message to the object contained in the super slot. Figure 6 shows the specialization of the Smalltalk AST to allow Prototalk to use different language semantics.

Primitives and Basic Behavior

Primitives refer to the methods implemented on the object model class that can be invoked (by a direct or indirect method call) from within code written in the prototype language implemented by the object model class. While the object model class instance represents prototype, methods defined by the user

Smalltalk Nodes Prototalk Nodes

Assignment Node NewtonScript AssignmentNode Fig. 6. Specialization of Smalltalk nodes to simulate prototype language behavior. on these instances are not defined on the object model class. Such methods are stored either in the methods dictionary of an object defined by the class VariableMethodProto or on slot dictionary of an object defined by the class SlotProto (see Figures 5 and4). These two method holders contain Smalltalk compiled methods in case of primitives, or AST in case of user defined methods.

Some utility methods are provided to enable the programmer to easily manipulate methods such as the method Object lookup: name that returns the class implementing a particular method name. In addition the method com-piledMethodAt: has been specialized to take care of the fact that the owner of a method is now an object instead of a class (i.e., Smalltalk).

Default Primitives

The class AbstractProto, which is the root of the object model classes, offers severals methods that can be used as primitives in the prototype-based languages. This class offers eleven primitives.

Four primitives are defined on the instance side of the class AbstractProto. (i) New primitives can be added using addPrimitive: aCompiledMethod named: sel. However it is declared as abstract but it is redefined in its two direct subclasses VariableMethodProto and SlotProto: either to store a primitive in a method or a slot. Global environment for a language can be accessed through a prototype (ii) globalVar: varName put: aValue and (iii) globalVarValue: varName are used for that. (iv) Creation from ex-nihilo (i.e., empty object) is available with newEmpty.

On the class side of AbstractProto seven primitives are offered. Even if these methods are usually not directly invoked during the interpretation of a program they are essential. (i) New primitives are added to the default objects offered to the user (e.g., PRoot) using addPrimitivesOn: aRoot. (ii) New method are added by the user through compile: aString (e.g., this method is indirectly called by addSlot:). (iii) The definition of the PRoot object is contained in the createRoot method. (iv) Compilation and execution of a program is done with evaluate: aStream. The result of this method is the result of the very last statement defined in the program passed as a Stream. The global environment for a language is managed by (v) globalVar: varName put: aValue and (vi) global-VarValue: varName. These methods are invoked by the corresponding method on the instance side. And the reference to the node builder is got by invoking (vii) nodeBuilder.

Evaluation

Even if programs expressed within Prototalk have a particular semantics, their syntax is always the one of Smalltalk (Section 6). Prototalk extends all of the Smalltalk AST nodes with the bare minimum, that defines a prototype language where: (i) variables do not need to be declared (they are created when first referenced) and (ii) any node of the AST can be particularized using subclassing.

The following classes implement an eval: context methods that simulate the normal Smalltalk behavior (which is identical to Prototalk's i.e., control flow structure): ArithmeticLoopNode, BlockNode, CascadeNode, ConditionalNode, Lit-eralNode, LoopNode, MessageNode, ReturnNode, SequenceNode.

Differences between Prototalk and Smalltalk only rely on a few nodes points: variable assignment, sending messages, and accessing variables.

As described below, an assignment refers either to binding a new value to a key existing in the context (i.e., self, super, or arguments passed to a method or a block) or creating a new global variable (explained later in this section). Accessing a variable looks at a binding up either in the current context or in the global environment. The class SimpleMessageNode is the node that represents a message send. It implements the default message send semantics. Its eval: context method performs the following steps: (i) evaluation of the receiver in the local context, (ii) evaluation of the arguments related to this message (the method evalList: is implemented on the class Collection), (iii) lookup of the prototype that defines the looked up method and if it is not found then raise an error, (iv) if the method retrieved is a CompiledMethod (i.e., if it is a primitive or if it correspond to a Smalltalk message) then the result of the methods is its execution 1 else, (v) the retrieved method is an AST (it corresponds to a method defined by the user) and it is applied to the arguments using a new context where the receiver is bound to #self.

Application

The classes BlockNode (representing a Smalltalk block closure) and MethodNode (representing a method definition) implement a method applyWith: args in: context invoked when a block or a method has to be evaluated (cf. last example in the previous paragraph).

Applying a block on a set of arguments (i) extends the local context with the arguments, and (ii) evaluate the block's body. If no error occurs during the application of a method then the result is the application of the related block defining a method. In Smalltalk the body of a method is represented as a block closure referenced by the instance variable block.

MethodNode applyWith: args in: context 1 note that the context is discarded because the method is not interpreted by prototalk

Extensions in basic classes

The classes Object and Behavior offered by Smalltalk has to be extended in order to make them normal smalltalk objects able to receive message from prototypes. The goal is to make Smalltalk objects usable in any language expressed in Prototalk.

Object is extended with a method lookup: selectorName used to return the class contained in the class hierarchy of the receiver that defines a method named selectorName. Methods are retrieved with methodNamed: name.

Implementing NewtonScript's Double Inheritance Semantics

Prototalk served as a basis to implement the key features of prototype-based languages as discussed. In this section we present how double inheritance of NewtonScript is implemented in Prototalk. We choose NewtonScript since it was one of the few prototype-based language used in production for the Apple Newton PDA [START_REF] Smith | Using a prototype-based language for user interface: The newton project's experience[END_REF]. The major design goals of the language were to minimize memory consumption and support graphical user interface definition by introducing an environmental acquisition mechanism [14] [30] that allows sharing between composite graphical objects and their parts. x 42

x is found here... new x slot is created here f := {retrieve: func () x, _proto: {_proto: {}}}; f._parent := {_proto: {x: 12}}; f._parent._parent := {_proto: {testAssign: func () x := 42}}; f:testAssign(); Print (f:retrieve()); Fig. 7. NewtonScript double inheritance method lookup and variable access.

NewtonScript

In NewtonScript an object is called a frame. A frame element is a slot which can either be an attribute or a function reference. Slots can be inserted or deleted dynamically at run time. New frames can be created from ex-nihilo (empty frame), by cloning and by extending an existing frame.

NewtonScript has a double inheritance scheme in which a prototype link ( proto) is searched prior to a parent one forming a comb-like graph traversal as shown in Figure 7. This specific inheritance supports the building of user-interfaces as well as the minimization of memory [START_REF] Noble | Flexible alias protection[END_REF]. Each frame has a prototype frame from which it is derived (refers to by a slot called proto).

Each time the NewtonScript interpreter does not find a slot variable or function locally it looks into the frame's prototype and then recursively into its prototype until the whole proto chain is searched through. When the slot is not found in the prototype chain of the receiver, it is looked in the parent (following the parent slot) and the parent prototype chain.

The semantics of assignment is slightly different and supports space consumption minimization: the same lookup occurs to locate the frame containing the variable, but the assignment is only allowed to alter an object in the parent chain, not the one in a proto chain. If necessary, a new slot is created in the object on the parent chain nearest the object where the slot was found as shown in Figure 7. It provides a form on copy-on-write in which the initial value of for a slot comes from the prototype. This way the allocation of the slot to hold a new value is delayed until a new value is actually assigned. The class NewtonScriptLike has to provide an accessor and a mutator for its instance variable proto (code not shown). These have to be accessible from a program intended to be interpreted. Therefore two primitives have to be added to the PRoot object which is the first prototype from which others can be cloned. By having the primitives proto and proto: defined in PRoot, they are accessible from each object.

NewtonScriptLike class addPrimitivesOn: aRoot super addPrimitivesOn: aRoot. aRoot addPrimitiveNamed: #proto. aRoot addPrimitiveNamed: #proto:. ˆaRoot

The object model class has to implement a method nodeBuilder that returns the class of its associated node builder (NewtonScriptPNB).

NewtonScriptLike class nodeBuilder ˆNewtonScriptPNB

Program Node Builder. The class NewtonScriptPNB inherits from Pro-gramNodeBuilder. It defines the program node builder used to yield proper nodes when requested by the Smalltalk parser. When the Smalltalk parser parses an assignment, the method newAssignmentVariable: var value: val leftArrow: bool is invoked on the program node builder. A proper node representing an assignment has to be emitted.

NewtonScriptPNB newAssignmentVariable: var value: val leftArrow: bool ˆNewtonScriptAssignmentNode new variable: var value: val leftArrow: bool

Sending a message has to trigger the method lookup algorithm described previously in the method NewtonScriptLike methodOwner:. Here we reuse the behavior of the class ImplicitDelegationMethodNode which implements a lookup of method and the use of super. The method ImplicitDelegationMethodNode eval: invokes the methodOwner: that is used to execute properly methods in presence of the parent slot. When invoked by the parser, the method newMes-sageReceiver: rcvr selector: sel arguments: args creates then an ImplicitDelega-tionMethodNode node.

receiver: rcvr selector: sel arguments: args Accessing a variable in NewtonScript has the same meaning as in Self: accessing a variable is equivalent to trigger its accessor. Referencing a variable foo is equivalent to sending the message foo to itself. On that point NewtonScript behaves in the same way as in Self. Therefore we reuse the SelfLikeVariableNode behavior as follows: First the right branch of the assignment (designed by the value instance variable) is evaluated using the current context. Then, if the left branch of the assignment, the variable named varName), is already defined in the context, it is a temporary variable. Then its value in it is updated. If not, a new frame variable or a global variable is created regarding if this assignment occurs in a method or not.

If the left branch of the assignment occurs in a method and if varName refers no local or global variable, then varName is related to the state of the current frame (self). According to the semantic given by NewtonScript a new variable is created in the current frame if none of its prototypes already has a slot named varName. If one of these already defines varName, then its value is updated by the value of the assignment.

This implementation of NewtonScript double inheritance shows how already existing semantical elements provided by the framework can be reused or redefined.

Evalutation

Prototalk is ideally suited for teaching concepts of object-oriented languages and has been successfully incorporated into the masters degree program at the University of Paris VI, Montpellier and Berne. It served as a tool to help teaching object-oriented languages and software engineering as well as program interpretation. Here a synthesis of what we learned from these experiments.

Prototalk has first proved to be a very interesting pedagogical tool although we did not perform registered and controlled experiments to evaluate and compare its impact. Firstly, it is an obvious help to explain what prototypes are and to ask students to invent or explain various languages. Secondly, its implementation is an interesting laboratory because it uses important objectoriented concepts and techniques. It is primarily a classical framework made of three main class hierarchies (object models, program nodes and program node builder) conceived to be extended. It also uses the Interpreter Design Pattern and extends it in various ways as such it could be called "Interpreter Family" and still remains to be described. Prototalk explicitly separates the object model from the instructions and their associated semantics in a language. Then it uses class specialization and composition to express the fact that various semantics can, in different languages, be associated to a single syntactic construction. For example each subclass of DelegationMessageNode and their respective eval: methods define one semantics of delegation whose study is an excellent way to present the semantics of delegation in prototype-based languages. Another very interesting point is the study of the AbstractProto class and subclasses. This class defines the structure and behavior of classless objects. The study of that apparent paradox (a class been used to describe and represent classless objects) is a key point for the understanding of language implementations and of reflective languages. Methods defined on AbstractProto are primitives of the classless languages. Within such a methods, an instance of VariableMethodProto for example, is a Smalltalk object but the same physical entity is a prototype in the implemented language.

From a research perspective Prototalk has been used to build the taxonomies and the evaluations presented in [START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF] [18] [START_REF] Dony | Classification of object-centered languages[END_REF]. Most of important feature of classless languages have been simulated with Prototalk.

Features and Languages Implemented. In addition to the NewtonScript's double inheritance, we modeled in Prototalk the following language facets.

• The proxy link of ACT-1 [START_REF] Lieberman | Using prototypical objects to implement shared behavior in object oriented systems[END_REF] and its associated explicit delegation mechanism. Cloning was then specialized to also clone also the object proxy. • ObjectLisp delegation. ObjectLisp, which was a layer on top of Allegro Lisp and presented as a class language, was underneath a prototype language inspired by Lieberan his. In ObjectLisp sending a message was performed using the construct ask. For example the (ask point (have 'y 4)) sends the message have to the object refer to the variable point. The receiver could be any expression, therefore it should be interpreted in the current context, but the arguments are executed in a new environment in which self is bound to the current receiver. The method ObjectLispAskMessageNode eval: context makes clear this semantical point. • Self's dynamic multiple inheritance. Depending on the versions of Self, an object could have multiple parents and their priority was denoted using *.

In the current version of Self (4.1), only one parent is used. In addition, the parent can be changed dynamically.

• Examplars [START_REF] Lalonde | Designing families of data types using exemplars[END_REF] mixed classes and prototypes hierarchies. Exemplars was a prospective language that proposed a dichotomy between a subtyping hierarchy made of classes and a reuse hierarchy made of prototypes. In fact Exemplar is very interesting because its classes were an exact intuition of Java interfaces. As we already mentioned in Section 3 and illustrated during the implementation of NewtonScript's double inheritance, Prototalk is a framework that provides predefined abstractions that can be reused, extended and combined to create different languages. At a structural level, three different elements are offered: objects with slots, objects with variables and methods, and objects with parent. In addition, object internal representation can be fixed or modifiable. From a behavioral perspective, Prototalk offers 4 different message passing semantics as we explained before, cloning and object creation with initial values are also offered.

About Influence of the Syntax. Prototalk is a platform supporting the coexistence of several prototype languages. Each language has the ability to execute programs written in this language, to debug programs and to test them. Each language expressed can reuse all the facilities provided by the classical Smalltalk environment. Using the Smalltalk syntax has the following advantages:

• Users can experiment with several conceptually different languages without having to learn several syntaxes. • By removing all the syntactic decorations, conceptual values are clearly offered without being obfuscated. • To not deal with lexical and syntactical parser keeps the implementation of Prototalk simple and the implementation of new language simple too. This helps to make its kernel focus only on essential mechanisms.

Code expressed in a prototype language has to have a Smalltalk syntax. This means that computation is described by sending messages where a receiver is explicitly designated. For instance a language where messages implicitly sent to self is implementable but the implementer should use a naming convention to distinguish self sends from implicit self-sends à la Self.

Conclusion and Further Work

Thanks to new application domains such as web programming, mobile and distributed computing, various kind of programming languages such as scripting, dynamically typed, or object classless languages are subject to a renewal of interest.

In this paper we have described Prototalk, a Smalltalk framework dedicated to the implementation of prototype-based language interpreters. We have presented it as a research as well as a pedagogical tool. Prototalk has been conceived and used in the nineties to evaluate and operationnaly compare into an uniform environment prototype-based languages such as ACT-1, ObjectLisp, Kevo or Self, considered as possible alternatives to class-based languages somehow and sometimes judged too complex or rigid. All the important facets of prototype-based languages are implemented and usable in a syntactically uniform environment that garanties for easy comparisons and classifications.

The paper precisely describes the Prototalk framework architecture based on an extension of the Interpreter design Pattern and its Smalltalk implementation. It explains the value of using an object-oriented programming language was paying off from a research and pedagogical point of view, as it supported well incremental definition and the possibility of reusing what is already exis-ting. It demonstrates why using Smalltalk, among other advantages, enabled us to easily implement that design pattern due to its fully integrated parser.

The paper illustrates Prototalk reuse capabilities by presenting the integration of the NewtonScript double inheritance semantics in the framework. It also illustrates why Prototalk has been successfully used as a pedagogical tool to teach object-oriented concepts and technologies.

The perspectives of this environment are numerous. Firstly, we plan to integrate in the platform interpreters for those new languages such as IO, Pic%, Slate or Prothon. Secondly, as Smalltalk only supports single inheritance and since our classifications are not only ontological but also operationnal, we faced the tyranny of the dominant decomposition. Indeed we had to follow a main decomposition and sometimes this forces us to duplicate the behavior. Ideally we would have prefer to have well-identified behaviors that we could freely compose together. Investigating the use of traits [START_REF] Schärli | Traits: Composable units of behavior[END_REF] could be a way to solve this problem and rely less on inheritance to model the languages. More generally, all new techniques which plug together components or aspects could be of interest to improve that work and enable it to evolve. Finally, it appeared to us that designing a similar environment for another family of languages (e.g., frame languages or component-based languages) should not be difficult and that a generalisation is somehow possible.

Fig. 1 .

 1 Fig.1. Classifying prototype-based languages[START_REF] Dony | Prototype-based languages: From a new taxonomy to constructive proposals and their validation[END_REF]

  nDic := Dictionary new. slots associationsDo: [:each | nDic add: each copy]. ˆself shallowCopy initMethDic: nDic L7AndImplicitDelegation class addPrimitivesOn: aRoot super addPrimitivesOn: aRoot. aRoot addPrimitiveNamed: #newSon. aRoot addPrimitiveNamed: #parent:. ˆaRoot Prototype Representation. Smalltalk instances of the object model class represent prototype objects. Therefore the object model class defines the common structure of any prototype. For instance prototypes in the SelfLike language are represented as instances of this object model class SelfLike. Proto-types are Smalltalk objects, therefore Prototalk does not have to deal with the garbage collector.

Fig. 4 .

 4 Fig. 4. Hierarchy of object model classes for languages having slots.

Fig. 5 .

 5 Fig. 5. Hierarchy of object model classes for languages having variables and methods.

  AssignmentNode eval: context | varName val client | varName := variable name asSymbol. val := value eval: context. (context hasLocalVar: varName) ifTrue: [ ˆcontext at: varName put: val ] ifFalse: [ client := context at: #self. ˆclient globalVar: varName put: val ] VariableNode eval: context | client varName | varName := name asSymbol. ˆcontext at: varName ifAbsent: [ client := context at: #self. client globalVarValue: varName ]

  BlockNode applyWith: args in: context 1 to: arguments size do: [:i | context at: ((arguments at: i) variable name asSymbol) put: (args at: i)]. ˆbody eval: context.

  ˆAbstractProto returnFromSignal handle: [:ex | ex returnWith: ex parameter] do: [block applyWith: args in: context]

  ObjectLispAskMessageNode eval: context "context contains self which is the initial receiver in the current delegation chain, that is the client and curRec the current receiver." | rec newContext result | rec := receiver eval: context. newContext := PContext new. newContext at: #self put: rec. arguments do: [:each | result := each eval: newContext]. ˆresult

  Variable Assignment. The class NewtonScriptAssignmentNode is a subclass of AssignmentNode. It implements the methods eval: context that defines semantics of assigning a value to a variable in NewtonScript. This method requires a context as argument containing the references to self and to the temporary local variables.

	NewtonScriptDelegationPNB newVariableName: nameString
	ˆSelfLikeVariableNode new name: nameString
	NewtonScriptAssignmentNode eval: context
	l varName val client owner l
	varName := variable name asSymbol.
	val := value eval: context.
	ˆ(context hasLocalVar: varName)
	ifTrue: [ context at: varName put: val ]
	ifFalse:
	[ client := context at: #self.
	self inAMethod
	ifTrue: [ owner := client methodOwnerInParentChain: varName.
	owner isNil
	ifTrue: [ client addSlot: (variable name, ' = ', val printString) ]
	ifFalse: [ owner addSlot: (variable name, ' = ', val printString) ]]
	ifFalse: [ client globalVar: varName put: val]]
	NewtonScriptLike methodOwnerInParentAndProtoChain: slotName
	"Return the first frame in the parent hierarchy that has (or one of its proto)
	a slotName defined"
	(slots includesKey: slotName)
	ifTrue: [ ˆself ]
	ifFalse: [
	proto notNil
	ifTrue: [ (self methodLookupInProtoChain: slotName) notNil
	ifTrue: [ ˆself ]].
	parent isNil
	ifTrue: [ ˆnil ]
	ifFalse: [ ˆparent methodOwnerInParentAndProtoChain: slotName ]]

NewtonScriptPNB newMessageReceiver: rcvr selector: sel arguments: args ˆImplicitDelegationMethodNode new

Acknowledgments. We gratefully acknowledge the financial support of the Swiss National Science Foundation for the projects "Tools and Techniques for Decomposing and Composing Software" (SNF Project No. 2000-067855.02) and "Recast: Evolution of Object-Oriented Applications" (SNF 2000-06165-5.00/1). We also thank Gabriela Arévalo and Orla Greevy for their feedback on the paper.

Here is an example of NewtonScript code and its implementation in Prototalk. Even if syntactically the two programs are different, their execution leads to the same objects and construction.

In Prototalk

The first step is to create the object model class NewtonScriptLike as shown below. Because of the similarity between Self and NewtonScript (implicit delegation, reference to a parent object, slot management, . . . ) the object model class inherits from the class SelfLike. In NewtonScript a frame has a parent (instance variable inherited from SelfLike) and a prototype named proto instance variable which has to be defined in the object class model.

Smalltalk defineClass: #NewtonScriptLike superclass: #{Smalltalk.SelfLike} instanceVariableNames: 'proto '

The method methodOwner has to return the object that implement the looked up method. The NewtonScript's method lookup semantics described previously is specified by specializing the method methodOwner: name as follow: if the current frame provides an implementation of a name method then return this frame, otherwise check if one of the frame's prototypes implements it. If not then we lookup in the frame's parent. The lookup in the prototype chain is simply done by running over it: for each frame it is checked if it implements a method named name. Note that this lookup does not have to run over the parent link.


Alexandre Bergel
email: bergel@iam.unibe.ch

Stéphane Ducasse
email: ducasse@iam.unibe.ch

Oscar Nierstrasz
email: nierstrasz@iam.unibe.ch

Roel Wuyts
email: wuyts@ulb.ac.be

Classboxes: Controlling Visibility of Class Extensions c

A class extension is a method that is defined in a module, but whose class is defined elsewhere. Class extensions offer a convenient way to incrementally modify existing classes when subclassing is inappropriate. Unfortunately existing approaches suffer from various limitations. Either class extensions have a global impact, with possibly negative effects for unexpected clients, or they have a purely local impact, with negative results for collaborating clients. Furthermore, conflicting class extensions are either disallowed, or resolved by linearization, with consequent negative effects. To solve these problems we present classboxes, a module system for object-oriented languages that provides for method addition and replacement. Moreover, the changes made by a classbox are only visible to that classbox (or classboxes that import it), a feature we call local rebinding. To validate the model we have implemented it in the Squeak Smalltalk environment, and performed benchmarks.

Introduction

It is well-established that object-oriented programming languages gain a great deal of their power and expressiveness from their support for the open/closed principle [START_REF] Meyer | Object-oriented Software Construction[END_REF]: classes are closed in the sense that they can be instantiated, but they are also open to incremental modification by inheritance.

Nevertheless, classes and inheritance alone are not adequate for expressing many useful forms of incremental change. For example, most modern objectoriented languages introduce modules as a complementary mechanism to structure classes and control visibility of names. Reflection is another example of an increasingly mainstream technique used to modify and adapt behaviour at run-time. Aspect-oriented programming, on the other hand, is a technique to adapt sets of related classes by introducing code that addresses cross-cutting aspects.

In this paper we focus on a particular technique, known as class extensions, which addresses the need to extend existing classes with new behaviour. Smalltalk [START_REF] Goldberg | Smalltalk-80: The Language[END_REF], CLOS [START_REF] Paepcke | User-level language crafting[END_REF], Objective-C [START_REF] Pinson | Objective-C[END_REF], and more recently MultiJava [START_REF] Clifton | MultiJava: Modular open classes and symmetric multiple dispatch for Java[END_REF] and As-pectJ [START_REF] Kiczales | An overview of AspectJ[END_REF] are examples of languages that support class extensions. Class extensions offer a good solution to the dilemma that arises when one would like to modify or extend the behaviour of an existing class, and subclassing is inappropriate because that specific class is referred to, but, one cannot modify the source code of the class in question. A class extension can then be applied to that specific class.

Despite the demonstrated utility of class extensions, a number of open problems have limited their widespread acceptance. Briefly, these problems are:

(1) Globality. In existing approaches, the effects of a class extension are either global (i.e., visible to all clients), or purely local (i.e., only to specific clients named in the application of the class extension). In the first case, clients that do not require the class extension may be adversely affected.

In the second case, collaborating clients that are not explicitly named will not see the class extension, even though they should. (2) Conflicts. If two or more class extensions attempt to extend the same class, this may lead to a conflict. In existing approaches, conflicts are either forbidden, or extensions are linearized, possibly leading to unexpected behaviour. In either case, the utility of class extensions is severely impacted.

We propose a modular approach to class extensions that largely solves these two problems by defining an implicit context in which class extensions are visible. A classbox is a kind of module with three main characteristics:

• It is a unit of scoping in which classes, global variables and methods are defined. Each entity belongs to precisely one classbox, namely the one it which it is first defined, but an entity can be made visible to other classboxes by importing it. Methods can be defined for any class visible within a classbox, independently of whether that class is defined or imported. Methods defined (or redefined) for imported classes are called class extensions. • A class extension is locally visible to the classbox in which it is defined. This means that the extension is only visible to (i) the extending classbox, and (ii) other classboxes that directly or indirectly import the extended class. • A class extension supports local rebinding. This means that, although extensions are locally visible, their effect extends to all collaborating classes. A classbox thereby determines a namespace within which local class extensions behave as though they were global. From the perspective of a classbox, the world is flattened.

We have previously introduced classboxes by means of a specialized method lookup algorithm [START_REF] Bergel | Classboxes: A minimal module model supporting local rebinding[END_REF] reproduced in Section 5. The main contributions of this paper are: (i) A set-theoretic account of the semantics of classboxes that does not require a special method lookup algorithm and (ii) a detailed description of the prototype implementation in the Squeak Smalltalk system, including performance benchmarks.

The rest of the paper is structured as follows. Section 2 presents the problems in supporting unanticipated changes by giving a motivating example and Section 3 outlines the classbox model. Then a set-theoretic account of classboxes is given in Section 4. We discuss implementation issues arising in our prototype implementation in Section 5. Section 6 contrasts classboxes with related work. Finally, in Section 7 we conclude with some remarks concerning future work.

Motivation: Supporting Unanticipated Change

Class extensions provide a mechanism to support unanticipated changes in a static setting. Let us first consider a typical scenario, which will enable us to establish some key requirements for class extensions, while highlighting the main problems to be overcome.

A Link-Checker is an application whose purpose is to report a list of the dead links on a web-page at a given URL. One natural way to implement a Link-Checker, depicted in Figure 1, is to download the HTML page from the remote website, and parse it to get an abstract syntax tree of the page composed of various elements representing the HTML tags. Then using a recursive call over the hierarchy, get the list of the links referenced in the page. The liveness of getLinks <heading> ... </heading> <body> ...

List

Parser Socket ping pingOnPort:

AST

GetLinks Network http://www....

Parser parse

Body getLinks

List getLinks

Fig. 1. The conceptual decomposition of the deadlink checker: an HTML parser, an abstract syntax tree for HTML documents, facility to get links from a page, and a network library. each these links elements is checked by pinging the associated host and trying to obtain the status of the linked page. When a timeout is issued or if the HTTP reply corresponds to an error the link is declared dead.

Based on this example we can identify four properties that a packaging system for an object-oriented programming language should support: class extensions allowing redefinition, locality of changes, propagation of changes to collaborating clients, and resolution of conflicts.

Class Extensions with Redefinition. First, the different elements composing the solution should be packaged so that they can be used in further applications. We can identify the following modules: an HTML scanner and parser, an abstract syntax tree for the HTML elements, a recursive call over these elements to get links contained in a page and some network facilities. One key point is that we have to be able to group together the definitions of the getLinks methods in a module that is different from that of the AST. This means that the GetLinks module has to be able to extend the class definitions of the tree node elements.

Although languages such as CLOS, Smalltalk, MultiJava, and AspectJ offer some solutions, most otherlanguages (including Java), do not allow a class to be extended by a different module or package than the one defining the class. Note that subclassing the tree node elements is not a general solution, since clients that explicitly name the original class will not see the subclass extension.

In our development environment, the default Squeak distribution, the ping method used by the environment does not raise an exception but opens a dialog box when a target host cannot be reached. We therefore not only need the ability to add methods (for packaging the GetLinks module), but also to redefine them (to patch existing methods). We therefore require a module system that supports class extensions with redefinition.

Locality of Changes. The second key aspect concerns the visibility of changes, i.e., which modules see the extensions made by other modules. In most ap-proaches that support them, class extensions have a global visibility. All clients have a common view of any given class, and any extensions are also seen by all clients. This may lead to unexpected behaviour for some clients.

In the case of the ping method, we only want our redefined version to be visible within the scope of our application. Other applications may actually rely on the ad-hoc behavior provided by ping. Therefore the extensions and changes to the system made by one module should not impact the system as a whole, but only the module introducing the changes and its client modules. Class extensions should be confined to the module that introduces them.

Local Rebindings. Even though class extensions should be visible only to the module that introduces them, the actual effect from the perspective of that module should be as if the extension were global.

The pingOnPort: method first adjusts the port (value kept in a variable) and then call the ping method. We want that any call to ping made by pingOnPort: triggers the definition brought by our LinkChecker application, even if pingOn-Port: is defined in a scope that also contains a previous definition of ping. Class extensions visible within a module should propagate to collaborating clients.

Conflicts. Class extensions are useful when, for instance, a library needs to add a particular method to a class provided by the system. Conflicts arise when an application relies on two modules that extend the same method of the same class in different ways.

The ping method provided by Squeak is useful for pinging a remote host. Its default behavior is to display the result in a popup window. The Link-Checker application redefines this method to make it yield a value and to raise an exception if the host is not reachable. Conflicts can arise with other modules that make changes to this method. As a concrete example, Squeak has a SocketICMP module that implements the ICMP network protocol. Amongst other things, this implementation redefines the ping method with an ICMPbased implementation. Using both the Link-Checker and the SocketICMP module therefore leads to a conflict because both redefine the method ping.

There are several ways to handle this conflict: (1) the definition in Link-Checker overrides the definition in SocketICMP's, (2) SocketICMP's definition overrides Link-Checker's, (3) a conflict is detected at composition time and needs to be resolved, or (4) each extension is defined in a different namespace than that of the class.

With Smalltalk, CLOS and Objective-C the result depends on which module is loaded/initialized last which effectively impacts the system. On the other hand, Multijava and Hyper/J detect conflicting situations at compile time. Selector namespaces, Smallscript [START_REF] Simmons | Smallscript[END_REF] and ModularSmalltalk [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF] define the ex-tension in a particular namespace: conflicts are avoided and both extensions are applied to the system within different scopes. Resolution of conflicting class extensions should take the context of affected clients into account.

Classboxes in a Nutshell

A classbox is a module containing scoped definitions and import statements. Classboxes define classes, methods and variables. Imported declarations may be extended, possibly redefining imported methods. When a classbox is instantiated, it yields a namespace in which the directly defined, imported and extended entities co-exist with the implicitly imported entities. Scoped Definitions. A classbox defines classes, methods, or variables. Each class, method or variable belongs to precisely one classbox, namely the one in which it is originally defined. Classes and variables defined in a classbox are globally accessible to all methods in the scope of that classbox.

Imports. A classbox may import classes and variables from other classboxes.

Imported entities thus become available within the scope of the importing classbox. An imported class may be extended with new methods, or methods that redefine existing methods. The extended class is then visible within the scope of the extending classbox, but not in the defining classbox of the extended class.

Scope of Methods

A method defined on a class in a classbox CB is visible within that classbox, and within other classboxes that import this class from CB. In a given classbox all the methods defined along the chain of import are visible within this classbox.

If several classboxes extend a class with a method with the same name but with different implementations, the implementation chosen during an invocation is the one that is reachable according to the import chain.

A classbox CB that defines a method that already exists in the import chain hides its former definition from this classbox CB and other classboxes that may import the extended class from CB.

The Link-Checker with Classboxes

This section shows how to use classboxes to modularize the Link-Checker example. Because classboxes have been fully implemented in the Squeak [START_REF] Ingalls | Back to the future: The story of Squeak, A practical Smalltalk written in itself[END_REF] environment, code fragments are presented in Smalltalk.

The architecture of the Link-Checker application is depicted in Figure 2. The classbox SqueakCB contains the network facility for checking the existence of a remote host (class Socket with class method ping: host) and for fetching the content associated to a given URL (class HTTPSocket with class method getHttp: url).

The classbox HtmlCB defines the HTML framework facilities. The class HTML-Parser is used to parse a text, yielding an abstract syntax tree (AST) composed of nodes such as HTMLEntity (the root of the structure), HTMLBody, HTML-Anchor (representing a link), . . . The classbox GetLinksCB implements the recursive algorithm intended to produce a collection of all the links contained over the AST elements. It imports the relevant nodes from the classbox HtmlCB and extends each of the classes representing HTML tag elements by defining the corresponding getLinks methods.

The classbox LinkCheckerCB contains the actual link checker application. It defines the class LinkChecker, containing one method (check: url) which is the entry point of the application. This method first gets the raw content of a page designated by url using the class HTTPSocket). It then parses the page using the class HTMLParser, obtaining an AST of the page. Then it invokes the method getLinks on the root of that AST, obtaining a collection of all the links on the page. Finally it checks the liveness of these links by pinging the hosts mentioned in each link. LinkCheckerCB imports the complete classbox Get-LinksCB, so all the extended classes (HTML nodes) are visible within it. As a consequence, within the classbox LinkCheckerCB the AST generated by HTML-Parser (class imported from HtmlCB) understands the extensions brought by GetLinksCB. To solve the problem that the method ping: host in the classbox SqueakCB displays its results in a dialog box, the classbox LinkCheckerCB redefines it to raise an exception instead.

Discussion

Locality of Changes. Although the method ping of class Socket is redefined, its visibility is confined to the LinkCheckerCB classbox. Unrelated code in the system relying on the original definition of this method is not affected. This illustrates both class extensions with redefinition and locality of changes.

Local Rebinding. The classbox SqueakCB defines the class Socket with two methods: ping: host onPort: number and ping: host. The first one calls the second one, and the latter posts a popup menu to display the result of pinging a host. This implementation is not suitable for our application. The classbox LinkCheckerCB imports the class Socket from SqueakCB and extends it by redefining the method ping: host with an implementation that throws an exception when a host is not reachable. Calling ping: host onPort: number within LinkCheckerCB triggers the new implementation of ping: host. This illustrates the local rebinding property.

Conflict. The classbox LinkCheckerCB extends the class Socket by redefining the method ping. This extension is local to the classbox. Figure 3 shows another classbox SocketIcmpCB that also imports the class Socket and redefines the same method ping. This class extension is local to SocketIcmpCB. Conflict is avoided because each extension is confined to the classbox that defines it. This section presents a set-theoretic model that precisely defines the semantics of classboxes. We abstract away from the operational details of statements and expressions of a given object-oriented language, and instead focus on the key features that interact with classboxes. We start by introducing a basic model of classes, objects and namespaces, where we capture instantiation, message sending, and self-and super-calls.

On top of this basic model, we then show how classboxes are defined as a mechanism for introducing class extensions, and for controlling the visibility of class extensions in different namespaces. We show how locality of changes and local rebinding arise as a consequence of the way that classboxes are composed.

Environments

We use the basic concept of an extensible environment as a mechanism for modeling classes, objects and classboxes.

Definition 1 An environment ǫ : D → R ⋆ , is a mapping from some domain D to an extended range R ⋆ = R ∪ {⊥}, such that the inverse image ǫ -1 (R) is finite.
We represent environments as finite sets of bindings, for example: ǫ 1 = {a → x, b → y} is an environment that maps a to x and b to y. All other values in the domain of this environment (for example, c) are mapped to ⊥.

We normally leave out unessential parentheses. Since an environment is a function, we simply invoke it to look up a binding. In this case, ǫ 1 a = x, ǫ 1 b = y and ǫ 1 c = ⊥. and (ǫ 1 ✄ ǫ 2 )c = w. We employ overriding both for method dictionaries and class namespaces.

Definition 2 An environment ǫ : D → R ⋆ may override another environment ǫ ′ . We define ǫ ✄ ǫ ′ : D → R ⋆ as follows: (ǫ ✄ ǫ ′ )x def =      ǫ ′ x if ǫx = ⊥ ǫx otherwise For example, if ǫ 2 = {b → z, c → w}, then (ǫ 1 ✄ ǫ 2 )a = x, (ǫ 1 ✄ ǫ 2 )b = y,

Classes, Namespaces and Objects

The primitive elements of our model are the following disjoint sets: C, a countable set of class names, M, a countable set of messages, and B, a countable set of method bodies.

Definition 3 A method dictionary, δ ∈ D is an environment, δ : M → B ⋆ that maps a finite set of messages to bodies.

For example, δ = {m 1 → b 1 , m 2 → b 2 } defines a dictionary d that maps message m 1 to body b 1 and m 2 to b 2 , and all other messages to ⊥.

Note that, for the purpose of this paper, we are not concerned with the implementation details of the method bodies. We only consider which kinds of messages are sent in the bodies.

Definition 4 A class, c δ, B, ǫ consists of a method dictionary δ, a superclass name B ∈ C ∪{nil}, and an environment ǫ, called a class namespace, that binds class names to classes.

nil represents an empty class, from which the root of a class hierarchy inherits. By convention, every class namespace is assumed to contain the binding nil → c ∅, nil, ∅ , which we therefore do not list explicitly.

Definition 5 An object o c, φ consists of a class c and an environment φ, which is a class namespace (obtained from c) extended with a binding for self.

Note that, for the present purposes, we do not model attributes (instance variables) of objects, aside from the pseudo-variables self and super.

We can send messages to classes and to objects. We use the notation x[m] to send the message m to the class or object x.

Definition 6

We can instantiate an object by sending the message new to a class c = c δ, B, ǫ :

c[new] def = µσ.o c, {self → σ} ✄ ǫ
At this point we recursively bind self to the value of the object itself.

As usual, µx.E binds free occurrences of x in E to the value of the recursive expression itself, i.e., µx.E def = E{µx.E/x}, where E{y/x} is the usual substitution operation, replacing free occurrences of x in E by y while avoiding name clashes.

Although we do not model the internal details of method bodies here, we must take care to be precise about the environment within which methods are evaluated. As we shall see when we define classboxes, it is precisely the way in which these environments are composed that determines the scope within which class extensions are visible.

Definition 7 A method closure m b, φ consists of a method body b and a class namespace φ that additionally binds both self and super.

Note that super is bound by methods, not objects, since super-calls are relative to the class in which a method is defined, not the class from which the object is instantiated.

o c, φ [m] def =              m δm, {super → o ǫB, φ } ✄ φ if δm = ⊥ o ǫB, φ [m] else if B = nil ⊥ otherwise
This definition captures the basic method lookup algorithm of object-oriented programming languages. If the message sent does not correspond to a method defined in the class of the object, the lookup continues in the parent class, and so on. If the method is not found, the message is reported as not being understood (⊥). If a suitable method is found, it is evaluated in a context where super is bound to the current object, but from the perspective of the method's superclass. As we can clearly see, super is an object, not a class. Note that according to Definition 4 the superclass B can be nil.

Definition 9 A closure may be evaluated, in which case it may send various messages. Here we are interested in self-and super-sends, and static class references.

m b, φ self m def = (φ self)[m] m b, φ super m def = (φ super)[m] m b, φ C new def = (φ C φ )[new]

Classboxes

A classbox is an open entity that provides a number of classes, and which can be extended. When a classbox is closed, it yields an ordinary class namespace (Definition 4).

The key point in modeling classboxes is that multiple versions of the same class may be implicitly present within the same classbox. Suppose that we import the class LinkChecker from the classbox LinkCheckerCB, and we locally define a class Socket. Even though LinkChecker collaborates with Socket, ours is a different socket class that has nothing to do with the Socket class known to LinkChecker. To capture this aspect we must refine the notion of class names to express the originating classbox to which a class belongs:

• C is the countable set of raw class names, • X is the set of classbox names,

• C + = {C n |C ∈ C, n ∈ X } is the set of decorated class names.
The decorated class name simply encodes the classbox to which the class belongs, i.e., where it was first defined. We call the superscript n of a decorated class name C n its origin.

Definition 10 A raw class name C matches a decorated class name B n if C = B: C ∼ B n iff C = B
For example, when we use the raw class name Socket, it may not be clear which Socket class we are referring to. However the decorated class name Socket SqueakCB unambiguously identifies the Socket class first introduced in the SqueakCB classbox.

Note that it is this same class that is extended in LinkCheckerCB, since there is no Socket class defined there. There is no Socket LinkCheckerCB .

C α def =      C n if ∃!n ∈ X , (b n, α [close])C n = ⊥ ⊥ otherwise
Suppose the LinkCheckerCB classbox is represented by b LinkCheckerCB, α . Then Socket α yields Socket SqueakCB , since SqueakCB is the origin of Socket in the LinkCheckerCB classbox.

n, α [def C subclasses B m with δ] def =      b n, λǫ.{C n → c δ, B m , ǫ } ✄ αǫ , if C α = ⊥ ⊥ otherwise
Note that the formal parameter ǫ represents the fixpoint we obtain when the classbox is finally closed. We must therefore extend αǫ with the new subclass definition, obtaining {C n → • • • } ✄ αǫ. We retain ǫ as a formal parameter so that the classbox remains open (i.e., λǫ. • • • ). The side condition states that it is an error to introduce a class that is already defined in the classbox. Within a classbox, only decorated class names occur. The newly introduced class has the origin n. We also explicitly identify the origin m of the superclass.

Importing Classes

n, α [import C from b m, β ] def =      b n, λǫ.{C β → (µφ.β(ǫ ✄ φ))C β } ✄ αǫ , if C α = ⊥ ⊥ otherwise
Let us call the new classbox we obtain b n, α ′ . α ′ extends α with the imported definition, but we must also take care that the environment of the imported class is properly extended with any pertinent definitions that occur in α ′ . As before, ǫ represents the class namespace that we obtain when we take the fixpoint of α ′ . We therefore pass ǫ to α so it is available to all the existing class definitions in α. We must also look up the correct decorated class name C β . Finally, we must bind this to the correct definition from β, extended with any new definitions from α ′ .

Suppose we would simply use C β → (µφ.βφ)C β , this would clearly be wrong, because the class we obtain would only see other class definitions from β, and not any definitions that may have already been extended in α. Instead, we create an intermediate namespace µφ.β(ǫ✄φ). ǫ✄φ represents the environment of β extended with any new definitions from α ′ . We then pass this into β to make it available to all class definitions in β. Finally we extract this definition, bind it to C β and use it to extend αǫ.

Consider, for example, the import relationships in Figure 2. The classbox Link-CheckerCB imports HTMLParser from HtmlCB and HTMLEntity and its subclasses from GetLinksCB. If HTMLParser were naively imported from HtmlCB, it would not see the extensions imported from GetLinksCB. Instead, the import operation is defined so that when HTMLParser is imported, its environment (i.e., φ) is extended by all definitions in LinkCheckerCB (i.e., ǫ ✄ φ). So when HTMLParser is imported, it sees the extended versions of HTMLEntity and its subclasses. This is the local rebinding mechanism of classboxes.

Note that it is critical that HTMLEntity imported from GetLinksCB has the same origin as that expected by HTMLParser. If LinkCheckerCB or GetLinks-CB were to define a new class HTMLEntity, then this would have a different decorated class name from the HTMLEntity originally defined in HtmlCB, and would therefore be invisible to HTMLParser.

Extending Imported Classes

] def =      b n, λǫ.{C β → δ ′ ✄ (µφ.β(ǫ ✄ φ))C β } ✄ αǫ if C α = ⊥ ⊥ otherwise where δ ′ ✄ c δ, B, ǫ def = c δ ✄ δ, B, ǫ
Extend works just like import, except that the imported class definition is extended with δ ′ .

As a consequence, importing a class is the same as extending it with a nil extension:

b n, α [import C from b m, β ] ≡ b n, α [extend C with ∅ from b m, β ]
As should be clear from the definition, class extensions are purely local to the classbox making the extension. This guarantees locality of changes. Extensions become visible to other classboxes only when they are explicitly imported, or implicitly made visible by the mechanism of local rebinding (as seen in the HTMLParser example discussed above).

Method redefinition is supported since the δ ′ introduced by a class extension can redefine methods existing in the class being extended. For example, not only can the GetLinksCB classbox extend the HTMLEntity and related classes with a new getLinks method, but the LinkCheckerCB classbox can import Socket from the SqueakCB classbox and redefine the ping method.

Proving Classbox Properties

Proposition 1 A method defined in a classbox is visible within this classbox.

Proof. Because a method is defined either when a class is (i) defined or (ii) imported, this Proof is divided in two parts.

(i) Methods defined at the same time than the class they refer to are visible within the classbox where they are effectively defined. This first part of the proof consists in showing that defining a class C with a method m bound to a compiled method CM makes this method visible within the classbox (i.e. invoking m on an instance of C triggers the expected method CM).

Without loss of generality, assume that C has no superclass (i.e. it inherits from nil).

b n, α [def C subclasses nil with {m → CM}]

= b n, λǫ.{C n → c {m → CM}, nil, ǫ } ✄ αǫ = b n, α ′
Proposition 3 Within a classbox, a method redefinition takes precedence over its former implementation.

Proof. Within a classbox b m, β a class C has in its method dictionary an entry m bound to a first implementation CM1. This proof consists in showing that importing C in another classbox and redefining m bound to CM2 hides the former implementation.

If b m, β C β = c {m → CM1}, B, ǫ then b n, α [extend C with {m → CM2} from b m, β ] = b n, λǫ.{C β → {m → CM2} ✄ (µφ.β(ǫ ✄ φ))C β } ✄ αǫ Assuming that C β = C p closing the resulting classbox yields: b n, . . . [close] = ϕ = {C p → {m → CM2} ✄ βC p } = {C p → {m → CM2} ✄ b m → CM1, B ϕ} = {C p → c {m → CM2}, B, ϕ }
The conclusion of this proof follows the end of the very first proof. Instantiating C p and sending the message m executes the new implementation CM2.

Resolving Diamond Conflicts

Conflicts are largely avoided. Classes that coincidentally have the same name but are introduced in different classboxes do not conflict because they have separate origins. Contradictions arising from attempts to import the same class from different classboxes of course cannot be resolved automatically. However, an important class of indirect conflicts is automatically resolved by the nature of the local rebinding mechanism.

Figure 4 illustrates a diamond pattern arising from two import chains with a common ancestor class. Classbox CB1 defines a class A which provides a method foo returning the value 1. This class is imported by CB2 where the method foo is redefined to return 2. CB2 also defines a subclass of A named B.

In a similar way, classbox CB3 imports A from CB1 and redefines foo to return 3. A subclass of A named C is also defined. A fourth classbox CB4 imports B from CB2 and C from CB3. CB4 does not explicitly import class A. In the context of CB4 invoking foo on an instance of B yields the value 2, whereas invoking foo on an instance of C yields 3. However, if CB4 would explicitly import A from any one of CB1, CB2 or CB3, then that version of A would be visible to both B and C. For example, if CB4 would import A from CB1 and redefine foo to return 4, then both instances of B and C would return 4 when foo is invoked.

Implementation Issues

Classboxes can be implemented by changing the method lookup algorithm in the virtual machine. This requires a virtual machine that is available for changing, which is why we performed our experiments in Squeak, a Smalltalk environment of which the virtual machine is open source [START_REF] Ingalls | Back to the future: The story of Squeak, A practical Smalltalk written in itself[END_REF][START_REF]Squeak home page[END_REF]. We adapted the method lookup and compiled a new virtual machine that is classboxaware. In this section we evaluate the impact of this extended method lookup algorithm on performance.

Method Lookup Description

Encoding the classbox with the method signature makes it possible for different implementations a method to coexist. However, to take advantage of this, the method lookup mechanism has to be changed as well. Figure 5 describes the lookup algorithm we implemented that ensures the local rebinding property.

The algorithm first checks whether the class in the current classbox implements the selector we are looking for (lines 5 to 9). If it is found, the lookup is successful and we return the found method (line 9). If it is not found, we recurse. The algorithm favours imports over inheritance, meaning that first the import chain is traversed (in lines 12 to 18) before considering the inheritance chain (in lines 19 to 30). This last part is the difficult part of the algorithm, since we need to find the classbox where the superclass is defined that is closest to the classbox we started the lookup from. Therefore the algorithm remembers the path while traversing the import chain (line 12), and uses this when determining the classbox for the superclass (line 21).

Import Takes Precedence Over Inheritance

Figure 5, lines 11-12 shows that if a class is imported (parentBox is not nil) then the lookup pursues in the provider classbox. If this class is not imported (parentBox is nil), as shown at the line 19, then the lookup continues in the superclass.

The lookup in a superclass is done only if it is stated that a class does not provide any implementation for a given message. Within the classbox model this implies that we have to run over the chain of imports to make sure that a classbox does not extend this class with the corresponding method. GraphicCB defines a hierarchy composed of three classes: Component provides Classboxes allow you to have several versions of a method to coexist simultaneously. Depending on where this method is called from (i.e. from which classbox) the right method implementation is selected according to the method lookup algorithm described previously. When a classbox extends a class it can either be a method addition or a method redefinition. With our current implementation, calling a method that has been simply added by a classbox does not impose any overhead. However calling a method that has been redefined has an extra cost: the lookup algorithm previously presented is performed. However, this result is cached. Our cache mechanism is based on the following basic a redefined method is often called by the same object within the same classbox. The byte-code of an extended method is transformed to include 5 byte-codes that check if the caller for this method is the one that has been previously cached. For method addition there is no need to use a cache because there is only one version of the method present in the system.

The following table illustrates the cost of the lookup of a redefined method compared with traditional lookup. The experiment consists in calling 6 millions times a method that is redefined. It shows that there is a constant overhead that does not depend on the graph of import. This overhead is due to the extra few byte-codes added at the beginning of the method. The method used for the benchmarks is composed of one byte-code (simply return a numerical value). The same method that checks if the cache is valid is about 2.5 times ((5176 -1477) / 1477) slower.

Related Work

Selector Namespaces. Languages like ModularSmalltalk [START_REF] Wirfs-Brock | An overview of modular Smalltalk[END_REF], Subsystems [START_REF] Wirfs-Brock | Subsystems -proposal[END_REF] and Smallscript [START_REF] Simmons | Smallscript[END_REF] Unit. MZScheme [START_REF] Flatt | Units: Cool modules for hot languages[END_REF] offers an advanced module system where a unit is the basic building block. A unit is a packaging entity composed of requirements, definitions and exports. Units have to be instantiated and composed with each other to form a program. The key point of this model is that connections between modules or classes are specified separately from their definitions. This principle allows a module to be instantiated at link time. Reusability and extensibility are expressed by recombining units. An application, made of units, can be recomposed and by aliasing new units can be inserted. Units differ from classboxes since a unit acts as a black box: a class within a unit cannot be extended. Instead a new unit has to be provided and included in a recomposition.

Hyper/J. Hyper/J [START_REF] Ossher | Hyper/J: multi-dimensional separation of concerns for java[END_REF] is based on the notion of hyperspaces, and promotes compositions of independent concerns at different times. Hyperslices are building blocks containing fragments of class definitions. They are intended to be composed to form larger building blocks (or complete systems) called hypermodules. A hyperslice defines methods on classes that are not necessarily defined in that hyperslice. Such methods define a class extension, and classes intended to be extended are known at integration time. However this kind of extension does not allow redefinition and consequently does not help in supporting unanticipated evolution.

Virtual Classes. The specification of a virtual class [16] [17] is completely analogous to the specification of a virtual procedure. By introducing a dynamic lookup of a class name in a hierarchy of encapsulating entities (module for Keris [START_REF] Zenger | Evolving software with extensible modules[END_REF], collaboration interfaces for Caesar [19] [20], classes for gbeta [START_REF] Ernst | gbeta -a language with virtual attributes, block structure, and propagating, dynamic inheritance[END_REF], or teams for Objectteams [START_REF] Herrmann | Object confinement in Object Teams -reconciling encapsulation and flexible integration[END_REF]) it is possible to refine a class within a subentity. One limitation with virtual classes is that the "virtuality" is scoped to a hierarchy: outside this hierarchy a class is not virtual anymore. For instance let us assume C to be a virtual class attribute in a hierarchy H1. In an unrelated hierarchy H2, class C is not virtual anymore and cannot be redefined.

Object-Based Inheritance. By providing true delegation, Lava [START_REF] Kniesel | Darwin -dynamic object-based inheritance with subtyping[END_REF] supports dynamic unanticipated changes using class wrappers. By introducing a new language construct, an object a (instance of A) can delegate all nonunderstood messages it receives to a delegatee object b (instance of B). Lava provides a true-delegation mechanism whereas the self reference used in the class B refers to the delegating object a. Methods defined in b that are unknown to a are the extensions brought on a. So redefined or new methods are attached to a particular object rather than a class. True delegation provides a way for adding or redefining methods for a particular object whereas classboxes extend classes.

Conclusion and Future Work

Classboxes address the problem that classical module systems do not offer the ability to add or replace a method in a class that is not defined in that module. Classboxes offer a minimal module system for object-oriented languages in which extensions (method addition and replacement) to imported classes are locally visible. Essentially, a classbox defines a scope within which certain entities, i.e., classes, methods and variables, are defined. A classbox may import entities from other classboxes, and optionally extend them without impacting the originating classbox. Concretely, classes may be imported, and methods may be added or redefined, without affecting clients of that class in other classboxes. Local rebinding strictly limits the impact of changes to clients of the extending classbox, leading to better control over changes, while giving the illusion from a local perspective that changes are global.

To see the impact of classboxes on a real-world example we remodularized an existing application (the seaside web server application [START_REF]Seaside: Squeak enterprise aubergines server[END_REF] built upon a web server [START_REF]Comanche: a full featured web serving environment for Smalltalk[END_REF]) with classboxes. The goal is to show the usefulness of class extensions by measuring the proportion of class extension among the defined methods (for more details see the technical report [START_REF] Bergel | Classboxes: Controlling visibility of class extensions[END_REF]).

We have implemented a proof-of-concept prototype of classboxes in Squeak.

In our implementation, the method lookup mechanism in the Squeak virtual machine has been modified to take classboxes into account. This prototype exhibits an overall 10% slowdown in performance for real-world applications.

In the future we will analyze some very large applications developed without any local rebinding facilities in order to identify places where programmers simulated local rebinding.

Currently classboxes function purely as a packaging and scoping mechanism. We intend to investigate various extensions of classboxes. We expect that an integration with traits will be fruitful, as this will enable packaging of collaborating traits [START_REF] Schärli | Traits: Composable units of behavior[END_REF] (and their associated tests). Presently classboxes lack any notion of a component model. We expect that explicit interfaces and composition mechanisms for classboxes will increase their usefulness. In particular, we intend to investigate the application of encapsulation policies [START_REF] Schärli | Composable encapsulation policies[END_REF] to class-

(

  Fig. 2. The dead-link checker modularized with classboxes.

Fig. 3 .

 3 Fig. 3. The method ping is extended by two different classboxes. Conflict is avoided because extensions are confined to their respective classboxes.

Definition 8

 8 We can send a message m to an object o c, φ , where c = c δ, B, ǫ obtaining a method closure:

Definition 11 A

 11 classbox b n, α consists of an identifier n ∈ X (i.e. classbox names) and a function α from class namespaces to class namespaces. The intuition here is that a classbox is open because it can always be extended with new class definitions, imports and extensions. As a consequence, we do not yet know the class namespace of the classes it provides. However we can close a classbox, thereby fixing the class namespace of all the provided classes. Definition 12 A classbox b n, α can be closed by sending it the close message, generating a fixpoint: b n, α [close] def = µǫ.αǫ The resulting class namespace must be closed, i.e., all used class names must be defined. Since α is a function from class namespaces to class namespaces, µǫ.αǫ represents a fixpoint in which all the classes provided by the classbox are made visible to each other. Definition 13 We may lookup the decorated class name C n corresponding to a raw class name C in a classbox b n, α :

Definition 14

 14 An empty classbox with identifier n is: empty(n) def = b n, λǫ → ∅ . Note that empty(n)[close] = ∅, i.e., closing an empty classbox yields an empty class namespace. Definition 15 We can introduce to a classbox b n, α a new class C that subclasses B (defined in a classbox b m, β ) with δ as method dictionary by sending it the message def subclasses with. b

Definition 16 A

 16 classbox b n, α may import a raw named class from another, classbox b m, β , by sending it the message import. b

Definition 17 A

 17 classbox b n, α may extend a raw class named class from another classbox b m, β , by sending it the message extend with. b n, α [extend C with δ ′ from b m, β

Fig. 4 .

 4 Fig. 4. Resolving Diamond conflicts

1 4 |

 4 lookup: selector class: cls 2 startBox: startbox currentBox: currentbox classboxPath: path 3

10 parentBox:

 10 = currentbox providerOf: cls name.

  path addLast: parentBox.

  theSuper := cls superclass.

20

  theSuper ifNil: [^cls method: selector notFoundIn: cls].

21 togoBox:

 21 = path detect: [:box | box scopeContains: theSuper].

22 newPath:

 22 = togoBox = startbox 23 ifTrue: [OrderedCollection with: startbox]

  24 ifFalse: [path].

Fig. 5 .

 5 Fig. 5. The lookup algorithm that provides the local rebinding.

Figure 6

 6 Figure 6 illustrates this property of the algorithm by depicting an example. It shows four classboxes: GraphicCB, RoundedWindowCB, DoubleBufferCB and DoubleBufferAndRoundedCB. Each of theses defines extensions or simply imports classes to combine some of the extensions.

  provide a scoping mechanism called Selector Namespaces, in which methods are inserted. As a result, class extension conflicts are avoided, and several applications can bring the same class extension referring to the same class and method without interfering with each other. As a result, class extensions are not globally visible, but confined to a bounded scope. However selector namespaces do not support the local rebinding property, since a new definition does not take precedence when original code is called. An open class is a class whose methods are extensible. New methods can be added to an open class. These new methods are visible within the package that provides them and in the packages importing that package. Method redefinitions are not allowed: an open class cannot have one of its existing methods redefined. On the other hand, two class extensions can define a method on the same class with the same signature. In that case the extensions are scoped separately.

Multijava. Multijava

[START_REF] Clifton | MultiJava: Modular open classes and symmetric multiple dispatch for Java[END_REF]

is an extension of Java that supports open classes and multiple method dispatch.

Acknowledgment. We also like to thank Curtis Clifton, Erik Ernst, Günter Kniesel and Peri Tarr for their valuable comments and discussions.

Foundation for the projects "Tools and Techniques for Decomposing and Composing Software" (SNF Project No. 2000-067855.02) and "Recast: Evolution of Object-Oriented Applications" (SNF 2000-061655.00/1).

The implementation identified for the method m is the result of {m → CM}m = CM.

(ii) Methods defined when importing a class are visible within the importing classbox.

The rest of the proof follows what is already shown in (i).

Proposition 2 Importing a class makes its methods previously defined visible in the importing classbox.

Then as already shown in the first proof, sending a message m to an instance of ϕC p triggers the execution of CM. In RoundedWindowCB the new implementation of paint does a super paint which executes the paint method in GraphicCB. Evaluating Frame new update in RoundedWindowCB triggers the update method contained in Component and the local definition of paint is executed, the one provided by RoundedWin-dowCB.

DoubleBufferAndRoundedCB combines the double buffer and the rounded facilities by importing Component from DoubleBufferCB and Frame from Rounded-WindowCB. Evaluating Frame new update in DoubleBufferAndRoundedCB triggers update defined in GraphicCB which send the message paint. The implementation taken is the one provided by RoundedWindowCB because Frame is imported from it. This implementation does a super paint, which execute the paint method defined in DoubleBufferCB.

Method Lookup Performance

Making the overhead related to our new method lookup as low as possible was one of our major concerns. Compared to the description given in [START_REF] Bergel | Classboxes: A minimal module model supporting local rebinding[END_REF], our implementation of the model is greatly enhanced: there is no need to modify the VM (due to the message passing control mechanism [START_REF] Ducasse | Evaluating message passing control techniques in Smalltalk[END_REF] offered by Squeak) and the cost of the new method lookup greatly reduced (thanks to a cache mechanism).

boxes.