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

  * Register usage

  * List and tuple representations

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.

An additional restriction required for the current implementation of tables

(as described below) applies to class definitions: each class must be defined

using a unique name; repeated definition of classes having the same name is

thus not permitted. This restriction arises from the use of the "full name" of

a class as a key to the object table, where the full name is a qualified path

via the module hierarchy ending with the name of the class.

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.

Context Value Types

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

The following types of context value exist:

    Type            Usage                           Transformations

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

    Replaceable     With functions (not methods)    May be replaced with an

                                                    instance or a class when a

                                                    value is stored on an

                                                    instance or class

    Placeholder     With classes                    May not be replaced

    Instance        With instances (and constants)  May not be replaced

                    or functions as methods

    Class           With functions as methods       May be replaced when a

                                                    value is loaded from a

                                                    class attribute via an

                                                    instance

Contexts in Acquired Values

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

There are four classes of instructions which provide values:

    Instruction         Purpose                 Context Operations

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

1)  LoadConst           Load module, constant   Use loaded object with itself

                                                as context

2)  LoadFunction        Load function           Combine replaceable context

                                                with loaded object

3)  LoadClass           Load class              Combine placeholder context

                                                with loaded object

4)  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 are two classes of instruction for storing values:

    Instruction         Purpose                 Context Operations

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

1)  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

2)  StoreAddressContext Store attribute in a    Override context if appropriate;

                        known object            if the value has a replaceable

                                                context, permit the target to

                                                take ownership of the value

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). Thus, each occupied table cell has the following

structure:

    attrcode, uses-absolute-address, address (or location)

This could be given instead as follows:

    attrcode, is-class-or-module, location

Since uses-absolute-address corresponds to is-class-or-module, and since there

is a need to test for classes and modules to prevent assignment to attributes

of such objects, this particular information is always required.

Comparing Tables as Matrices with Displacement Lists

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

Although displacement lists can provide reasonable levels of compaction for

attribute data, the element size is larger than that required for a simple

matrix: the attribute code (attrcode) need not be stored since each element

unambiguously refers to the availability of an attribute for a particular

class or instance of that class, and so the data at a given element need not

be tested for relevance to a given attribute access operation.

Given a program with 20 object types and 100 attribute types, a matrix would

occupy the following amount of space:

    number of object types * number of attribute types * element size

  = 20 * 100 * 1 (assuming that a single location is sufficient for an element)

  = 2000

In contrast, given a compaction to 40% of the matrix size (without considering

element size) in a displacement list, the amount of space would be as follows:

    number of elements * element size

  = 40% * (20 * 100) * 2 (assuming that one additional location is required)

  = 1600

Consequently, the principal overhead of using a displacement list is likely to

be in the need to check element relevance when retrieving values from such a

list.

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 some generic

built-in type, 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. In addition, support

has also been removed for testing modules in the same way, meaning that the

attrcode is also not specified for modules.

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

Confusion can occur when functions are adopted as methods, since the context

then occupies the first slot in the invocation frame:

    def f(x, y, z):

        pass

    f(x=1, y=2, z=3) -> f(<context>, 1, 2, 3)

                     -> f(1, 2, 3)

    class C:

        f = f

        def g(x, y, z):

            pass

    c = C()

    c.f(y=2, z=3) -> f(<context>, 2, 3)

    c.g(y=2, z=3) -> C.g(<context>, 2, 3)

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.

Register Usage

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

During code generation, much of the evaluation produces results which are

implicitly recorded in the "active value" register, and various instructions

will consume the active value. In addition, some instructions will consume a

separate "active source value" from a register, typically those which are

assigning the result of an expression to an assignment target.

Since values often need to be retained for later use, a set of temporary

storage locations are typically employed. However, optimisations may reduce

the need to use such temporary storage where instructions which provide the

"active value" can be re-executed and will produce the same result.

List and Tuple Representations

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

Since tuples have a fixed size, the representation of a tuple instance is

merely a header describing the size of the entire object, together with a

sequence of references to the object "stored" at each position in the

structure. Such references consist of the usual context and reference pair.

Lists, however, have a variable size and must be accessible via an unchanging

location even as more memory is allocated elsewhere to accommodate the

contents of the list. Consequently, the representation must resemble the

following:

    Structure header for list (size == header plus special attribute)

    Special attribute referencing the underlying sequence

The underlying sequence has a fixed size, like a tuple, but may contain fewer

elements than the size of the sequence permits:

    Special header indicating the current size and allocated size

    Element

    ...             <-- current size

    (Unused space)

    ...             <-- allocated size

This representation permits the allocation of a new sequence when space is

exhausted in an existing sequence, with the new sequence address stored in the

main list structure. Since access to the contents of the list must go through

the main list structure, underlying allocation activities may take place

without the users of a list having to be aware of such activities.