Oscar Nierstrasz

Marcus Denker

Tudor Gîrba

Adrian Lienhard

Analyzing, Capturing and Taming Software Change *

Software systems need to continuously change to remain useful. Change appears in several forms and needs to be accommodated at different levels. We propose Changeboxes as a mechanism to encapsulate, manage, analyze and exploit changes to software systems. Our thesis is that only by making change explicit and manipulable can we enable the software developer to manage software change more effectively than is currently possible. Furthermore we argue that we need new insights into assessing the impact of changes and we need to provide new tools and techniques to manage them. We report on the results of some initial prototyping efforts, and we outline a series of research activities that we have started to explore the potential of Changeboxes.

Introduction

Complex software systems must change in order to keep pace with changing needs and requirements [START_REF] Lehman | Program Evolution: Processes of Software Change[END_REF]. If we carry this observation to its logical conclusion, the ability to plan needs to be augmented by the ability to change [START_REF] Beck | Extreme Programming Explained: Embrace Change[END_REF]. Curiously, however, modern programming languages and environments provide little support for the fact that the systems being built will inevitably change [START_REF] Nierstrasz | On the revival of dynamic languages[END_REF]. In fact, more emphasis is placed on mechanisms to enforce consistency and to limit the effects of change than on enabling change.

This position paper targets the following questions:

-How can we encapsulate change in order to better specify, manipulate and control it? -How can we manage the scope of change, especially in a running system? -How can we assess the impact of change in a complex system? -How can we exploit change to reveal implicit trends and emergent software artifacts?

To answer these questions, we propose to (i) introduce Changeboxes, a programming language construct to package incremental modifications to complex software systems, and use these constructs to express both low-level (syntactic) and high-level (semantic) changes, (ii) develop a scoped approach to behavioural and structural reflection in which the visibility of reflective features, and thus of changes, can be controlled at a fine level of granularity, (iii) explore techniques for tracing the impact of changes back to their source by monitoring the flow of object references in a running system, and (iv) analyze the evolution of the software and related artifacts to identify higher-level semantic entities.

Changeboxes: How to encapsulate change?

Present-day development tools and environments do not deal with change in an explicit way. Although integrated development environments such as Eclipse help in integrating different aspects of the development process (i.e., revision control, code refactoring) the current solutions are far from ideal because they are not based on a common infrastructure. They do not support well:

• Capturing information about changes. Most revision control systems are only snapshotbased and changes can only be identified post facto as differences between versions [START_REF] Mackenzie | Comparing and Merging Files With Gnu Diff and Patch[END_REF]. Furthermore, they do not provide any semantical information about the changes performed.

• Concurrent development in a team. Short synchronization cycles and switching between different versions of a software are hampered by a tedious file-and snapshot-based, update-merge-commit procedure [START_REF] Robbes | Versioning systems for evolution research[END_REF].

• Incremental adaption of a system to cope with a specific change. Large refactorings can affect many parts of a system and therefore may need a considerable amount of work to be pushed through [START_REF] Dig | The role of refactorings in API evolution[END_REF][START_REF] Henkel | CatchUp!: capturing and replaying refactorings to support API evolution[END_REF]. While unfinished, the system is not in a consistent shape and cannot be integrated with other work, hindering the evolution or even preventing developers from applying the refactoring.

We propose to investigate means to better support evolution of software systems by explicitly modeling changes at the level of the development environment and programming language. The specific question we want to answer is: What are the appropriate abstractions to explicitly model the evolution of a software system?

Classboxes are a scoping mechanism to support unanticipated changes [START_REF] Bergel | Classbox/J: Controlling the scope of change in Java[END_REF][START_REF] Bergel | Classboxes: Controlling visibility of class extensions[END_REF]. Classboxes are coarse-grained components that enable developers to locally extend software in a uniform way without impacting other users of that software. As Classboxes have been designed to enable scoping of class extensions, we propose to apply the same principle not only to scope structural changes but also to scope changes over time in an uniform way. From another perspective, as a result of our research in understanding software evolution we concluded that evolution should be modeled as a first class entity [START_REF] Gîrba | Modeling history to analyze software evolution[END_REF].

We propose to explore a model for fine-grained changes as first-class entities, and we propose to use this mechanism, called Changeboxes, to express both time-based and structural scoping mechanisms. Changeboxes will allow several versions of the same software artifact to coexist and to be runnable at the same time.

We plan to model changes as ubiquitous events in the evolution of a system, that is, each change brought by a developer will be immediately accessible by any other team member. The difference to changes having global effect is that each change is performed within a specific scope, and the environment allows the developer to switch between these scopes as appropriate. We believe this will achieve a more transparent development process, and will provide a rich model for integrating tools and performing analysis for reverse and reengineering.

We will start by implementing a Smalltalk prototype of Changeboxes which will express the possibility of add or remove methods. The first prototype will be based on the Classbox implementation. The next step will be to enable the addition or removal of classes, instance variables and changes in inheritance relationships.

Changebox Prototype

We have started our prototype from the approach implemented in Classboxes. In short, this consists of changing the method lookup of Squeak to take into account different versions of methods depending on the execution context. This allows additions and changes of methods to be expressed. We have further extended this approach to deal with removing methods.

The sequence of method changes is reified by modeling method versions as first-class entities. The prototype allows one to select any version of the system and execute or browse the source code of the program in this context. This approach is based on the dynamic lookup in object-oriented systems and on the fact that in Squeak we can reify method execution. In Squeak, however, the lookup of classes is not dynamic (i.e., it is performed at compile time), hence we cannot apply the same approach for expressing several versions of a class definition, for example to take into account instance variable or inheritance modifications.

We are currently investigating ways of modifying the class lookup of the system to be dynamic and to introduce namespaces for managing different versions of the same class. Combined, these techniques would allow for looking up the appropriate class based on the active version of the execution context.

A key validation of Changeboxes will be to express not only low-level modifications to specific versions, but to also express higher-level refactorings which can eventually be applied to different versions of different artifacts. A more important long-term goal is to be able to use Changeboxes as a mechanism to push changes through a system in a controlled way, using scoped reflection.

3 Scoped Reflection: How to manage the scope of change?

Not only source-code, but running systems need to evolve as well. Software systems are typically changed by modifying the source code and recompiling the whole system. This rather old-fashioned model of software development suffers from two outmoded assumptions that are increasingly in conflict with the reality of modern software applications. First is the assumption that the system must be stopped, recompiled and restarted. Many of today's software systems must be up virtually all the time. Second is the assumption that the universe is consistent. Software systems today must cope with the fact that libraries, components and peer systems may be based on incompatible versions of interfaces, protocols and standards. We therefore need mechanisms to enable (i) runtime changes, and (ii) scoped visibility of changes.

