Didier Verna
email: didier@lrde.epita.fr

Method Combinators

Keywords: Software and its engineering → Object oriented languages, Extensible languages, Polymorphism, Inheritance, Classes and objects, Object oriented architectures, Abstraction, modeling and modularity, Object-Oriented Programming, Common Lisp Object System, Meta-Object Protocol, Generic Functions, Dynamic Dispatch, Polymorphism, Multi-Methods, Method Combinations, Orthogonality

In traditional object-oriented languages, the dynamic dispatch algorithm is hardwired: for every polymorphic call, only the most speci c method is used. C , the Common Lisp Object System, goes beyond the traditional approach by providing an abstraction known as method combinations: when several methods are applicable, it is possible to select several of them, decide in which order they will be called, and how to combine their results, essentially making the dynamic dispatch algorithm user-programmable.

Although a powerful abstraction, method combinations are underspeci ed in the Common Lisp standard, and the M , the Meta-Object Protocol underlying many implementations of C , worsens the situation by either contradicting it or providing unclear protocols. As a consequence, too much freedom is granted to conforming implementations. The exact or intended behavior of method combinations is unclear and not necessarily coherent with the rest of C .

In this paper, we provide a detailed analysis of the problems posed by method combinations, the consequences of their lack of proper speci cation in one particular implementation, and a Mbased extension called method combinators, aiming at correcting these problems and possibly o er new functionality.

INTRODUCTION

Common Lisp was the rst programming language equipped with an object-oriented (OO) layer to be standardized [START_REF]American National Standard: Programming Language -Common Lisp[END_REF]. Although in the lineage of traditional class-based OO languages such as Smalltalk and later C++ and Java, C , the Common Lisp Object System [START_REF] Daniel | Common lisp object system speci cation[END_REF][START_REF] Demichiel | The common lisp object system: An overview[END_REF][START_REF] Gabriel | Clos: integrating objectoriented and functional programming[END_REF][START_REF] Keene | Object-Oriented Programming in Common Lisp: a Programmer's Guide to C[END_REF], departs from those in several important ways.

First of all, C o ers native support for multiple dispatch [START_REF] Castagna | Object-Oriented Programming, A Uni ed Foundation[END_REF][START_REF] Castagna | A calculus for overloaded functions with subtyping[END_REF]. Multiple dispatch is a generalization of single dispatch a.k.a. inclusion polymorphism [START_REF] Nygaard | The development of the SIMULA languages[END_REF]. In the classic message-passing style of single dispatch, the appropriate method is selected according to the type of the receiver (the object through which the method is called). In multiple dispatch however, the method selection algorithm may use as many arguments as requested in the generic call. Because this kind of polymorphism doesn't grant any object argument a particular status (message receiver), methods (herein called multi-methods) are naturally decoupled from classes and generic function calls look like ordinary function calls. The existence of multi-methods thus pushes dynamic dispatch one step further in the direction of separation of concerns: polymorphism and inheritance are clearly separated.

Next, C itself is written on top of a meta-object protocol, the C M [START_REF] Kiczales | The Art of the Metaobject Protocol[END_REF][START_REF] Paepcke | User-level language crafting -introducing the C metaobject protocol[END_REF]. Although not part of the ANSI speci cation, the C M is a de facto standard well supported by many implementations. In supporting implementations, the M layer not only allows for C to be implemented in itself (classes being instances of their meta-classes etc.), but also lets the programmer extend or modify its very semantics, hence providing a form of homogeneous behavioral re ection [START_REF] Maes | Concepts and experiments in computational re ection[END_REF][START_REF] Sheard | Accomplishments and research challenges in meta-programming[END_REF][START_REF] Smith | Re ection and semantics in Lisp[END_REF]].

Yet another improvement over the classical OO approach lies in the concept of method combination. In the traditional approach, the dynamic dispatch algorithm is hardwired: every polymorphic call ends up executing the most speci c method available (applicable) and using other, less speci c ones requires explicit calls to them. In C however, a generic function can be programmed to implicitly call several applicable methods (possibly all of them), not necessarily by order of speci city, and combine their results (not necessarily all of them) in a particular way. Along with multiple dispatch, method combinations constitute one more step towards orthogonality [8, chapter 8]: a generic function can now be seen as a 2D concept: 1. a set of methods and 2. a speci c way of combining them. As usual with this language, method combinations are also fully programmable, essentially turning the dynamic dispatch algorithm into a user-level facility.

Richard P. Gabriel reports 1 that at the time Common Lisp was standardized, the standardization committee didn't believe that (defgeneric details (human) (:method-combination append :most-specific-last)) (defmethod details append ((human human)) ...) (defmethod details append ((employee employee)) ...))

Figure 1: Short Method Combination Usage Example method combinations were mature enough to make people implement them in one particular way (the only industrial-strength implementation available back then was in Flavors on Lisp Machines). Consequently, they intentionally under-speci ed them in order to leave room for experimentation. At the time, the M was not ready either, and only added later, sometimes with unclear or contradictory protocols. The purpose of this paper is to provide a detailed analysis of the current status of method combinations, and also to o er possible improvements over them.

Section 2 provides a detailed analysis of the speci cation for method combinations (both C and the M ) and points out its caveats. Section 3 describes how S2 implements method combinations, and exhibits some of their inconsistent or unfortunate (although conformant) behavior. Sections 4 and 5 provide an extension to method combinations, called method combinators, aimed at xing the problems previously described. Finally, Section 6 demonstrates an additional feature made possible with method combinators, which increases yet again the orthogonality of generic functions in Common Lisp.

METHOD COMBINATIONS ISSUES

In this section, we provide an analysis of how method combinations are speci ed and point out a set of important caveats. This analysis is not only based on what the Common Lisp standard claims, but also on the additional requirements imposed by the C M . In the remainder of this paper, some basic knowledge on method combinations is expected, notably on how to de ne them in both short and long forms. The reader unfamiliar with define-method-combination is invited to look at the examples provided in the Common Lisp standard rst 3 .

Lack of Orthogonality

As already mentioned, method combinations help increase the separation of concerns in Common Lisp's view on generic functions. The orthogonality of the concept goes only so far however, and even seems to be hindered by the standard itself occasionally. This is particularly true in the case of method combinations de ned in short form (or built-in ones, which obey the same semantics).

Figure 1 demonstrates the use of the append built-in combination, concatenating the results of all applicable methods. In this particular example, and given that employees are humans, calling details on an employee would collect the results of both methods. Short combinations require methods to have exactly one quali er: either the combination's name for primary methods (append in our example), or the :around tag 4 . This means that one cannot change a generic function's (short) method combination in a practical way, as it would basically render every primary method unusable (the standard also mandates that an error be signaled if methods without a quali er, or a di erent one are found). Hence, method combinations are not completely orthogonal to generic functions. On the other hand, :around methods remain valid after a combination change, a behavior inconsistent with that of primary methods.

Perhaps the original intent was to improve readability or safety: when adding a new method to a generic function using a short method combination, it may be nice to be reminded of the combination's name, or make sure that the programmer remembers that it's a non-standard one. If such is the case, it also fails to do so in a consistent way. Indeed, short method combinations support an option a ecting the order in which the methods are called, and passed to the :method-combination option of a defgeneric call (:most-specific-first/last, also illustrated in Figure 1). Thus, if one is bound to restate the combination's name anyway, why not restate the potential option as well? Finally, one may also wonder why short method combinations didn't get support for :before and :after methods as well as :around ones.

Because short method combinations were added to enshrine common, simple cases in a shorter de nition form, orthogonality was not really a concern. Fortunately, short method combinations can easily be implemented as long ones, without the limitations exhibited in this section (see Appendix A).

Lack of Structure

The Common Lisp standard provides a number of concepts related to object-orientation, such as objects, classes, generic functions, and methods. Such concepts are usually gracefully integrated into the type system through a set of classes called system classes. Generic functions, classes, and methods are equipped with two classes: a class named C serving as the root for the whole concept hierarchy, and a class named standard-C serving as the default class for objects created programmatically. In every case, the standard explicitly names the APIs leading to the creation of objects of such standard classes. For example, standard-method is a subclass of method and is "the default class of methods de ned by the defmethod and defgeneric forms" 5 .

