Low-level Implementation Details

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

Although micropython delegates the generation of low-level program code and

data to syspython, various considerations of how an eventual program might be

structured have been used to inform the way micropython represents the details

of a program. This document describes these considerations and indicates how

syspython or other technologies might represent a working program.

 * Objects and structures 

 * Instantiation

 * List and tuple representations

 * Instruction evaluation model

 * Exception handling

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

    0           1           2           3           4           5           6

    classcode   attrcode/   invocation  funccode    size        attribute   ...

                instance    reference                           reference

                status

Classcode

---------

Used in attribute lookup.

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

described in concepts.txt). 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

    classcode   (unused)    __new__     funccode    size        attribute   ...

    for C                   reference   for                     reference

                                        instantiator

Instance of C:

    0           1           2           3           4           5           6

    classcode   attrcode    C.__call__  funccode    size        attribute   ...

    for C       for C       reference   for                     reference

                            (if exists) C.__call__

Function f:

    0           1           2           3           4           5           6

    classcode   attrcode    code        funccode    size        attribute   ...

    for         for         reference                           (default)

    function    function                                        reference

Module m:

    0           1           2           3           4           5           6

    classcode   attrcode    (unused)    (unused)    (unused)    attribute   ...

    for m       for m                                           (global)

                                                                reference

The __class__ Attribute

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

All objects should support the __class__ attribute, and in most cases this is

done using the object table, yielding a common address for all instances of a

given class.

Function: refers to the function class

Instance: refers to the class instantiated to make the object

The object table cannot support two definitions simultaneously for both

instances and their classes. Consequently, __class__ access on classes must be

tested for and a special result returned.

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

For convenience, the first attribute of a class will be the common __class__

attribute for all its instances. As noted above, direct access to this

attribute will not be possible for classes, and a constant result will be

returned instead.

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 in concepts.txt.

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.

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.

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.

Instruction Evaluation Model

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

Programs use a value stack containing local and temporary storage. 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

                    ...

Unlike the CPython virtual machine, programs do not use a value stack

containing the results of expression evaluations. Instead, temporary storage

is statically allocated and employed by instructions.

Loading local names and temporary values 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. A number of locations for the arguments required by the invocation

are then reserved. With a frame to prepare, positional arguments are added to

the frame in order such that the first argument positions are filled. The

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

consult the parameter table and to find the frame location in which such

arguments are to be stored.

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

    Frame

    -----

    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

Where arguments are specified positionally, such "attributes" are set in

order. Keyword arguments are set using a name-to-position attribute-like

mapping, where the position of each argument is discovered using the parameter

table.

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)

    Frame

    -----

    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.

To obtain the default values, a reference to the function object is required.

This can be provided either in an additional frame location or in a special

register.

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.

Exception Handling

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

Active Exceptions

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

When an exception is raised, an exception instance is defined as the active

exception. This active exception remains in force until either a new exception

is raised in any handling of the exception, or upon exit of a handler where

the active exception has been caught (thus resetting the active exception).

The following operations can be employed to achieve this:

StoreException records the current value reference using the exception

register.

LoadException obtains the current exception and puts it in the value register.

CheckException checks the current exception against a class referenced by the

current value.

ClearException resets the exception register.

Handlers

--------

An exception handler stack is defined such that when a try...except or

try...finally block is entered, a new handler is defined.

When an exception is raised, the program jumps to the most recently defined

handler. Inside the handler, the stack entry for the handler will be removed.

Depending on the nature of the handler and whether the exception is handled,

the program may jump to the next most recent handler, and so on.

If no handler is defined when an exception is raised or re-raised, the program

should terminate. This might be done by having a "handler #0" which explicitly

terminates the program.

The following operations can be employed to achieve this:

PushHandler(block) defines an active handler at the location indicated by the

given block.

PopHandler(n) removes the n topmost active handlers. A single handler is

typically removed when leaving a try block, but potentially more handlers are

removed when such a block is exited using a return statement.