Concepts

========

This document describes the underlying concepts employed in micropython.

  * Namespaces and attribute definition

  * Contexts and values

  * Tables, attributes and lookups

  * Objects and structures

  * Parameters and lookups

  * Instantiation

Namespaces and Attribute Definition

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

Namespaces are any objects which can retain attributes.

  * 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.

These restrictions apply because such attributes are thus explicitly declared,

permitting the use of tables (described below). Module and class attributes

can also be finalised in this way in order to permit certain optimisations.

See rejected.txt for complicating mechanisms which could be applied to

mitigate the effects of these restrictions on optimisations.

Contexts and Values

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

Values are used as the common reference representation in micropython: as

stored representations of attributes (of classes, instances, modules, and

other objects supporting attribute-like entities) as well as the stored values

associated with names in functions and methods.

Unlike other implementations, micropython does not create things like bound

method objects for individual instances. Instead, all objects are referenced

using a context, reference pair:

Value Layout

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

    0           1

    context     object

    reference   reference

Specific implementations might reverse this ordering for optimisation

purposes.

Rationale

---------

To reduce the number of created objects whilst retaining the ability to

support bound method invocations. The context indicates the context in which

an invocation is performed, typically the owner of the method.

Usage

-----

The context may be inserted as the first argument when a value is involved in

an invocation. This argument may then be omitted from the invocation if its

usage is not appropriate.

See invocation.txt for details.

Contexts in Acquired Values

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

There are two classes of instructions which provide values:

    Instruction         Purpose                 Context Operations

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

    LoadConst           Load class, function,   Combine null context with

                        module, constant        loaded object

    LoadAddress*        Load attribute from     Preserve or override stored

    LoadAttr*           class, module,          context (as described in

                        instance                assignment.txt)

In order to comply with traditional Python behaviour, contexts may or may not

represent the object from which an attribute has been acquired.

See assignment.txt for details.

Contexts in Stored Values

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

There is only one class of instruction for storing values:

    Instruction     Purpose                 Context Operations

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

    StoreAddress    Store attribute in a    Preserve context; note that no

                    known object            test for class attribute

                                            assignment should be necessary

                                            since this instruction should only

                                            be generated for module globals

    StoreAttr       Store attribute in an   Preserve context; note that no

                    instance                test for class attribute

                                            assignment should be necessary

                                            since this instruction should only

                                            be generated for self accesses

    StoreAttrIndex  Store attribute in an   Preserve context; since the index

                    unknown object          lookup could yield a class

                                            attribute, a test of the nature of

                                            the nature of the structure is

                                            necessary in order to prevent

                                            assignments to classes

Note that contexts are never changed in the stored value: they are preserved.

See assignment.txt for details.

Tables, Attributes and Lookups

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

Attribute lookups, where the exact location of an object attribute is deduced,

are performed differently in micropython than in other implementations.

Instead of providing attribute dictionaries, in which attributes are found,

attributes are located at fixed places in object structures (described below)

and their locations are stored using a special representation known as a

table.

For a given program, a table can be considered as being like a matrix mapping

classes to attribute names. For example:

    class A:

        # instances have attributes x, y

    class B(A):

        # introduces attribute z for instances

    class C:

        # instances have attributes a, b, z

This would provide the following table, referred to as an object table in the

context of classes and instances:

    Class/attr      a   b   x   y   z

    A                       1   2

    B                       1   2   3

    C               1   2           3

A limitation of this representation is that instance attributes may not shadow

class attributes: if an attribute with a given name is not defined on an

instance, an attribute with the same name cannot be provided by the class of

the instance or any superclass of the instance's class.

The table can be compacted using a representation known as a displacement

list (referred to as an object list in this context):

                Classes with attribute offsets

    classcode   A

    attrcode    a   b   x   y   z

                        B

                        a   b   x   y   z

                                            C

                                            a   b   x   y   z

    List        .   .   1   2   1   2   3   1   2   .   .   3

Here, the classcode refers to the offset in the list at which a class's

attributes are defined, whereas the attrcode defines the offset within a

region of attributes corresponding to a single attribute of a given name.

Attribute Locations

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

The locations stored in table/list elements are for instance attributes

relative to the location of the instance, whereas those for class attributes

and modules are absolute addresses (although these could also be changed to

object-relative locations).

Objects and Structures 

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

As well as references, micropython needs to have actual objects to refer to.

Since classes, functions and instances are all objects, it is desirable that

certain common features and operations are supported in the same way for all

of these things. To permit this, a common data structure format is used.

    Header....................................................  Attributes.................

    Identifier  Identifier  Address     Identifier  Size        Object      Object      ...

    0           1           2           3           4           5           6           7

    classcode   attrcode/   invocation  funccode    size        __class__   attribute   ...

                instance    reference                           reference   reference

                status

Classcode

---------

Used in attribute lookup.

Here, the classcode refers to the attribute lookup table for the object (as

described above). Classes and instances share the same classcode, and their

structures reflect this. Functions all belong to the same type and thus employ

the classcode for the function built-in type, whereas modules have distinct

types since they must support different sets of attributes.

Attrcode

--------

Used to test instances for membership of classes (or descendants of classes).

