Marcus Denker

Stéphane Ducasse

Éric Tanter

Runtime Bytecode Transformation for Smalltalk

Keywords: Smalltalk, object-oriented programming, bytecode transformation, metaprogramming

à 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

Many objectives of software engineering can be served by appropriate program transformation techniques. Software adaptation can be used for Binary Component Adaptation (BCA), a technique proposed by Keller and Hölzle which relies on coarse-grained alterations of component binaries to make them interoperable [START_REF] Keller | Binary component adaptation[END_REF]. Another objective of software adaptation is that of separation of concerns [START_REF] Parnas | On the criteria to be used in decomposing systems into modules[END_REF], as first emphasized by work carried out in the reflection community [START_REF] Stroud | Using metaobject protocols to satisfy non-functional requirements[END_REF][START_REF] Tanter | Managing references upon object migration: Applying separation of concerns[END_REF][START_REF] Mcaffer | Meta-level architecture support for distributed objects[END_REF], and more recently, aspect-oriented programming (AOP) [START_REF] Kiczales | Aspect-Oriented Programming[END_REF]. In this context, transformation techniques are used to merge together different pieces of software encapsulating different concerns of the global system. Program transformation is a valid implementation techniques for reflection and AOP when an open interpreter of the considered language is not available.

Fine-grained control of computation, such as message passing control in the context of object-oriented programming, is the corner stone of many interesting applications [START_REF] Ducasse | Evaluating message passing control techniques in Smalltalk[END_REF]. It has been used for a wide range of application analysis approaches, such as tracing [START_REF] Heinz-Dieter | What tracers are made of[END_REF][START_REF] Pachet | Spying as an Object-Oriented Programming Paradigm[END_REF][START_REF] Brant | Wrappers to the Rescue[END_REF], automatic construction of interaction diagrams, class affinity graphs, test coverage, as well as new debugging approaches [START_REF] Lewis | Debugging backwards in time[END_REF][START_REF] Ko | Designing the whyline: a debugging interface for asking questions about program behavior[END_REF]. Message passing control has also been used to introduce new language features in several languages, for instance multiple inheritance [START_REF] Borning | Multiple inheritance in Smalltalk-80[END_REF], distribution [START_REF] Garbinato | Distributed programming in GARF[END_REF][START_REF] Bennett | The design and implementation of distributed Smalltalk[END_REF][START_REF] Mccullough | Transparent forwarding: First steps[END_REF], instance-based programming [START_REF] Beck | Instance specific behavior: Digitalk implementation and the deep meaning of it all[END_REF], active objects [START_REF] Briot | Actalk: A testbed for classifying and designing actor languages in the Smalltalk-80 environment[END_REF], concurrent objects [START_REF] Yokote | Experience and evolution of ConcurrentSmalltalk[END_REF], futures [START_REF] Pascoe | Encapsulators: A new software paradigm in Smalltalk-80[END_REF] and atomic messages [START_REF] Foote | Reflective facilities in Smalltalk-80[END_REF][START_REF] Mcaffer | Meta-level programming with coda[END_REF], as well as backtracking facilities [START_REF] Lalonde | Building a backtracking facility in Smalltalk without kernel support[END_REF].

CLOS is one the few languages that offers a dedicated metaobject protocol supporting language semantics customization [START_REF] Kiczales | The Art of the Metaobject Protocol[END_REF]. Other languages such as Smalltalk and Java rely on techniques or libraries to either transform code or take control of the program execution [START_REF] Ducasse | Evaluating message passing control techniques in Smalltalk[END_REF][START_REF] Tanter | Altering Java semantics via bytecode manipulation[END_REF]. The most basic way to alter programs is of course to modify the source code and recompile it. This approach is used by several Java systems, such as OpenJava [START_REF] Tatsubori | OpenJava: A class-based macro system for java[END_REF] and the Java Syntactic Extender [START_REF] Bachrach | The Java Syntactic Extender (JSE)[END_REF]. However, in many contexts, relying on the availability of source code is limiting since most applications ship in binary form, and in open distributed systems, source code is usually not known in advance. Furthermore, the source language from which the actual binary was obtained is not necessar-⋆ 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. [START_REF] Ko | Designing the whyline: a debugging interface for asking questions about program behavior[END_REF]-Sept. 2006) and "RECAST: Evolution of Object-Oriented Applications" (SNF Project No. 620-066077, Sept. 2002 -Aug. 2006). É. Tanter is financed by the Millennium Nucleus Center for Web Research, Grant P01-029-F, Mideplan, Chile.

Email addresses: denker@iam.unibe.ch (Marcus Denker), ducasse@iam.unibe.ch (Stéphane Ducasse), etanter@dcc.uchile.cl ( Éric Tanter).

ily the mainstream language of the runtime system. Bytecode manipulation, as done in the Java world by tools such as BCEL [START_REF] Dahm | Byte code engineering[END_REF] and Javassist [START_REF] Chiba | An easy-to-use toolkit for efficient Java bytecode translators[END_REF] is a particularly pertinent alternative. The challenge is to provide appropriate high-level abstractions to bytecode transformation, in order to shield users from the burden of working at the bytecode level [START_REF] Tanter | Altering Java semantics via bytecode manipulation[END_REF].

To the best of our knowledge, there is no single bytecode transformation tool for the Smalltalk/Squeak environment, in the line of what Javassist represents for the Java world. This is all the more surprising that the Squeak environment actually represents an ideal environment for bytecode transformation. In contrast with Java where full bytecode transformation is only possible at load time, and very severely limited at runtime, Squeak enables the full power of bytecode transformation to be used dynamically. The purpose of Byte-Surgeon is precisely to leverage the flexibility of the Smalltalk language and the Squeak environment to provide a backend to designers of toolkits for component adaptation, reflective and metaprogramming, and aspect-oriented programming.

The contributions of this paper are:

• a motivation for the need of a dynamic bytecode transformation framework for Smalltalk, working at appropriate levels of abstraction, • a framework, called ByteSurgeon, that enables runtime bytecode transformation via a two level API, • a simple MOP that can be used to compare bytecode transformation frameworks.

The paper is organized as follows: Section 2 explains the need for bytecode manipulation at appropriate levels of abstraction, by discussing related work.

Then we present ByteSurgeon at work in Section 3. Section 4 details some aspects of the architecture. In Section 5, we validate the interest of our framework via the implementation of two language features: method wrappers [START_REF] Brant | Wrappers to the Rescue[END_REF], and a simple runtime metaobject protocol (MOP) making use of runtime manipulation for dynamic (un)installation of hooks; a first set of benchmarks completes the validation of ByteSurgeon. Section 6 discusses future work and concludes.

The Need for Bytecode Manipulation

There are many ways to change the semantics of programs, ranging from code preprocessing to modification of the language runtime environment. If the language runtime is not an open implementation offering an adequate metaobject protocol (MOP) [START_REF] Kiczales | The Art of the Metaobject Protocol[END_REF], then modifying it directly sacrifices portability; since mainstream Smalltalk virtual machines such as Squeak are not open in this sense, we discard the alternative of intervening at the VM level.

Source code transformation can be done either directly on the text (concrete syntax) or on the abstract syntax tree (abstract syntax). Furthermore, in language environments where source code is compiled to an intermediate bytecode language which is abstract enough, bytecode transformation is an interesting approach; it is actually widely used in the Java community.

In Section 2.1 we discuss the inconveniences of source code approaches. Still, once bytecode transformation is agreed upon, the issue of the abstraction level offered to the programmer appears, discussed in Section 2.2. We also discuss the limitations of bytecode transformation in the context of Java.

Disadvantages of Source Code Transformation

Transforming source code at the concrete syntax level is typically avoided because of the lack of structure and abstraction at the text level. Transformation of abstract syntax trees (ASTs) is much more adequate, but still suffers from a number of limitations.

No access to the source code. For the sake of saving space or ensuring a first level of privacy, the source code of an application is usually not distributed. Using source code strippers or removing symbolic information are current practices to reduce the size of an application before deployment.

Furthermore, in open contexts such as mobile agent platforms and open distributed systems, code is typically not known in advance. One can of course rebuild an AST from bytecode, but this technique presents a number of challenges: bytecode-to-AST decompiling is a slow process, and typically requires the decompiler to know about bytecode generation patterns used by the compiler so as to rebuild meaningful AST nodes.

