Oscar Nierstrasz

Marcus Denker

Tudor Girba

Adrian Lienhard

David Roethlisberger

Tudor Gîrba

David Röthlisberger

Change-Enabled Software System

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Software inevitably changes, but our development methods, programming languages, development environments and run-time systems generally assume 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 change is enabled in a fundamental way in our platforms, run-time environments and development environments [START_REF] Nierstrasz | Software evolution as the key to productivity[END_REF]. In particular, not only software systems themselves, but their development and support environments need to be far more dynamic than they are today. 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 evolving software 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. To manage change over time, the history of the system must also be accessible and first-class (see Section 2). -Second, an evolving software 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 3). -Third, to enable continuous evolution, a software 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 4).

We will explore these themes in some detail, in each case summarizing previous work, and establishing a research agenda for further work. We conclude with summary remarks about next steps.

2 Self-aware platforms to support change 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. Evolving software 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]. Evolving 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 a continuously evolving software system, just as we cannot stop and restart the Internet. The Internet has been up and running since 1969, although many of its atoms have been changed many times 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 run-time systems that can serve as a platform for developing evolving software systems.

Previous work

In order to enable change at run-time, an evolving system must be able to fully reflect on itself, that is, it must be self-aware. It is not enough to be modeldriven. The models must be explicit and accessible to the run-time system. A reflective system provides a description of itself available from within. This description can be queried (introspection) as well as changed (intercession). In the past, computational reflection has been an active area of research [START_REF] Ducasse | Evaluating message passing control techniques in Smalltalk[END_REF][START_REF] Ferber | Computational reflection in class-based object-oriented languages[END_REF][START_REF] Maes | Computational Reflection[END_REF][START_REF] Cantwell | Reflection and semantics in a procedural language[END_REF]. Nevertheless, languages used in industry today do not provide full reflection, and many mainstream languages have no self representation at all (for example C and C++). More recently created languages like Java and C# support limited introspection, but no intercession.

In recent years, dynamic languages have attracted much attention [START_REF] Nierstrasz | On the revival of dynamic languages[END_REF] and are increasingly being used in industry (e.g., Python, Ruby, Smalltalk). Dynamic languages provide a representation that can be queried and changed at run-time and thus are reflective. But even in these dynamic languages, the support for reflection is limited. The structural representation of the program stops at the granularity of the method. Classes and methods are represented as objects and available to be queried and changed, but the structure of the methods themselves is not represented. Behavioral reflection is limited as we cannot change behavior on a fine-grained level. In addition, when applying behavioral reflection to the system (as opposed to an application), the programmer will soon run into the problem of meta-object call recursion [START_REF] Denker | The meta in meta-object architectures[END_REF].

We have extended structural reflection to model the structure of methods: sub-method reflection [START_REF] Denker | Submethod reflection[END_REF] represents the complete structure, down to the code itself. The representation can be annotated and thus can be used for integrating tools. One example is feature annotation [START_REF] Denker | Supporting feature analysis with runtime annotations[END_REF]. Instead of recording full traces to analyze features, we can simply annotate the static structure of the system with feature information. Partial behavioral reflection [START_REF] Röthlisberger | Unanticipated partial behavioral reflection: Adapting applications at runtime[END_REF][START_REF] Tanter | Partial behavioral reflection: Spatial and temporal selection of reification[END_REF] provides means to select where and when a meta-object is activated and allows us to define which information is passed to the meta-object. We can introduce behavioral changes at run-time which provides the basis to supporting unanticipated change to the systems. Examples range from tools like tracers or profilers [START_REF] Röthlisberger | Unanticipated partial behavioral reflection: Adapting applications at runtime[END_REF] to changes of the language semantics, for example transactional memory [START_REF] Renggli | Transactional memory for Smalltalk[END_REF]. The problem of meta-object call recursion is solved by representing meta-level execution as a context and by making meta-object activation context-aware [START_REF] Denker | The meta in meta-object architectures[END_REF].

It is well-established that suitable abstractions are needed to enable programming in the large [START_REF] David | On the criteria to be used in decomposing systems into modules[END_REF]. But in the case of scale, we need to think again: are existing abstractions good enough for very large software systems? For example, as software gets larger the assumption that every part of the system must stay in sync with every other part is not very convincing because the systems of the future will be so large that we will never be able to evolve them in a single, synchronous step. As a consequence, an evolving system 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, evolving 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 contextoriented programming [START_REF] Costanza | Language constructs for context-oriented programming: An overview of ContextL[END_REF][START_REF] Hirschfeld | Context-oriented programming[END_REF]. Visibility of changes can then be restricted to the context in which these changes are guaranteed to be valid.

Changeboxes [START_REF] Denker | Encapsulating and exploiting change with Changeboxes[END_REF] provide a mechanism for encapsulating change as a first-class entity in a running software system. Changeboxes support multiple, concurrent and possibly inconsistent views of software artifacts within the same running system. Since changeboxes are first-class, they can be manipulated to control the scope of change in a running system. Furthermore, changeboxes capture the semantics of change. Changeboxes can be used, for example, to encapsulate refactorings, or to replay or analyze the history of changes.

Research agenda

We maintain that both reflection and context are crucial to support change and evolution. There has been much recent progress, but more research is needed. In particular, the key ideas emerging from previous research need to be consolidated and integrated into a comprehensive model.

Efficient and practical reflective languages. Sub-method structural reflection and partial behavioral reflection are improvements over conventional reflective systems. One problem with reflection, even with efficient partial reflection [START_REF] Röthlisberger | Unanticipated partial behavioral reflection: Adapting applications at runtime[END_REF][START_REF] Tanter | Partial behavioral reflection: Spatial and temporal selection of reification[END_REF] is performance. With behavioral reflection, we introduce new behavior that replaces the default behavior. One example is method lookup. The default lookup is extremely optimized and realized in the virtual machine, so any reflective redefinition is often slower by an order of magnitude. This difference in performance can render a system unusable in practice. We need to integrate reflection better into the virtual machine, leveraging the dynamic code generator of modern just-in-time compilers. Another interesting question is how to resolve static typing with reflection. Type-systems reason about properties that can be guaranteed in the future, whereas reflection is about changing the future. We need a way to check reflective change before it is applied to the system. Backward compatibility. Backward compatibility is the enemy of forward evolvability. Nevertheless, we cannot live in a world where the old is ignored. An often overlooked property of software is that new systems can simulate the old, and the recent trends in hardware virtualization have shown that simulation of the old is far easier than for the new to stay compatible. A snapshot of an old Windows machine can run on a virtual machine forever, whereas keeping an operating system compatible forever is bound to fail. Programming languages for evolving 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 itself at any point in the past. Our work on changeboxes forms one first step towards this goal. However, changeboxes are only concerned with code, thus an important aspect of future work is the problem of migrating data between versions.

