Namespace Definition

====================

Module attributes are defined either at the module level or by global

statements.

Class attributes are defined only within class statements.

Instance attributes are defined only by assignments to attributes of self

within __init__ methods.

Potential Restrictions

----------------------

Names of classes and functions could be restricted to only refer to those

objects within the same namespace. If redefinition were to occur, or if

multiple possibilities were present, these restrictions could be moderated as

follows:

  * Classes assigned to the same name could provide the union of their

    attributes. This would, however, cause a potential collision of attribute

    definitions such as methods.

  * Functions, if they share compatible signatures, could share parameter list

    definitions.

Data Structures

===============

The fundamental "value type" is a pair of references: one pointing to the

referenced object represented by the interchangeable value; one referring to

the context of the referenced object, typically the object through which the

referenced object was acquired as an attribute.A

Value Layout

------------

    0           1

    object      context

    reference   reference

Acquiring Values

----------------

Values are acquired through name lookups and attribute access, yielding

the appropriate object reference together with a context reference as

indicated in the following table:

    Type of Access          Context     Notes

    --------------          -------     -----

    Local name              Preserved   Functions provide no context

    Global name             Preserved   Modules provide no context

    Class-originating       Accessor    Methods acquire the context of their

    attribute                 -or-      accessor if an instance...

                            Preserved   or retain the original context if the

                                        accessor is a class

    Instance-originating    Preserved   Methods retain their original context

    attribute

There may be some scope for simplifying the above, to the detriment of Python

compatibility, since the unbound vs. bound methods situation can be confusing.

Objects

-------

Since classes, functions and instances are all "objects", each must support

certain features and operations in the same way.

The __class__ Attribute

-----------------------

All objects support the __class__ attribute:

Class: refers to the type class (type.__class__ also refers to the type class)

Function: refers to the function class

Instance: refers to the class instantiated to make the object

Invocation

----------

The following actions need to be supported:

Class: create instance, call __init__ with instance, return object

Function: call function body, return result

Instance: call __call__ method, return result

Structure Layout

----------------

A suitable structure layout might be something like this:

    Identifier  Address     Type        Object      ...

    0           1           2           3           4

    classcode   invocation  __class__   attribute   ...

                reference   reference   reference

Here, the classcode refers to the attribute lookup table for the object. Since

classes and instances share the same classcode, they might resemble the

following:

Class C:

    0           1           2           3           4

    code for C  __new__     class type  attribute   ...

                reference   reference   reference

Instance of C:

    0           1           2           3           4

    code for C  C.__call__  class C     attribute   ...

                reference   reference   reference

                (if exists)

The __new__ reference would lead to code consisting of the following

instructions:

    create instance for C

    call C.__init__(instance, ...)

    return instance

If C has a __call__ attribute, the invocation "slot" of C instances would

refer to the same thing as C.__call__.

For functions, the same general layout applies:

Function f:

    0           1           2           3           4

    code for    code        class       attribute   ...

    function    reference   function    reference

                            reference

Here, the code reference would lead to code for the function. Note that the

function locals are completely distinct from this structure and are not

comparable to attributes.

For modules, there is no meaningful invocation reference:

Module m:

    0           1           2           3           4

    code for m  (unused)    module type attribute   ...

                            reference   (global)

                                        reference

Both classes and modules have code in their definitions, but this would be

generated in order and not referenced externally.

Invocation Operation

--------------------

Consequently, regardless of the object an invocation is always done as

follows:

    get invocation reference (at object+1)

    jump to reference

Additional preparation is necessary before the above code: positional

arguments must be saved to the parameter stack, and keyword arguments must be

resolved and saved to the appropriate position in the parameter stack.

Attribute Operations

--------------------

Attribute access needs to go through the attribute lookup table. Some

optimisations are possible and are described in the appropriate section.

One important aspect of attribute access is the appropriate setting of the

context in the acquired attribute value. From the table describing the

acquisition of values, it is clear that the principal exception is that where

a class-originating attribute is accessed on an instance. Consequently, the

following algorithm could be employed once an attribute has been located:

 1. If the attribute's context is a special value, indicating that it should

    be replaced upon instance access, then proceed to the next step;

    otherwise, acquire both the context and the object as they are.

 2. If the accessor is an instance, use that as the value's context, acquiring

    only the object from the attribute.

Where accesses can be determined ahead of time (as discussed in the

optimisations section), the above algorithm may not necessarily be employed in

the generated code for some accesses.

Instruction Evaluation Model

============================

Programs use a value stack where evaluated instructions may save their

results. A value stack pointer indicates the top of this stack. In addition, a

separate stack is used to record the invocation frames. All stack pointers

refer to the next address to be used by the stack, not the address of the