Reflection is the ability of a system to change itself at runtime [START_REF] Cantwell | Reflection and semantics in a procedural language[END_REF][START_REF] Maes | Concepts and experiments in computational reflection[END_REF][START_REF] Ferber | Computational reflection in class-based object-oriented languages[END_REF]. Smalltalk is a reflective system in which the structure of the system is described by classes and can be changed anytime. Aside from these structural reflective capabilities, however, there is no meta object protocol to support fine-grained control of behavior. We have recently implemented Geppetto [START_REF] Röthlisberger | Geppetto: Enhancing Smalltalk's reflective capabilities with unanticipated reflection[END_REF], a dynamic runtime meta object protocol for behavioral reflection based on the design of Reflex [START_REF] Tanter | Partial behavioral reflection: Spatial and temporal selection of reification[END_REF].

We plan to extend the behavioral reflection framework of Geppetto with the notion of scoped behavioral reflection. This means we want not only to control what (spatial) and when (temporal) to reflect, but in addition to control the reifications based on the control flow. For example, we want to specify that reifications are active only if the control flow originates in a specified sub-system.

We plan to explore a reflective system that not only scopes behavioral reflection, but in addition provides scoping capabilities for structural reflection. In this track we plan to leverage the work on Changeboxes. We plan to use the behavioural reflection framework as a mechanism to selectively scope the application of Changeboxes dependent on a given context. Conversely, we also plan to use Changeboxes as a mechanism for controlling the availability of the reflective mechanisms themselves. Depending on the current context, then, reflective capabilities may be available, or safely locked away.

In the long term, we plan to explore how the combination of scoped reflection and Changeboxes can enable a more general model of context-oriented programming [START_REF] Costanza | Language constructs for context-oriented programming[END_REF], in which the structure and behaviour of software artifacts may change dynamically but in a controlled way depending on the dynamic context.

4 Object Flow Analysis: How to assess the impact of change?

Even small changes can break a system in unexpected ways. To fix a problem the developer has to understand the connection between the location where the problem manifests itself and its cause, the change that introduced the problem.

Dynamic analysis covers a number of techniques for analyzing information gathered while running the program [START_REF] Ball | The Concept of Dynamic Analysis[END_REF][START_REF] Systä | Understanding the behavior of Java programs[END_REF]. As object-oriented technology became more wide-spread, it was only natural that procedural analysis techniques were adapted to object-oriented languages. In this context many dynamic analysis techniques focus on only the execution trace as a sequence of message sends [START_REF] Michael | GraphTrace -understanding object-oriented systems using concurrently animated views[END_REF][START_REF] Licata | The feature signatures of evolving programs[END_REF][START_REF] El-Ramly | Recovering software requirements from system-user interaction traces[END_REF][START_REF] Zaidman | Applying webmining techniques to execution traces to support the program comprehension process[END_REF][START_REF] Antoniol | Feature identification: a novel approach and a case study[END_REF].

In object-oriented programming the understanding of problems is often complicated due to the temporal and spatial gap between the root cause and the effect of errors. Figure 1 illustrates an example of an execution trace of a program. The order of method activations (squares) is from bottom to top and left to right. While the cause of the bug is introduced at the beginning of the execution, the effect occurs much later on (temporal gap). Moreover, the locations of the cause and the effect are distant in the object space because objects have been passed around during execution (spatial gap). Figure 1 also illustrates the execution stack at the point when the error occurred. This is the typical view of a debugger showing the method activation in which the bug is manifested.

The location of the cause of the bug, however, is hidden.

The reason for this gap is static object aliasing -an inherent property of object-orientation. By means of instance variables the flow of an object can bridge the linear sequence of method executions.

Figure 2 illustrates the flow of an object relative to the same program execution. While the object is first passed along with the execution trace, its path later diverges and jumps to distant branches of the tree. This example illustrates how changes to the software system which modify the behavior of objects may have unexpected effect at distant locations of program execution. Therefore, to connect the cause and the effect of errors we need to trace the flow of objects. This will support the developer in finding errors by allowing him to follow incorrectly behaving objects back along their path.

We plan to investigate a run-time model that complements execution traces with object flow information. We are currently working on a prototype for run-time analysis which introduces the concept of object alias to represent explicitly the references to an object.

In comparison to the concept of omniscient debugging [START_REF] Lewis | Debugging backwards in time[END_REF] which traces the whole execution of the program at a low level, our prototype will additionally provide information about the flow of objects.

Based on this model we plan to build a high-level object-centric debugger. By tracing the flow of objects the debugger can provide shortcuts between the chronological sequence of method executions.

Changeboxes will allow for several versions to coexist in the same system. To identify the impact of changes from one version to another, we will implement analyses to compare the dynamic information of the execution of the two versions. In this way we can get closer to identifying the cause of a bug.

Evolution Analysis: How to exploit change?

The evolution of software systems is driven by changes at the level of the domain (e.g., features), as change requests are specified in terms of domain concepts. That is why it is important to map domain concepts to code [START_REF] Fischer | Visualizing feature evolution of large-scale software based on problem and modification report data[END_REF][START_REF] Fischer | Analyzing and relating bug report data for feature tracking[END_REF][START_REF] Cubranić | Hipikat: Recommending pertinent software development artifacts[END_REF].

We propose to pursue several techniques to locate domain concepts from the code and then to analyze how the domain concepts have evolved in the code as opposed to how they are linked conceptually. Different works analyze how the changes in the code relate to the features implemented, by using dynamic analysis [START_REF] Antoniol | Feature identification: a novel approach and a case study[END_REF][START_REF] Greevy | Correlating features and code using a compact twosided trace analysis approach[END_REF][START_REF] Zaidman | Applying webmining techniques to execution traces to support the program comprehension process[END_REF]. We argue that we need to further investigate this path to recover domain interpretations for the changes in the code, that is, to identify the reasons why the code was changed [START_REF] Greevy | Analyzing feature traces to incorporate the semantics of change in software evolution analysis[END_REF].

Other sources of domain information are the comments and the names of the identifiers [START_REF] Kuhn | Enriching reverse engineering with semantic clustering[END_REF]. The analyses proposed so far typically focus on one version only. We argue that we need to use information retrieval techniques over several versions of a system to detect when the concepts appear in the system, how they spread and perhaps how they die.

Our main goal is to identify the kind of semantics of changes that would be useful to be encapsulated in Changeboxes. Current versioning systems allow for a textual description to be attached to every new version, but this free-form is difficult to analyze automatically. We plan to allow the developer to relate his changes with the domain concepts using Changeboxes. On the one hand, we want to identify what mechanisms we need for modeling the domain knowledge and relate them to the code changes. On the other hand, we plan to use our automatic analyses to provide hints for the relevant concepts for a change.