Contextual reflection. Context appears to be deeply related to reflection. In the case of changeboxes, the currently active changebox provides a context for execution. For partial behavioral reflection, we solve the problem of meta-object call recursion by representing the execution of the meta-level as a context [START_REF] Denker | The meta in meta-object architectures[END_REF]. We think that the next step is to revisit these cases and integrate the notion of context into the reflective model of the language and the virtual machine.

Languages supporting multiple views. In general, we need to explore multidimensional object systems. After achieving a reflective model that is aware of context, the next step is to build language support that makes this concept available to the programmer. Some very relevant work has been done in the past, for example the work on PIE [START_REF] Daniel | Representing design alternatives[END_REF][START_REF] Goldstein | Descriptions for a programming environment[END_REF][START_REF] Goldstein | Extending object-oriented programming in Smalltalk[END_REF][START_REF] Goldstein | A layered approach to software design[END_REF], Us [START_REF] Smith | A simple and unifying approach to subjective objects[END_REF] and more recently ContextL and ContextS [START_REF] Costanza | Language constructs for context-oriented programming: An overview of ContextL[END_REF][START_REF] Hirschfeld | Context-oriented programming[END_REF]. More research is needed to explore how to combine these ideas with contextual reflection and changeboxes.

Evolving languages. Evolving systems need languages that support continuous development and evolution. But there is another aspect when considering the language itself: 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 software systems needs to be itself an evolving system. An evolving 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].

Monitoring and analyzing change

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. A self-aware system can reflect on its own specification, which is an aid to static analysis. But emergent properties as well as program failures can only be monitored with the help of dynamic analysis [START_REF] Hamou | A survey of trace exploration tools and techniques[END_REF].

Ideally, a productive system should constantly monitor and analyze itself. This would allow us to discover properties that are only visible over a longer period of time, such as performance degradation, memory leaks, shifts in how the system is used, effects of structural changes etc. Furthermore, collecting detailed data about the program execution can provide crucial information to uncover the cause of program failures.

Previous work

Program failures for large, long-lived software systems can be hard to reproduce, and hard to simulate in a test environment. As a consequence, systems need to dynamically analyze their behavior to gather execution history while they are running and allow for remote and safe debugging inside the live system. To be able to reason about the run-time behavior of a system, dynamic information has to be linked with the model of the software structure. A platform that provides an integrated, high-level model of its own structure, design, and behavior (see Section 2) would offer an appropriate foundation for building self-analyzing systems.

The challenge we face with such an architecture is that the current state of the art in dynamic analysis does not permit run-time information to be gathered below the method level in live systems due to performance reasons. The main obstacles are (i) code instrumentation requires a system to be restarted, (ii) run-time overhead can be huge (up to a factor of 100 or more for non-trivial programs [START_REF] Lewis | Using events to debug Java programs backwards in time[END_REF]), and (iii) available memory to store the gathered data limits the analysis to only few and short user sessions.

Most existing dynamic analysis approaches are detached from the run-time environment, i.e., virtual machine, and hence have only limited means to adapt and reconfigure the system at runtime without restarting it. Instrumentation code is weaved into the application code at compile time, for instance through bytecode manipulation. This additional code then generates data during execution, which is either stored as a trace of events in memory or in a database where it is processed post mortem. An evolving system that needs to be running all the time cannot be restarted to reconfigure the analyzer. Therefore, the run-time analysis of a self-aware system needs to be an integral part of its run-time environment. Like this, no hard-wired instrumentation code is required, but rather the analyzer is a self-aware component of the virtual machine. The analyzer needs to be always running and capable of adjusting its own behavior, much like garbage collectors are always active in modern virtual machines.

We have addressed some of these problems as follows [START_REF] Lienhard | Taking an object-centric view on dynamic information with object flow analysis[END_REF][START_REF] Lienhard | Practical object-oriented back-in-time debugging[END_REF][START_REF] Lienhard | Test blueprints -exposing side effects in execution traces to support writing unit tests[END_REF]. We have extended the object memory model of conventional object-oriented virtual machines by representing object references as real objects on the heap. In this way we seamlessly integrate historical execution data into the object model of the virtual machine. Our approach discards unneeded historical execution data by employing the standard garbage collector of the VM. We showed that this approach can dramatically improve the data explosion problem and has much lower execution overheads compared to other back-in-time debuggers [START_REF] Lewis | Using events to debug Java programs backwards in time[END_REF][START_REF] Pothier | Scalable omniscient debugging[END_REF] that are not implemented at the virtual machine level.

We have extended the common dynamic analysis model with the notion of object aliases. That is, object references are explicitly represented in our model, which allows us to track the flow of objects in the system or to analyze how side effects are produced [START_REF] Lienhard | Tracking objects to detect feature dependencies[END_REF][START_REF] Lienhard | Test blueprints -exposing side effects in execution traces to support writing unit tests[END_REF].

By enabling dynamic analysis on live systems, innovative debugging and analysis techniques come within reach. In a recent study, Liblit et al. examined bug symptoms for various programs and found that in 50% of the cases the execution stack contains essentially no information about the bug's cause [START_REF] Liblit | Scalable statistical bug isolation[END_REF]. Back-in-time debuggers [START_REF] Hofer | Design and implementation of a backward-in-time debugger[END_REF][START_REF] Lewis | Using events to debug Java programs backwards in time[END_REF][START_REF] Pothier | Scalable omniscient debugging[END_REF] allow the developer to explore the program state at those points in time that are no longer represented on the run-time stack. We are currently exploring the development of a highly performant backin-time debugger on top of our history-aware VM.

In evolving software systems, the changes to the static parts are directly accessible as first class entities. As such, in evolving software systems, not only the run-time is dynamic, but also the static part is dynamic when seen from an 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]. For example, we can predict where changes are likely to occur [START_REF] Gîrba | Yesterday's Weather: Guiding early reverse engineering efforts by summarizing the evolution of changes[END_REF], we can detect classes that are changed frequently [START_REF] Gîrba | Characterizing the evolution of class hierarchies[END_REF], or we can identify crosscutting concerns by detecting which parts change at the same time and in the same way [START_REF] Gîrba | Using concept analysis to detect co-change patterns[END_REF].

Given the size of evolving 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 should also include reasoning about how developers collaborate [START_REF] Balint | How developers copy[END_REF][START_REF] Gîrba | How developers drive software evolution[END_REF][START_REF] Greevy | How developers develop features[END_REF].

Research agenda

In the long-term, we expect that run-time monitoring of program execution and evolution will become not only practical but essential to the survival of longlived software systems. To make this a reality however, further research will be needed in the following areas.

Efficient run-time analysis. Dynamic analysis will only be widely adopted if it is cheap in time and space. The emergence of multi-core architectures for offthe-shelf desktop and laptop machines suggests that parallelization should be explored as one way to reduce the execution time. Even though future hardware capacity will allow for storing more data more efficiently, more advanced models for discarding unneeded data are important, as faster running systems also produce data faster.