uppermost element.

    Frame Stack     Value Stack

    -----------     -----------     Address of Callable

                                    -------------------

    previous        ...

    current ------> callable -----> identifier

                    arg1            reference to code

                    arg2

                    arg3

                    local4

                    local5

                    ...

Loading local names is a matter of performing frame-relative accesses to the

value stack.

Invocations and Argument Evaluation

-----------------------------------

When preparing for an invocation, the caller first sets the invocation frame

pointer. Then, positional arguments are added to the stack such that the first

argument positions are filled. A number of stack locations for the remaining

arguments specified in the program are then reserved. The names of keyword

arguments are used (in the form of table index values) to consult the

parameter table and to find the location in which such arguments are to be

stored.

    fn(a, b, d=1, e=2, c=3) -> fn(a, b, c, d, e)

    Value Stack

    -----------

    ...             ...             ...             ...

    fn              fn              fn              fn

    a               a               a               a

    b               b               b               b

    ___             ___             ___         --> 3

    ___         --> 1               1           |   1

    ___         |   ___         --> 2           |   2

    1 -----------   2 -----------   3 -----------

Conceptually, the frame can be considered as a collection of attributes, as

seen in other kinds of structures:

Frame for invocation of fn:

    0           1           2           3           4           5

    code        a           b           c           d           e

    reference

However, where arguments are specified positionally, such "attributes" are not

set using a comparable approach to that employed with other structures.

Keyword arguments are set using an attribute-like mechanism, though, where the

position of each argument discovered using the parameter table.

Where the target of the invocation is known, the above procedure can be

optimised slightly by attempting to add keyword argument values directly to

the stack:

    Value Stack

    -----------

    ...             ...             ...             ...             ...

    fn              fn              fn              fn              fn

    a               a               a               a               a

    b               b               b               b               b

                    ___             ___             ___         --> 3

                    1               1               1           |   1

                                    2               1           |   2

                                                    3 -----------

    (reserve for    (add in-place)  (add in-place)  (evaluate)      (store by

    parameter c)                                                    index)

Method Invocations

------------------

Method invocations incorporate an implicit first argument which is obtained

from the context of the method:

    method(a, b, d=1, e=2, c=3) -> method(self, a, b, c, d, e)

    Value Stack

    -----------

    ...

    method

    context of method

    a

    b

    3

    1

    2

Although it could be possible to permit any object to be provided as the first

argument, in order to optimise instance attribute access in methods, we should

seek to restrict the object type.

Verifying Supplied Arguments

----------------------------

In order to ensure a correct invocation, it is also necessary to check the

number of supplied arguments. If the target of the invocation is known at

compile-time, no additional instructions need to be emitted; otherwise, the

generated code must test for the following situations:

 1. That the number of supplied arguments is equal to the number of expected

    parameters.

 2. That no keyword argument overwrites an existing positional parameter.

Default Arguments

-----------------

Some arguments may have default values which are used if no value is provided

in an invocation. Such defaults are initialised when the function itself is

initialised, and are used to fill in any invocation frames that are known at

compile-time.

Tuples, Frames and Allocation

-----------------------------

Using the approach where arguments are treated like attributes in some kind of

structure, we could choose to allocate frames in places other than a stack.

This would produce something somewhat similar to a plain tuple object.

Optimisations

=============

Some optimisations around constant objects might be possible; these depend on

the following:

  * Reliable tracking of assignments: where assignment operations occur, the

    target of the assignment should be determined if any hope of optimisation

    is to be maintained. Where no guarantees can be made about the target of

    an assignment, no assignment-related information should be written to

    potential targets.

  * Objects acting as "containers" of attributes must be regarded as "safe":

    where assignments are recorded as occurring on an attribute, it must be

    guaranteed that no other unforeseen ways exist to assign to such

    attributes.

The discussion below presents certain rules which must be imposed to uphold

the above requirements.

Safe Containers

---------------

Where attributes of modules, classes and instances are only set once and are

effectively constant, it should be possible to circumvent the attribute lookup

mechanism and to directly reference the attribute value. This technique may

only be considered applicable for the following "container" objects, subject

to the noted constraints:

 1. For modules, "safety" is enforced by ensuring that assignments to module

    attributes are only permitted within the module itself either at the

    top-level or via names declared as globals. Thus, the following would not

    be permitted:

    another_module.this_module.attr = value

    In the above, this_module is a reference to the current module.

 2. For classes, "safety" is enforced by ensuring that assignments to class

    attributes are only permitted within the class definition, outside

    methods. This would mean that classes would be "sealed" at definition time

    (like functions).

Unlike the property of function locals that they may only sensibly be accessed

within the function in which they reside, these cases demand additional

controls or assumptions on or about access to the stored data. Meanwhile, it

would be difficult to detect eligible attributes on arbitrary instances due to

the need for some kind of type inference or abstract execution.

Constant Attributes

-------------------

When accessed via "safe containers", as described above, any attribute with