From another perspective, software evolution is driven by developers. That is why we need to get more insights into how developers work together to better understand how to support their activities. Several techniques have been proposed to detect patterns of how developers change the system, by analyzing versioning repositories [START_REF] Ball | Software visualization in the large[END_REF][START_REF] Gîrba | How developers drive software evolution[END_REF][START_REF] Mockus | Identifying reasons for software change using historic databases[END_REF][START_REF] Wu | Exploring software evolution using spectrographs[END_REF][START_REF] Wu | A reverse engineering approach to support software maintenance: Version control knowledge extraction[END_REF]. A particular focus is to combine the developer analysis with the concept location analysis to assign domain concepts to developers. In this way, we link the reasons for change with the different behaviors. By analyzing the developers patterns, we expect to gather requirements for building tools on top of the Changeboxes to facilitate the distributed team development.

Concluding remarks

Current programming languages and development environments are focused on limiting the effects of change rather than on enabling change. We have argued here that we need a fresh perspective on how to approach changes, and we have identified several paths to be followed.

On the one hand, we have proposed to tackle changes from a forward engineering point of view. We have proposed Changeboxes, a mechanism that treats changes as first class entities in the environment. Scoped Reflection extends the idea of Changeboxes to cover reflective change. We have proposed to broaden the notion of scope for behavioral reflection and explore the idea of scoping structural reflective change. On the other hand, we have argued that we need to advance our understanding of changes. In this direction, we have proposed a novel approach to assess the impact of change by analyzing how objects flow through a running system. We have also argued for the need to understand how developers drive software evolution and how the evolution of the system relates to the evolution of the domain concepts.

We hope that these efforts will constitute a small step in the direction of freeing programming languages from the stranglehold of static thinking that has historically dominated and (in our opinion) stifled programming language development. Sooner, rather than later, we expect to see a new class of dynamic languages emerge that consider change to be a normal and essential component of the programming language itself.

Figure 1 :

 1 Figure 1: Execution trace emphasizing the cause effect gap of a bug.

Figure 2 :

 2 Figure 2: Object flow observed from the execution perspective.

Acknowledgments

We gratefully acknowledge the financial support of the Swiss National Science Foundation for the project "A Unified Approach to Composition and Extensibility" (SNF Project No. 200020-105091/1, Oct. 2004 -Sept. 2006).

The research proposed in the paper is planned to be carried out in the context of "Analyzing, capturing and taming software change" (SNF Project Proposal No. 200020-113342, Oct. 2006 -Sept. 2008).


Abtract

Few real software systems are built completely from scratch nowadays. Instead, systems are built iteratively and incrementally, while integrating and interacting with components from many other systems. These systems also last longer than their developers might imagine -they are, in effect, eternal. Nevertheless the platforms, tools and environments we use to develop software are still largely based on an outmoded model that presupposes that software systems are closed and will not significantly evolve after deployment. We claim that in order to enable effective and graceful evolution of eternal systems, we must make them self-aware. A self-aware eternal system supports evolution by: (i) providing explicit, first-class models of software artifacts, change and history at the level of the platform, (ii) continuously analysing static and dynamic evolution to track emergent properties, and (iii) closing the gap between the domain model and the developers' view of the evolving system. We outline our vision of self-aware eternal systems and identify the research challenges to realizing this vision.

IAM-08-001 2 Eternal Systems

Software inevitably changes, but our development methods, programming languages, development environments and run-time systems provide little that acknowledges this fact. There is a general assumption behind most tools and methods that one is building a closed, internally consistent application, which will not significantly change after deployment. Anticipated evolution can be built in to some extent, for example by applying well-known design patterns, but unanticipated changes in requirements are hard to accommodate without reengineering the system, redeploying it, and possible migrating persistent data. The vision of an eternal software-intensive system is that of a system that can survive such unanticipated changes with little or no human intervention at the lowest level [START_REF]Report of the Beyond the Horizon thematic group 6 on Software Intensive Systems[END_REF]. We claim that this vision can only be realized if software evolution is supported in a fundamental way in our platforms, runtime environments and development environments [START_REF] Nierstrasz | Software evolution as the key to productivity[END_REF]. Specifically, what does this entail? First of all, we need to provide platforms in terms of programming languages and run-time environments that make it possible to manipulate and operate on change as a first-class entity. This in turn implies that an eternal system is not only model-driven, but actually self-aware -it must have a first-class representation of itself available to enable change. To control the scope of change, change itself should be represented as a first-class, high-level entity. And to manage change over time, the history of the system must also be accessible and first-class (see Section 3). Second, a self-aware eternal system must be capable of analyzing itself, and in particular of recognizing emergent properties. This means that the evolution of the static and dynamic models must be monitored, and the resulting data be analyzed as the system is running (see Section 4). Third, to enable continuous evolution, a self-aware eternal system must close the gap between the development and deployment views of itself. Domain models, usage models, and features, for example, must be made explicit in the system to facilitate change (see Section 5). Finally, concrete incentives are needed to bring research and practice closer together (see Section 6).

Self-aware Platforms for Eternal Systems

Traditionally, the development and deployment of software are viewed as being separate in time and space: first a system is developed, then it is deployed. Indeed, in the classical view, we deal with two completely different artifacts: the source code that can be developed, debugged and understood on the one hand, and on the other hand a generated, closed, non-understandable binary program that just can be run. Classical development plays out like a finite game with fixed rules and boundaries. Eternal software-intensive systems, on the other hand, are better thought of as infinite games without fixed rules or boundaries [START_REF] Carse | Finite and Infinite Games -A Vision of Life as Play and Possibility[END_REF]. Eternal systems will not have a clear separation of development and deployment. The system will continue to evolve when it is already deployed. The systems of the future will not be developed from the outside as a finite game. Development itself will be part of the infinite game of the system. Evolution needs to happen in parts of the system, while it is running. We cannot afford to stop and restart an eternal software system, just as we cannot stop and restart the Internet. The Internet has been up and running since 1969, although each atom that it is physically made of has been replaced since then. The software intensive systems of the future will need to learn from these loosely-coupled, long-lived systems. To support this view, we need appropriate core technologies in terms of programming languages and runtime systems that can serve as a platform for developing eternal systems. In order to enable change at runtime, an eternal system must be able to fully reflect on itself, that is, it must be self-aware. It is not enough to be model-driven. The models must be explicit and accessible to the run-time system. Furthermore, changes to the model and the system must be explicit and manipulable, so changes must have a first-class representation. Finally, in order to reason about the impact of changes, it is essential that the history of the system must also be fully accessible and manipulable. It has been very early understood that abstractions are needed for making programming in the large possible. But with scale, we need to think again: are existing abstractions good enough for very large software systems? One example is that as software gets larger, the idea that every part of the system is in sync with any other part is not very convincing: in huge systems, the parts will indeed be inconsistent. Evolution itself will lead to inconsistency, as the system is so large that we can never evolve the complete system at the same time. As a consequence, an eternal system IAM-08-001 must be able to cope with multiple, inconsistent views of itself. Inconsistency is only tolerable if specific and individual views appear to be locally consistent. Instead of allowing all changes to be globally visible, we need a means to control the scope of changes. That is, eternal systems must support a notion of context and the run-time infrastructure must be context-aware. Being able to dispatch on context means that we need to support a form of context-oriented programming [START_REF] Costanza | Language constructs for contextoriented programming: An overview of ContextL[END_REF]. Visibility of changes can then be restricted to the context in which these changes are guaranteed to be valid. Backward compatibility is the enemy of forward-evolvability. Nevertheless, we cannot live in a world were the old is ignored. A snapshot of an old Windows machine can run on a virtual machine forever, whereas keeping an operating system compatible forever will be bound to fail. Programming languages for eternal systems should provide backwards compatibility in the same way: we need a first class description of the history of all code of the system, freeing the present from being compatible with the past while at the same time providing the possibility to go back in time easily. The system should provide complete, runnable snapshots of the system at any point in the past.