Detecting emergent properties. High-level run-time models are needed to reason about the system from within the system. In an object-oriented system, recording method execution events alone is not enough for certain analyses and for debugging. Also, a run-time model should be seamlessly connected with the static model, which captures structural program entities and their evolution. This allows for recognizing links between the behavior of a system and its evolution and can serve as a source of information for maintainers in their development environment. By correlating static and dynamic information over time, one should be able to detect emergent properties, such as maintenance hot spots, performance bottlenecks and other opportunities for refactoring and reengineering.

Automatic model reconstruction. Heterogeneous and legacy sources of information can be obstacles to analysis and evolution. Yet another complicating factor is the use of different programming languages and media such as mainstream compiled languages, scripting languages, domain specific languages, HTML, XML and query languages within the same system. Furthermore, some of the languages used will be either legacy languages or dialects (such as legacy dialects of C++). Post-hoc parsing of components built with these languages will be difficult and error-prone since the original language specifications may not be available. Thus, an evolving software can be seen as a multi-dimensional space of data that needs to be continuously analyzed. Techniques will be needed to automatically reconstruct high-level models and meta-models from lower-level data, without necessarily having up-to-date access to the syntax specifications.. Possible approaches include abstraction from examples [START_REF] Nierstrasz | Example-driven reconstruction of software models[END_REF] and formal concept analysis [START_REF] Arévalo | Detecting implicit collaboration patterns[END_REF][START_REF] Lienhard | Identifying traits with formal concept analysis[END_REF], amongst many others.

Enabling change for the developer

The evolution, or rather continuous development, of evolving 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 evolving system as an infinite game, it becomes clear that one cannot anticipate all forms of evolution.

Current IDEs focus on providing the developer only with a static view of the source code without offering any information about how the code is actually executed at run-time, about why a bug occurred, or about whether there are performance issues or memory consumption problems. Furthermore, modern IDEs do not provide means to bridge 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 of a large system by studying its sources code alone.

We envision a development environment in which change is enabled by bridging the static and dynamic views of the system and by bringing the results of dynamic analysis to the IDE. Ultimately, the IDE should be an active player in the development process, enabling developers to interactively manipulate and extend the system at a high level of abstraction.

Previous work

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 [START_REF] Fowler | Refactoring: Improving the Design of Existing Code[END_REF]. Many modern IDEs provide some automated mechanisms to change and evolve software systems but they tend to be low level, like renaming a class or moving a method [START_REF] Roberts | A refactoring tool for Smalltalk[END_REF]. Furthermore, developers receive little guidance in identifying opportunities for refactoring [START_REF] Lanza | Object-Oriented Metrics in Practice[END_REF], and the knowledge about performed refactorings is usually not kept. A promising approach is to offer a better versioning system that is able to store the high level knowledge about a change [START_REF] Robbes | Characterizing and understanding development sessions[END_REF] and then provide this information for further analysis [START_REF] Dig | Refactoring-aware configuration management for object-oriented programs[END_REF].

Empirical studies report that a developer performing maintenance tasks on a system spends at least 35% of the time in navigating source code [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 degreeof-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]. Other proposals [START_REF] Robillard | Feat: A tool for locating, describing, and analyzing concerns in source code[END_REF][START_REF] Singer | Navtracks: Supporting navigation in software maintenance[END_REF] focus emphasizing relations between source artifacts by recommending related artifacts based on the past sequence of browsing, or by characterizing the kinds of changes that have taken place during development sessions [START_REF] Robbes | Characterizing and understanding development sessions[END_REF].

Hermion is an experimental IDE that brings run-time information to the developer to better support maintenance tasks [START_REF] Röthlisberger | Exploiting runtime information in the ide[END_REF]. Dynamic information gathered at run-time provides the developer with the possibility to directly navigate to actual senders and implementors of messages, or to navigate to the actual concrete types to which variables have been dynamically bound. Statistical data about the run-time call graph is also integrated into the static code views, and is dynamically updated as the code under development is further exercised. Dynamic monitoring is realized by means of mechanisms in the underlying reflectivity framework (see Section 2) which support unanticipated partial behavioural reflection [START_REF] Röthlisberger | Unanticipated partial behavioral reflection: Adapting applications at runtime[END_REF]. This allows running code to be instrumented on-the-fly at a high level of abstraction, and without modifying the underlying source code.

Visualizations can convey complex information in a condensed and effective manner. Extensions to the VisualWorks Smalltalk IDE (e.g., RBCrawler) integrate various well-known visualizations such as class blueprints [START_REF] Ducasse | The class blueprint: Visually supporting the understanding of classes[END_REF], polymetric views [START_REF] Lanza | Polymetric views-a lightweight visual approach to reverse engineering[END_REF] or system complexity views [START_REF] Lanza | Polymetric views-a lightweight visual approach to reverse engineering[END_REF]. They are well integrated in the static source navigation tools of this IDE, however, they do not take dynamic information into account and are thus just a starting point for further work.

One particularly useful application of visualization is to correlate static views of software components, with the features of the running systems. Feature-driven browsing exploits run-time information gathered when exercising features and presents this information as a visual map [START_REF] Röthlisberger | Feature driven browsing[END_REF]. This enables us to quickly identify the components responsible for a feature and to highlight the dependencies between different features. As this feature visualization is integrated in the IDE, the developer can also better assess the impact of a source code level change on various features of the system if there is an explicit mapping between features and source artifacts available.

Research agenda

Today's IDEs are largely passive players in the development process, though there is a clear and gradual trend towards IDEs and tools that play a more active role. We believe that further research is needed here to make the IDE a more active player in enabling change. Some promising research tracks follow.

Automatic and continuous execution. Not only should the IDE provide complete information, it should also do this efficiently to avoid slowing down the development process. To achieve efficient integration of dynamic information, we envision applying the concept of continuous integration by running the system automatically and continuously in the background. This relieves the developer from the burden of having to manually trigger the execution of the system while modifying it.