No original language warranty. Most mainstream languages today, such as Java, Squeak and C#, are based on a virtual machine executing bytecodes, and these virtual machines are actually used as the execution engines of various languages, other than the "original" ones. For instance, for the Croquet environment [START_REF] Smith | Croquet, A Collaboration System Architecture[END_REF], a number of experimental scripting languages have been developed, among them languages similar to JavaScript and LOGO. Another example is the Python language, which can be compiled to Java bytecodes [START_REF]Jython[END_REF].

To provide practical performance, these languages come with their own custom compiler that produces bytecode for a production-quality virtual machine. Therefore a code transformation tool working at the AST level rebuilding the AST from bytecode would require a custom decompiler. On the other hand, working on bytecode, although lower-level than AST, makes it possible to uni-formly apply transformations even in the presence of non-original languages.

Recompiling is slow. Finally, transforming source code means that a compiling phase is necessary afterwards to regenerate bytecodes. Recompilation is a slow process, much slower than manipulating bytecode; benchmarks of Section 5.3 validate this statement.

Bytecode Transformation Approaches

Due to the many reasons explained above, a wide variety of tools have been proposed that rely on bytecode transformation. Surprisingly, most of these tools have been made for Java, and we are aware of very few related proposals in the Smalltalk world.

Java and Bytecode Transformation. The Java standard environment only allows for bytecode transformation at load time. At runtime, it is only possible to dynamically generate new classes from scratch, not to modify existing ones. These restrictions have been somehow relaxed in the context of the JVM debugger interface (JDI) [START_REF]Java debug interface[END_REF], but relying on the debugger interface is not reasonable in a production environment. Furthermore, the possibilities of class reloading are strongly limited as, for instance, new members cannot be added to classes. Using load-time transformation in Java also raises a number of subtle issues related to class loaders and the way they define namespaces in Java [START_REF] Liang | Dynamic class loading in the Java virtual machine[END_REF].

Level of Abstraction. The experience gained with Java bytecode transformation tools brings a number of insights that ought to be considered when designing a new framework. The most fundamental one is that of the level of abstraction provided to programmers.

Tools like BCEL [START_REF] Dahm | Byte code engineering[END_REF] and ASM [START_REF] Bruneton | ASM: A code manipulation tool to implement adaptable systems[END_REF] strictly reify bytecode instructions: as a consequence, users have to know the Java bytecode language very well and have to deal with low-level details such as jumps and alternate bytecode instructions (a Java method invocation can be implemented by several bytecode instructions, depending on whether the invoked method is from an interface, is private, etc.).

On the contrary, Javassist [START_REF] Chiba | Load-time structural reflection in Java[END_REF] and Jinline [START_REF] Tanter | Altering Java semantics via bytecode manipulation[END_REF] focus on providing source code level abstractions: although the actual transformation is performed on bytecode, the API exposes concepts of the source language. This is highly profitable to end users. In its latest version [START_REF] Chiba | An easy-to-use toolkit for efficient Java bytecode translators[END_REF], Javassist even offers a lightweight online compiler so that injected code can be specified as a string of source code. The Javassist compiler supports a number of dedicated metavariables, which can be used to refer to the context in which a piece of code is injected.

As a matter of fact, bytecode-level manipulation is more complex than sourcelevel manipulation because of the many low-level details one needs to deal with. However, working at the bytecode level also makes it possible to express code that is not directly expressable in the source language(s). This dilemma basically motivates the need for both APIs, as is done in Javassist: a high-level API provides source-level abstractions, and a low-level API provides bytecodelevel abstractions.

Proposals for Smalltalk. To the best of our knowledge there is no generalpurpose bytecode manipulation tool for a Smalltalk dialect. AOStA [START_REF] Miranda | A Sketch for an Adaptive Optimizer for Smalltalk written in Smalltalk[END_REF] is a bytecode-to-bytecode translator that aims at providing higher-level, transparent, type-feedback-driven optimizations. It was not thought to be open to end users for bytecode manipulation1 . Method wrappers [START_REF] Brant | Wrappers to the Rescue[END_REF] make it possible to wrap a method with before/after code. They are very fast to install and remove, as they do not need to parse bytecode or generate methods, but are not a general-purpose transformation tool. Several extensions actually need more power than just before/after control. AspectS [START_REF] Hirschfeld | AspectS -Aspect-Oriented Programming with Squeak[END_REF] has been recently proposed as an aspect-oriented interface to the reflective capabilities of Smalltalk combined with method wrappers (to implement before/after advices). AspectS is actually a tool that would much profit from ByteSurgeon, as it would significantly raise its expressive power.

Motivation

From the above, it should be clear that a general-purpose bytecode manipulation tool for Smalltalk is missing. Such a tool ought to provide convenient abstractions to users, both at the source level and bytecode level. Byte-Surgeon is precisely such a tool. Beyond its interest for the Smalltalk community, ByteSurgeon also opens the door to a brand new range of experiments with runtime bytecode transformations, since it has none of the limitations of existing Java proposals. For instance, ByteSurgeon makes it possible to analyze concrete issues of fully-dynamic AOP.

ByteSurgeon at Work

ByteSurgeon is our library for runtime program transformation in Smalltalk, currently implemented in the Squeak environment. ByteSurgeon complements the reflective abilities of Smalltalk [START_REF] Rivard | Smalltalk : a Reflective Language[END_REF] with the possibility to instru-ment methods, down to method bodies. Smalltalk provides a great deal of structural reflection: the structure of the system is described in itself. Structural reflection can be used to obtain the object representing any language entity. For instance, the global variable Example stands for the class (the object representing the class) Example, and the object describing the compiled method aMethod in class Example is returned by the expression Exam-ple>>#aMethod. Dynamically adding instance variables and methods to an existing class is fully supported by any standard Smalltalk environment. However the structural description of a Smalltalk system stops at the level of methods: compiled method cannot be reflected upon. Conversely, ByteSurgeon can be used to do both introspection and intercession on compiled methods.

Introspecting Method Bodies

Let us first see how ByteSurgeon is used to introspect method bodies. The following code statically counts the number of instructions that occur in all methods of the class Example:

InstrCounter reset.

Example instrument: [ :instr | InstrCounter increase ]

The instrument: method is implemented in class Behavior. As a parameter it is given a block (of standard Smalltalk code) that takes one argument. This block is an instrumentation block: for each instruction within all methods of the class, the instrumentation block is evaluated with a reification of the current instruction as parameter. We will see later what an instruction reification is. For now, suffices to say that for each instruction, a global counter is increased.

There are variants of the instrument: method for each particular language operation: constant, variable access, read and store and message sending. For instance, instrumentSend: only evaluates the instrumentation block upon occurrences of the message send operation. Besides calling the instrumentation method on a class, thereby affecting all its methods, we can call it on a single method:

SendMCounter reset.