Method combinations, on the other hand, only get one standardized class, the method-combination class. The M further states that this class should be abstract (not meant to be instantiated), and also explicitly states that it "does not specify the structure of method combination metaobjects" [10, p. 140]. Yet, because the standard also requires that method combination objects be "indirect instances" of the method-combination class 6 , it is mandatory that subclasses are provided by conforming implementations (although no provisions are made for a standard-method-combination class for instance). Although this design may seem inconsistent with the rest of C , the idea, again, was to leave room for experimentation. For example, knowing that method combinations come in two forms, short and long, and that short combinations may be implemented as long ones, implementations can choose whether to represent short and long combinations in a single or as separate hierarchies. The unfortunate consequence, however, is that it is impossible to specialize method combinations in a portable way, because implementation-dependent knowledge of the exact method combination classes is needed in order to subclass them.

Yet another unfortunate consequence of this under-speci cation lies in whether method combinations should be objects or classes to be instantiated, although the original intent was to consider them as some kind of macros involved in method de nition. The Common Lisp standard consistently talks of "method combination types", and in particular, this is what is supposed to be created by define-method-combination 7 . This seems to suggest the creation of classes. On the other hand, method combinations can be parametrized when they are used. The long form allows a full ordinary lambda-list to be used when generic functions are created. The short form supports one option called :identity-with-one-argument, in uencing the combination's behavior at creation-time (originally out of a concern for e ciency), and another one, the optional order argument, to be used by generic functions themselves. The long form also has several creation-time options for method groups such as :order and :required, but it turns out that these options can also be set at use-time, through the lambda-list.

Unclear Protocols

The third and nal issue we see with method combinations is that the M , instead of clarifying the situation, worsens it by providing unclear or inconsistent protocols.

2.

3.1 find-method-combination. In Common Lisp, most global objects can be retrieved by name one way or another. For example, symbol-function and symbol-value give you access to the Lisp-2 namespaces [START_REF] Gabriel | Technical issues of separation in function cells and value cells[END_REF], and other operators perform a similar task for other categories of objects (compiler-macro-function being an example). The Common Lisp standard de nes a number of find-* operators for retrieving objects. Amongst those are find-method and find-class which belong to the C part of the standard, but there is no equivalent for method combinations.

The M , on the other hand, provides a generic function called find-method-combination [10, p. 191]. However, this protocol only adds to the confusion. First of all, the arguments to this function are a generic function, a method combination type name, and some method combination options. From this prototype, we can deduce that contrary to find-class for example, it is not meant to retrieve a globally de ned method combination by name. Indeed, the description of this function says that it is "called to determine the method combination object used by a generic function". Exactly who calls it and when is unspeci ed however, and if the purpose is to retrieve the method combination used by a generic function, then one can wonder what the second and third arguments (method combination type and options) are for, and what happens if the requested type is not the type actually used by the generic function. In fact, the M already provides a more straightforward way of inquiring a generic function about its method combination. generic-function-method-combination is an accessor doing just that. 7 http://www.lispworks.com/documentation/lw70/CLHS/Body/m_de _4.htm 2.3.2 compute-effective-method. Another oddity of method combinations lies in the design of the generic function invocation protocol. This protocol is more or less a two steps process. The rst step consists in determining the set of applicable methods for a particular call, based on the arguments (or their classes). The Common Lisp standard speci es a function (which the M later re nes), compute-applicable-methods, which unsurprisingly accepts two arguments: a generic function and its arguments for this speci c call. The second step consists in computing (and then calling) the e ective method, that is, the combination of applicable methods, precisely combined in a manner speci ed by the generic function's method combination. While the Common Lisp standard doesn't specify how this is done, the M does, via a function called compute-effective-method. Unsurprisingly again, this function accepts two arguments: a generic function and a set of (applicable) methods that should be combined together. More surprisingly however, it takes a method combination as a third (middle) argument. One can't help but wonder why such an argument exists, as the generic function's method combination can be retrieved through its accessor which, as we saw earlier, is standardized. Here again, we may be facing a aborted attempt at more orthogonality. Indeed, this protocol makes it possible to compute an e ective method for any method combination, not just the one currently in use by the generic function (note also that the M explicitly mentions that compute-effective-method may be called by the user [10, p. 176]). However, the rest of C or the M doesn't support using compute-effective-method in this extended way. It is, however, an incentive for more functionality (see Section 6).

Memoization.

One nal remark in the area of protocols is about the care they take for performance. The M describes precisely how and when a discriminating function is allowed to cache lists of applicable methods [10, p. 175]. Note that nothing is said about the location of such a cache however (within the discriminating function, in a lexical closure over it, globally for every generic function etc.), but it doesn't really matter. On the other hand, the M says nothing about caching of e ective methods. This means that conforming implementations are free to do what they want (provided that the semantics of C is preserved). In particular, if caching of e ective methods is done, whether such a cache is maintained once for every generic function, or once for every generic function/method combination pair is unspeci ed. This is rather unfortunate, both for separation of concerns, and also for the extension that we propose in Section 6.

THE CASE OF SBCL

In this section, we analyse S 's implementation of C , and speci cally the consequences of the issues described in the previous section. Note that with one exception, the analysis below also stands for C

8 from which S is derived, and which in turn derives its implementation of C from P [1].

Classes

The S method combination classes hierarchy is depicted in was missing from the standard (see Section 2.2), although this class doesn't serve as the default implementation for method combinations, as two subclasses are provided for that, one for each combination form. The options slot in the base class stores the usetime options (the ones passed to the :method-combination option to a defgeneric call). New method combination de nitions are not represented by new classes; only by instances of either the short or long-method-combination ones. As a result, method combinations retrieved later on are objects containing a mix of de nition-time and use-time options.

Short Method Combinations

Investigating how short method combinations are created in S uncovers a very peculiar behavior. define-method-combination expands to a call to load-short-defcombin, which in turn creates a method on find-method-combination, eql-specialized on the combination's name and ignoring its rst argument (the generic function). This method is encapsulated in a closure containing the method combination's parameters, and recreates and returns a new method combination object on the y every time it is called. This has at least three important consequences.