Since, in traditional Python, classes are only ever instances of the "type"

built-in class, support for testing such a relationship directly has been

removed and the attrcode is not specified for classes: the presence of an

attrcode indicates that a given object is an instance.

See the "Testing Instance Compatibility with Classes (Attrcode)" section below

for details of attrcodes.

Invocation Reference

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

Used when an object is called.

This is the address of the code to be executed when an invocation is performed

on the object.

Funccode

--------

Used to look up argument positions by name.

The strategy with keyword arguments in micropython is to attempt to position

such arguments in the invocation frame as it is being constructed.

See the "Parameters and Lookups" section for more information.

Size

----

Used to indicate the size of an object including attributes.

Attributes

----------

For classes, modules and instances, the attributes in the structure correspond

to the attributes of each kind of object. For functions, however, the

attributes in the structure correspond to the default arguments for each

function, if any.

Structure Types

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

Class C:

    0           1           2           3           4           5           6           7

    classcode   (unused)    __new__     funccode    size        class type  attribute   ...

    for C                   reference   for                     reference   reference

                                        instantiator

Instance of C:

    0           1           2           3           4           5           6           7

    classcode   attrcode    C.__call__  funccode    size        class C     attribute   ...

    for C       for C       reference   for                     reference   reference

                            (if exists) C.__call__

Function f:

    0           1           2           3           4           5           6           7

    classcode   attrcode    code        funccode    size        class       attribute   ...

    for         for         reference                           function    (default)

    function    function                                        reference   reference

Module m:

    0           1           2           3           4           5           6           7

    classcode   attrcode    (unused)    (unused)    (unused)    module type attribute   ...

    for m       for m                                           reference   (global)

                                                                            reference

The __class__ Attribute

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

All objects support the __class__ attribute and this is illustrated above with

the first 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

Lists and Tuples

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

The built-in list and tuple sequences employ variable length structures using

the attribute locations to store their elements, where each element is a

reference to a separately stored object.

Testing Instance Compatibility with Classes (Attrcode)

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

Although it would be possible to have a data structure mapping classes to

compatible classes, such as a matrix indicating the subclasses (or

superclasses) of each class, the need to retain the key to such a data

structure for each class might introduce a noticeable overhead.

Instead of having a separate structure, descendant classes of each class are

inserted as special attributes into the object table. This requires an extra

key to be retained, since each class must provide its own attribute code such

that upon an instance/class compatibility test, the code may be obtained and

used in the object table.

Invocation and Code References

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

Modules: there is no meaningful invocation reference since modules cannot be

explicitly called.

Functions: a simple code reference is employed pointing to code implementing

the function. Note that the function locals are completely distinct from this

structure and are not comparable to attributes. Instead, attributes are

reserved for default parameter values, although they do not appear in the

object table described above, appearing instead in a separate parameter table

described below.

Classes: given that classes must be invoked in order to create instances, a

reference must be provided in class structures. However, this reference does

not point directly at the __init__ method of the class. Instead, the

referenced code belongs to a special initialiser function, __new__, consisting

of the following instructions:

    create instance for C

    call C.__init__(instance, ...)

    return instance

Instances: each instance employs a reference to any __call__ method defined in

the class hierarchy for the instance, thus maintaining its callable nature.

Both classes and modules may contain code in their definitions - the former in

the "body" of the class, potentially defining attributes, and the latter as

the "top-level" code in the module, potentially defining attributes/globals -

but this code is not associated with any invocation target. It is thus

generated in order of appearance and is not referenced externally.

Invocation Operation

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

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

follows:

    get invocation reference from the header

    jump to reference

Additional preparation is necessary before the above code: positional

arguments must be saved in the invocation frame, and keyword arguments must be

resolved and saved to the appropriate position in the invocation frame.

See invocation.txt for details.

Parameters and Lookups 

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

Since Python supports keyword arguments when making invocations, it becomes

necessary to record the parameter names associated with each function or

method. Just as object tables record attributes positions on classes and

instances, parameter tables record parameter positions in function or method

parameter lists.

For a given program, a parameter table can be considered as being like a

matrix mapping functions/methods to parameter names. For example:

    def f(x, y, z):

        pass

    def g(a, b, c):

        pass

    def h(a, x):

        pass

This would provide the following table, referred to as a parameter table in

the context of functions and methods:

    Function/param  a   b   c   x   y   z

    f                           1   2   3

    g               1   2   3

    h               1           2

Just as with parameter tables, a displacement list can be prepared from a

parameter table:

                Functions with parameter (attribute) offsets

    funccode    f

    attrcode    a   b   c   x   y   z

                                        g

                                        a   b   c   x   y   z

                                                    h

                                                    a   b   c   x   y   z

    List        .   .   .   1   2   3   1   2   3   1   .   .   2   .   .

Here, the funccode refers to the offset in the list at which a function's

parameters are defined, whereas the attrcode defines the offset within a

region of attributes corresponding to a single parameter of a given name.

Instantiation

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

When instantiating classes, memory must be reserved for the header of the

resulting instance, along with locations for the attributes of the instance.

Since the instance header contains data common to all instances of a class, a

template header is copied to the start of the newly reserved memory region.