Full coverage. Since manually triggered dynamic analyses normally do not cover the entire system (i.e., all system's features), the IDE should assume the responsibility to ensure full coverage and cover all code still being used by the application. The IDE should analyze all execution paths through the system by running the code currently being studied by the developer. If system monitoring and analysis (see Section 3) can be made sufficiently efficient and non-intrusive, possibly by exploiting the possibilities of parallel hardware, information gathered from the execution of the live system by real users and certainly also of recorded scripts could also be fed automatically back to the IDE.

Exploiting fine-grained change histories. Software is currently developed following a checkout/change/commit life cycle. This approach hides the local events and changes from the overall development. To limit this loss of information developers are advised to commit as often as possible in the central repository.

In the future we envision a central environment that is tightly integrated with the versioning system and that stores all changes performed on the system. Furthermore, instead of being snapshot-based, change logs will capture the intent of changes, such as common refactoring operations. This information can then be fed back into the IDE so that developers can immediately access historical information in a productive and integrated way.

Autonomous system evolution. The IDE as an active player should be able to autonomously perform many maintenance tasks. For instance, the IDE should be able to automatically detect defects, and with the help of dynamic analysis, suggest repair strategies to the developer. If a certain feature of such an evolving system is broken, the environment should be able to locate this feature in source code and determine which classes or methods need to be corrected to successfully solve the issue. Fine-grained historical information about changes to the software supporting the defective features should also be a valuable input to automatically provide focus to the developer to correct the defect.

Model-centric development. Software developers today generally edit and manipulate textual representations of the systems being developed, i.e., as source code. However, text is by definition static while the resulting system is dynamic and neither knows nor cares about the textual representation from which it has initially been built. We envision a system in which the developer directly manipulates high-level models that more closely represent the conceptual entities of the software application. Such an approach would be model-centric rather than "model-driven", since models would directly represent the running application, rather than serving to generate it. Such a system could be realized by a visual programming environment that enables developers to develop and change directly the dynamic structure, e.g., by working with visual components of a system's behavior that can be dragged, dropped, parameterized, adapted, extended and reorganized, directly modifying the behavior.

Concluding remarks

We have argued that traditional approaches to software development do not adequately support the inevitable change that software will undergo during its lifetime. We have summarized some current and ongoing research activities to enable change for long-lived software systems, and we have presented an agenda of critical research topics for further investigation. Briefly, we see the need for further research in the following three related areas:

-Self-aware platforms to enable change. In order to enable change for software applications, the underlying platform (i.e., programming language and run-time environment) must support change in a deep way. Such systems must therefore be reflective, by means of high-level models. Change must be modeled as a first-class entity, so that changes can be manipulated and reasoned about. Finally, the platform must be context-aware so that the scope of change can be controlled to ensure safe evolution at run-time. We have argued that these ingredients are necessary for a future generation of selfaware, long-lived, evolving software applications. Some of these ideas have been prototyped, but much research is needed before they are ready to be adopted in mainstream platforms. -Monitoring and analyzing change. A long-lived, evolving software system must provide means to monitor and analyze change, both in terms of shortterm, dynamic adaptations, and long-term software evolution. Dynamic analysis today is mostly post hoc. For performance reasons it is generally impractical to monitor and analyze live systems. Novel techniques for monitoring, debugging and analyzing live systems are being developed, but further research is needed to make these approaches practical, for example by exploiting the possibilities of the emerging class of multi-core processors. Further research is also needed to detect emergent properties of long-lived evolving software systems, particularly in terms of correlating static and dynamic software structures. Automatic detection of maintenance hot spots, performance bottlenecks, and opportunities for refactoring are some of the areas where further research is needed. -Enabling change for the developer. Modern application development environments essentially provide developers with static views of the application source code. Particularly in the case of object-oriented software development, the gap between the static and the run-time structures implies that much valuable information is simply not available to the developer. By bringing together static and dynamic views of the live system, many opportunities present themselves to improve the productivity of the developer. For instance, dynamic information integrated into the static software views provides richer navigation possibilities. Further research is needed to make the IDE itself an active player that exercises, tests and analyzes the live system as it is being developed, actively updates the static views with the results of dynamic analysis, automatically detects defects and actively suggests repair strategies, and keeps track of changes and their intent at a finer granularity than is currently supported. As a long-term goal, we envision IDEs that are not so much focussed on editing source code, but rather support direct manipulation and transformation of models of the live system under development.

As a closing remark, we note that this kind of research is almost impossible to carry out effectively by isolated researchers. A certain critical mass in terms of software infrastructure is needed before research results stabilize and new ideas can be built on top of older ones. Much of current research results in prototypes that do not even begin to achieve the level of stability that is needed before other researchers can build something new on top of them.

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 evolving systems. On the other hand, just like evolving 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 products 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 architecture, 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 evolving software intensive systems, an analogous 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) and that of the Hasler Foundation for the project "Enabling the evolution of J2EE applications through reverse engineering and quality assurance".


Camillo Bruni

Toon Verwaest

Marcus Denker

PyGirl Generating Whole-System VMs from high-level models using PyPy

Keywords: D.1.5 Object-oriented Programming; C.4 [Performance of Systems]: Design studies Languages, Performance pypy, python, rpython, whole system virtual machine, translation toolchain, high-level language

Virtual machines emulating hardware devices are generally implemented in low-level languages and using a low-level style for performance reasons. This trend results in largely difficult to understand, difficult to extend and unmaintainable systems. As new general techniques for virtual machines arise, it gets harder to incorporate or test these techniques because of early design and optimization decisions. In this paper we show how such decisions can be postponed to later phases by separating virtual machine implementation issues from the high-level machine-specific model. We construct compact models of whole-system VMs in a high-level language, which exclude all low-level implementation details. We use the pluggable translation toolchain PYPY to translate those models to executables. During the translation process, the toolchain reintroduces the VM implementation and optimization details for specific target platforms. As a case study we implement an executable model of a hardware gaming device. We show that our approach to VM building increases understandability, maintainability and extendability while preserving performance.

Introduction

The research field revolving around virtual machines (VMs) is mainly split up in two big subfields. On the one hand we have the whole-system VM (WSVM) community working on new ways of building and optimizing emulators for hardware devices. These VMs have close resemblance to how the actual hardware which they are emulating. On the other we have the language community building high-level language VMs (HLLVM). These VMs only exist virtually. There are no hardware counterparts which natively understand the code running on those VMs. Although both domains share conceptual and implementation similarities, only recently the awareness has been growing about the overlap of ideas and acknowledgement that both fields can learn from each other. As a clear example of this fact we see that modern VM books discuss both fields [START_REF] Smith | Virtual Machines[END_REF]. But while up until now almost only performance enhancement techniques have been adapted, we are confident that more can be shared. In this paper we show how the effort of separating language specific VM models from the general implementation and optimization details, which has been developed for HLLVMs in the PYPY project 1 can also greatly improve understandability, maintainability, extendability and possibly even performance optimization of WSVMs. Similar to Spy [START_REF] Bolz | Back to the future in one week -implementing a smalltalk vm in pypy[END_REF] we will build a custom high-level virtual machine model, but this time rather than implementing a HLLVM, we will concentrate on emulating a hardware gaming device. We focus on building a high-level, abstract but executable model rather than an inflexible, early optimized system. We will then show that by using the PYPY toolchain, we are able to generate performant low-level virtual machines from those models. The main contributions of this paper are • We show how the execution and implementation details of WSVMs can separated in the same way as this was previously done for HLLVMs

• We provide an implementation of a WSVM model for PYPY, for which we show the improved readability, maintainability and understandability without loss of performance

The paper is structured as follows. In Section 2 on page 3 we will give an introduction to the PYPY project. Section 3 on page 7 covers the technical details of the emulated game device, followed by the actual implementation details of PYGIRL in Section 4 on page 9. In Section 5 on page 18 we compare the performance of the different WSVMs implementations. We provide an outlook of our future work in Section 6 on page 21. Then finally we provide a brief overview of our achievements in Section 7 on page 23.

PyPy in a Nutshell

