[pypy-dev] Very relevant stuff (was: [pypy-svn] rev 812 - in pypy/trunk/src/pypy:interpreter objspace/std objspace/std/test)

[Christian Tismer]

Howdy,

I thought it would make sense to post the most relevant
text of this check-in to the list.
It also would make sense to add this to the PyPy Wiki.

arigo at codespeak.net wrote:

> Added: pypy/trunk/src/pypy/objspace/std/mm_notes.txt
> ==============================================================================
Notes on Multimethods
*********************

Interpreter-level classes correspond to implementations of application-level
types. Several implementations can be given for the same type (e.g. several
ways to code strings or dictionaries), and conversely the same 
implementation
can cover several types (e.g. all instances of user-defined types currently
share the same implementation).

The hierarchy among the classes used for the implementations is convenient
for implementation purposes. It is not related to any application-level type
hierarchy.


Dispatch
--------

Multimethods dispatch by looking in a set of registered functions. Each
registered function has a signature, which defines which object 
implementation
classes are accepted at the corresponding argument position.

The name 'W_ANY' is a synonym for 'W_Object' (currently, possibly 'object'
later). As it accepts anything, it is the only way to guarantee that the
registered function will be called with exactly the same object as was
passed originally. ATTENTION: in all other cases the argument received by
the function may have been converted in some way. It must thus not be
considered to be 'id'entical to the original argument. For example it should
not be stored in a data structure, nor be queried for type, nor be used for
another multimethod dispatch -- the only thing you should do is read and
write its internal data.

For example, 'getattr(obj, attr)' is implemented with a W_StringObject 
second
argument when all it needs is just the name of the attr, and with a W_ANY
when the 'attr' object could be used as a key in obj.__dict__.


Delegation
----------

Delegation is a transparent convertion mechanism between object
implementations. The convertion can give a result of a different type
(e.g. int -> float) or of the same type (e.g. W_VeryLongString -> str).
There is a global table of delegators. We should not rely on the delegators
to be tried in any particlar order, or at all (e.g. the int -> float 
delegator
could be ignored when we know that no registered function will accept a 
float
anyway).

Delegation is also used to emulate inheritance between built-in types
(e.g. bool -> int). This is done by delegation because there is no reason
that a particular implementation of a sub-type can be trivially typecast
to some other particular implementation of the parent type; the process 
might
require some work.


Types
-----

Types are implemented by the class W_TypeObject. This is where 
inheritance and the Method Resolution Order are defined, and where
attribute look-ups are done.

Instances of user-defined types are implementated as W_UserObjects.
A user-defined type can inherit from built-in types (maybe more
than one, although this is incompatible with CPython). The
W_UserObject delegator converts the object into any of these
"parent objects" if needed. This is how user-defined types appear
to inherit all built-in operator implementations.

Delegators should be able to invoke user code; this would let us
implement special methods like __int__() by calling them within a
W_UserObject -> int delegator.


Specifics of multimethods
-------------------------

Multimethods dispatch more-specific-first, left-to-right (i.e. if
there is an exact match for the first argument it will always be
tried first).

Delegators are automatically chained (i.e. A -> B and B -> C would be
combined to allow for A -> C delegation).

Delegators do not publish the class of the converted object in advance,
so that the W_UserObject delegator can potentially produce any other
built-in implementation. This means chaining and chain loop detection 
cannot be done statically (at least without help from an analysis
tool like the translator-to-C). To break loops, we can assume (unless
a particular need arises) that delegators are looping when they return
an object of an already-seen class.


Registration
------------

The register() method of multimethods adds a function to its database of
functions, with the given signature. A function that raises
FailedToImplement causes the next match to be tried.

'delegate' is the special unary multimethod that should try to convert
its argument to something else. For greater control, it can also return
a list of 2-tuples (class, object), or an empty list for failure to 
convert the argument to anything. All delegators will potentially be
tried, and recursively on each other's results to do chaining.

A priority ordering between delegators is used. See objspace.PRIORITY_*.


Translation
-----------

The code in multimethod.py is not supposed to be read by the
translator-to-C. Special optimized code will be generated instead
(typically some kind of precomputed dispatch tables).

Delegation is special-cased too. Most delegators will be found
to return an object of a statically known class, which means that
most of the chaining and loop detection can be done in advance.


Multimethod slicing
-------------------

Multimethods are visible to user code as (bound or unbound) methods
defined for the corresponding types. (At some point built-in functions
like len() and the operator.xxx() should really directly map to the
multimethods themselves, too.)

To build a method from a multimethod (e.g. as in 'l.append' or
'int.__add__'), the result is actually a "slice" of the whole
multimethod, i.e. a sub-multimethod in which the registration table has
been trimmed down. (Delegation mechanisms are not restricted for sliced
multimethods.)

Say that C is the class the new method is attached to (in the above
examples, respectively, C=type(l) and C=int). The restriction is
based on the registered class of the first argument ('self' for the
new method) in the signature. If this class corresponds to a fixed
type (as advertized by 'statictype'), and this fixed type is C or a
superclass of C, then we keep it.

Some multimethods can also be sliced along their second argument,
e.g. for __radd__().

-- 
Christian Tismer             :^)   <mailto:tismer at tismer.com>
Mission Impossible 5oftware  :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34  home +49 30 802 86 56  pager +49 173 24 18 776
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/