Eternal systems need languages that support continuous development and evolution. But there is another aspect to the language: to think that we can envision the perfect language to realize all future systems is to treat language design like a finite game. Thus a language suited for implementing ever-evolving, eternal software systems needs to be itself an eternal program. An eternal language must evolve to incorporate new ideas and practices while it is used. It needs to be extensible and growable from within [START_REF] Steele | Growing a language[END_REF].

Analyzing Self-aware Eternal Systems

To change a system we must first understand the system and the consequences of change. Since change inevitably causes the system to drift from its initial documentation, the most reliable source of information is the system itself. However, documentation will not only be provided in form of documents, but also in various other forms like online discussions, bug reports, and description of the changes [START_REF] Fischer | Analyzing and relating bug report data for feature tracking[END_REF]. Therefore, software analysis tools for reverse engineering are central to support software evolution [START_REF] Nierstrasz | Analyzing, capturing and taming software change[END_REF].

A self-aware system can reflect on its own specification, which is an aid to static analysis. But the run-time architecture and other emergent properties can only be monitored with the help of dynamic analysis [START_REF] Hamou-Lhadj | A survey of trace exploration tools and techniques[END_REF]. A self-aware, eternal system must be capable of tracing and analyzing its run-time behaviour while it is online, much like garbage collectors are always active in modern virtual machines.

In eternal software systems, the changes to the static parts are directly accessible as first class entities. As such, in eternal software systems, not only the run-time is dynamic, but also the static part is dynamic when seen from a historical perspective. Treating history as a first-class entity enables analyses of the evolution of software artifacts [START_REF] Gîrba | Modeling history to analyze software evolution[END_REF]. Given the size of eternal systems, they will not be developed by an isolated team, but rather by several teams that are physically distributed. In this context, the social aspect of the development will become increasingly important [START_REF] Conway | How do committees invent?[END_REF]. Thus, analysis will also consist of reasoning about how developers collaborate. Yet another complicating factor is the use of different languages and media within the same system. Furthermore, some of the languages used will be either legacy languages or dialects. For this reason, post-hoc parsing of components built with these languages will be difficult and error-prone. Thus, a software eternal software can be seen as a multi-dimensional space of data that needs to be continuously analyzed.

IAM-08-001

Environments for Evolving Eternal Systems

The evolution, or rather continuous development, of eternal systems places special demands on the development environment.

To some extent systems can be designed for evolution. But if we see the development of an eternal system as an infinite game, it becomes clear that one cannot anticipate all forms of evolution. Support for refactoring, reorganizing and reengineering must be part of the evolving system. The state-of-the-art in refactoring support is still in its infancy. Many modern IDEs provide some automated mechanisms to change and evolve a software-intensive systems. For instance, they support automated refactorings such as renaming a class or moving a method from one class to another [START_REF] Roberts | A refactoring tool for Smalltalk[END_REF]. Eclipse, for example, is very well adopted in industry, with more than half of all Java developers using this environment in their daily work [START_REF] Goth | Beware the march of this IDE: Eclipse is overshadowing other tool technologies[END_REF]. Nevertheless, automated refactorings tend to be low-level, the fact that code has been refactored is not evident in the code base, and developers obtain no guidance in identifying opportunities for refactoring.

Examples of promising research directions that would help to support the development of eternal systems include mining system histories to guide developers in implementing or adapting features [START_REF] Zimmermann | Mining version histories to guide software changes[END_REF], and guiding developers to the use and reuse of existing components [START_REF] Ye | Reuse-conducive development environments[END_REF][START_REF] Cubranic | Hipikat: Recommending pertinent software development artifacts[END_REF]. A further problem with modern IDEs is the difficulty of bridging the gap between the users' view and the developers' view of the system. For instance, it is hard to locate and understand a specific feature in a system consisting of a large number of classes. Furthermore, there is a significant gap between the static, class-oriented view of the source code and the dynamic, object-based view of the run-time system. To build a comprehensive mental map of a large system the developer needs to navigate many classes and methods, a process which is only poorly supported by Eclipse and most other modern IDEs.

Empirical studies report that a developer performing maintenance tasks on a system spends at least 35% of the time in navigating source code to get a understanding for the implementation of a specific feature [START_REF] Ko | Eliciting design requirements for maintenance-oriented ides: a detailed study of corrective and perfective maintenance tasks[END_REF].

A maintenance-oriented IDE should present the developer with a working set of source code containing all functionality for a specific maintenance task to reduce the navigational load. By monitoring the programmer's activity to get a degree-of-interest for program elements scattered across a large code base, the IDE can reveal code elements that are likely to be important for the task at hand [START_REF] Kersten | Mylar: a degree-of-interest model for ides[END_REF]. By monitoring the execution of common user tasks, an eternal system can correlate features with software artifacts [START_REF] Greevy | Analyzing software evolution through feature views[END_REF] and use this information to drive development tasks related to those features.

Static and dynamic analysis of eternal systems, as outlined in Section 4, can be tightly integrated into the development environment to help drive evolution. For instance, visualizations of the system or of a specific feature should be accessible directly in the programming environment. As the system evolves these visualizations have to evolve as well to constantly reflect the changing structure and behavior.

IAM-08-001

Fostering Research in Eternal Systems

Not only do we need to research new ways of dealing with software evolution, but the way to conduct the research needs to be adapted to the task. The greater the body of existing work, the more people will research the area, and the more difficult it will be for a single person to achieve a reasonable delta within a reasonable amount of time. As a consequence, it becomes essential to have an infrastructure that allows the state of the art to be readily applied. Currently PhD students serve as the engine of much research. Typically a PhD student must ensure that the research carried out be distant enough from that of his peers that there be no overlap in terms of the new ideas. Hence, the PhD student will tend to implement and validate his work alone. As a consequence, although the new ideas may spread, there is no incentive to ensure that the implementation will survive to be used by others. The next PhD student will have to re-implement those ideas before he can build on them. This process does not scale, as the research space grows larger.