(1) Short method combinations never actually globally exist per se (they don't have a namespace proper). Indeed, what is de ned is not a method combination object (not even a class), but a means to create one on-demand. In particular, every generic function gets its own brand new object representing its method combination. (2) find-method-combination neither does what its name suggests, nor what the M seems to imply. Indeed, because the generic function argument is ignored, it doesn't "determine the method combination object used by a generic function", but just creates whatever method combination instance you wish, of whichever known type and use-time option you like.

(3) It also turns out that rede ning a short method combination (for example by calling define-method-combination again) doesn't a ect the existing generic functions using it (each have a local object representing it). This is in contradiction with how every other C component behaves (class changes are propagated to live instances, method rede nitions update their respective generic functions etc.).

Long Combinations

The case of long method combinations is very similar, although with one additional oddity. Originally in P (and still the case in C

), long method combinations are compiled into so-called combination functions, which are in turn called in order to compute e ective methods. In both P and C , these functions are stored in the function slot of the long method combination objects (see Figure 2). In S however, this slot is not used anymore. Instead, S stores those functions in a global hash table named *long-method-combination-functions* (the hash keys being the combination names). The result is that long method combinations are represented half-locally (local objects in generic functions), half-globally with this hash table.

Now suppose that one particular long method combination is rede ned while some generic functions are using it. As for the short ones, this rede nition will not (immediately) a ect the generic functions in question, because each one has its own local object representing it. However, the combination function in the global hash table will be updated. As a result, if any concerned generic function ever needs to recompute its e ective method(s) (for instance, if some methods are added or removed, if the set of applicable methods changes from one call to another, or simply if the generic function needs to be reinitialized), then the updated hash table entry will be used and the generic function's behavior will indeed change according to the updated method combination. With e ective methods caching (as is the case in S ) and a little (bad) luck, one may even end up with a generic function using di erent method combinations for di erent calls at the same time (see Appendix B).

METHOD COMBINATORS

In this section, we propose an extension to method combinations called method combinators, aiming at correcting the problems described in Sections 2 and 3. Most importantly, method combinators have a global namespace and generic functions using them are sensitive to their modi cation. Method combinators come with a set of new protocols inspired from what already exists in C , thus making them more consistent with it. As an extension to method combinations, they are designed to work on top of them, in a nonintrusive way (regular method combinations continue to work as before). Finally, their implementation tries to be as portable as possible (although, as we have already seen, some vendor-speci c bits are unavoidable). We provide two classes, short/long-method-combinator, themselves subclasses of their corresponding, implementation-dependent, method combination classes. A method-combinator-mixin is also added as a superclass for both, maintaining additional information (the clients slot will be explained in Section 5.3) and serving as a means to specialize on both kinds of method combinators at the same time.

Method Combinator Classes

Method Combinators Namespace

Method combinators are stored globally in a hash table and accessed by name. This hash table is manipulated through an accessor called method-combinator-mixin clients short-method-combination long-method-combination short-method-combinator long-method-combinator Figure 3: Method Combinator Classes Hierarchy find-method-combinator (and its accompanying setf function). This accessor can be seen as the equivalent of find-class for method combinators, and has the same prototype. It thus considerably departs from the original M protocol, but is much more consistent with C itself.

Method Combinators Management

4.3.1 Protocols. The short method combinator protocol is designed in the same layered fashion as the rest of the M . First, we provide a macro called define-short-method-combinator behaving as the short form of define-method-combination, and mostly taking care of quoting. This macro expands to a call to ensure-short-method-combinator. In turn, this (regular) function calls the ensure-short-method-combinator-using-class generic function. Unsurprisingly, this generic function takes a method combinator as its rst argument, either null when a new combinator is created, or an existing one in case of a rede nition. Note that the M is not always clear or consistent with its ensure-* family of functions, and their relation to the macro layer. In method combinators, we adopt a simple policy: while the functional layer may default some optional or keyword arguments, the macro layer only passes down those arguments which have been explicitly given in the macro call.

The same protocol is put in place for long method combinators. Note that it is currently undecided whether we want to keep distinct interfaces and protocols for short and long forms. The current choice of separation simply comes from the fact that P implements them separately. Another yet undecided feature is how to handle de nition-time vs. use-time options. Currently, in order to simplify the matter as a proof of concept, the (normally) use-time option :most-specific-first/last is handled when a short combinator is de ned rather than when it is used, and the lambda-list for long forms is deactivated. In other words, use-time options are not supported. Note that this is of little consequence in practice: instead of using the same combination with di erent use-time arguments, one would just need to de ne di erent (yet similar) combinations with those arguments hard-wired in the code.

Creation.

A new method combinator is created in 3 steps.

(1) define-method-combination is bypassed. Because regular method combinations do not have any other protocol speci ed, we use S 's internal functions directly. Recall that the e ect of these functions is to add a new method to find-method-combination. (2) We subsequently call this new method in order to retrieve an actual combination object, and upgrade it to a combinator by calling change-class.

(3) Finally, this upgraded object is stored in the global combinators hash table by calling (setf find-method-combinator).

All of this is done in layer 3 of the protocols, except that in the case of long combinators, the combination function is computed at the macro level (this is how S does it). Additionally, as C still does, but contrary to S , we update the function slot in the long combinator objects.

The advantage of this process is that de ning a combinator also inserts a regular method combination in the system. Regular generic functions may thus use the new combination without any of the combinator extensions. 4.3.3 Modification. An existing method combinator may be updated by the user via the rst two protocol layers (the define-* macro layer or the ensure-* functional one). The updating process is quite simple: it merely involves a call to reinitialize-instance or to change-class if we are switching combinator forms. The de nition change is also propagated to the regular combination layer, and in the case of the long form, care is taken to update not only the function slot of the combinator object, but S 's *long-method-combination-functions* hash table as well. [START_REF] Castagna | A calculus for overloaded functions with subtyping[END_REF]. 3.4 Built-in Combinators. Finally, we provide new versions of the standard and built-in method combinations as combinators. These combinators are named with keywords, so as to both co-exist gracefully with the original Common Lisp ones, and still be easily accessible by name. On top of that, the built-in method combinators are de ned in long forms, so as to provide support for :before and :after methods, and also avoid requiring the combinator's name as a quali er to primary methods. In fact, a user-level macro called define-long-short-method-combinator is provided for de ning such "pseudo-short" combinators easily.

COMBINED GENERIC FUNCTIONS

At that point, generic functions can seamlessly use method combinators as regular combinations, although with not much bene t (apart from the extended versions of the built-in ones). Our next goal is to ensure that the global method combinator namespace is functioning properly.

Generic Functions Subclassing

As usual, in order to remain unobtrusive with standard C , we specialize the behavior of generic functions with a subclass handling method combinators in the desired way. This class, called combined-generic-function, is depicted in Figure 4 (an explanation for the functions slot will be provided in Section 6.2.2). For convenience, a macro called defcombined is provided as a wrapper around defgeneric. This macro takes care of setting the generic function class to combined-generic-function (unless otherwise speci ed). Also for convenience, a new :method-combinator option is provided to replace the regular :method-combination one, but ultimately transformed back into Finally, the (not portable) method-combination slot of generic functions is extended to recognize a :method-combinator initarg, and a method-combinator accessor.

Method Combinator Management

Initialization.

In the absence of an explicit method combinator option, new combined generic functions should use the :standard one. This is easily done by providing a default initarg for :method-combinator to the combined-generic-function class, with a value of (find-method-combinator :standard).

The case of a provided method combinator name is more interesting. Normally, we would wrap ensure-generic-function/using-class with specialized versions to look up a combinator instead of a combination. However, at the expense of portability (a necessity anyway), we can do a little simpler. As it turns out, S initializes a generic function's method combination by calling find-method-combination on the generic function's class prototype. Consequently, we can simply specialize this function with an eql specializer on the combined-generic-function class prototype, and look up for the appropriate global method combinator object there. Note that in order to specialize on a class prototype, the class needs to have been nalized already. Because of that, we need to call finalize-inheritance explicitly and very early on the class combined-generic-function.

Sanitation

. This is also a good opportunity for us to sanitize the find-method-combination protocol for combined generic functions. A new method specialized on such functions is provided. Contrary to the default behavior, this method ensures that the requested method combinator is indeed the one in use by the function, and then returns it (recall that this is a global object). Otherwise, an error is signaled.

Updating.

In order to change a combined generic function's method combinator, we provide a convenience function called change-method-combinator. This function accepts a combined generic function (to be modi ed) and a method combinator designator (either a name, or directly an object) which it canonicalizes. In the ideal case, this function should be able to only invalidate the generic function's e ective method cache. Unfortunately, this cannot be done in a portable way. Thus, the only thing we can do portably is to call reinitialize-instance with the new method combinator.

Client Maintenance

The last thing we need to do is make sure that method combinator updates are correctly propagated to relevant combined generic functions. A combined generic function using a method combinator is called its client. Every method combinator maintains a list of clients, thanks to the the clients slot of the mixin (see Figure 3).

Registration.

Registering a combined generic function as a method combinator client is implemented via two methods. One, on initialize-instance, adds a new combined generic function to its method combinator's clients slot. The other one, on reinitialize-instance, checks whether an existing combined generic function's combinator has changed, and performs the updating accordingly (recall that reinitializing the instance is the only portable way to change a generic function's method combination).

Note that while the Common Lisp standard allows a generic function's class to change, provided that both classes are "compatible" (a term which remains unde ned) 9 , the M seems to imply that meta-classes are only compatible with themselves (it is forbidden to change a generic function's meta-class [10, p. 187]). This restriction makes the client registration process simpler, as a regular generic function cannot become a combined one, or vice versa.

Updating.

When a method combinator is rede ned, it can either remain in the same form, or switch from short to long and vice versa. These two situations can be easily detected by specializing reinitialize-instance and u-i-f-d-c10 (we could also use shared-initialize). Two such :after methods are provided, which trigger updating of all the method combinator's clients.

Client updating is implemented thanks to a new protocol inspired from the instance updating one: we provide a generic function called make-clients-obsolete, which starts the updating process. During updating, the generic function u-c-g-f-f-r-m-c11 is called on every client. As mentioned previously, there is no portable way to invalidate an e ective methods cache in the C M , so the only thing we can do safely is to completely reinitialize the generic function.

The problem we have here is that while the method combinator has been rede ned, the object identity is preserved. Still, we need to trick the implementation into believing that the generic function's method combinator object has changed. In order to do that, we rst set the combined generic function's method-combination slot to nil manually (and directly; bypassing all o cial protocols), and then call reinitialize-instance with a :method-combinator option pointing to the same combinator as before. The implementation then mistakenly thinks that the combinator has changed, and e ectively reinitializes the instance, invalidating previously cached e ective methods.

ALTERNATIVE COMBINATORS

In Section 4. 3.4, we provided new versions of the built-in method combinations allowing primary methods to remain unquali ed. In Section 5. 2.3 we o ered a convenience function to change the method combinator of a combined generic function more easily (hence the use for unquali ed methods). In the spirit of increasing the separation of concerns yet again, the question of alternative combinators follows naturally: what about calling a generic function with a di erent, temporary method combinator, or even maintaining several combinators at once in the same generic function?

In the current state of things, we can already change the method combinator temporarily, call the generic function, and then switch the combinator back to its original value. Of course, the cost of doing it this way is prohibitive, as the generic function would need to be reinitialized as many times as one changes its combinator. There is however, a way to do it more e ciently. While highly experimental, it has been tested and seems to work properly in S .

Protocols

At the lowest level lies a function called call-with-combinator. This function takes a combinator object, a combined generic function object and a &rest of arguments. Its purpose is to call the generic function on the provided arguments, only with the temporary combinator instead of the original one. On top of this function, we provide a macro called call/cb (pun intended) accepting designators (e.g. names) for the combinator and generic function arguments, instead of actual objects. Finally, it is not di cult to extend the Lisp syntax with a reader macro to denote alternative generic calls in a concise way. For demonstration purposes, a #! dispatching macro character may be installed and used like this:

#!combinator(func arg1 arg2 ...)
This syntax is transformed into the following macro call:

(call/cb combinator func arg1 arg2 ...)
In turn, this is nally expanded into:

(call-with-combinator (find-method-combinator combinator) # func arg1 arg2 ...)

Implementation

Method combinations normally only a ect the computation of effective methods. Unfortunately, we have already seen that the C M doesn't specify how or when e ective methods may be cached. Consequently, the only portable way of changing them is to reinitialize a generic function with a di erent combination. Although e ective methods cannot be portably accessed, the generic function's discriminating function can, at least in a half-portable fashion. This gives us an incentive towards a possible implementation.

Discriminating Functions / Funcallable Instances.

A generic function is an instance of a funcallable class (see Figure 4), which means that generic function objects may be used where functional values are expected. When a generic function (object) is "called", its discriminating function is actually called. The M speci es that discriminating functions are installed by the (regular) function set-funcallable-instance-function. This strongly suggests that the discriminating function is stored somewhere in the generic function object. Unfortunately, the M doesn't specify a reader for that potential slot, although every implementation will need one (this is why we said earlier that discriminating functions could be accessed in a half-portable way). In S , it is called funcallable-instance-fun.

Discriminating Function Caches.

The idea underlying our implementation of alternative combinators is thus the following. Every combined generic function maintains a cache of discriminating functions, one per alternative combinator used (this is the functions slot seen in Figure 4). When an alternative combinator is used for the rst time (via a call to call-with-combinator), the generic function is reinitialized with this temporary combinator, called, and the new discriminating function is memoized. The function is then reinitialized back to its original combinator, and the values from the call are returned. It is important to actually execute the call before retrieving the new discriminating function, because it may not have been calculated before that.

If the alternative combinator was already used before with this generic function, then the appropriate discriminating function is retrieved from the cache and called directly. Of course, care is also taken to call the generic function directly if the alternative combinator is in fact the generic function's default one.

Client Maintenance.

Alternative combinators complicate client maintenance (see Section 5.3), but the complication is not insurmountable. When an alternative combinator is used for the rst time, the corresponding generic function is registered as one of its clients. The client updating protocol (see Section 5. 3.2) is extended so that if the modi ed combinator is not the generic function's original one, then the generic function is not reinitialized. Instead, only the memoized discriminating function corresponding to this combinator is invalidated. 6.2.4 Disclaimer. Generic functions were never meant to work with multiple combinations in parallel, so there is no guarantee on how or where applicable and e ective method caches, if any, are maintained. Our implementation of alternative combinators can only work if each discriminating function gets its own set of caches, for example by closing over them. According to both the result of experimentation and some bits of documentation 12 , it appears to be the case in S . If, on the other hand, an implementation maintains a cache of e ective methods outside the discriminating functions (for instance, directly in the generic function object), then, this implementation is guaranteed to never work.

PERFORMANCE

Because method combinators are implemented in terms of regular combinations, the cost of a (combined) generic call shouldn't be impacted. In S , only the standard combination is special-cased for bootstrapping and performance reasons, so some loss could be noticeable with the :standard combinator. Method combinator updates or changes do have a cost, as clients need to be reinitialized, but this is not di erent from updating a regular generic function for a new method combination. Again, the only portable way to do so is also to completely reinitialize the generic function.

Alternative combinators, on the other hand, do come at a cost, and it is up to the programmer to decide whether the additional expressiveness is worth it. Using an alternative combinator for the rst time is very costly, as the generic function will be reinitialized twice (hence a ecting the next regular call to it as well) and client maintenance will be triggered. Once an alternative discriminating function has been memoized, an "alternative call" will essentially require looking it up in a hash table (twice if find-method-combinator is involved in the call) before calling it.

In order to both con rm and illustrate those points, some rough performance measurements have been conducted and are reported in Figure 5. The rst batch of timings involve a generic function with 4 methods simply returning their (numerical) argument. The second one involves a generic function with 4 methods printing their argument on a stream with format. The idea is that the methods in the numerical case are extremely short, while the ones performing I/O take much longer to execute. The timings are presented in seconds, for 10 8 and 10 7 consecutive iterations respectively.

The rst two bars show the timings for a regular generic function with the standard method combination, and an equivalent combined generic function with the :standard combinator. In the numerical case, we observe a 45% performance loss, while in the I/O case, the di erence is of 5%. This is due to S optimizing the standard method combination but not the :standard combinator.

The next two bars show the timings for a built-in method combination compared to its equivalent combinator (+ for the numerical case, progn for the I/O one). Recall that short combinators are in fact implemented as long ones, so the comparison is not necessarily fair. Nevertheless, the di erence in either case is not measurable. Again, this is due to the fact that method combinators are implemented in terms of regular combinations.

Finally, the last bars show the timings involved in calling a generic function with an alternative combinator. Recall that this simply means calling a memoized discriminating function (hence taking the time displayed by the 4 th bars) after having looked it up in a hash table. The large number of iterations measured ensures that the overhead of rst-time memoization is cushioned). In the rst (numerical) case, the overhead of using the :+ combinator as an alternative instead of as the original one is of 90%. The methods being very short, the impact of an additional has table lookup is important. In the (longer) I/O case and for the :progn combinator however, this impact is amortized and falls down to 8%.

RELATED WORK

Greg Pfeil has put up a set of useful method combination utilities on Github 13 . These utilities include functions and macros frequently used in the development of new combinations or helping in the debugging of their expansion, and also some pre-made ones.

His library addresses some of the orthogonality concerns raised in Section 2. 1. In particular, the append/nconc combination allows one to switch between the append and nconc operators without the need for requalifying all the primary methods (they still need to be quali ed as append/nconc though, so are short forms de ned with the basic combination).

Greg Pfeil's library does not attempt to address the primary concern of this paper, namely the overall consistence of the design of method combinations, and more speci cally their namespace behavior. In one particular case, it even takes the opposite direction. The basic combination implements an interesting idea: it serves as a unique short form, making the operator a use-time value. In this way, it is not necessary anymore to de ne short combinations globally before using them. Every short combination essentially becomes local to one generic function.

Note that even though we attempted to do the exact opposite with method combinators, it is also possible to use them locally. Indeed, one can always break the link from a name to a combinator by calling (setf (find-method-combinator name) nil). After this, the combinator will only be shared by combined generic functions already using it. Again, this behavior is similar to that of find-class 14 .

Finally, the basic combination also addresses some of the concerns raised in Section 2.2. On top of allowing :before and :after methods in short forms, the distinction between de nition-time and use-time options is removed. Indeed, since the operator has become a use-time option itself, the same holds for the option :identity-with-one-argument. What we have done, on the contrary, is to turn the order option into a de nition-time one (see Section 4.3.1).

CONCLUSION

Method combinations are one of the very powerful features of C , perhaps not used as much as they deserve, due to their apparent complexity and the terse documentation that the standard provides. The additional expressiveness and orthogonality they aim at providing is also hindered by several weaknesses in their design.

In this paper, we have provided a detailed analysis of these problems, and the consequences on their implementation in S . Basically, the under-speci cation or inconsistency of the associated protocols can lead to non-portable, obscure, or even surprising, yet conforming behavior.

We have also proposed an extension called method combinators designed to correct the situation. Method combinators work on top of regular combinations in a non-intrusive way and behave in a more consistent fashion, thanks to a set of additional protocols following some usual patterns in the C M . The full code is available on Github 15 . It has been successfully tested on S .

PERSPECTIVES

Method combinators are currently provided as a proof of concept. They still require some work and also raise a number of new issues. First of all, it is our intention to properly package them and provide them as an actual A system library. Next, we plan on investigating their implementation for vendors other than S , and in particular guring out whether alternative combinators are possible or not. As of this writing, the code is in fact already ported to C

, but surprisingly enough, it doesn't work as it is. Most of the tests fail or even trigger crashes of the Lisp engine. It seems that C su ers from many bugs in its implementation of P , and it is our hope that xing those bugs would su ce to get combinators working.

One still undecided issue is whether to keep long and short forms implemented separately (as in P ), or unify everything under the long form. We prefer to defer that decision until more information on how other vendors implement combinations is acquired. The second issue is on the status of the long form's lambda-list (currently deactivated) and consequently whether new combinators should be represented by new classes or only instances of the general one (see Section 4.3.1).

As we have seen, the lack of speci cation makes it impossible to implement method combinators in a completely portable way, and having to resort to reinitialize-instance is overkill in many situations, at least in theory. Getting insight on how exactly the di erent vendors handle applicable and e ective methods caches could give us hints on how to implement method combinators more e ciently, alternative combinators in particular.

Apart from the additional functionality, several aspects of method combinators and their protocols only ll gaps left open in the M . Ultimately, these protocols (generic function updating notably) should belong in the M itself, although a revised version of it is quite unlikely to see the day. It is our hope, however, that this paper would be an incentive for vendors to re ne their implementations of method combinations with our propositions in mind.

Finally, one more step towards full orthogonality in the generic function design can still be taken. The Common Lisp standard forbids methods to belong to several generic functions simultaneously. By relaxing this constraint, we could reach full 3D separation of concerns. Method combinators exist as global objects, so would " oating" methods, and generic functions simply become mutable sets of shareable methods, independent from the way(s) their methods are combined.

A LONG SHORT METHOD COMBINATIONS

The Common Lisp standard provides several examples of builtin method combinations, and their equivalent de nition in long form 16 . In a similar vein, the macro proposed in Figure 6 de nes method combinations similar to those created with the short form, only with the following di erences:

(1) the primary methods must not be quali ed, (2) :before and :after methods are available.

As in the original short form of define-method-combination, identity-with-one-argument is available as an optimization avoiding the call to the operator when a single method is invoked. The long form's lambda-list is used to de ne the order optional argument, directly passed along as the value of the :order keyword to the primary method group.

B LONG METHOD COMBINATION WOES

This section demonstrates an inconsistent behavior of generic functions using long method combinations in S , when the combination is rede ned. First, we de ne a progn-like long method combination, ordering the methods in the default, most speci c rst way. (define-method-combination my-progn () ((primary () :order :most-specific-first :required t)) (progn ,@(mapcar (lambda (method) (defmacro define-long-short-method-combination (name &key documentation identity-with-one-argument (operator name)) Define NAME as a long-short method combination. OPERATOR will be used to define a combination resembling a short method combination, with the following differences: -the primary methods must not be qualified, -:before and :after methods are available.

(let ((documentation (when documentation (list documentation))) (single-method-call (if identity-with-one-argument (call-method ,(first primary)) (, ,operator (call-method ,(first primary)))))) (define-method-combination ,name (&optional (order :most-specific-first)) ((around (:around)) (before (:before)) ;; :before methods provided (primary (#| combination name removed |#) :order order :required t) (after (:after))) ;; :after methods provided ,@documentation (flet ((call-methods (methods) (mapcar (lambda (method) (call-method ,method)) methods))) (let* ((primary-form (if (rest primary) (, ,operator ,@(call-methods primary)) ,single-method-call)) (form (if (or before after) (multiple-value-prog1 (progn ,@(call-methods before) ,primary-form) ,@(call-methods (reverse after))) primary-form))) (if around (call-method ,(first around) (,@(rest around) (make-method ,form))) form))))))

Figure 6: Long Short Method Combinations (call-method ,method)) primary)))

Next, we de ne a generic function using it with two methods.

(defgeneric test (i) (:method-combination my-progn) (:method ((i number)) (print number)) (:method ((i fixnum)) (print fixnum)))

Calling it on a fixnum will execute the two methods from most to speci c.

CL-USER> (test 1) FIXNUM NUMBER

Next, we rede ne the combination to reverse the ordering of the methods.

(define-method-combination my-progn () ((primary () :order :most-specific-last :required t)) (progn ,@(mapcar (lambda (method) (call-method ,method)) primary)))

This does not (yet) a ect the generic function.

CL-USER> (test 1) FIXNUM NUMBER

We now add a new method on float, which normally reinitializes the generic function. (defmethod test ((i float)) (print float)) However, a fixnum call is not a ected, indicating that some caching of the previous behavior is still going on.

CL-USER> (test 1) FIXNUM NUMBER

A rst float call, however, will notice the new combination function. CL-USER> (test 1.5) NUMBER FLOAT Meanwhile, fixnum calls continue to use the old one. CL-USER> (test 1) FIXNUM NUMBER

Figure 2

 2 Figure 2: S Method Combination Classes Hierarchy

Figure 3

 3 Figure3depicts the implementation of method combinators in S . We provide two classes, short/long-method-combinator, themselves subclasses of their corresponding, implementation-dependent, method combination classes. A method-combinator-mixin is also added as a superclass for both, maintaining additional information (the clients slot will be explained in Section5.3) and serving as a means to specialize on both kinds of method combinators at the same time.

Figure 4 :

 4 Figure 4: Combined Generic Functions

Figure 5 :

 5 Figure 5: Benchmarks

http://www.sbcl.org

http://www.lispworks.com/documentation/lw70/CLHS/Body/m_de_4.htm

http://www.lispworks.com/documentation/lw70/CLHS/Body/07_ d.htm

http://www.lispworks.com/documentation/lw70/CLHS/Body/t_std_me.htm

http://www.lispworks.com/documentation/lw70/CLHS/Body/t_meth_1.htm

https://www.cons.org/cmucl/

http://www.lispworks.com/documentation/lw70/CLHS/Body/f_ensure.htm

update-instance-for-different-class

update-combined-generic-function-for-redefined-method-combinator

http://www.sbcl.org/sbcl-internals/Discriminating-Functions.html# Discriminating-Functions

https://github.com/sellout/method-combination-utilities

https://github.com/didierverna/ELS2018-method-combinators

ACKNOWLEDGMENTS

Richard P. Gabriel provided some important feedback on the history of method combinations, Christophe Rhodes some documentation on S 's internals, and Pascal Costanza and Martin Simmons some valuable insight or opinions on several aspects of the M .


Eric Prina

Emeric Roux

Denise Mattei

Geneviève Milon

Genevie ` Ve Milon

Leishmania DNA is rapidly degraded following parasite death: an analysis by microscopy and real-time PCR

Control of human leishmaniases relies on appropriate diagnosis and reliable methods for monitoring chemotherapy. The current method used for estimation of parasite burden during chemotherapy patient follow-up as well as in pharmacological studies performed in experimental models involves PCR-based assays. Compared to time-consuming conventional methods, this type of Leishmania DNA detection-based method is extremely sensitive, but could fail in distinguishing viable Leishmania from slowly degenerating ones. We have used an in vitro model to monitor the duration of Leishmania DNA persistence in mouse macrophages following exposure to L-leucine ester, a molecule otherwise known to rapidly kill intracellular Leishmania amazonensis amastigotes. At one hour post L-leucine ester exposure, more than 98% of amastigote-loaded macrophages harbored killed parasites and parasite remnants, as assessed by microscopy. This dramatic decrease in parasite load and the microscopic parasite follow-up over the 120 h time period studied correlated with Leishmania DNA as quantified by real-time PCR. Our results indicate that kinetoplast and nuclear parasite DNA degradation occurs very rapidly after amastigote death. These data add further weight to the argument that PCR assays represent not only a robust method for diagnosis but can also be reliable for monitoring parasite size reduction rate post any intervention (Leishmaniatargeting molecules, immunomodulators…).

Introduction

Leishmaniases are parasitic diseases that are endemic to nearly 90 countries, affecting some 12 million individuals in tropical, subtropical and Mediterranean regions [1]. The causal agents, Leishmania spp, are digenetic protozoan parasites belonging to the Trypanosomatidae family. The life cycle of these parasites requires two hosts, blood-feeding phlebotomine insects and mammals, including mainly rodents and carnivorous mammals. During their blood meal, Leishmania-housing vectors deliver the metacyclic infective promastigote stage into vertebrate host skin. Parasites are rapidly captured, mainly by macrophages, and then differentiate into their obligatory intracellular amastigote stage. Various clinical manifestations are described, ranging from less severe cutaneous forms to a fatal, if untreated, visceral form, depending on the parasite species and immunological status of the host [2]. Furthermore, a hallmark feature of the Leishmania parasite is the ability to reside in some mammalian hosts without inducing clinical symptoms [3,4]. This asymptomatic parasitism assesses a dynamic equilibrium between distinct immune cells and molecules that either clear parasites or facilitate their persistence [5]. Disruption of this equilibrium in asymptomatic hosts can induce Leishmania multiplication and allow for the development of clinical symptoms [6].

To date, chemotherapy is the only intervention used for patients displaying clinical signs of the various forms of these parasitic diseases, since there are no effective preventive or therapeutic vaccines available [7]. Though the advent of effective new orally administered drugs such as Miltefosine, an alkylphosphocholine used primarily as an anti-cancer agent, represents a real hope for patients housing antimonial resistant Leishmania [8], chemotherapy of visceral leishmaniasis is far from satisfactory. In drug-treated patients, particularly those who are immunocompromised, it is of utmost importance to determine whether clearance of parasites has been achieved to avoid recurrence / relapses and complications. Methods based on parasite DNA detection, such as PCR, have proved highly specific and sensitive for monitoring parasite presence either for diagnosis or during follow-up of parasite load reduction in patients undergoing chemotherapy. Recently, some authors have evaluated the usefulness of PCR methods in assessing parasitological cure: a negative result was correlated with parasitological cure and a positive result with the presence of living parasites [9 -11].

In order to establish the reliability of PCR for therapy monitoring in either drug-treated patients or animal models, it is important to know whether the parasite DNA detected and quantified by PCR exclusively assesses the presence of living amastigotes. In this study, we used a real-time PCR assay along with immunofluorescence and phase contrast microscopy to follow the parasite load fluctuations in Leishmania-harbouring macrophages that have been exposed to a leishmanicidal drug that acts very rapidly on amastigotes [12].

Materials and methods

Mice and parasites

Female Swiss nu/nu and BALB/c mice, between 8-and 12-weeks old, were obtained from Charles River (St Germain-sur l'Arbresle, France) and Janvier (Le Genest-St-Isle, France). L. amazonensis strain LV79 (MPRO/BR/1972/M1841) was propagated in Swiss nu/nu mice. Amastigotes were isolated from lesions and purified as described [13]. Promastigotes that had been differentiated from lesion-derived amastigotes were grown at 26°C in HOSMEM-II [13] supplemented with 20 % heat-inactivated fetal calf serum (FCS, Dutscher, Brumath, France), 50 µg/mL of streptomycin and 50 IU/mL of penicillin (Antibiotics, Seromed, Berlin, Germany). Parasites were collected from Log phase cultures.

Preparation of macrophages and loading with L. amazonensis amastigotes

Bone marrow cell suspensions recovered from tibias and femurs of BALB/c mice were suspended in RPMI 1640 medium (Seromed) supplemented with 10% FCS, antibiotics (culture medium) and 20% L-929 fibroblast-conditioned medium. Cells were distributed in bacteriologic Petri dishes (Greiner, Germany) and incubated at 37 °C in a 5% CO 2 air atmosphere. Six days later, bone marrow-derived smoothly adherent macrophages (BMDM) were washed with Dulbecco's phosphate buffered solution (PBS) and resuspended in prewarmed 1% EDTA in Dulbecco's PBS without Ca2 + and Mg2 + (Biochrom AG, Berlin, Germany). Recovered BMDM were deposited in flat-bottom 24-well plates (Tanner, Switzerland) at a density of 5 x 10 5 cells per well. For light microscopic studies, BMDM were allowed to adhere on 12 mm round glass coverslips. BMDM were then maintained in the same conditions as above, except that culture medium was supplemented with 4% L-929 fibroblast-conditioned medium. Twenty-four hours after replating, BMDM nuclei were counted in control wells run in parallel [13] and amastigotes were added at a multiplicity of six amastigotes per host cell. BMDM cultures were incubated at 34 °C, which is the permissive temperature for survival and multiplication of strain LV79 [14].

Leishmanicidal treatment and parasite load follow-up

The protocol used to kill intracellular amastigotes was adapted from Rabinovitch et al. [12]. Briefly, 24 hours after contact with parasites, BMDM cultures were incubated at 37 °C with RPMI-HEPES 20 mM, pH 7.4 supplemented with 3% FCS, antibiotics and 2 mM L- Leucine methyl ester (Leu-oMe). After 1 hour of contact, Leu-oMe-containing medium was removed and replaced with either lysis medium for immediate DNA extraction and purification (see § 2.5) or culture medium. In the latter case, all drug exposed and unexposed BMDM cultures were maintained at either 34 °C (any living intracellular amastigote develops) or at 37 °C or 37.5°C (intracellular parasites die, 14). At various time points after Leu-oMe exposure (1 to 120 h), BMDM cultures were processed for DNA isolation and fluorescence microscopy. All experimental points have been performed in duplicate.

Microscopic analysis

After fixation with paraformaldehyde, BMDMs were permeabilized and labeled with primary antibodies (Abs) and relevant fluorescent conjugates according to standard procedures [13]. Parasites were detected with parasite-specific mAb 2A3-26 [13]. Host cell molecules were detected with i) mAb specific for α-tubulin (Clone DM 1A, Sigma-Aldrich, Milwaukee, WI, USA), and ii) biotinylated mAb specific for mouse Major Histocompatibility Complex class I molecules (clone 34-1-2S, eBioscience, San Siego, CA, USA). After immunolabeling, cell preparations were incubated for 5 min with 5 µg/ml Hoechst 33342 (Molecular probes, Invitrogen SARL, Cergy Pontoise, France) in PBS to stain the nuclei of host cells and parasites. Coverslips were mounted in Mowiol (Calbiochem, San Diego, CA) before observation under an inverted microscope Zeiss Axiovert 200M piloted by Zeiss Axiovision 4.4 software (Carl Zeiss Microscopy, Jena, Germany). Images were acquired with a black and white CCD camera (Roper Scientific GmbH Germany) and further processed using Photoshop software (Adobe®Photoshop®CS).

Leishmanicidal effects were monitored by two parameters: (a) the reduction of parasitophorous vacuole (PV) size and number and (b) the overall decrease in intracellular amastigote number.

Cell lysis and DNA isolation

Cell lysis and DNA isolation from adherent BMDMs, cultured promastigotes and lesionderived purified amastigotes, were performed with the DNeasy Tissue kit (Qiagen, Courtaboeuf, France), according to the manufacturer's instructions.

Leishmania and mouse macrophage DNA targets selected for amplification

Sets of primers generating Leishmania genomic or kinetoplastic DNA amplification products were designed using unique or multiple sequences retrieved from NCBI databanks (http://www.ncbi.nlm.nih.gov/). Alignment of sequences was generated with the MultAlin algorithm [15, http://prodes.toulouse.inra.fr/multalin/multalin.html]. Oligonucleotide pairs were chosen using the LightCycler Probe Design software (version 1.0, Idaho Technology Inc.). Similarities of primer sequences with those present in nucleotide databanks were validated using the BLAST program (http://www.ncbi.nlm.nih.gov/BLAST/). The mouse-specific housekeeping gene beta-catenin (β-cat) was amplified to monitor i) sample DNA degradation, ii) presence of potential inhibitors of PCR or iii) variation in DNA yield. Characteristics of targets and primers used in this study are summarized in Table 1.

Real-time PCR conditions and cycling parameters

PCR was performed using a LightCycler® 480 system (Roche Diagnostics, Meylan, France) and set up in white opaque polypropylene wells (LightCycler ® 480 Multiwell Plates 384) in a final volume of 10 µl per reaction. Briefly, 1 µl of sample DNA was added to 9 µl of a master mix containing 5 µl of QuantiTect SYBR Green Kit (Qiagen) and 4 µl of nucleasefree water with primers (Guaranteed Oligos™, Sigma-Aldrich) at a final concentration of 0.5 µM. Activation of the Qiagen Thermophilus aquaticus polymerase was performed at 95 °C for 15 min. The PCR program included 40 cycles of denaturation at 95 °C for 10 s, annealing at 54 °C for 25 s and extension at 72 °C for 30 s. SYBR Green fluorescent emission was measured at the end of the elongation step. Subsequently, a melting curve program was applied with a continuous fluorescent measurement starting at 70 °C and ending at 95 °C (ramping rate of 0.1 °C/s).

Specificity and sensitivity of the PCR assay

Product identification was performed using a melting curve analysis at the end of each PCR. Melting curves were converted to melting peaks and the Tm for each amplicon was determined (Table 1). PCR products were checked after migration in a 1.5% agarose gel in TBE stained with ethidium bromide.

Sensitivity assays included BMDM cultures spiked with defined numbers of amastigotes immediately prior to the lysis process and 10-fold serial dilutions of DNA from lesion-derived purified amastigotes or log-phase promastigotes.

Analysis of PCR data

Mean Crossing Point values (Cp) were determined by the second derivative maximum method of the LightCycler® 480 Basic Software. Cp were used for relative quantitative data analysis using the Pfaffl method [16]. The relative expression ratio R of a parasite gene was computed based on the amplification efficiency (E) and Cp deviation between a sample (Cp sample ) and a control (L. amazonensis-loaded BMDM before Leu-oMe exposure; Cp La- BMDM ). Cp values for the host β-cat reference gene were used for data normalization. Amplification efficiency of each target was determined according to the equation E=10 (-

1/S)
, where S is the slope of the standard curve generated from ten-fold serial dilutions of purified parasite or host cell DNA.

Data processing and presentation were performed using Microsoft Excel and SigmaPlot 2004 software (Systat), respectively.

Results

The aim of the present study was to determine the outcome of Leishmania DNA post exposure of intracellular amastigotes to a rapidly acting leishmanicidal molecule. The leishmanicidal amino acid ester Leu-oMe induces massive, immediate killing of intracellular amastigotes of the L. mexicana complex [12]. The killing mechanism involves lysosomal compartments (megasomes) found only within members of this Leishmania complex, and relies on their acidic hydrolase activities [17]. Application of this simple and swift protocol allowed for efficient monitoring of L. amazonensis amastigote outcome as well as parasite DNA fate. We also benefited from the temperature sensitivity of strain LV79, which stops growing and eventually dies when incubated at 37 °C (this study) or 37.5°C [14] for a prolonged period of time.

Microscopic follow-up of parasite load in Leu-oMe-exposed L. amazonensis-harboring BMDMs

Twenty-four or forty-eight hours after onset of intracellular parasitism, L. amazonensisloaded BMDMs showed a regular shape and usually contained one or more large PVs housing amastigotes (Fig. 1A, 1B: white stars). Numerous parasites were seen as smooth, rice shaped bodies, usually attached to the PV membrane (Fig. 1A, 1B: white arrows). Hoechst staining of nucleic acids allowed for visualization of nuclei from both host macrophages and amastigotes (Fig. 1: blue). The presence of intracellular parasites with intact morphology (Fig. 1A,1B) correlated with the detection of their nuclei (Fig . 1B,1C).

After one hour of exposure to Leu-oMe at 37°C, there was a sharp decrease in parasite burden as evidenced by the low percentage (<1%) of BMDMs still harboring amastigotes with normal morphology and attached to the PV membrane, compared to > 98% in cultures at 34°C not exposed to Leu-oMe (Fig. 1 and data not shown). In most microscopic fields observed, neither morphologically intact amastigotes nor parasite nuclei could be evidenced (Fig. 1E,1F). However, parasite remnants were still detected by fluorescence (Fig. 1D, green, cyan arrows) and differential interference contrast microscopy (Fig. 1E, cyan arrows). For cell cultures maintained at 37 °C following Leu-oMe exposure, the percentage of L. amazonensis-loaded BMDMs remained stable from 5 to 24 h and decreased after 48 h to almost undetectable levels at 120 h (data not shown).

At 34 °C and until 48 h post Leu-oMe exposure, only minute numbers of unaltered intracellular amastigotes could be counted in the PVs of rare BMDMs containing parasites (Fig. 2D-F, white arrows) compared to Leu-oMe-unexposed BMDMs, which harbored more than 10 parasites per cell (Fig. 2A-C).

Leishmania DNA targets and selection of primers for real-time PCR assays

We have designed primers for various Leishmania target genes to follow the fate of Leishmania DNA: mitochondrial or kinetoplast DNA (kDNA) and nuclear DNA. Sequences for DNA polymerase α (DNA Pol α), glucose 6-phospate dehydrogenase (G6PD), hexokinase and the small subunit ribosomal RNA (ssr RNA, multy-copy gene) were retrieved from the NCBI database. Primers were designed and selected according to the guidelines described in § 2.6 Primers obtained following this procedure could thus be used in one unique PCR protocol as defined in §2.7. Modified published primer sequences were used to detect kDNA minicircle targets (JW11 and JW12, [9,18]). Primers specific for host β-cat DNA gene were designed to compensate for inter-PCR variations and differences in DNA yields between samples, As an initial control, the PCR product of each target was analyzed on an agarose gel to confirm the single product size (data not shown) and, subsequently, the Tm was determined to assess the specificity of the amplicons (Table 1). Absence of primer cross-reactivity between host cell and Leishmania DNA was assessed with various template amounts from both organisms (data not shown). All relevant information about the primers and amplicons is displayed in Table 1.

The dynamic range of the real-time quantitative Leishmania PCR test was determined by serial dilutions of L. amazonensis DNA in water. Representative data for all Leishmania targets are shown in Figure 3. Amplicon detection was linear over a 6 log-fold range of Leishmania DNA concentrations and the assay allowed us to accurately detect as few as 100 fg of parasite DNA (Fig. 3A). PCR efficiency for each target was determined from the E=10 [- 1/slope] equation, plotting the Cp values against the log of the initial template concentration (Fig. 3B). Efficiencies were found to be high and constant with a strong correlation coefficient (R 2 >0.99) over the concentration/dilution range studied (Fig. 3B and data not shown). ssrRNA-and kDNA-specific primers showed higher sensitivity, as repeatedly demonstrated by lower Cp values compared to other nuclear DNA targets (data not shown). However, after 38 PCR cycles, the increase in fluorescence values detected was deemed unreliable due to Poisson distribution statistics. Positive detection from approximately 10 fg of parasite DNA suggested nearly single-parasite sensitivity.

Only one melting peak with a near constant value was observed for each PCR amplification product (Table 1). For example, the Tm of ssrRNA amplicons calculated from melting curves was 79.07°C +/-0.08°C (Fig. 3C). No primer-dimers were detected except for the kinetoplastic minicircle target, the detection of which was based on the use of JW11/JW12 primers (Fig. 3C, Table 1 and data not shown).

PCR assays on BMDMs harboring L. amazonensis amastigotes

Efficacy of the combined procedure of PCR (DNA extraction and purification steps) was first verified. To this end, BMDM samples spiked with defined amounts of Leishmania amastigotes were prepared. Highly reproducible results were obtained for each spiked control (performed in duplicate samples) and high linearity was maintained over the range of template parasite numbers added (Fig. 4 and data not shown). Presence of host cell DNA did not hinder the detection of Leishmania DNA, even in the presence of very few parasites i.e. 0.2 parasites per PCR (10 parasites per well).

Parasite DNA is rapidly degraded once the parasite is killed

PCR results for the detection of parasite DNA are expressed as fold differences (termed R) in L. amazonensis gene copies relative to mouse host gene copies (see §2.9 of Materials and Methods). After 1 h of Leu-oMe exposure, less than 1% of the initial leishmanial nuclear DNA content could be detected by PCR using ssrRNA specific primers (Fig. 5). Under these conditions, the leishmanicidal activity of Leu-oMe resulted in swift and almost complete killing of intracellular amastigotes. When the culture was subsequently maintained at 37 °C, the parasite burden slowly decreased to very low levels at 120 h post Leu-oMe exposure. The same parasite DNA detection profile pattern was obtained using primers specific for other nuclear genes studied (DNA Pol, Hexokinase and G6PD) as well as with primers that amplify conserved regions of kinetoplast minicircles (data not shown).

A few hours after Leu-oMe exposure, the low parasite burden determined by PCR was correlated with detection of very small numbers of unaltered intracellular amastigotes by microscopy. Furthermore, in parallel experiments and until 48 h post leishmanicidal treatment, positive cultures for promastigote growth were obtained from BMDMs maintained at 26 °C in HOSMEM-II medium (data not shown). These data revealed the presence of living amastigotes that have resisted the single shot leishmanicidal effect of Leu-oMe and were able to differentiate into promastigotes and multiply in the relevant medium. When the cell culture was maintained at 34 °C, the few living parasites detected at 5 h could resume their growth as demonstrated by the progressive increase in relative expression values calculated at 24, 48 and 120 h (Fig. 5). Moreover, the temperature shift from 34 °C to 37 °C without drug treatment had a progressive leishmanicidal effect which became detectable after 48 h. Very few parasite-harbouring BMDMs could be detected after 120 h in cultures that had been exposed to leishmanicidal treatment (Fig. 5). In control experiments performed at 34 °C, the amount of Leishmania DNA in BMDMs left unexposed to Leu-oMe slowly increased over the time period studied.

Discussion

Conventional methods used for leishmaniasis diagnosis can also be used to assess therapeutic regimens for efficiency of Leishmania clearance. Indeed, limiting dilution assays [19] allow for the quantification of parasites present within tissue biopsies but, although sensitive, these culture-based methods are tedious and time-consuming. Moreover, not all parasites are cultivable. The ex vivo / in vitro growth and subsequent quantification of Leishmania promastigotes by limiting dilution assays may be impeded by the Leishmania species used, the composition of the medium (FCS and other additives) and / or the presence of host tissue material. This is particularly evident when parasites are scarce [3, 4, 20 and unpublished observations]. Moreover, many current serological methods cannot distinguish between current, past or asymptomatic Leishmania-driven parasitism. Due to its high sensitivity and specificity, the use of real-time PCR may offer a number of advantages over conventional assays to monitor parasite load outcome in human patients undergoing chemotherapy or in pharmacological studies developed in experimental models.

However, the question of whether Leishmania DNA detected and quantified by PCR is indicative of live parasites represents a critical issue that needs to be addressed. This study was designed to investigate the fate of Leishmania DNA within BMDMs that were loaded with L. amazonensis amastigotes and briefly exposed to a leishmanicidal molecule. We adapted a protocol based on the use of Leu-oMe, an experimental leishmanicidal drug that only acts on intracellular amastigotes belonging to L. amazonensis or L. mexicana species. This drug, which induces rapid death, was used to avoid the problem of detecting DNA originating from a mixed population of living and dead organisms at each given time point. Indeed, commercially available drugs are known to act progressively over a long period of time. After one hour of exposure to this amino acid ester, we noticed a decrease in parasite burden of more than 98%, as assessed by both microscopy and real-time PCR. Validation of the real-time PCR method by another established method i.e. the identification of unaltered amastigotes by microscopy, allowed for a high correlation between PCR values and living parasite numbers to be established [this study and 21]. Furthermore, the survival of some amastigotes post-leishmanicidal treatment was evidenced in parallel experiments by their ability to differentiate into promastigotes and multiply in culture (data not shown). Exposing BMDM cultures to 34 °C after Leu-oMe exposure allowed for the detection of a progressive increase in parasite load by real-time PCR. This observation highlights the fact that intracellular surviving L. amazonensis amastigotes were able to resume growth at a permissive temperature. Thus, our results demonstrated that Leishmania DNA detected by PCR is derived from intact parasites and that nuclear DNA and kDNA are rapidly degraded following amastigote death. These data are in agreement with those from recent clinical studies, in which a positive PCR result was correlated to the presence of living parasites while a negative result was obtained after parasitological cure [10,11,22]. This concordance is not restricted to Leishmania and to leishmaniases. Indeed, studies on other eukaryotic protozoan parasites such as Plasmodium chabaudi, Trypanosoma cruzi, and Toxoplasma gondii also strengthen the observation that a positive PCR result assesses the presence of viable parasites [23 -25]. Interestingly, this is in contrast to assessment of bacterial DNA, especially Mycobacterium [26 -30].

In most clinical studies in which PCR has been used to monitor the presence of Leishmania, parasite DNA remained detectable in all cured individuals who experienced relapse. However, some cured individuals who were PCR negative could still develop clinical symptoms, while others exhibiting Leishmania-DNA positive PCR did not develop disease [22]. This indicates that attention should be paid to the sensitivity threshold of the PCR assay used as well as the necessity to perform a kinetic detection study, not just end-point detection. In our study, the detection limit was around 0.2 to 1 parasites for 1 µl of sample. In other studies, in which optimization of extraction methods and PCR conditions were enhanced (end point or real-time PCR), the sensitivity threshold fell below 0.01 parasites per PCR, which should allow for accurate follow-up of parasite load in patients benefiting from therapeutic interventions [21,29,30].

In conclusion, our data add further weight to the argument that the PCR assay represents not only a robust method of diagnosis, but can also be a reliable tool for monitoring the efficacy of Leishmania-targeting molecules as well as an early, preclinical, prognostic marker of relapse.

Figure 1. Microscopic follow-up of intracellular L. amazonensis amastigotes in BALB/c

BMDMs 1 h post exposure to Leu-oMe. Leishmania-harboring macrophages were grown at 34°C (A, B, C) or exposed at 37°C to Leu-oMe for 1 h (D, E, F) before fixation and processing for immunofluorescence microscopy analysis. Intracellular amastigotes were stained with Alexa-488-conjugated specific mAb 2A3.26 (A, D). Host intracellular (A) or membrane (D) macrophage molecules were stained using anti α-tubulin and anti MHC Class I molecule Ab, respectively, followed by Texas Red conjugated secondary Abs. Host macrophage and parasite DNA were stained with Hoechst dye. Black and white images acquired with the CCD camera were colorized according to standards used in fluorescence microscopy: green: Alexa-488, red: Texas Red and blue: Hoechst. The presence of intact parasites and the lumen of PVs are indicated by white arrows (A, B) and white asterisks (A, B, C), respectively. Following Leu-oMe exposure, only parasite remnants could be detected (cyan arrows, D, E). Note the absence of DNA staining for drugexposed Leishmania amastigotes (E, F) compared to healthy parasites (B, C). A net correlation is observed between DNA detection and parasite morphology as revealed by differential interference contrast microscopy (B, E). A yellow color indicates co-localisation or very tight association of the molecules concerned (A, D). Anti α-tubulin mAb also recognizes Leishmania tubulin (data not shown).

Figure 2. Microscopic follow-up of intracellular L. amazonensis amastigotes in BALB/c

BMDMs 48 h post exposure to Leu-oMe. Leishmania-harboring macrophages were left unexposed at 34°C (A, B, C) or exposed at 37°C to Leu-oMe for 1h and then left unexposed at 34°C for 48 h (D, E, F) before fixation and processing for immunofluorescence microscopy analysis. Staining of parasites, a-tubulin, MHC class I molecules and nucleic acids along with images' colorization were performed as described in the legend to Fig. 1. In macrophages unexposed to Leu-oMe, numerous parasites are detected within large PVs (green-yellow staining, A; smooth rice-shaped bodies, B). Each amastigote is associated with DNA staining (blue spot, B, C). After Leu-oMe exposure and following a 48 h incubation period at 34°C, the permissive temperature for LV79 strain development, very few intact parasites could be visualized by immunofluorescence or differential interference contrast microscopy (D, E, F; white arrows). Note that nucleic acid staining is only associated with intact amastigotes (E, F, white arrows). In cured macrophages, PVs have been reduced or have disappeared completely but parasite remnants are still detected (green-yellow staining, D), sometimes associated with granular structures revealed by differential interference contrast microscopy (E) but without DNA costaining (E, F). At different time points post Leu-oMe addition to LV79 amastigote-loaded BMDMs, total DNA was isolated and real-time PCR assays were performed to quantify Leishmania (L) DNA targets. As a representative example, the relative quantity (R) of ssrRNA target was expressed comparatively to the Mus (M) β-cat DNA for each sample. Data were expressed using the sample Leishmania-loaded BMDM before Leu-oMe addition as a calibrator (R=1). Leu-oMe-exposed macrophages are represented by squares and those not exposed to drug by circles. Macrophage cultures were maintained either at 37°C (red color) or 34°C (blue color). These data are representative of three experiments.

Figure 3 .

 3 Figure 3. Sensitivity and specificity of the real-time PCR assay. (A) Amplification plots for the ssrRNA gene from serial 10-fold dilutions of L. amazonensis DNA (B) Plot of mean Cp values +/-1 S.D. (technical duplicates) against the logarithmic quantity of Leishmania DNA (10 ng to 100 fg per reaction). Cp values were extracted from graph (A) fluorescence values using the second derivative maximum method. (C) Melting peaks were determined from the first negative derivative of the fluorescence versus the temperature i.e. melting curves for each amplicon.

Figure 4 .

 4 Figure 4. Reproducibility and sensitivity of PCR assays from spiked controls. BMDMs were seeded with increased numbers of purified amastigotes before total DNA isolation. Relative quantity (R) represents the normalized ratio of Leishmania (L) DNA target

Figure 5 .

 5 Figure 5. Real-time PCR follow-up of parasite DNA after exposure to Leu-oMe.At different time points post Leu-oMe addition to LV79 amastigote-loaded BMDMs, total DNA was isolated and real-time PCR assays were performed to quantify Leishmania (L) DNA targets. As a representative example, the relative quantity (R) of ssrRNA target was

Hal-Pasteur author manuscript pasteur-00181350, version 1

Acknowledgments:

We apologize to authors for failing to cite their work directly owing to space constraints. The authors are mostly indebted to Roche Diagnostics (Meylan, France) for providing them with the LightCycler® 480 system. This work was supported by Le Fonds Dédié numéro 13, Combattre les Maladies Parasitaires (Sanofi-Aventis, Institut Pasteur and Ministère de la Recherche).

The authors have no conflicting financial interests.