In this section we describe the PyPy project, which we use as a translation toolchain.

The goal of PYPY was to write an full featured, customizable and fast interpreter for Python written in Python itself, in order to have the language described in itself. Of course, running an interpreter on top of another interpreter results in slow execution, and still requires a first interpreter written in another language below it. For this reason it was decided to build a "domain specific compiler", a toolchain which translates high-level specifications of interpreters (VMs) in Python down to low-level backends, such as C/Posix [START_REF] Rigo | PyPy's approach to virtual machine construction[END_REF]. Like the interpreter, the toolchain itself is written in Python. This effort is similar to other self-sustaining systems like Squeak where the VM is written in Slang [START_REF] Ingalls | Back to the future: The story of Squeak, a practical Smalltalk written in itself[END_REF]. The major difference between Slang and PYPY is that Slang is a thinly veiled Smalltalk-syntax on top of the semantics of C, whereas PYPY focuses on making a more complete subset of the Python language translatable to C. This difference is clearly visible in the level of abstraction used by programs written for the respective plattforms.

The Interpreter

The starting point for PYPY was to create a minimal but full interpreter for Python written in Python itself. With minimal we mean that all interpreter implementation details such as garbage collector and optimizations are not implemented. For these features the PYPY interpreter rather relies on the garbage collector and optimizations available in the environment running it. This results in a very clean and concise implementation of the interpreter which models how the language works without obscuring implementation details.

The Translation Toolchain

Since high-level executable models of VMs will not run fast by themselves, PYPY also implements a "domain specific compiler", which can translate VMs in Python down to low-level code. This translator is designed as a flexible toolchain where front-and backends can be replaced so that it can generate VMs for different languages which will run on different platforms.

IAM-09-002

Not only the front-and backend can be changed, but also different aspects of the translation itself. This results in fast and portable VMs. First the toolchain builds a modifiable and dynamic flow graph from the target program's sources. From there on, this model is transformed in several steps until the final binary results. Using the same intermediate representation for a large part of the translation and applying transformations in small steps allows us to add custom modifications for every translation aspect.

Translation Steps

In the first step the translator loads the source-code it will translate. Unlike standard compilers which would start by parsing the source code, the PYPY toolchain never even sees the Python source code. Since the input code for the translator is RPython code (which is a subset of Python code), and the toolchain itself is running on top of a Python interpreter, the toolchain can use its hosting Python interpreter to load its input files. While loading, the Python interpreter will evaluate all top-level statements and add the loaded method and class definitions to the global Python memory. After loading, the toolchain uses the the globally loaded main function as starting point for its input graph. This setup allows the input model to apply metaprogramming in plain Python code at preprocessing time, as long as the resulting graph in memory is RPython compatible (Listing 2 on page 12 shows an example of this feature). From the code objects resulting from loading the sources, a control flow graph is generated. Because PYPY mostly targets statically typed backends, the graph is annotated with inferred types. Starting with a specified entry point, the type inference engine works its way through the object flow graph and tries to infer most specific types. If multiple types are possible for a certain node, the type inference engine will try to select the common superclass as type. If the most specific type found for a node would be the most common type object type in the system, an error is thrown to show that no specialization was possible. The same happens when two types are incompatible, like booleans and objects. If such type-errors arise, they have to be solved by the programmer. Such problems are often solved by introducing a new common superclass or moving a method higher up the hierarchy. In other cases they really are semantical errors and require restructuring (Section 4.3 on page 14 covers some aspects of resolving errors discovered by the toolchain). Here we see that the compiling process has an impact on the structure of the input source code. It effectively limits the expressiveness of the input language. For this reason we call the input language understood by the PYPY toolchain RPython instead of Python, as we will see in Section 2.3 on the following page. The annotation step is followed by the conversion from a high-level flowgraph into a low-level one. There is currently a converter which specializes towards low-level backends and one which specializes towards objectoriented backends (Figure 1 on the preceding page).

On the low-level flow-graph, optional backend optimizations are performed. These optimizations are rather similar to optimizations found in standard compilers, like function inlining and escape analysis.

After the low-level flow-graph is optimized, it gets specialized for a specific backend. The preparation for code generation covers the following points:

• insertion of explicit exception handling

• adding memory management details. Different garbage-collection strategies are available2 . Note that these garbage collectors themselves are also written in Python code. They also get translated and woven into the VM definition.

• creation of low-level names for generated function and variables

IAM-09-002

Finally the language-specific flow-graph is transformed into source files. These source files are then again compiled or assembled to binaries by a language-specific compiler or assembler, which can perform further domain-specific optimizations. For example generated C source files are compiled with GCC with the -O3 flag.

RPython

In order to boost the performance of the Python interpreter written in Python, the PYPY translation toolchain was created. The translation from a dynamically typed language like Python to a statically typed language like C is however not straightforward. As mentioned before, in order to do this in a semantically correct way, we are enforced to limit the expressiveness of the input language. For this reason, when we talk about the language understood by the translation toolchain, we do not call this Python but rather RPython or restricted Python. The language is rather imprecisely defined as Python with the following restrictions applied:

• Variables need to be type consistent

• Runtime reflection is not supported
• All globals are assumed to be constants

• All code has to be type inferable

The complete definition of RPython itself is fuzzy as it is defined by the evolution of the translator and the community. 3Although these restrictions seem to be substantial for a dynamic language such as Python, it is still possible to use high-level features like single inheritance, mixins and exception handling. More importantly, since RPython is a proper subset of Python, it is possible to test and debug the input program with the known Python tools before trying to translate it using PYPY. As such the VM models we build for PYPY are executable by themselves, thus giving a great speedup against a classical compile-waittest cycle.

Gaming Device Hardware Technical Details

In this section we list the technical details of the gaming hardware. An official documentation is available on the producer's website. 4Device RAM ROM JoyPad Video Sound CPU Cartridge

Hardware Pieces

The system is composed of 6 essential pieces which are accessible through shared memory. External events are supported through a 8 bit maskable interrupt channel. The use of an 8 bit processor makes the handling of opcodes compact and maintainable. There are two kind of opcodes:

• First order opcodes are executed directly

• Second order opcodes fetch the next instruction for execution. The combined opcode doubles the range of possible instructions at the cost of execution speed. The second order opcodes are mostly used for bit testing and bit setting on the different registers.

The following list show some more specific details of the different parts of our gaming device.

• The 8 bit CPU is a slightly modified version of the Zilog 80 with a speed of 4.19 MHz.

The CPU supports two power-saving mechanisms, which both work in a similar way. After a certain interrupt, the CPU is put into a low power consumption mode which is left only after another interrupt occurred.

IAM-09-002

• The cartridge contains ROM with the embedded game and possibly additional RAM and/or other devices. The size of the RAM is depending on the type of cartridge. Some types of cartridges support an additional battery to store game-state. Switchable memory banks are used to extend the 8 bit limited address range. A checksum in the header and a startup procedure are used to guarantee that the device is working correctly and the cartridge is not corrupted.