On the one hand, we advocate that the research process will need to acknowledge and to reward the engineering effort. In the future, research and engineering must meet to face the wide space opened by eternal systems. On the other hand, just like eternal systems will not be the result of one team's work, we advocate that research will need to break the group boundary and open towards research networks [START_REF] Bennis | Organizing Genius -The Secrets of Creative Collaboration[END_REF].

Bringing together research and engineering will also bring together two worlds that are now rather separated: research and practice. Practitioners face real problems and need new ideas to solve these problems, but cannot afford the time and effort to experiment with unproven ideas. Researchers need real problems to develop new ideas, but cannot afford the effort to fully validate and mature these ideas in a practical setting. Each group is under pressure to get their product out the door with acceptable quality and minimum cost. As a consequence few new ideas get proven in practice, and real problems of practitioners tend not to propagate in the research environment. The perceived cost of collaboration is just too high. A first step to bring these groups together and reduce the cost of collaboration is to provide an infrastructure in which new ideas can be quickly implemented, tested and adopted. The need for collaboration to build a successful infrastructure can be seen in the wide adoption of Eclipse as a platform [START_REF] Holzner | Eclipse[END_REF]. Many teams contribute to Eclipse due to its open archi-tecture, and many researchers are using it for implementing their vision. While Eclipse is not an academic exercise, it does facilitate software evolution research. To facilitate relevant and collaborative research into eternal software intensive systems, a common infrastructure will be needed upon which both research and practice can build.

Acknowledgments

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

IAM-08-001


Christoph Hofer

Marcus Denker

Stéphane Ducasse

Design and Implementation of a Backward-In-Time Debugger *

Traditional debugging and stepping execution trace are well-accepted techniques to understand deep internals about a program. However in many cases navigating the stack trace is not enough to find bugs, since the cause of a bug is often not in the stack trace anymore and old state is lost, so out of reach from the debugger. In this paper, we present the design and implementation of a backward-in-time debugger for a dynamic language, i.e., a debugger that allows one to navigate back the history of the application. We present the design and implementation of a backward-in-time debugger called UNSTUCK and show our solution to key implementation challenges.

Introduction

Debuggers offer the ability to stop a program at a chosen place, either due to an error or an explicit request (breakpoint). They provide the current states of the involved objects together with a stack trace. However, while stepping through the code is a powerful technique to get a deep understanding of a certain functionality [START_REF] Demeyer | Object-Oriented Reengineering Patterns[END_REF], in many cases this information is not enough to find bugs. The programmer is often forced to build new hypotheses about the possible cause of the bugs, set new breakpoints and restart the program to find the source of the problem. Often several iterations are necessary and it may be difficult to recreate the exact same context [START_REF] Lencevicius | Dynamic Query-Based Debugging[END_REF].

The questions a programmer has are often: "where was this variable set?", "why is this object reference nil?" or "what was the previous state of that object?". A static debugger cannot answer these questions, since it has only access to the current execution stack. There is no possibility to backtrack the state of an object or to find out why especially this object was passed to a method. The Omniscient Debugger is a first attempt to answer these problems [START_REF] Lewis | Debugging Backwards in Time[END_REF], however it is limited to java and instrumentation is done at bytecode load time.

To understand the challenges faced by building a backward in time debugger, i.e., a debugger that allows one to query the state history of a program, we developed a backward in time debugger in Squeak called UNSTUCK. For its implementation we collect rich information about the program execution in terms of events, which are used to recreate the state of objects at particular points in time.

The contributions of this paper are:

• A model for a back-in-time debugger.

• A user interface to present and query the massive amount of data generated by the recording of all the objects states.

• An implementation for Squeak Smalltalk

The paper is organized as follows. Section 2 shows the problems of conventional debuggers. Section 3 then presents trace based debugging. After a short overview of the implementation in Section 5, we present related work in Section 7. Finally, we conclude in Section 8 with an overview of future work.

Why Stack Trace is Not Enough

After an error occured a standard debugger shows the current stack. The problem is that only methods which have not yet been executed are on the stack, those that have finished execution are no longer available.

A Simple Example

The following example demonstrates the problem: there is a class Foo with two instance variables var1 and var2 and the following methods: In a normal debugger, we see a stack trace: only methods on the stack are shown, those methods which have been completely executed are not available anymore. Figure 2.1 right shows a complete execution trace of all methods executed. Only a small part of that (visualized with the dashed box) are part of the stack trace the debugger can show.

When inspecting objects, only the current state is accessible but the old state is lost. Even when selecting a method that is not on top of the stack, the debugger does not revert but presents the same state as before. Assume the situation in Figure 2.1 right: if we select moreBar: or bar:, the debugger presents the state of the program when the error occurred, even if the state has been different at the execution of these methods.

Recapitulating there are mainly two issues: loss of execution trace and loss of objects old state.

The Debugging Problem

The missing information on the execution trace and object state makes debugging much harder: with a debugger that is unable to provide this information, we have to work around to get to this information by running the program multiple times with different breakpoints.

For our example, typical steps we have to make to find the bug might be:

• The first question is "Was the initialize method executed?" A breakpoint in the initialize method and a restart of the program confirm that the variables were properly initialized.

• Putting another breakpoint in the setter method of var2 does not halt (the newly restarted) program. We learned that var2 was not set to nil over the setter method. But this does not help anything in finding the bug.

• Now it is not clear where the next breakpoint should go. We have to explore the code deeper. There is no simple procedure to find the next place for a breakpoint.

The debugger does not offer information about the previous values of var2 nor about where they were assigned. The bug is in an already finished method and the debugger cannot jump backwards to this method.

To find the bug as fast as possible the programmer should not have to think about where to put breakpoints. From this example, we see that a developer missed ways to explore the complete execution trace. He should have the possibility to explore previous states of an object, navigate through the places where variables changed their value and analyze the already executed methods.

Some approaches already used execution traces of programs, but in the context of debugging procedural languages [START_REF] Ducassé | Opium: An extendable trace analyser for Prolog[END_REF], or for exploring and reverse engineering objectoriented applications [CM93,LN95,RD99]. In object-oriented program debugging, querybased debugging combines conditional breakpoints with logic queries, evaluating a querylike expression is evaluated each time a conditional breakpoint is reached [START_REF] Lencevicius | Query-Based Debugging of Object-Oriented Programs[END_REF][START_REF] Lencevicius | Dynamic Query-Based Debugging[END_REF]. However, such approaches require to add clever probes in advance. The Omniscient Debugger [START_REF] Lewis | Debugging Backwards in Time[END_REF] is an attempt to provide the full stack to the programmer. TestLog [START_REF] Ducasse | Object-Oriented Legacy System Trace-based Logic Testing[END_REF] uses a logic engine to query the trace of object-oriented application with the possibility to query the previous state of objects.