only one recorded assignment on it can be considered a constant attribute and

this eligible for optimisation, the consequence of which would be the

replacement of a LoadAttrIndex instruction (which needs to look up an

attribute using the run-time details of the "container" and the compile-time

details of the attribute) with a LoadAttr instruction.

However, some restrictions exist on assignment operations which may be

regarded to cause only one assignment in the lifetime of a program:

 1. For module attributes, only assignments at the top-level outside loop

    statements can be reliably assumed to cause only a single assignment.

 2. For class attributes, only assignments at the top-level within class

    definitions and outside loop statements can be reliably assumed to cause

    only a single assignment.

All assignments satisfying the "safe container" requirements, but not the

requirements immediately above, should each be recorded as causing at least

one assignment.

Additional Controls

-------------------

For the above cases for "container" objects, the following controls would need

to apply:

 1. Modules would need to be immutable after initialisation. However, during

    initialisation, there remains a possibility of another module attempting

    to access the original module. For example, if ppp/__init__.py contained

    the following...

    x = 1

    import ppp.qqq

    print x

    ...and if ppp/qqq.py contained the following...

    import ppp

    ppp.x = 2

    ...then the value 2 would be printed. Since modules are objects which are

    registered globally in a program, it would be possible to set attributes

    in the above way.

 2. Classes would need to be immutable after initialisation. However, since

    classes are objects, any reference to a class after initialisation could

    be used to set attributes on the class.

Solutions:

 1. Insist on global scope for module attribute assignments.

 2. Insist on local scope within classes.

Both of the above measures need to be enforced at run-time, since an arbitrary

attribute assignment could be attempted on any kind of object, yet to uphold

the properties of "safe containers", attempts to change attributes of such

objects should be denied. Since foreseen attribute assignment operations have

certain properties detectable at compile-time, it could be appropriate to

generate special instructions (or modified instructions) during the

initialisation of modules and classes for such foreseen assignments, whilst

employing normal attribute assignment operations in all other cases. Indeed,

the StoreAttr instruction, which is used to set attributes in "safe

containers" would be used exclusively for this purpose; the StoreAttrIndex

instruction would be used exclusively for all other attribute assignments.

To ensure the "sealing" of modules and classes, entries in the attribute

lookup table would encode whether a class or module is being accessed, so

that the StoreAttrIndex instruction could reject such accesses.

Constant Attribute Values

-------------------------

Where an attribute value is itself regarded as constant, is a "safe container"

and is used in an operation accessing its own attributes, the value can be

directly inspected for optimisations or employed in the generated code. For

the attribute values themselves, only objects of a constant nature may be

considered suitable for this particular optimisation:

  * Classes

  * Modules

  * Instances defined as constant literals

This is because arbitrary objects (such as most instances) have no

well-defined form before run-time and cannot be investigated further at

compile-time or have a representation inserted into the generated code.

Class Attributes and Access via Instances

-----------------------------------------

Unlike module attributes, class attributes can be accessed in a number of

different ways:

  * Using the class itself:

    C.x = 123

    cls = C; cls.x = 234

  * Using a subclass of the class (for reading attributes):

    class D(C):

        pass

    D.x # setting D.x would populate D, not C

  * Using instances of the class or a subclass of the class (for reading

    attributes):

    c = C()

    c.x # setting c.x would populate c, not C

Since assignments are only achieved using direct references to the class, and

since class attributes should be defined only within the class initialisation

process, the properties of class attributes should be consistent with those

desired.

Method Access via Instances

---------------------------

It is desirable to optimise method access, even though most method calls are

likely to occur via instances. It is possible, given the properties of methods

as class attributes to investigate the kind of instance that the self

parameter/local refers to within each method: it should be an instance either

of the class in which the method is defined or a compatible class, although

situations exist where this might not be the case:

  * Explicit invocation of a method:

    d = D() # D is not related to C

    C.f(d) # calling f(self) in C

If blatant usage of incompatible instances were somehow disallowed, it would

still be necessary to investigate the properties of an instance's class and

its relationship with other classes. Consider the following example:

    class A:

        def f(self): ...

    class B:

        def f(self): ...

        def g(self):

            self.f()

    class C(A, B):

        pass

Here, instances of B passed into the method B.g could be assumed to provide

access to B.f when self.f is resolved at compile-time. However, instances of C

passed into B.g would instead provide access to A.f when self.f is resolved at

compile-time (since the method resolution order is C, A, B instead of just B).

One solution might be to specialise methods for each instance type, but this

could be costly. Another less ambitious solution might only involve the

optimisation of such internal method calls if an unambiguous target can be

resolved.

Optimising Function Invocations

-------------------------------

Where an attribute value is itself regarded as constant and is a function,

knowledge about the parameters of the function can be employed to optimise the

preparation of the invocation frame.