• The supported Resolution is 160 × 144 Pixels with 4 shades. It is possible to show maximally 40 Sprites of 8 × 16 or 16 × 16 pixels at the same time. The video chip has two tile-map registers, one for the background and one for the foreground. A masking window can be used to crop the background thus enabling basic low-level support for scrolling.

• A serial connection can be used to communicate with another device. This is useful for multiplayer games.

• The sound chip supports stereo sound and has four internal mono sound channels. Sound can be either read directly from the RAM, thus creating arbitrary sound at the cost of its calculation, or it can be produced via a noise-channel or via two different wave pattern generators.

PyGirl Implementation

In this section we will highlight some specific implementation details of the PYGIRL VM.

For our implementation we did not start from a formal specification of the hardware. Instead we chose to adapt an existing stereotypical implementation of a VM for the same device to PYPY style for easier comparison.

Source Implementation

The VM implementation we chose as a basis [START_REF] Hasan | Jmario[END_REF] is a VM written in Java.

It is developed in a portable manner. By abstracting out platform-specific details to certain components, they are able to provide variants of the emulator for the different versions of Java architectures like the Java Standard Edition and Applets for the web. The application is structured by providing mappings for each piece of hardware to one class. Platform-specific parts are factored out by providing a set of abstract driver interfaces which handle input and output. These drivers are then implemented for each architecture separately, adapting to the requirements. Even though this is a fairly abstract and portable design, this again shows that by implementing your VM without a toolchain, your VM codebase will be cluttered with backend specific details. While the code is written in an object-oriented manner at first glance, many parts of the Java system strictly follow the low-level execution details of the hardware. On top of this, the implementation is cluttered with local optimizations. Two types of optimization strategies clearly stand out: manual inlining of code and manual unrolling of loops. Both strategies result in an overly expanded code-base, obscuring the overall design and semantics. For example, the CPU class is cluttered with such speed optimizations. The reason is that a CPU is a very low-level general-purpose device which provides less possibilities for abstraction than others. However, even the video chip is implemented in a non-abstract procedural way. This even though there are more conceptual components ready for abstract representation, such as sprites, background and foreground.

From Java to Python

We started off by migrating the source VM from Java to Python, without applying any optimizations or refactorings. Like this we could easily track IAM-09-002 the progress we made while refactoring. During the whole process, we kept the overall structure of the existing system as it directly corresponds to the hardware.

The following sections cover different refactorings we applied and abstractions we introduced, to go from a low-level detailed implementation to a high-level model of the VM.

Memory Usage Considerations

The Java code is cluttered with type-casts between bytes and integers.

Bytes are used to represent the 8 bit hardware architecture, whereas the integers are used for all kind of operations. Instead of using integers whenever possible, the Java version focuses on reducing the memory footprint of the running emulator and even more, it focuses on the implementation details of the original hardware. Only at very few places in the code was the usage of bytes justified by the resulting two's-complement interpretation of the numbers.

In our model type-casts are removed wherever possible to improve readability. Firstly we consider the memory footprint of the device we will emulate too small to justify optimizing memory usage. Even if we use four to eight times as much memory as the original device would have used, corresponding to an expansion from 8 to 32 or 64 Bit, this means that we will end up with about 20Mb memory usage, which is a negligible amount for modern computers. Secondly and more importantly, it is (hypothetically speaking) possible to plug an additional transformation into the toolchain, which converts all integers to bytes, so that the memory footprint of the final VM is equal to the original device.

The God Switch

The most prominent candidate for refactoring duplicated and inlined code is the CPU class. In the original version the class is around 4000 lines long, featuring an unpleasant 1700 line switch which delegates the incoming opcodes.

♣✉❜ On top of that, there is a nested switch of 800 LOC, which handles the second order opcodes. In both switches we could identify patterns which could be used as basis for extra abstractions. In the following excerpt from the original Java code we can see how bytecodes directly encode their semantics in a structured way The Java code covers all these cases by manually specifying them in the switch and by encoding the logic in one function per opcode. Since all these operations are symmetrical in terms of semantics and usage of cycles, even while there are only few lines of code per operation, there is quite some redundancy. The opcodes in Listing 1 encode the arguments which should be passed to the load function. Instead of separated functions PYGIRL uses a load for different registers such that it can be reused for more than one opcode.