(Example>>#aMethod) instrumentSend: [ :send | SendMCounter increase ]

Reification of Language Operations

Instructions in a method body are static occurrences of the operations of a language. ByteSurgeon supports message send, access to instance variable and local variables, and constants. The structural model representing language operations is shown on Figure 1 2 . This structural model is bytecode-based. It does not encode as much information as an AST does, e.g., it is not possible to extract, from an IRSend, the instructions that correspond to the arguments of the send. This is a limitation of bytecode-based transformation against AST-based transformation. When calling an instrumentation method (i.e., instrument:, instrumentSend:) reification of instructions are built, as instances of the appropriate class in the hierarchy, and passed to the instrumentation block. The instrumentation can then introspect and change them. For instance, the following piece of code prints the selector of each message send occurring within Example>>#aMethod:

(Example>>#aMethod) instrumentSend: [ :send |
Transcript show: send selector printString; cr] Method Evaluation. A peculiar language operation is message receive (the callee-side equivalent of a message send). Actually, a message receive is realized by two operations: method lookup and method evaluation. Since we are working at the bytecode level, we do not have access to method lookup, only method evaluation. Rather than corresponding to a bytecode instruction inside a method body, method evaluation corresponds to a method body as a whole. Since ByteSurgeon treats all language operations in a uniform manner, methods have the same introspection and intercession interface than instructions (e.g., see Section 3.3.3).

Modifying Method Bodies

ByteSurgeon supports two ways of modifying method bodies: a bytecodelevel manner, where the user directly specifies the required transformation in terms of bytecode representations, and a source-level manner, where the transformation is specified with a string of source code. We hereby only present the source-level API. The bytecode-level API is briefly mentioned in Section 4.3.

Similarly to Javassist [START_REF] Chiba | An easy-to-use toolkit for efficient Java bytecode translators[END_REF], ByteSurgeon provides an online compiler that makes it possible to specify code to be inserted as a string. The methods to insert code before, after and instead of an occurrence of a language operation are named respectively insertBefore:, insertAfter: and replace:. They take as argument the source code as a string, which is subsequently compiled by the ByteSurgeon compiler, and the resulting code is inserted at the appropriate position. For instance, the following code inserts a call to the system beeper before each message send occurring within Example>>#aMethod:

(Example>>#aMethod) instrumentSend: [ :send | send insertBefore: 'Beeper beep' ]

The code string can contain any valid Smalltalk code3 , plus two kinds of special variables: user-defined variables to refer to statically-available information, and metavariables for runtime information.

Accessing Static Information: User-defined Variables

Statically-known information about an instruction can be used in the construction of the string. For instance, the following example records the name of selector of each message send occurring at runtime: Here we query the objects describing the message send operations for the name of the message sent. To ease the construction of the string and avoid hard-to-understand string concatenation, ByteSurgeon makes it possible to define custom variables with the syntax <: #variable>, and giving a list of association from variable names to object references4 :

(Example>>#
(Example>>#aMethod) instrumentSend: [ :send | send insertAfter: 'Logger logSend: <: #sel>'] using: { #sel -> send selector }

Accessing Runtime Information: Metavariables

The online compiler of ByteSurgeon also supports a number of predefined metavariables that refer to information available at runtime, such as the receiver of a message send (Figure 2). Metavariables are an essential part of the expressiveness of a good bytecode transformation framework. The exact set of available metavariables depends on both the operation selected -in the case of a message send, metavariables are provided to refer to the sender, the receiver and the arguments-and the transformation to perform -when inserting after, it is possible to access the result-. Metavariables are denoted by the <meta: #variable> construct. For instance, the following code replaces each message send with a call to a dispatcher metaobject in charge of the actual method lookup [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]:

(Example>>#aMethod) instrumentSend: [ :send | send replace: 'CustomDispatcher send: <: #selSymbol> to: <meta: #receiver> with: <meta: #arguments>' ] using: { #selSymbol -> send selector printString }

The ByteSurgeon online compiler takes care of generating the code to access the runtime information denoted by the metavariables, by adding a preamble before the inlined code. The runtime overhead due to preambles motivated us to maintain a special syntax for metavariables (meta), to raise the attention of users that these variables should be used conscientiously.

Altering Method Evaluation

To support transformation of method evaluation, method objects also support the insertBefore:, insertAfter: and replace: messages. As an example, the following code inserts a trace before each evaluation of a method in Example:

Example instrumentMethods: [ :m | m insertBefore: 'Logger logExec: <: #sel> ' using:

{ #sel -> m selector } ]
The metavariables for method evaluation are the same as for message sending (see Figure 2). The following example uses a metavariable to access the method evaluation result: We now give an overview of the implementation of ByteSurgeon, in particular the relation with the closure compiler and the transformation process. The low-level transformation API is also discussed.

Squeak

ByteSurgeon is currently implemented in Squeak [START_REF] Ingalls | Back to the future: The story of Squeak, A practical Smalltalk written in itself[END_REF], an open source implementation of Smalltalk-80 [START_REF] Goldberg | Smalltalk 80: the Language and its Implementation[END_REF]. Squeak is based on a virtual machine that interprets bytecodes. During a normal compilation phase, method source code is scanned and parsed, an abstract syntax tree (AST) is created and bytecodes are generated for the corresponding methods (Figure 3).

Code Generator

Scanner/ Parser source text bytecode AST Fig. 3. The standard Smalltalk to bytecode compiler.

To implement ByteSurgeon in Squeak we could have directly work on bytecode. However, rewriting bytecode is tedious and error-prone for several reasons: the bytecode vocabulary is low-level, jumps have to be calculated by hand, the expression of the context where bytecodes should be inserted is limited. Even simple modifications are surprisingly tedious to manage. Fortunately, a new compiler for Squeak, the closure compiler, has been recently proposed which offers a better intermediate bytecode representation.

The Closure Compiler and its Intermediate Representation

The closure compiler [START_REF] Hannan | Squeak Closure Compiler[END_REF] relies on a more complex bytecode generation step (Figure 4): first an Intermediate Representation (IR) is created; then the IR is used to generate the real bytecode (the raw numbers). The IR is a high-level representation of bytecode, abstracting away specific details: jumps are encoded in a graph structure, sequences of bytecode-nodes form a basic block, and jump-bytecodes concatenate these blocks to encode control flow. The main goal of IR is to abstract from specific bytecode encodings: for instance, although the bytecode for a program in Squeak is encoded differently than in VisualWorks, their IR is identical. Using IR therefore makes the porting to other bytecode sets simple.

The closure compiler has a counterpart, the decompiler, which converts bytecode back to text. Here, the whole process works backwards: from bytecode to IR, from IR to AST, and finally from AST to text.

As motivated in Section 2.2, ByteSurgeon ought to offer adequate abstractions for both bytecode-level and source-level transformations. The IR of the closure compiler actually represents an excellent alternative for working at the bytecode level: it makes it possible to express code that is not directly obtainable from Smalltalk source code, while abstracting away many details.

All classes reifying instructions (recall Figure 1) are from the closure compiler IR. The low-level transformation API of ByteSurgeon is based on these classes. In addition to the classes reifying instructions which correspond to language operations, the IR includes classes reifying bytecode-only instructions: IRPop, IRDup, IRJump, IRReturn, etc.

Low-level Transformation API

In Section 3, we have used the high-level API of ByteSurgeon to specify transformations giving a string of source code, which may contain metavariables to access dynamic information. The description of the new code to be inlined can also be done by directly editing the instruction objects for the IR hierarchy. In the following example, the selector of all sends of the message oldMessage:with: are replaced by sends of the message newMessage:with:, by using the selector: accessor of an IRSend object: The IRInstruction class can also be used as a factory to produce new objects describing bytecode. These objects can be used in replacement of the original instruction or be inlined before or after it. An alternative implementation of the code above is: This implementation replaces the message send bytecode by a new one having a different selector. IRInstruction send: #newMessage:with: returns an object that describes a message send bytecode.

(Example>>#
(Example>>#
Specifying the transformation at the bytecode-level makes it possible to express constructs that are impossible at the level of the Smalltalk language, and to easily specify transformations that are more complex to express with the source-level API. For instance, using the source-level API to change the selector of a message send, as done above, is done as follows:

(Example>>#aMeth) instrumentSend: [ :send | send selector = #oldMessage:with: ifTrue: [ send replace: '<meta: #receiver> perform: #newMessage:with: with: <meta: #arguments> ' ] ].

Apart from being slightly more verbose and relying on the use of the reflective message sending perform:with:, this approach requires the use of metavariables, which are more costly due to the associated preambles that needs to be generated (as shown in Section 4.4). Conversely, the low-level API makes it possible to do this transformation directly, without requiring runtime reification.

Implementation of Metavariables

When ByteSurgeon instruments a method, the bytecode-to-IR part of the closure compiler generates the IR objects that are passed to the instrumentation block specified by the user. If the source-level API is used, then the code to be inserted is preprocessed to generate the IR nodes and to handle the metavariables, if any. For metavariables, a preamble code is generated to ensure that the expected values will be on the stack. Then, the preamble and code are inserted into the IR of the method. Finally, the IR-to-bytecode part of the closure compiler generates raw bytecodes and replaces the old method with the new, transformed version.

In the following we explain the implementation of metavariables which reify runtime information. Let us consider the reification of the receiver of a message send.

Preambles. Squeak uses a stack-based bytecode, so all parameters for a message send are pushed on the stack before the send bytecode is executed: first the receiver, and then the arguments. For instance, the bytecode for the expression 3 + 4 is as follows:

77 pushConstant: 3 20 pushConstant: 4 B0 send: + 7C returnTop

Consider that we now want to provide access to the receiver (3) via a metavariable:

(Example>>#method) instrumentSend: [:send | send insertBefore: 'Transcript show: <meta: #receiver> asString'].

To support metavariables, we need to add bytecode to store the necessary values, by popping them from the stack and storing them in additional temporary variables. In our example, we need the receiver. Since the receiver is deep in the stack, below the arguments, we also need to store the arguments in temporary variables, to be able to access them afterwards. In the case of before/after, it is also necessary to rebuild the stack. The resulting bytecode for our example is as follows:

22 pushConstant: 3 23 pushConstant: 4 68 popIntoTemp: 0 "put argument in temp 0" 69 popIntoTemp: 1 "put receiver in temp 1" 24 pushLit: ##Transcript "start of inserted code" 11 pushTemp: 1 "push receiver for printing" D5 send: asString E6 send: show: 87 pop "end of inserted code" 11 pushTemp: 1 "rebuild the stack" 10 pushTemp: 0 B0 send: + "original code" 7C returnTop

To access all arguments as an array, the compiler generates code to create the array instance, to add arguments to it, and to store the array in a temporary variable.

For performance and space reasons, preamble generation needs to be optimized. First, the compiler only generates code for the metavariables that are effectively used in the inlined code. For instance, if access to the arguments is not needed, then the array creation is avoided. The second important optimization is to reuse temporary variables. Indeed, there are potentially many operations for which we need to generate a preamble, in a single method. If we used new temporary variables for each, we would soon run out of temporary variables (Squeak imposes a limit of 256 temporary variables per method). Therefore, ByteSurgeon remembers the original number of temporary variables and reuses the variables added for each preamble. This information is saved inside the compiled method object, so that reuse of variables works even if instrument: is executed several times on the same method.

Inlining code. Once the preamble is added, the code to inline can be inserted. First, the ByteSurgeon compiler generates the IR for the new code. For metavariables, the compiler generates code that loads the corresponding temporary variables. The generated IR instructions are then added to the original IR of the method. If necessary, jump targets are adjusted and basic blocks renumbered. The new method IR is then given to the closure compiler, which generates the final raw bytecodes and installs the new method.

Validation

We now validate the interest of ByteSurgeon by showing how easy it is to implement two language extensions: method wrappers [10] and a simple runtime MOP for controlling accesses to instance variables. Section 5.3 completes this validation by reporting on performance measurements.

Method Wrappers

Method wrappers [START_REF] Brant | Wrappers to the Rescue[END_REF] wrap a method with before/after behavior. Wrapping a method is implemented by swapping out the compiled method by another one, valueWithReceiver:arguments: that calls the before method, then the original method, and finally the after method5 : MethodWrapper>>valueWithReceiver: anObject arguments: args self beforeMethod.

ˆ[clientMethod valueWithReceiver: anObject arguments: args] ensure: [self afterMethod]

The BSMethodWrapper class contains the logic to install an instance of itself as a method wrapper, with empty before/after methods.

To define a wrapper, a subclass should be created, specifying the before/after methods. For instance, class CountingMethodWrapper wraps a method to count invocation of calls to a given method:

BSMethodWrapper subclass: #CountingMethodWrapper instanceVariableNames: 'count'...

CountingMethodWrapper >>beforeMethod self count: self count + 1

To count the invocations on a method, we install the wrapper:

wrapper := CountingMethodWrapper on: #aMethod inClass: Example. wrapper install.

The installation of a method wrapper consists in first decompiling the before/after methods to IR (ir), stripping the return at the end (strip), then replacing all self references to refer to the wrapper (replaceSelf:), and finally inlining the before/after methods (insertBefore:after:): As we can see, method wrappers are straightforward to implement with Byte-Surgeon. The complete implementation included in the distribution consists of 41 lines of code, with comments. This implementation of method wrapper should only serve as an example of use of ByteSurgeon, it is not meant to be a replacement yet since not all features of method wrappers are supported. Furthermore, as illustrated in Section 5.3, standard method wrappers and ByteSurgeon method wrappers have different performance profiles.

BSMethodWrapper>>inlineBeforeAfter | before

A Small Runtime MOP

We now show how to implement a small runtime MOP for controlling accesses to instance variables. A metaobject can be associated to a class, and upon accesses to instance variables of objects from the class, it gets control via either its instVarRead:in: method (if it is a read access) or its instVarWrite:in:value: method (if it is a write access). For instance, the following The dict dictionary is used to hold the reference to the metaobject controlling accesses, and for each access instruction, the name of the variable is put in it. This makes it possible to use user-defined variables when specifying the transformation.

Furthermore, since ByteSurgeon supports runtime bytecode manipulation, we are able to completely uninstall hooks when needed: MOP uninstall: MOExample.

Of course, this simple MOP is not complete: if methods are changed (recompiled), the MOP is removed, there is no way to compose multiple metaobjects on the same class, it is not possible to associate different metaobjects to different instances, etc. But the basic features are there: a MOP for instance variable accesses that can be installed and retracted at runtime -and completely implemented in less than 10 lines-.

Benchmarks

We now report on several preliminary benchmarks 6 we have performed to evaluate the efficiency of ByteSurgeon. First, we report on transformation vs. compilation costs, and then study the performance of the standard implementation of method wrappers with that based on ByteSurgeon.

Transformation performance. One of the reasons for editing bytecode instead of source is performance. To verify this claim, we have carried out a simple set of benchmarks, in which we compare the time to compile some code with both the standard compiler of Squeak and the new compiler (closure compiler), and the time taken by ByteSurgeon to transform all instructions in the code with an empty block. Hence what we actually measure for Byte-Surgeon is the time it takes to decompile methods to IR, execute the block for each instruction (which does nothing), generate a new identical method and install it. The results of both benchmarks are presented in Figure 5. As expected, Byte-Surgeon performs very well. The highly optimized standard compiler is approximately twice slower than ByteSurgeon, while the new compiler, which is much easier to reuse and extend but less optimized, is around 6 times slower.

Method wrapper performance. We now compare the performance of the standard implementation of method wrappers with that based on Byte-Surgeon. We compare both installation (transformation) time and execution time.

The test consists of a simple before/after counter manipulation wrapping a straightforward method:

Bench>>run beforeMethod afterMethod ˆ3+4.

BCounter inc BCounter inc

The benchmark of the installation/uninstallation is run as follows:

[1000 timesRepeat: [ w := TestMethodWrapper on: #run inClass: Bench. w install.

w uninstall]] timeToRun

The runtime performance of both implementations is compared to that of method that directly implements the wrapper:

Bench>>run | t | BCounter inc. t := 3+4. BCounter inc. ˆt.
To be fair in our evaluation, we changed the execution semantics of standard method wrappers, so that they do not wrap the after in an exception handler, but rather inline both before and after methods. The benchmark for both cases is run as follows:

[1000000 timesRepeat: [Bench new run]] timeToRun

The results of the benchmarks (Figure 6) show that ByteSurgeon is slower for installing wrappers. This was expected because method wrappers actually simply swap the wrapped compiled method with the wrapper one, while ByteSurgeon actually modifies the original method. The other side of the coin is that ByteSurgeon-based method wrappers are much more efficient at runtime. Standard method wrappers are 3.5 times slower than the handcoded version, while the ByteSurgeon implementation is as fast as the hand-coded version. The slight enhancement that can be observed comes from the fact that, in the considered case, ByteSurgeon does not need to use a temporary variable to store the return value, it just uses the stack.

Conclusion and Future Work

We have presented ByteSurgeon, an efficient library for runtime bytecode manipulation in Smalltalk, implemented in Squeak. We have shown:

• APIs for specifying transformations that allow users to control the tradeoff between expressiveness and performance for the code to be inlined: Byte-Surgeon users can either specify Smalltalk code with metavariables or specify the code at the bytecode level. • the expressiveness of ByteSurgeon by showing how well-known language extensions are concisely expressed, and reported on preliminary benchmarks validating our efficiency claim. • the runtime capabilities of ByteSurgeon with a simple MOP that can be dynamically installed and retracted. Such runtime changes are not feasible in a static system like Java without changing the virtual machine.

Future work can be dividing in two directions: the first is to continue improving ByteSurgeon as such, and the second consists in using ByteSurgeon in a number of projects that will directly benefit from its features. Of course, both tracks mutually benefit from each other.

Regarding ByteSurgeon itself, there is a number of features that are being discussed at this time. In particular, ByteSurgeon should be extended with support for exception handling. It is also appealing to offer a kind of proceed instruction to trigger the execution of a replaced operation occurrence from inside the metacomputation. Another direction to explore is that of the abstraction layer used to describe a method. As of now we use a bytecode representation, but it would be interesting to explore the direct use of abstract syntax trees at this level. The choice between AST and bytecode presents a tradeoff between performance and expressiveness: decompiling to AST and code-generation will be slower than using the the bytecode-level abstractions of the IR, but in turn we gain a lot in expressiveness and ease of use, since AST is more structured than IR. We plan to explore these tradeoffs in the future.

As regards applications of ByteSurgeon in other projects, the perspectives are manifold. We plan to use ByteSurgeon for code annotation to collect runtime traces of program execution to support omniscient debugging [START_REF] Lewis | Debugging backwards in time[END_REF]. Reflex is a system based on bytecode transformation providing partial behavioral reflection in Java [START_REF] Tanter | Partial behavioral reflection: Spatial and temporal selection of reification[END_REF]. It has recently evolved to a versatile kernel for multi-language AOP [START_REF] Tanter | A versatile kernel for multi-language AOP[END_REF], easing the implementation of (domain-specific) aspect languages and providing support for the detection and resolution of aspect interactions. The on-going Geppetto project aims at exploring the possibilities offered by an implementation of Reflex in Squeak, using ByteSurgeon, enjoying the flexibility of true runtime code transformation.

Fig. 1 .

 1 Fig. 1. Structural model of instructions in ByteSurgeon.

  aMethod) instrumentSend: [ :send | send insertAfter: 'Logger logSend:' , send selector printString]

  Example instrumentMethods:[ :m | m insertAfter: 'Logger logExec: <: #sel> result: <meta: #result>' using:{ #sel -> m selector } ]4 Inside ByteSurgeon

Fig. 4 .

 4 Fig. 4. The closure compiler.

  aMeth) instrumentSend: [ :send | send selector = #oldMessage:with: ifTrue: [ send selector: #newMessage:with: ] ].

  aMeth) instrumentSend: [ :send | send selector = #oldMessage:with: ifTrue: [ send replace: (IRInstruction send: #newMessage:with:)] ].

  The first benchmark is applied to the Object class:"Test compilers" [Object compileAll] timeToRun "Test ByteSurgeon" [Object instrument: [:inst | self ]] timeToRunClass Object contains 429 methods, amounting to 2344 lines of code. We did the same experiment on a larger code base: the whole hierarchy of collection classes. This hierarchy consists of 76 classes, 2231 methods, summing up to 15783 lines of code. The benchmark is run as: "Test compilers" [Collection allSubclasses do: [ :c | c compileAll ]] timeToRun "Test ByteSurgeon" [Collection allSubclasses do: [ :c | c instrument: [ :inst | self ]]] timeToRun

Fig. 5 .

 5 Fig. 5. Comparing compilation and transformation times.

  TraceMO simply outputs what is happening to the transcript and then performs the standard action, i.e., returning the instance variable value, or storing the new value:This metaobject can be installed on class Point as follows:MOP install: TraceMO new on: PointThe MOP>>install method uses ByteSurgeon to replace the bytecodes that read or store instance variables with calls to the metaobject (aka. hooks):

	Transcript show: 'var store: ', newVal printString; cr.
	ˆobject instVarNamed: name put: newVal.
	MOP class >>install: mop on: aClass
	| dict |
	dict := Dictionary newFrom: #mo -> mop.
	aClass instrumentInstVarAccess: [:instr |
	dict at: #name put: instr varname.
	instr isRead
	ifTrue: [instr replace: '<: #mo> instVarRead: <: #name> in: self'
	using: dict]
	ifFalse: [instr replace: '<: #mo> instVarStore: <: #name> in: self
	value: <meta: #newvalue>'
	using: dict] ].
	TraceMO>>instVarRead: name in: object
	| val |
	val := object instVarNamed: name.
	Transcript show: 'var read: ', val printString; cr.
	ˆval.
	TraceMO>>instVarStore: name in: object value: newVal

Actually, ByteSurgeon could profitably use AOStA for its backend, but this study is left as future work.

The isXXX methods (e.g., isSend) are provided as a convenience to avoid the use of visitors and double dispatch.

self, super and thisContext have their usual meaning, knowing that this code will be evaluated in the place where it is inserted.

This is a limited sort of quasi-quoting a la Scheme; supporting true quasi-quoting (with no needs to specify manually the associations) is left as future work.

At the time of this writing, ByteSurgeon does not yet support exception handlers, so we actually implemented a simplified version where the after method is just inlined at the end of the method.

Machine used: Apple PowerBook 1.5Ghz, Squeak 3.8

Acknowledgements. We thank David Röthlisberger and the anonymous reviewers for their comments.


Bruno Bouchard Ceremade

Ngoc Minh Dang
email: dang@ceremade.dauphine.fr

Optimal Control versus Stochastic Target problems: An Equivalence Result

Keywords: Stochastic target, stochastic control, viscosity solutions. Mathematical subject classifications: Primary 49-00; secondary 49L25

, whenever the underlying filtered probability space admits a suitable martingale representation property. This provides a unified way of treating these two classes of stochastic control problems. As an illustration, we show, within a jump diffusion framework, how the Hamilton-Jacobi-Bellman equations associated to an optimal control problem in standard form can be easily retrieved from the partial differential equations associated to its stochastic target counterpart.

Introduction

In their simplest form, stochastic target problems can be formulated as follows. Given a controlled process Z ν t,x,y = (X ν t,x , Y ν t,x,y ), associated to the initial condition Z ν t,x,y (t) = (x, y) ∈ R d ×R at time t, find the set S(t) of initial conditions (x, y) such that Ψ(X ν t,x (T ), Y ν t,x,y (T )) ≥ 0 Pa.s. for some control ν ∈ U, where Ψ is a given real valued Borel measurable map and U is a prescribed set of controls. When y → Y ν t,x,y (T ) and y → Ψ(•, y) are non-decreasing, for all ν ∈ U, then the set S(t) can be identified to {(x, y) ∈ R d × R : y ≥ v(t, x)} where v(t, x) := inf{y ∈ R : ∃ ν ∈ U s.t. Ψ(Z ν t,x,y (T )) ≥ 0 Pa.s.}, whenever the above infimum is achieved. Such problems can be viewed as a natural generalization of the so-called super-hedging problem in mathematical finance. In this case, Y ν t,x,y is interpreted as the wealth process associated to a given investment policy ν, X ν t,x as stock prices or factors (that can possibly be influenced by the trading strategy) and Ψ takes the form Ψ(x, y) = yg(x) where g is viewed as the payoff function of an European option. Then, Ψ(X ν t,x (T ), Y ν t,x,y (T )) ≥ 0 means Y ν t,x,y (T ) ≥ g(X ν t,x (T )), i.e. the value of the hedging portfolio is greater at time T than the payoff g(X ν t,x (T )) of the European claim. The value function v(t, x) then coincides with the super-hedging price of the option, see e.g. [START_REF] Karatzas | Methods of Mathematical Finance[END_REF] for references on mathematical finance. Motivated by the study of super-hedging problems under Gamma constraints, Soner and Touzi [START_REF] Soner | Super-replication under Gamma constraint[END_REF] were the first to propose a direct treatment of a particular class of stochastic target problems. It relies on a Geometric Dynamic Programming Principle (GDP) which essentially asserts that

S(t) = {(x, y) ∈ R d × R : ∃ ν ∈ U s.t. Z ν t,
x,y (θ) ∈ S(θ) a.s.} for all [t, T ]-valued stopping time θ. The main observation of Soner and Touzi is that it actually allows one to provide a direct characterization of the associated value function v as a viscosity solution of a non-linear parabolic partial differential equation. This approach was further exploited in [START_REF] Bouchard | Explicit solution of the multivariate super-replication problem under transaction costs[END_REF] and [START_REF] Touzi | Direct characterization of the value of super-replication under stochastic volatility and portfolio constraints[END_REF], in the context of super-hedging problems in mathematical finance. A general version of the GDP was then proved in [START_REF] Soner | Dynamic programming for stochastic target problems and geometric flows[END_REF], where the authors also used this methodology to provide a new probabilistic representation of a class of geometric flows. The link with PDEs in a general Markovian framework for Brownian diffusion processes was established in [START_REF] Soner | Stochastic target problems, dynamic programming and viscosity solutions[END_REF], and extended to jump diffusion processes in [START_REF] Bouchard | Stochastic Target with Mixed diffusion processes[END_REF] whose main motivation was to apply this approach to provision management in insurance. Finally, an extension to path dependent constraints was proposed in [START_REF] Bouchard | The American version of the geometric dynamic programming principle, Application to the pricing of american options under constraints[END_REF]. This approach turned out to be very powerful to study a large family of non-standard stochastic control problems in which a target has to be reached with probability one at a given time horizon T . However, it was limited to this case, up to the paper [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] who showed how the a.s. constraint Ψ(Z ν t,x,y (T )) ≥ 0 can indeed be relaxed in moment constraints of the form E Ψ(Z ν t,x,y (T )) ≥ p, where the real number p is a given threshold, typically non-positive. This relaxed version was called stochastic target problem with controlled loss in [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF]. The result of [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] (extended by [START_REF] Moreau | Stochastic Target Problems with Controlled Loss in jump diffusion models[END_REF] to jump diffusion processes) opened the door to a wide range of new applications. In particular in mathematical finance, in which a P-a.s. constraint would typically lead to degenerate results, i.e. v ≡ ∞ or v much too large in comparison to what can be observed in practice, while the above relaxation provides meaningful results. A good illustration of such a situation in given in [START_REF] Bouchard | Generalized stochastic target problems for pricing and partial hedging under loss constraints -Application in optimal book liquidation[END_REF] which discusses the pricing of financial book liquidation contracts. See also the forthcoming paper [START_REF] Bouchard | A PDE formulation for P&L Matching Problems[END_REF] on the problem of P&L matching in option hedging or optimal investment problems.

In view of all the potential practical applications of the technology originally proposed by Soner and Touzi in [START_REF] Soner | Super-replication under Gamma constraint[END_REF], and given the fact that the theory is now well-established, it seems natural to consider this recently developed class of (non-standard) stochastic control problems as a part of the general well-known tool box in optimal control. However, it seems a-priori that stochastic target problems and optimal control problems in standard form (i.e. expected cost minimization problems) have to be discussed separately as they rely on different dynamic programming principles. This short note can be viewed as a teacher's note that explains why they can actually be treated in a unified framework. More precisely: any optimal control problem in standard form admits a (simple and natural) representation in terms of a stochastic target problem. In the following, we first discuss this equivalence result in a rather general abstract framework. In the next section, we show through a simple example how the Hamilton-Jacobi-Bellman equations of an optimal control problem in standard form can be easily recovered from the PDEs associated to the corresponding stochastic target problem. We will not provide in this short note the proof of the PDE characterization for stochastic target problems. We refer to [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] and [START_REF] Moreau | Stochastic Target Problems with Controlled Loss in jump diffusion models[END_REF] for the complete arguments.

Notations: We denote by x i the i-th component of a vector x ∈ R d , which will always be viewed as a column vector, with transposed vector x ⊤ , and Euclidean norm |x|. The set M d is the collection of d-dimensional square matrices A with coordinates A ij , and norm |A| defined by viewing A as an element of R d×d . Given a smooth function ϕ : (t, x) ∈ R + × R d → R, we denote by ∂ t ϕ its derivative with respect to its first variable, we write Dϕ and D 2 ϕ for the Jacobian and Hessian matrix with respect to x. The set of continuous function C 0 (B) on a Borel subset B ⊂ R + × R d is endowed with the topology of uniform convergence on compact sets. Any inequality or inclusion involving random variables has to be taken in the a.s. sense.

The equivalence result

Let T be a finite time horizon, given a general probability space (Ω, F, P) endowed with a filtration F = {F t } t≤T satisfying the usual conditions. We assume that F 0 is trivial.

Let us consider an optimal control problem defined as follows. First, given a set U of deterministic functions from R + to R κ , κ ≥ 1, we define

Ũ = {ν : F-predictable process s.t. t -→ ν(t, ω) ∈ U for P-almost every ω ∈ Ω} .
The controlled terminal cost is a map

ν ∈ Ũ -→ G ν ∈ L 0 (Ω, F T , P) .
Without loss of generality, we can restrict to a subset of controls U ⊂ Ũ such that

U ⊂ ν ∈ Ũ : G ν ∈ L 1 (Ω, F T , P) .
Given (t, ν) ∈ [0, T ] × U, we can then define the conditional optimal expected cost:

V ν t := ess inf µ∈U (t,ν) E [G µ | F t ] , (2.1)
where U(t, ν) := {µ ∈ U : µ = ν on [0, t] Pa.s.} .

Our main observation is that the optimal control problem (2.1) can be interpreted as a stochastic target problem involving an additional controlled process chosen in a suitable family of martingales. Moreover, existence in one problem is equivalent to existence in the other.

Lemma 2.1. [Stochastic target representation] Let M be a any family of martingales such that

G := {G ν , ν ∈ U} ⊂ {M T , M ∈ M} . (2.2)
Then, for each (t, ν) ∈ [0, T ] × U:

V ν t = Y ν t , (2.3)
where

Y ν t := essinf Y ∈ L 1 (Ω, F t , P) ∃(M, µ) ∈ M × U(t, ν) s.t. Y + M T -M t ≥ G µ . (2.4)
Moreover, there exists μ ∈ U(t, ν) such that

V ν t = E G μ | F t (2.5)
if and only if there exists ( M , μ) ∈ M × U(t, ν) such that

Y ν t + MT -Mt ≥ G μ . (2.6)
In this case, one can choose μ = μ, and M satisfies

Y ν t + MT -Mt = G μ . (2.7)
Let us make some remarks before to provide the short proof.

Remark 2.2. It is clear that a family M satisfying (2.2) always exists. In particular, one can take

M = M := {(E [G ν | F t ]) t≥0 , ν ∈ U}.
When the filtration is generated by a ddimensional Brownian motion W , then the martingale representation theorem allows one to rewrite any element M of M in the form M = P α 0,M 0 := M 0 +

• 0 α ⊤ s dW s where α belongs to A loc , the set of R d -valued locally square integrable predictable processes such that P α 0,0 is a martingale. This allows choosing M as {P α 0,p , (p, α) ∈ R × A loc }. When G ⊂ L 2 (Ω, F T , P), then we can replace A loc by the set A of R d -valued square integrable predictable processes. A similar reduction can be obtained when the filtration is generated by Lévy processes. We shall see below in Section 3 that such classes of families M allow us to convert a Markovian optimal control problem in standard form into a Markovian stochastic target problem for which a PDE characterization can be derived. A similar idea was already used in [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] to convert stochastic target problems under controlled loss, i.e. with a constraint in expectation, into regular stochastic target problems, i.e. associated to a Pa.s.-constraint, see their Section 3.

Remark 2.3. A similar representation result was obtained in [START_REF] Bouchard | A stochastic target formulation for optimal switching problems in finite horizon[END_REF] where it is shown that a certain class of optimal switching problems can be translated into stochastic target problems for jump diffusion processes. In this paper, the author also introduces an additional controlled martingale part but the identification of the two control problems is made through their associated PDEs (and a suitable comparison theorem) and not by pure probabilistic arguments. Moreover, an additional randomization of the switching policy is introduced in order to remove this initial control process.

Remark 2.4. It is well-known that, under mild assumptions (see [START_REF] Karoui | Les aspects probabilistes du contrôle stochastique[END_REF]), the map t ∈ [0, T ] → V ν t can be aggregated by a càdlàd process V ν which is a submartingale for each ν ∈ U, and that a control μ is optimal for (2.1) if and only if V μ is a martingale on [t, T ]. This is indeed a consequence of the dynamic programming principle which can be (at least formally) stated as

V ν t = essinf{E V µ θ | F t ,
ν t ≥ V ν t , fix Y ∈ L 1 (Ω, F t , P) and (M, µ) ∈ M × U(t, ν) such that Y + M T -M t ≥ G µ .
Then, by taking the conditional expectation on both sides, we obtain

Y ≥ E [G µ | F t ] ≥ essinf{E G µ ′ | F t , µ ′ ∈ U(t, ν)} = V ν t , which implies that Y ν t ≥ V ν t .
On the other hand, (2.2) implies that, for each µ ∈ U(t, ν), there exists

M µ ∈ M such that G µ = E [G µ | F t ] + M µ T -M µ t . In particular, E [G µ | F t ] + M µ T -M µ t ≥ G µ . This shows that E [G µ | F t ] ≥ Y ν
t for all µ ∈ U(t, ν), and therefore

V ν t ≥ Y ν t . b. We now assume that μ ∈ U(t, ν) is such that (2.5) holds. Since V ν t = Y ν t , this leads to Y ν t = E G μ | F t . Moreover, (2.2) implies that there exists M ∈ M such that E G μ | F t + MT -Mt = G μ.
Hence, (2.6) and (2.7) hold with μ = μ. Conversely, if ( M , μ) ∈ M × U(t, ν) is such that (2.6) holds, then the identity (2.3) implies that

V ν t = Y ν t ≥ E [G μ | F t ] ≥ V ν t .
Hence, (2.5) holds with μ = μ. ✷

Example

In this section, we show how the Hamilton-Jacobi-Bellman equations associated to an optimal control problem in standard form can be deduced from its stochastic target formulation. We restrict to a classical case where the filtration is generated by a d-dimensional Brownian motion W and a E-marked integer-valued right-continuous point process N (de, dt) with predictable (P, F)-intensity kernel m(de)dt such that m(E) < ∞ and supp(m) = E, where supp denotes the support and E is a Borel subset of R d with Borel tribe E. We denote by Ñ (de, dt) = N (de, dt)m(de)dt the associated compensated random measure, see e.g. [START_REF] Brémaud | Point Processes and Queues -Martingale Dynamics[END_REF] for details on random jump measures. The set of controls U is now defined as the collection of square integrable predictable K-valued processes, for some K ⊂ R d . Given ν ∈ U and (t, x) ∈ [0, T ]×R d , we define X ν t,x as the unique strong solution on [t, T ] of

X ν = x + • t µ(X ν (r), ν r )dr + • t σ(X ν (r), ν r )dW r + • t E
β(X ν (r-), ν r , e)N (de, dr) ,(

where (µ, σ, β)

: (x, u, e) ∈ R d × K × E -→ R d × M d × R d
are measurable and are assumed to be such that there exists L > 0 for which

|µ(x, u) -µ(x ′ , u)| + |σ(x, u) -σ(x ′ , u)| + E |β(x, u, e) -β(x ′ , u, e)| 2 m(de) 1 2 ≤ L|x -x ′ | |µ(x, u)| + |σ(x, u)| + ess sup e ′ ∈E |β(x, u, e ′ )| ≤ L(1 + |x| + |u|), (3.2)
for all x, x ′ ∈ R d and u ∈ K.

Given a continuous map g with linear growth (for sake of simplicity), we then define the optimal control problem in standard form:

v(t, x) := inf ν∈U E g X ν t,x (T ) .
Remark 3.1. Contrary to the above section, we do not fix here the path of the control ν on [0, t]. This is due to the fact that X ν t,x depends on ν only on (t, T ], since the probability of having a jump a time t is equal to 0. Moreover, we can always reduce in the above definition to controls ν in U that are independent of F t , see Remark 5.2 in [START_REF] Bouchard | Weak Dynamic Programming Principle for Viscosity Solutions[END_REF].

Then, it follows from standard arguments, see [START_REF] Fleming | Controlled Markov Processes and Viscosity Solutions[END_REF] or [START_REF] Yong | Stochastic Controls: Hamiltonian Systems and HJB Equations[END_REF] and the recent paper [START_REF] Bouchard | Weak Dynamic Programming Principle for Viscosity Solutions[END_REF], that the lower-semicontinuous envelope v * and the upper-semicontinuous envelope v * of v defined as v * (t, x) := lim inf

(t ′ ,x ′ )→(t,x),t ′ <T v(t ′ , x ′ ) and v * (t, x) := lim sup (t ′ ,x ′ )→(t,x),t ′ <T v(t ′ , x ′ ) , (t, x) ∈ [0, T ] × R d satisfy:
Theorem 3.2. Assume that v is locally bounded. Then, v * is a viscosity supersolution of

-∂ t ϕ + H * (•, Dϕ, D 2 ϕ, ϕ) = 0 on [0, T ) × R d (ϕ -g)1 H * (•,Dϕ,D 2 ϕ,ϕ)<∞ (T, •) = 0 on R d , (3.3)
where H * is the upper-semicontinuous envelope of the lower-semicontinuous map

H : [0, T ] × R d × R d × M d × C 0 ([0, T ] × R d ) → R (t, x, q, A, f ) → sup u∈K -I[f ](t, x, u) -µ(x, u) ⊤ q - 1 2 Tr[σσ ⊤ (x, u)A] ,
with

I[f ](t, x, u) := E (f (t, x + β(x, u, e)) -f (t, x)) m(de) .
Moreover, v * is a viscosity subsolution of

-∂ t ϕ + H(•, Dϕ, D 2 ϕ, ϕ) = 0 on [0, T ) × R d (ϕ -g)(T, •) = 0 on R d . (3.4)
On the other hand, it follows from (3.2) and the linear growth condition on g that g X ν t,x (T ) ∈ L 2 (Ω, F T , P) for all ν ∈ U. The martingale representation theorem then implies that (2.2) holds for the family of martingales M defined as

M := R + • 0 α ⊤ s dW s + • 0 E γ s (e) Ñ (de, ds), (α, γ) ∈ A × Γ
where A denotes the set of square integrable R d -valued predictable processes, and Γ is the

set of P ⊗ E measurable maps γ : Ω × [0, T ] × E → R such that E T 0 E |γ s (e)| 2 m(de)ds < ∞ ,
with P defined as the σ-algebra of F-predictable subsets of Ω × [0, T ]. Hence, we deduce from Lemma 2.1 that

v(t, x) = inf p ∈ R : ∃(ν, α, γ) ∈ U × A × Γ s.t. P α,γ t,p (T ) ≥ g X ν t,x (T ) , where P α,γ t,p := p + • t α ⊤ s dW s + • t E
γ s (e) Ñ (de, ds) .

We therefore retrieve a stochastic target problem in the form studied in [START_REF] Moreau | Stochastic Target Problems with Controlled Loss in jump diffusion models[END_REF].

If v is locally bounded, we can then apply the main result of [START_REF] Moreau | Stochastic Target Problems with Controlled Loss in jump diffusion models[END_REF] (see [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF] for the case of Brownian diffusion models) to deduce that v * is a viscosity supersolution of

-∂ t ϕ + F * 0,0 (•, Dϕ, D 2 ϕ, ϕ) = 0 on [0, T ) × R d (ϕ -g)1 F * 0,0 (•,Dϕ,D 2 ϕ,ϕ)<∞ (T, •) = 0 on R d , (3.5)
where F * is the upper-semicontinuous envelope of the map F defined for (ε, η, t, x, q, A, f ) ∈

[0, 1] × [-1, 1] × [0, T ] × R d × R d × M d × C 0 ([0, T ] × R d ) by F ε,η (t, x, q, A, f ) := sup (u,a,b)∈Nε,η(t,x,q,f ) - E b(e)m(de) -µ(x, u) ⊤ q - 1 2 Tr[σσ ⊤ (x, u)A] ,
with N ε,η (t, x, q, f ) defined as the set of elements (u, a, b)

∈ K × R d × L 2 (E, E, m) such that |a -σ(x, u) ⊤ q| ≤ ε and b(e) -f (t, x + β(x, u, e)) + f (t, x) ≥ η for m-a.e e ∈ E .
Similarly, Theorem 2.1 in [START_REF] Moreau | Stochastic Target Problems with Controlled Loss in jump diffusion models[END_REF] states that v * is a viscosity subsolution of

-∂ t ϕ + F 0,0 * (•, Dϕ, D 2 ϕ, ϕ) = 0 on [0, T ) × R d (ϕ -g)(T, •) = 0 on R d , (3.6)
where F * is the lower-semicontinuous envelope of F .

To retrieve the result of Theorem 3.2, it suffices to show the following.

Proposition 3.3. F * 0,0 ≤ H * and F 0,0 * ≥ H.

Proof. First note that u ∈ K implies that (u, σ(x, u) ⊤ q, f (t, x + β(x, u, •))f (t, x) + η) ∈ N 0,η (t, x, q, f ). This implies that F 0,η ≥ H. Since ε ≥ 0 → F ε,• is non-decreasing, it follows that F 0,0 * ≥ H. On the other hand, fix (t, x) ∈ [0, T )×R d and (q, A, f ) ∈ R d ×M d ×C 0 ([0, T ]× R d ), and consider a sequence (ε n , η n , t n , x n , q n , A n , f n ) n that converges to (0, 0, t, x, q, A, f ) such that lim n→∞ F εn,ηn (t n , x n , q n , A n , f n ) = F * 0,0 (t, x, q, A, f ) .

Then, by definition of N εn,ηn (t n , x n , q n , f n ), we have ≤ H * (t, x, q, A, f ) .

F * 0,

✷

Remark 3.4. It is clear that the same ideas apply to various classes of optimal control problems: singular control, optimal stopping, impulse control, problem involving state constraints, etc. We refer to [START_REF] Bouchard | Generalized stochastic target problems for pricing and partial hedging under loss constraints -Application in optimal book liquidation[END_REF] and [START_REF] Bouchard | The American version of the geometric dynamic programming principle, Application to the pricing of american options under constraints[END_REF] for the study of stochastic target problems with controls including bounded variation processes or stopping times. The case of state constraints is discussed in [START_REF] Bouchard | The American version of the geometric dynamic programming principle, Application to the pricing of american options under constraints[END_REF], see also [START_REF] Bouchard | Optimal Control under Stochastic Target Constraints[END_REF].

  It is clear from the proof below that the additional controlled process (Y ν t + Ms -Mt ) s≥t whose T -value appears in (2.7) then coincides with this martingale.Proof of Lemma 2.1 a. We first prove (2.3). To see that Y

µ ∈ U(t, ν)} for all stopping time θ with values in [t, T ].

  0 (t, x, q, A, f ) = lim n→∞ F εn,ηn (t n , x n , q n , A n , f n )

	≤ lim

n→∞ |η n |m(E) + sup u∈K -I[f n ](t n , x n , u)µ(x n , u) ⊤ q n -1 2 Tr[σσ ⊤ (x n , u)A n ]


R G Novikov
email: novikov@cmap.polytechnique.fr

Weighted Radon transforms for which the Chang approximate inversion formula is precise

We describe all weighted Radon transforms on the plane for which the Chang approximate inversion formula is precise. Some subsequent results, including the Cormack type inversion for these transforms, are also given.

1.Introduction

We consider the weighted ray transformation P W defined by the formula

P W f (s, θ) = R W (sθ ⊥ + tθ, θ)f (sθ ⊥ + tθ)dt, s ∈ R, θ = (θ 1 , θ 2 ) ∈ S 1 , θ ⊥ = (-θ 2 , θ 1 ), (1)
where W = W (x, θ) is the weight, f = f (x) is a test function, x ∈ R, θ ∈ S 1 . Up to change of variables, P W is known also as weighted Radon transform on the plane.

We recall that in definition (1) the product R×S 1 is interpreted as the set of all oriented straight lines in R 2 . If γ = (s, θ) ∈ R × S 1 , then γ = {x ∈ R 2 : x = sθ ⊥ + tθ, t ∈ R} (modulo orientation) and θ gives the orientation of γ.

We assume that

W is complex -valued, W ∈ C(R 2 × S 1 ) ∩ L ∞ (R 2 ∩ S 1 ), w 0 (x) def = 1 2π S 1 W (x, θ)dθ = 0, x ∈ R 2 , ( 2
)
where dθ is the standard element of arc length on S 1 . If W ≡ 1, then P W is known as the classical ray (or Radon) transform on the plane.

If W (x, θ) = exp(-Da(x, θ)), Da(x, θ) = +∞ 0 a(x + tθ)dt, ( 3
)
where a is a complex-valued sufficiently regular function on R 2 with sufficient decay at infinity, then P W is known as the attenuated ray (or Radon) transform. The classical Radon transform arises, in particular, in the X-ray transmission tomography. The attenuated Radon transform (at least, with a ≥ 0) arises, in particular, in the single photon emission computed tomography (SPECT). Some other weights W also arise in applications. For more information in this connection see, for example, [Na], [K].

Precise and simultaneously explicite inversion formulas for the classical and attenuated Radon transforms were given for the first time in [R] and [No], respectively. For some other weights W precise and simultaneously explicite inversion formulas were given in [BS], [G].

On the other hand, the following Chang approximate inversion formula for P W , where W is given by (3) with a ≥ 0, is used for a long time, see [Ch], [M], [K]:

f appr (x) = 1 4πw 0 (x) S 1 h ′ (xθ ⊥ , θ)dθ, h ′ (s, θ) = d ds h(s, θ), h(s, θ) = 1 π p.v. R P W f (t, θ) s -t dt, s ∈ R, θ ∈ S 1 , x ∈ R 2 , ( 4
)
where w 0 is defined in (2). It is known that ( 4) is efficient as the first approximation in SPECT reconstructions and, in particular, is sufficiently stable to the strong Poisson noise of SPECT data. The results of the present note consist of the following:

(1) In Theorem, under assumptions (2), we describe all weights W for which the Chang approximate inversion formula (4) is precise, that is f appr ≡ f on R 2 ; (2) For P W with W of Theorem we give also the Cormack type inversion (see Remark A)

and inversion from limited angle data (see Remark B). These results are presented in detail in the next section. In addition, we give also an explanation of efficiency of the Chang formula (4) as the first approximation in SPECT reconstructions (on the level of integral geometry).

Results

Let

C 0 (R 2 ) denote the space of continuous compactly supported functions on R 2 .

(5)

Let L ∞,σ (R 2 ) = {f : M σ f ∈ L ∞ (R 2 )}, M σ f (x) = (1 + |x|) σ f (x), x ∈ R 2 , σ ≥ 0. ( 6
)
Theorem. Let assumptions (2) hold and let f appr (x) be given by (4). Then

f appr = f (in the sense of distributios) on R 2 f or all f ∈ C 0 (R 2 ) (7)
if and only if

W (x, θ) -w 0 (x) ≡ w 0 (x) -W (x, -θ), x ∈ R 2 , θ ∈ S 1 . ( 8
)
(This result remains valid with C 0 (R 2 ) replaced by L ∞,σ (R 2 ) for σ > 1.) Theorem 1 is based on the following facts:

• Formula (4) coincides with the classical Radon inversion formula if W ≡ 1 and, as a corollary, is precise if W ≡ w 0 . • Formula ( 4) is equivalent to the symmetrized formula

f appr (x) = 1 4πw 0 (x) S 1 g ′ (xθ ⊥ , θ)dθ, x ∈ R 2 , g(s, θ) = 1 2π p.v. R P W f (t, θ) + P W f (-t, -θ) s -t dt, (s, θ) ∈ R × S 1 . (9)
• The following formula holds:

1 2 (P W f (s, θ) + P W f (-s, -θ)) = P W sym f (s, θ), (s, θ) ∈ R × S 1 , W sym (x, θ) = 1 2 (W (x, θ) + W (x, -θ)), x ∈ R 2 , θ ∈ S 1 .
(10)

• If q ∈ C(R × S 1 ), supp q is compact, q(s, θ) = q(-s, -θ), g(s, θ) = 1 π p.v. R q(t, θ) s -t dt, (s, θ) ∈ R × S 1 , S 1 g ′ (xθ ⊥ , θ)dθ ≡ 0 as a distribution of x ∈ R 2 , (11)
then q ≡ 0 on R × S 1 . The statement that, under the assumptions of Theorem, property (8) implies ( 7) can be also deduced from considerations developed in [K].

Using that W sym ≡ w 0 under condition (8), we obtain also the following Remarks. Let conditions (2), (8) be fulfiled. Let f ∈ C 0 (R 2 ). Then: (A) P W f on Ω(D) uniquely determines f (or more precisely w 0 f ) on R 2 \D via (10) and the Cornack inversion from P W sym f on Ω(D), where D is a compact in R 2 , Ω(D) denotes the set of all straight lines in R 2 which do not intersect D; (B) P W f on R × (S + ∪ S -) uniquely determines f on R 2 via (10) and standard inversion from the limited angle data P W sym f on R × S + , where S + is an arbitrary nonempty open connected subset of S 1 , S -= -S + .

For the case when W is given by (3) under the additional conditions that a ≥ 0 and supp a ⊂ D, where D is some known bounded domain which is not too big, and for f ∈ C(R 2 ), f ≥ 0, supp f ⊂ D, the transform P W f is relatively well approximated by P W appr f , where W appr (x, θ) = w 0 (x) + (1/2)(W (x, θ) -W (x, -θ)). In addition, this W appr already satisfies (8). This explains the efficiency of (4) as the first aproximation in SPECT reconstructions (on the level of integral geometry).