UNSTUCK: A Backward-In-Time Debugger

Our solution to the problem presented before is to offer a debugger based on event traces and a specific interface to navigate backward in time.

Trace-Based Debugging

One solution to provide more advanced debugging support is to keep much more information about the execution of a program. For this purpose we collect events representing runtime data. For each method we record the name, the receiver, the arguments and the return value (see Section 5). This information is completed by collecting every write access to a variable (instance and local). This means that we record every state change. The collected events are basically a data structure containing the specific runtime information.

There is one event for each method executed, its returned value and for every write access to a variable. This data can answer many of the questions a programmer has during debugging, but simple navigation through this mass of data is needed.

We make a trace out of a set of given classes which are interesting for the user to debug. We instrument transparently the methods of these classes to produce the needed data at runtime. Further we will refer to objects from these classes as instrumented objects.

The execution trace holds a huge amount of data, thus we need a methodology for interacting with the debugger, which is described in the following sections.

User Interface for Navigating the Execution

Basically the user interface of the Unstuck Debugger consists of several views on the collected data from the TraceLibrary, enhanced with search and navigation functions. In the following we describe these views. They are identified in Figure 2 with numbered black boxes. The corresponding number is specified in brackets.

Method trace (1). Each line represents a method call. The format is of the form receiver# selector(arg1, arg2, ...) -> return value.

Each line is indented according to the depth of the message sends. Methods can be collapsed if they are of no interest (and of course expanded as well). Methods can be highlighted for remembering them easily. We can step through the highlighted lines.

For the receiver and the return value of the selected method the object history can be viewed in the object history (4) over a context menu. This view selects always the current method in the trace. It can change due to interaction with another view, too.

Object views (2).