♣✉❜•✐❝ ✈♦✐❞ execute(✐♥t opcode) { ...
❞❡❢ load(self, register1, register2):

register1.set(register2.get())

IAM-09-002

To refactor Listing 1 on the previous page, we created such reusable functions for all the different types of operations. Then we simply replaced the whole switch with a compact lookup in an opcode table which we generate from the abstract functionality descriptions using metaprogramming.

❞❡❢ execute(self, op_code):

OP_CODES[op_code](self) Instead of hardcoding the mapping to the respective functions, we used metaprogramming to compute the definition at translation time. The mapping of opcodes to function in the example Listing 1 on the preceding page can be replaced with the following flexible definition.

❞❡❢ create_op_codes(table): op_codes

= [] ❢♦r entry ✐♥ table: op_code = entry[0] step = entry[1] function = entry[2]
❢♦r getter ✐♥ entry [START_REF] Rigo | PyPy's approach to virtual machine construction[END_REF] The create_op_codes-function creates a part of the final opcode table from a list of inputs. Each input entry consists of a start opcode, the offset to add to get the following opcode and finally an ordered list of registers. The input set allowed us to keep a clean and compact notation for the variety of opcode mappings. We used the static creation of opcode table entries for most of the register operations, such as loading and storing, but also for nearly all other register operations. In total we were able use metaprogramming for about 450 out of all 512 opcodes. As a note on performance, when translating this code to C, PYPY is able to take the preprocessed opcode table and translate it back into an optimized switch. So the source code stays compact and maintainable, without loss in performance. Even better, PYPY should be able to optimize the switch at runtime so that often used branches are scheduled first. PYPY can then also inline small methods. Although the author of the Java version didn't inline any method, it would have been the next logical step to optimize the code in a classical way. By letting PYPY handle the optimizations, we maintain a clean implementation.

Abstraction

Since the Java implementation tries to evade methods calls, different internal subparts of the hardware device were implemented as simple byte or integer fields rather than separate high-level objects. This was mostly likely again for memory footprint reasons. Since we care more about having a nicely designed high-level model of the VM, we introduced classes for the different registers and the interrupt IAM-09-002 channel. This new abstraction reduced the usage of byte operations in many places. As another abstraction, we created a flag register to handle the different states and results of CPU operations. In the original code every single bit of the flag had to be extracted with a mask and a had to be checked with an integer or byte comparison, cluttering the code once more. Our flag register consists of 8 boolean fields which can be accessed by a representative name, hence increasing the understandability and maintainability of the code. The following example shows the code of two flag-related methods in Java and the corresponding ones in Python. The ccf-method inverts the carryflag and resets all the other flags but the zero-flag. The scf-method resets all flags except for the zero-flag and sets the carry-flag:

♣✉❜•✐❝ ❢✐♥❛• ✈♦✐❞ ccf() { t❤✐s.f = (t❤✐s.f & (Z_FLAG | C_FLAG)) ^C_FLAG; } ♣✉❜•✐❝ ❢✐♥❛• ✈♦✐❞ scf() { t❤✐s.f = (t❤✐s.f & Z_FLAG) | C_FLAG; }
The corresponding code in PYGIRL is not that compact, but more importantly the understandability is increased:

❞❡❢ complement_carry_flag(

Translation

We now describe some of the problems we encountered while using PYPY to translate our VM down to a low-level backend. Such problems typically arise because of differences between Python and its restricted subset, RPython, described in Section 2.3 on page 6. Generally these problems only require small refactorings and only come up when the VM is already in a pretty stable state. This results from the fact that our executable model fully runs on a normal Python interpreter, which allows us to execute first prototypes without having to care if it can already be translated with PYPY. We show some examples and how to solve these specific cases so that the translation can succeed.

The easiest translation bugs are related to straightforward syntactic bugs, like typos. After these inconsistencies are cleared out, we encountered typical type conversion errors. Some of those problems were related to confusions between integers and floats, others were related to wrong inheritance. For some classes we introduced abstract superclasses so that they would have a common type.

Call Wrappers

We handled operations on registers and other CPU functions elegantly by just passing around the function closures, allowing us to reuse methods for different actions. A very common example is the following load method: RegisterCallWrapper takes a register and calls get or set on it. The CPUFetchCaller is used as an abstraction for the fetch method of the CPU so that it can be used as a possible argument for the load-method. These are two out of the 5 total call-wrappers we used to handle closure passing. The common superclass CallWrapper makes it possible for PYPY to infer a common type for the argument of every method. Something which is not that clearly visible in this code is the fact that every get-method of the call-wrapper returns an integer. Thus all methods would have the same signature. To support the call-wrappers we replaced the closure calls by a get or set on the call wrappers. Applied to the load method this resulted in the following code ❞❡❢ load(self, getCaller, setCaller):

❞❡❢ load(self,
setCaller.set(getCaller.get())

Then the method-calls from the original example look now like

State of the Implementation

The current version supports simple test ROMs without sound and moving sprites. Static images and bit-blitting are supported. This means that most games are able to show an intro image but there is no animation. In the current version, the video part is heavily redesigned, using high-level definitions for all the logical parts in the video chip. Because we mostly focussed on the graphics part, the sound chip has not yet been implemented for PYGIRL. The CPU is fully functional and like all other parts, completely test-covered.

IAM-09-002

Performance evaluation

We ran the emulation on three different flavours of the VM. The original Java emulation, the interpreted variant of our implementation and finally the translated version. The interpreted version was run on top of the Python 2.5 Interpreter5 , whereas the translated version was built from those sources. The benchmarks are shown for the original Java implementation, the interpreted sources of PYGIRL and finally for the translated binaries of PY-GIRL. Each test shows the average execution time over 1000 runs using Java 1.6.0_06, 1.5.0_15 and Python 2.5.2 on a 64 Bit Ubuntu 8.04.1 server machine with an Intel Xeon CPU QuadCore 2.00 GHz processor. We use revision number 59328 of the PyPy project. PYPY uses the following GCC optimizations when creating the binary executable:

-O3 -fomit-frame-pointer -pthread -I/usr/include/python2.5

The complete GCC calls and arguments are visible during the end of the translation process. Instructions for running the benchmarks are given in Appendix 11 on page 26.

All opcodes

This benchmark covered all possible opcodes which were executed equally distributed, giving a theoretical speed of the WSVM. The results of this benchmarks are shown in Figure 2 on the next page.

It is clearly visible that the interpreted version running on top of CPython is approximately 100 times slower than the Java version and 250 times slower than the translated version. This test compares the overall performance of the system, which is no directly related to the performance of the emulator running a game.

Typical opcode Set

To compare the performance of the emulator in a typical situation, we considered in this test a weighted opcode set which we constructed by running multiple games. From these test-runs, the 30 most executed opcodes are selected, as they probably represent typical in-game performance. The The results differ from the first benchmark, which has its origins in the different relative execution times of opcodes in the Java and in the translated version. Java also was able to optimize the code at runtime, using a JIT. While this will also be available for VMs build using PYPY, it is currently still in development [START_REF] Pedroni | JIT compiler architecture[END_REF]. Comparing the execution time of each opcode, a steady performance optimization is visible in Java. The different distribution of the executed opcodes in this benchmark (Table 2 on page 28) allows Java to further improve the result. Java can optimize the most frequently executed opcodes, which weigh heavier on the total result in this benchmark than in the first one.

Future Work

In this section we discuss the future work needed for PYGIRL and corresponding tasks for PYPY.

PyGirl

The current implementation is not fully usable yet. First of all, there is no implementation yet of the sound unit available in our emulation of the device. We chose to postpone the development of this unit since all other parts had a much higher priority. Surely this unit has to be considered as an important task for completing the system. From all the hardware parts which already do have a software counterpart, only the video driver is not working properly yet. It is currently able to display simple graphics and supports most operations. Still there are some hidden bugs, which occur only after a certain combination of instructions.

Most of the bit-operations have been replaced by more readable boolean comparisons, like described in Section 4.2.3 on page 13. The graphic part, however, still relies on pixel operations and raw memory access, much like the original version. In order to create a fully object-oriented implementation, a replacement of each sprite with a corresponding sprite-object is required. The video-chip itself also supports more abstract features like a masking window and a background which should be represented by objects too.

PyPy

The current state of the implementation only allows the code of PYGIRL to be translated using the C-backend. This is due to the fact that the I/O drivers for PYPY has only been completed for that backend. The fact that we only need very low level support for most VMs, like simple bitblitting, makes enabling graphics support for the other backends a straightforward task.

Translating PYGIRL with the JVM as target, would make it possible to compare the performance of the original Java implementation directly with our approach. Another important factor is the availability and wide spread distribution of the Java Virtual Machine. It would be interesting to be able to run PYGIRL on a mobile device [START_REF] Aubry | Case study on using pypy for embedded devices[END_REF]. Since the Java Mobile Edition is for the biggest part a subset of the Standard Edition, the toolchain needs only mi-IAM-09-002 nor changes. Because our implementation does not rely on features which are not available on the Mobile Edition, PYGIRL should be translatable in the same way to C, Java SE and Java ME.

Conclusion

In this paper we have shown that the usage of high-level models for the definition of whole-system VMs will increase understandability, maintainability and extendability through separation of the implementation details and the actual platform specific model. Our prototype model PYGIRL is implemented in a high-level language without the incorporation of any standard VM optimizations. Because of the strong metaprogramming capabilities of the model definition language, we were able to abstract away clear patterns in the mapping between opcodes and their semantics.

All the standard VM implementation tricks are abstracted away from the actual model to the used translation toolkit PYPY. This toolchain reintroduces all implementation details to our VM at model transformation time, thus still resulting in a highly optimized binary. We validated the approach by comparing the performance of our VM written for PYPY with a standard implementation of a VM in Java emulating the same hardware. Our benchmarks showed that both implementations result in the same magnitude of execution performance. We showed that the combination of a high-level executable model and a translation toolchain can serve as a new approach for creating flexible and maintainable whole-system VMs for different platforms.

How to run PyGirl

PYGIRL requires Python version 2.5 or higher, the sources are available on the codespeak svn-repository.

How to run the Benchmarks

In this section we show how to use the benchmark tools to reproduce the results from Section 5 on page 18. Since PYPY is an evolving system, the results of the newest version might be different from the ones presented in the benchmark section. In order to run the benchmarks properly you have to download the sources first. Since the profiler depends on a certain structure, the PYPY project and the JMARIO are packaged in this repository. Also the JMARIO implementation has an extended build file and some modified sources, targeting the benchmarks.

> svn co https://www.iam.unibe.ch/scg/svn_repos/Students/cami/pyGirl > ls profiling/ ... profileAll.sh profileEach.sh profileJIT.sh profileTypical.sh ...

To run a benchmark, execute one of the listend bash scripts. Each script takes the number of test probes and the number of executions as arguments. The execution is then averaged over the number of test probes. To run 10 test probes which execute each test 100 times, type the following:

> profiling/profileAll.sh 10 100 ------------------------------------------------------java1.6 - ---------------------------------------------------- Further instruction on translating the sources can be found on the PYPY website under 6 .

Performance Evaluation

The following list shows the the 30 most executed opcodes summed over four different Games. Each game was allowed to execute 500'000 operations. Table 2 shows the results of this analyzation, which we used to compare the different VM implementations (Section 5 on page 18).

Figure 1 :

 1 Figure 1: PYPY translation toolchain architecture

♣

  ✉❜•✐❝ ❢✐♥❛• ✈♦✐❞ ld_A_B() { t❤✐s.a = t❤✐s.b; t❤✐s.cycles -= 1; } Listing 1: Java: Grouped opcode mappings

Figure 2 :Figure 3 :

 23 Figure 2: Benchmark: Comparing the execution time of PYGIRL with the Java version weighting all opcodes equally

  Due to the different origins of the passed function closures, the toolchain was unable to transform this into a typed counterpart. As solution we created call-wrappers with a common superclass. Introducing call-wrappers for the passed function closures added some overhead, but it was a simple way to keep the code minimal and close to the original idea of passing around closures. The following code shows the same function calls using wrappers for each passed type of closure

	IAM-09-002
	❝•❛ss RegisterCallWrapper(CallWrapper):
	❞❡❢ __init__(self, register):
	self.register = register
	❞❡❢ get(self, use_cycles=True):
	r❡t✉r♥ self.register.get(use_cycles)
	❞❡❢ set(self, value, use_cycles=True):
	r❡t✉r♥ self.register.set(value, use_cycles)
	❝•❛ss CPUFetchCaller(CallWrapper):
	❞❡❢ __init__(self, CPU):
	self.CPU = CPU
	❝•❛ss CallWrapper(object):
	❞❡❢ get(self, use_cycles=True):
	r❛✐s❡ Exception("called CallWrapper.get")
	❞❡❢ set(self, value, use_cycles=True):
	r❛✐s❡ Exception("called CallWrapper.set")

getter, setter): setter(getter()) ... load(self.flag.get, self.a.set) load(self.fetch, self.a.set) load is called with different arguments. In the first example it is used to copy the values from the flag-register into the register a. The second example loads the next instruction into register a.

❞❡❢ get(self, use_cycles=True): r❡t✉r♥ self.CPU.fetch(use_cycles)

How to run the Test-cases

  To run the test-cases make sure you checked out the latest version of the PYPY distribution, including the PYGIRL project. Please make sure that pypy-dist/py is in your Python include path. Go to the gameboy-folder and run py.test To run the original Java version, you have to download the sources from the sourceforge project website IAM-09-002 http://sourceforge.net/projects/mario/ Or you can download the sources directly from the cvs repository > cvs -z3 \ -d:pserver:anonymous@mario.cvs.sourceforge.net:\ /cvsroot/mario co -P jmario To run the script you have to change to the jmario folder and run the ant buildfile.Then the compiled jar is available in the build folder. Type the following commands to run the jar with a test-ROM. Simple test-ROMs are included in the PYPY distribution. Test-ROMs number 8 and 9 have graphical output, the others only serve for testing the opcodes > cd build/ > java -jar jmario.jar path/to/your/testROM.gb

	To run the project you have to checkout
	the full PYPY sources
	> svn co http://codespeak.net/svn/pypy/dist pypy-dist
	> cd pypy-dist
	To translate PYGIRL you to go to the translation goal folder and then run
	the translation script > cd jmario/
	> ant
	> cd pypy/translator/goal
	> ./translate.py --gc=generation --batch \
	targetgbimplementation.py
	After translating you can run the binary file with one of the test roms which
	are located in pypy/lang/gameboy/rom
	> ./targetgbimplementation-c \
	../../lang/gameboy/rom/rom8/rom8.gb
	To stop the emulation hit the ESC-key.
	The full project's sources are located under pypy/lang/gameboy
	9 > cd pypy-dist/pypy/lang/gameboy
	> py.test
	10 How to run JMario

  -BUILD SUCCESSFUL Total time: 2 seconds Starting 10 test runs: .......... So this test took 0.2054 Seconds and the standard deviation over the 10 test runs is ±0.0030 Seconds. Each of the profiling scripts automatically creates the binaries necessary to run the benchmarks. To create the binaries manually, either run the ant script in the JMARIO project with the profiling target, > cd jmario; ant dist-profile or the profiling target in the PYPY project, which needs a running version of the developer version of Python installed.

		Concatenating results
	The	results	are	stored	into	files	under
	ARCHITECTURE/result/PROFILE_XYZ.txt.
	> cat profiling/java1.6/result/PROFILE_All.txt
		0.2054 0.0030

> cd pypy-dist/pypy/translator/goal/ > ./translate.py --gc=generation targetgbprofiling

Performance Evaluation

http://codespeak.net/pypy/

http://codespeak.net/pypy/dist/pypy/doc/garbage_collection.html

http://codespeak.net/pypy/dist/pypy/doc/coding-guide.html# restricted-python

http://www.nintendo.co.uk/NOE/en_GB/support/game_boy__pocket__color_

559_562.html

http://python.org/download/

http://codespeak.net/pypy/dist/pypy/doc/getting-started.html

IAM-09-002

IAM-09-002

JIT Comparison

In order to show the impact of a JIT to the results of the benchmarks, we run in this section the equally distributed opcode set of Section 5.1 on page 18 with different execution counts. As the number of execution grows, the difference between the Java and the translated Python version shrinks, and eventually the Java version gets faster than the translated version.

Executions