There are two views displaying objects according to the currently selected method in the method trace: one displays the receiver of the method and the temporary variables (on the left side, the first line represents the receiver, beneath the temporary variables with the variable name), the other one the passed arguments (on the right side, with the argument's name). If an object is instrumented, it can be expanded to display the instance variables. Thus each line represents an object: these lines can be inspected or used for the object history over the context menu. If an object is an instance variable of an instrumented object, the setter methods of this instance variable and the object it belongs to can be highlighted in the method trace using the context menu. This enables to quickly see where this instance variable changed. We can step through these highlighted methods in the method trace, or use the stepping functions provided by the UI: step to the next/previous/first/last value of this instance variable to navigate through the variable's assignments.

Source code (3). This view displays the source code of the current selected method in the method trace. Here the source mapping of the events is used to highlight the current event. Normal debugging steps are provided to step through the source code (respectively through the events). The user can select source code and inspect it. He can also change manually the current focus in the execution trace. The object history can display the history for the current selected object. This view is used to program, i.e., the source code can be edited and recompiled.

Object history (4). This view displays every occurence of a user-selected object in the trace. The events are message reception by the object, object passed as argument, object state change, object's variable assignment or object returned from a method. This is useful for backtracking an object, because if we have an occurence in the trace, we can go backwards through the trace with this object. gument, thus we know from where it came, finally arriving at the first occurrence (normally its creation).

Searching (5). This pane consists of a simple search field, where the user can query the events. The method trace (1) highlights the found events. Section 3.3.1 presents this functionality in more detail.

Additional User Interface Features

We need supplementary features to locate interesting events and to mark interesting objects that will help finding bugs. In the following sections we describe the searching and coloring functions.

Simple Searching

Searching is important and thus should be simple. This is realized in the following manner: there is only one search field where the programmer can provide a boolean expression to identify specific events. Some predefined variables are available: event for searching in all the trace events (variable access or message send), send for searching only message send events. Table 1 presents the predefined variables that the programmer can used. In the current version, it is not possible to define other variables. Appropriate accessor methods are available for the events to access the collected runtime data (as shown in Table 2). The expression is used as the selection criteria on the adequate events. The result of the search is a set of events, which are then highlighted in the method trace.

The search expression is expressed in the implementation language, here Smalltalk. With this approach users are familiar with the search language, they can access the needed data using a known language. In addition, they have full access to the domain objects (via e.g., event sender). Thus it is easy to add methods to the domain classes to simplify the more complex queries.

Query

Result

send selector = #foo
All the executed methods named "foo"

varAccess newValue class = Foo
Every variable assignment, where the assigned object's class is Foo

return returnValue > 4
All returns with a return value greater than 4 events isSend & (event arg1 = 4) & (event arguments size = 1)

Only methods which have exactly one argument, which was 4

Coloring

Coloring is a useful tool for the developer: it enables tracking objects. The user can assign a color for an object in the trace. Various views (method trace, object views, object history) highlight the object with the assigned color. So it is easy to see if that object was passed as an argument, or was the receiver of a message or the instance variable of another object.

For an example see Figure 2. In the method trace an object ("a RBMethodNode") is colored. The user can easily detect the object in the trace and quickly see when it was the receiver of a message, an argument or the returned value.

Finding our Bug with the Unstuck Debugger

Coming back to the problem we presented in Section 2, here is how we solve it with the Unstuck Debugger:

• Start the Unstuck Debugger.

• Select the class Foo and provide the code to start the execution (Foo new start).

• The Unstuck Debugger instruments the bytecode of the methods of Foo, starts the program and collects the execution trace and presents it in the main user window.

• The error is already visible and it is obvious that nil received the message size.

• We want to see the code with the call of the message size, thus we step one back in the source view. The source code shows now that var2 received the message size

• Select var2 in the source code or in the object view.

• Highlight the modifiers of var2 (see Figure 3).

• There are two modifiers: one in the initialize method and one in beforeBar, which is the faulty one.

• Another possibility is to highlight var2 in the object view and use the stepping functions for the modifiers. The Unstuck Debugger offers us with the information we needed: the modifiers of var2.

They are only available because the old state and the execution trace are not lost. We do have to think about breakpoints but instead can directly navigate to the source of the bug.

Implementation

UNSTUCK is implemented in Squeak, the open-source Smalltalk distribution [IKM + 97].

UNSTUCK is based on the TraceLibrary which offers execution trace infrastructure. Basically the debugger collects the events, orders them and prepares the state reconstruction.

To generate events (method invocation, variable access and method return), the methods are instrumented using BYTESURGEON which is a high-level library to manipulate method bytecodes [START_REF] Denker | Runtime Bytecode Transformation for Smalltalk[END_REF]. Figure 4 shows the different layers. The following subsections describe each layer and how they work together.

Trace Library

The TraceLibrary supports the generation of execution traces from a set of classes and the code to start the program. BYTESURGEON instruments the methods of the given classes to generate the events at runtime. During the execution, a collector gathers these events and forms the program trace.

The Trace and Event Model

A trace is composed of events, depending on the situation the events are holding different information depending of the kind of events they represent and also whether the method execution terminated or not:

• An event representing a message sent describes the selector, the receiver, the arguments, as well as the definition class of the method, i.e., the class which defines the method and holds the source code.

• When the method returns, a return event is generated with the returned value.

• When the value of a variable (instance or temporary variable) is changed, a write access event is generated holding the variable name and the new value.

Additionally every event holds a source range, the mapping between the bytecode and the sourcecode. The depth of an event and the timestamp are added when the collector collects the events.

Figure 4 shows an UML diagram of the model: a trace consists of several Events. There are specific events, which are containing different information as mentioned before. The non-specific Event class shows which information is common to all events. For optimizing the model, a tree is built: an Event belongs to one MessageSend, thus a MessageSend can have multiple Events.

Event Processing

A collector, a TraceCollector, collects these events at runtime and processes them to define an order, to optimize the data structure and to prepare state reconstruction of the objects (receiver, variables and arguments) participating to the trace.

Order Definition. The collector has the responsibility to define the order of the event it receives, events are tagged with a timestamp. The depth of the event is also calculated by collector.

Data structure optimization. We create an event tree from a sequence of events, using the return events as marker of the end of a method execution. Back pointers to navigate from the subevents to the parent events are also managed as part of this process.

State reconstruction preparation. The collector handles every occurrence of objects in the trace for later state reconstruction. By state reconstruction we mean the ability to reconstruct the exact state of an object at any point in time as we will explain in Section 5.1.3. We distinguish three cases for treating all the objects participating into an event (i.e., receiver, arguments, variables): objects that are instances of instrumented classes, instances of other classes and collection instances.

• Instrumented objects: they do not need any special handling. The collector gets the state changes of such objects from instance variable write access events. With these changes we are able to provide the state of these objects at any time by applying the latest change before that point in time.

• Non instrumented objects: to remember their state the collector copies these objects.

• Collections: because a collector does not get any events for changes in a collection, a copy of a collection is saved with the current timestamp. Basically a collector creates a new collection of the same kind and processes every object of the collection as if it would be in the trace, i.e., recursively apply the same process: check if the object is instrumented or not, if it is a collection and process them as described above.

To support object identity checks, each event has a pointer to the original object and in addition for non instrumented objects to their copy.

When a collector gathers an event from an instance variable write access, then the new value represents a state change of an instrumented object. This change is tied with the current timestamp and the variable name to the corresponding object. This is useful for later state reconstruction, because we do not have to go through the whole trace and collect the needed changes. Note that the previous behavior is not necessary since we could walk over the trace and collect all changes belonging to an object. Here they are just ordered at runtime and acts as a cache.

State Reconstruction

State reconstruction is the process of reverting an object's state to any desired point in time in the trace. As explained above a collector prepared the state reconstruction. Depending on the type of objects, the reconstruction is different:

• Instrumented objects: for every instance variable we take the latest change before the desired time and apply this change. The applied value is reverted to the desired time, too.

• Non instrumented objects: no reconstruction needed, we just take the copy the collector has made and associated with the event.

• Collections: we take the last occurence of the collection in the trace and every object inside is reverted to the desired time.

The following examples show the special handling of collections: the first example adds a collection to the receiver which is aCollection too. Let's assume that the method addAll: is not instrumented but the expression is inside an instrumented method.

... aCollection addAll: anotherCollection ... ˆsomeExpression

When the collector treats the MessageSend for the method addAll:, it processes the two collections (because they were involved in the method's execution, as the receiver and as an argument). The collector creates a new collection with the current objects inside to remember which ones were in the collection at this time and handles each object inside as it would be an object in the trace (as described in Section 5.1.2). The same happens when the collector receives a Return event. To get the state of a collection right before this method was executed, we take the new collection created by the collector and reconstruct the state of the objects inside. To get the state of the collection after this method was executed, we take the second collection the collector created when it was treating the return event. This collection includes the newly added objects, thus we get the right state back.

... aCollection foo: otherCollection ... ˆsomeExpression with foo defined as:

foo: collection collection removeFirst Similarly to the previous example, let's assume that the method foo: is not instrumented.

In addition, let's assume that we have two objects inside otherCollection, one instrumented and other not. After the execution of foo:, the collector creates a new collection. The instrumented object is put in it, and a copy of the not instrumented one. Thus we remark that the otherCollection has changed. To get the state at the end of the method's execution, we take the newly created collection and put the two following objects inside: the reverted instrumented one (by applying the latest changes) and the copy of the not instrumented object.

Event Gathering Using BYTESURGEON

BYTESURGEON [START_REF] Denker | Runtime Bytecode Transformation for Smalltalk[END_REF] is a tool for transforming Smalltalk bytecode at runtime. It provides high-level abstractions, thus developers do not need to program at bytecode level. Bytecodes are low-level instructions for the Virtual Machine stack machine. BYTE-SURGEON can insert code before, after or for an instruction. This code is passed in form of a string of Smalltalk code. If we insert code after an instruction, it will be executed right after the execution of the instruction. Additionaly BYTESURGEON provides the same functionality for methods instead of instructions.

For accessing runtime information (such as the receiver of a message, the passed arguments), BYTESURGEON provides meta variables. They have a special syntax (<meta: #var>) and can be added to the string that represents the code to insert. BYTESURGEON provides the receiver, the arguments and the returned value of a message send, the variable name and the new value of a write access to a variable. The IRInstruction (an intermediate representation, which represents a bytecode instruction) delivers the static information, i.e., the selector and the definition class of a message send and the source range of all events.

As an example we describe how to generate the method send events of a method: BYTESURGEON iterates over the IRInstructions, thus we work with an IRSend, which represents a message send at bytecode level. It provides the static information (selector, source range, definitionclass). BYTESURGEON provides the runtime information over meta variables (the receiver is accessible with <meta: #receiver>, the arguments with <meta: #arguments>). BYTESURGEON takes a string to insert code, thus we generate the string as follows:

'TraceCollector default take: (MessageSend withSelector: ', instr selector printString // include the selector ,' withArguments: <meta: #arguments> // include the arguments withReceiver: <meta: #receiver> // include the receiver withSourceRange: ', instr sourceRange printString // include the source range , ' class: ', instr superOf printString,')' // include the definition class This generates our needed event and the collector stores it. Then we instrument every send in a method with the following code:

Evaluation and Discussion

For evaluating the practicality of our Unstuck Debugger implementation, we provide three benchmarks: the simple example shown in Section 1, then a bug of the Squeak abstract syntax tree (AST) that results in a slightly larger trace. The third case study (Pier) is the trace resulting from running the tests of a larger system. We show the number of events, the slowdown compared to a simulated run in the standard Debugger and memory usage. Query-based debugging [LHS97,LHS99] use logic programming to express complex queries over a large number of object. Some queries are triggered at run-time while the program is running. The logic queries act as clever program probes. Here the intention is different, in our approach we navigate the history of the program.

Caffeine [START_REF] Guéhéneuc | No Java without Caffeine: A Tool for Dynamic Analysis of Java Programs[END_REF] is a Java-based tool that uses the Java debugging API to capture execution events and uses a Prolog variant to express and execute queries on a dynamic trace. Caffeine does not support state history access. TestLog [START_REF] Ducasse | Object-Oriented Legacy System Trace-based Logic Testing[END_REF] which uses a logic engine to query the trace of object-oriented applications, is much closer to Unstuck Debugger since it offers the possibility to query the previous state of objects. However, no user interface is provided.

OPIUM [START_REF] Ducassé | Opium: An extendable trace analyser for Prolog[END_REF] is a tool that allows a user to debug Prolog program using a set of debugging queries on event traces. Prolog is used as a base language and as meta language to reason about events. The main usage scenario of OPIUM is the implementation of a high level debugger for Prolog that allows forward navigation to the next event that satisfies a certain condition. Coca [START_REF] Ducassé | Coca: An Automated Debugger for C[END_REF] supports the debugging of C programs based on events. Opium and Coca are mainly used to show the values of variables. In addition, both Opium and Coca do not support object-oriented programming. In addition, the history of object state is not available.

Auguston [START_REF] Auguston | Building program Behavior Models[END_REF][START_REF] Auguston | Program Behavior Model Based on Event Grammar and its Application for Debugging Automation[END_REF] also uses a trace composed of event models and test programs. However it is based on procedural programming languages and does not take into account the specific behavioural aspects of object-oriented languages such object creation and the state of objects.

Lewis in [START_REF] Lewis | Debugging Backwards in Time[END_REF] proposes to merge the approach of omniscient debuggers which collect all the run-time information and supports the exploration of the history and event-based tools that monitors program execution and allow queries. It however it is limited to java and instrumentation is done at bytecode load time.

ZStep [START_REF] Lieberman | ZStep 95: A reversible, animated source code stepper[END_REF] provides a back-in-time debugger for Lisp. The focus of this research was to provide a environment that allows reversing both program state and the side effects of GUI output to understand the correspondence between static program code and dynamic program execution.

Conclusion and future work

In many cases the Unstuck Debugger provides an improvement over conventional debugging: if we have a faulty value it is easy to find the place where it was set uncorrectly. The bug can be chased in the program history. Such a kind of behavior is not possible in a normal debugger where this work has do be done manually using multiple restart and breakpoints. When we select a message send in the Unstuck Debugger it is like we stopped the program there with a breakpoint. We have the same information, but there is no need to put a new breakpoint for stopping the program in another situation. In the debugger we can just go there. Completed with backtracking and searching functions the debugger helps us finding bugs much faster.

To have all this information available there is a price to pay: a slow down of application runtime. But this needs to be compared to the time won when finding bugs. Up until now the Unstuck Debugger has been working on limited but still challenging case studies such as debugging abstract syntax tree and compiler internals. An application to larger systems has shown that both execution speed and memory consumption need to be analyzed and improved.

In addition as Smalltalk offers a dynamic programming style with on the fly recompilation, we plan to investigate if it is realistic to instrument the complete environment and be able to debug any application without having to provide a program seed.

Other possible enhancements are support for threads and the ability to restart execution in the past: the Unstuck Debugger should be able restart the execution trace from any point in the past but this would require to recreate stack execution on the fly.

Foo≫start

  : 10) do: [:each tmp := tmp + each ]. self var1: tmp. Foo≫moreBar var2 size > 0 ifTrue: [ ˆvar2 at: 1]. ˆ''Accessor methods are defined for var1 and var2. Foo new start starts the program execution. The debugger comes up because of an error, var2 is nil in method moreBar (see 2.1 left).

Figure 1 :

 1 Figure 1: Left: error in the squeak Squeak debugger. Right: method calls and the resulting stack trace. Only the methods in the dashed box are in the stack trace when an error occurs in method moreBar

Figure 2 :

 2 Figure 2: The user interface of the Unstuck Debugger.

Figure 3 :

 3 Figure 3: Left: highlight the modifiers of a variable over the context menu in the source view. Right: the result of the action made on the left side: highlighted methods in which var2 was modified (i.e., changed the value)

Figure 4 :

 4 Figure 4: Left: the TraceLibrary is built on top of BYTESURGEON and the Unstuck Debugger is build on top of the TraceLibrary. Right: the Trace and Event model.

  aCompiledMethod instrument: [:instr instr isSend ifTrue: [instr insertBefore: theString]].

Table 1 :

 1 Back to a previous occurence, see what happend to the object. We see where it was passed as an ar-Predefined search variables

	Variable	Search domain
	event	All events
	send	Events representing a method send

return Events representing a method's return varAccess Events representing a variable store (instance or local) instVarAccess Events representing only an instance variable store tempVarAccess Events representing only a local variable store

Table 2 :

 2 Some search expression examples

  Whyline[START_REF] Ko | Designing the whyline: a debugging interface for asking questions about program behavior[END_REF] implements Interrogative Debugging for Alice a 3D world[Ali]. Here the focus lies on providing an interface to ask questions such as why or why not things are happening in an Alice world. Thus this debugging facilities are totally tied to the, quite simple, domain model of Alice. Such an approach does not scale when the domain is more complex as in normal development. Visualising debuggers can work directly via instrumentation on the program being executed, or are based on post-mortem traces [CM93, LN95]. Visualisation of dynamic information is also related to our work in the sense that it is based on a program trace. DePauw et al. [DPLVW98] and Walker et al. [WMFB + 98] use program events traces to visualise program execution patterns and event-based object relationships such as method invocations and object creation.

		Number of events Slowdown Memory usage (kb)
	Simple Example 74	6	16
	AST Bug	2725	3.8	800
	Pier Trace	389689	248	88800
	With a slowdown of 4-6 times, the program is still usable for debugging, but as soon as
	the traces get large, runtime degrades. Memory grows linearly, as expected. This suggests
	runtime as the main focus for future research (see Section 8).
	7 Related work

Acknowledgments. We acknowledge the financial support of the Swiss National Science Foundation for the project "A Unified Approach to Composition and Extensibility" (SNF Project No. 200020-105091/1, Oct. 2004 -Sept. 2006) and the french ANR project "Cook: Réarchitecturisation des applications industrielles objets" (JC05 42872)