PyMite: A Flyweight Python Interpreter for 8-bit Architectures

Dean W. Hall
dean.hall@computer.org
Austin, TX, U.S.A.

19 March 2003

Abstract:

PyMite is a flyweight Python interpreter written from scratch to execute on 8-bit microcontrollers as well as desktop computers. It is a work-in-progress, but is developed enough to run demonstration programs. This paper explains the motivation for creating PyMite and gives an overview of what PyMite can and cannot do. Then the current status and the work ahead are discussed. This is followed by details on the design and implementation of PyMite. Two new features are mentioned: ``stackless'' frames and in-line native code. Finally, information is given on how to obtain PyMite.

Motivation

There are more embedded microcontrollers (MCU) on this planet than there are people living. The ubiquity of these devices is due to the low cost and high power of the 8-bit architecture. Programming 8-bit microcontrollers is both an occupation and a hobby. All 8-bit architectures can be programmed in assembly, fewer in C, and still fewer in a higher level language. C and BASIC are the most popular languages above assembly for these devices. To the hobbyist, C has a steep learning curve. For the professional, BASIC lacks powerful semantics. PyMite brings the expressive, high level language, Python, to the embedded space.

Python has a short learning curve and robust builtin data types. The short learning curve will make the recreational programmer more productive and the data types will make him more effective. Python is also a rapid prototyping language. Bringing this feature to the embedded space is a real benefit. PyMite tries to keep everything that makes Python a great language.

The Media Laboratory at the Massachusetts Institute of Technology created Interactive C (IC) to assist the development of intelligent mobile robots [1]. IC compiles a subset of C to bytecode and interprets that on an 8-bit Motorola 68HC11. PyMite replaces IC and provides a modern language with powerful builtin datatypes.

Overview

This section gives an overview of what PyMite is, how it is used, the current status of the project, and the work yet to be done.

What PyMite Is

PyMite is a bytecode interpreter and set of libraries that can execute an application on an 8-bit microcontroller. The application is written in the Python syntax and compiled to a code object by Python. At that point, a new tool, PmImgCreator, creates a relocatable image of the program. This image is comparable to a .pyc file, but is condensed and formatted for PyMite. The image does not need to be linked to the PyMite executable, unless it contains native code. If the image contains no native code, PyMite only needs to be informed where to find the image.

Once the microcontroller is programmed and operating, the PyMite system initializes itself and loads the application image. Just like a Python module, the application can be a simple script, a set of functions, or a class with methods. It can import other modules and call those functions. It can even call native C libraries or assembly code through a PyMite-specific native code mechanism. PyMite uses a heap to manage memory. A hybrid best-fit allocator distributes memory chunks, while a hybrid mark-sweep collector reclaims them.

Current Status

PyMite can execute many programs that are filtered through PmImgCreator. PmImgCreator detects and reports source code that produces unsupported bytecode. Once these errors are fixed, PyMite can run the program on a limited basis. For example, if the code is ``answer = 40 + 2'' it will execute as expected. However, if the code is ``answer = "forty" + "two"'', it will fail during execution because the string-concatenation definition of the addition operator is not implemented. There is not yet a definitive list of supported features. The general rule is that nearly all of the arithmetic and logical operations on integers are supported. Only some of the operations on the remaining builtin types (Strings, Lists, Tuples, Dicts) are supported, and very few of Python's fancy features are implemented. To be more concrete on this matter, a well-known module is demonstrated.

The PyStone Benchmark Program (pystone.py) comes as a part of the standard Python 2.0 distribution. This program only needs two changes in order to run in PyMite.

When this module is parsed by PmImgCreator, line 37 returns one bytecode incompatibility. Line 37 reads ``from time import clock'' which is compiled to the unsupported bytecode IMPORT_FROM. The source line is changed to two lines: ``import time'' and ``clock = time.clock''. Now, PmImgCreator compiles and creates and image. When the image is interpreted, a runtime error occurs.

Line 251 uses the Python magic ``if __name__ == '__main__':'' to conditionally call the main() function. PyMite does not yet support the __name__ attribute, so this line is removed and the subsequent line is unindented so that main() is called unconditionally.

With these two changes made, pystone.py compiles to an image containing 4823 bytes. The image loads into the PyMite interpreter and executes properly until the target device's heap is exhausted and the interpreter halts.

In addition to simple scripts, PyMite is capable of running code which calls native library functions and controls the author's mobile robot platform. Despite this minor success, there is plenty of work remaining. Classes can be created, but inheritance does not work. The try/catch mechanism creates the necessary blocks of information, but raising and handling exceptions is not yet implemented. Heap memory is allocated using a hybrid best-or-nearest-fit policy and some deleted objects are reclaimed explicitly. The collector is designed and developed, but not completely tested. The list goes on. The author is resolving these needs on a priority basis.

Design

This section discusses the goals established when designing PyMite and what it took to meet these goals.

The goals of the PyMite interpreter are:

The goal of fitting within a fixed size environment is listed first because it is the most obvious and most restrictive constraint of this project.

A Python in Worm's Clothing

Most 8-bit microcontrollers are limited to 16-bit addressing. This means that only 64 KiB of memory is directly addressable. The sum total of addressable memory is divided among program memory and RAM in various ways depending on the target device's architecture. RAM is further divided between the interpreter's run-time requirements and PyMite's heap. Regardless of how memory is divided, 64 KiB is a very real and very tight boundary compared to the near limitless boundaries Python uses on a 32-bit PC with virtual memory.

Concerning size, there are two pieces of good news. The first is that some architectures have separate program and data memories, so there can be as many as 64 Ki addressable words in each memory. The second is that persistent memory can be extended with the addition of serial memories. This persistent memory could hold code images such as PyMite's library and the application.

Constraining for Size

In order to meet the 64 KiB limit, PyMite is written from scratch, rather than trimmed from the Python source tree. This decision allows all objects to be reimplemented and reduced in size. For example, in Python the Dict object uses a hash table in its implementation; but in PyMite, a segmented linked list (seglist) structure is used for its small size and simplicity. The seglist is also reused for the implementation of PyMite's List type. Using the seglist also reduces memory fragmentation by reusing identically sized segments.

By shrinking the objects and removing extraneous pointers, some of Python's dynamic features are sacrificed. For instance, if two integer variables are added via the BINARY_ADD bytecode, they will always be added via an internal function. This is different from Python where each object would be inspected for an __add__() method. The example above shows how the ability to overload the addition operator is lost in PyMite.

To date, there are no complex, long, or floating point data types or operations. Floating point might be added, but only after more important features such as exceptions and garbage collection are completed. Since PyMite is not finished, a complete list of unsupported features and operations is not available.

New Features

PyMite is not without new and novel features. A ``stackless'' frame implementation and native code lead the innovative features in PyMite.

In the Python community ``stackless'' has come to mean an implementation of the interpreter function that is decoupled from the C stack [2]. The term ``stackless'' comes from the fact that a non-stackless (stackful?) implementation consumes C stack space with each nested Python function. The C stack grows with every Python function call and Python objects can sometimes be found in C function arguments and return values. There are currently no plans for PyMite to support coroutines or generators like Tismer's Stackless, but having a stackless implementation leaves the door open. For now, PyMite's stackless implementation simply makes its RAM usage and threading model more compact.

The second new feature added to PyMite is its convenient method of adding native code to the application. In-line native code allows insertion of a compiled language into the Python code. PyMite does this by letting the programmer write C code inside the documentation string (docstring) of a Python function. The docstring is a triple-quoted string usually used to describe the purpose of the function. PyMite's size constraints eliminate using docstrings for introspection, so the author redesignated the purpose of this string. The contents of the docstring are largely ignored by the Python compiler. The image creator tool, PmImgCreator, extracts docstrings prefixed with the substring ``__NATIVE__\n'', reformats the source, and compiles the results into a native C module that must be linked with the PyMite executable. Native code is explained in greater detail in [3].

Implementation

This section gives a brief overview of how PyMite is implemented. The run-time datastructures are presented and the interpreter is explained. But first, some comments on portability.

Portability

The PyMite interpreter is written in ANSI C with Doxygen style comments[4]. Platform-specific extensions are written in gcc-compatible syntax. The author uses GCC compile to the desktop host and cross-compile to the target. The source code is written to be highly portable. With the introduction of native code, it is the author's goal to make the interpreter's source code completely portable, and place the platform-specific code in native libraries. It remains to be seen if 100% portability can be achieved.

PyMite is currently targeted to the Atmel AtMega103 8-bit microcontroller. This is the processor found on the author's mobile robotics circuit board, the MMB103. The AtMega103 has 128 KiB programming memory (arranged as 64 Ki words), 4 KiB SRAM and 4 KiB EEPROM.

Figure 1: PyMite's Target 8-bit Platform, the MMB103.
Target 8-bit platform circuit board.

Before exiting the topic of portability, it should be mentioned that PyMite currently compiles for Linux/x86 as well. Doing this changes the sizes of the run-time datastructures because pointers become 32-bit fields instead of 16. Aside from that, and the need to put all code images into RAM, PyMite can execute on an x86 running Linux. This configuration is used for testing and debugging.

Datastructures

PyMite has a set of datastructures that are the foundation of the interpreter. There are implicit structures for image objects and explicit structures for dynamic objects. The implicit structures are used to load a static image from memory into a dynamic structure in RAM. The explicit structures are used to build the run-time framework of the interpreter and represent the dynamic objects within the running program.

The implicit structures for images are not defined by a C structure, instead they are a convention used by PmImgCreator and PyMite's image loader system. There are seven implicit structures for None, Integer, Float, String, Tuple, CodeObject and NativeCodeObject. None is represented by a single null byte. Integer and Float share the same simple form. The remaining four--String, Tuple, CodeObject, and NativeCodeObject--are slightly more complex. These images are loaded into their corresponding dynamic structures, discussed next.

Figure 2: Diagrams of implicit structs
Diagrams of image structs.

The head of every datatype contains a two byte Object Descriptor (OD). The OD, in turn, contains size and type fields and two bits used by the heap management system. The size field is used by the memory system to assist with best-fit allocation. The type information is used throughout the interpreter to define the type of the object. Every PyMite object has an OD embedded in the head of its structure. The core objects are presented in order from simple to complex.

The None object is simply an OD with its type set to None. An Integer object is an OD follow by four bytes. The four bytes contain a signed integer value. Floating point objects are not yet supported and will not be discussed further. A String has an OD header, an unsigned byte representing the number of bytes in the string, followed by that many bytes containing the UTF-8 null-terminated string.

Figure 3: Diagrams of simple structures.
Diagrams of None, Int and String Objects.

The complex objects are Tuples, Lists and Dicts. They are called complex because they may contain other objects. Tuples are immutable objects whose size is predetermined. The tuple's structure is allocated with exactly enough memory for its contents. Lists and Dicts are mutable, dynamic objects. They are both implemented using segmented linked lists (seglist) to allow for varying content length. The Dict uses one seglist for its keys and one for its values.

Figure 4: Diagrams of complex structures.
Diagrams of Tuple, List and Dict Objects.

There are also structures for the objects that work behind the scenes. These are code objects (CO), functions and frames.

Figure 5: Diagrams of CO, Func, Frame structures.
Diagrams of CodeObj, Func and Frame Objects.

The Interpreter

Once the system is initialized and images are loaded into a CO, a function object is created for the root bytecode of the target module. This root function object is passed to the interpret function, interp(), where a frame is created and execution begins. The frame is the run-time representation of the function. The frame is responsible for maintaining state information during execution and when a nested function is called. Figure 6 shows how images, code objects, functions and frames link together to form the core organization of the interpreter.

Figure 6: Diagram of image, CO, function and frame in action.
Diagram of image, CO, function and frame in action.

The PyMite interpreter has the prototypical while-switch organization. Interpretation of bytecodes happens as long as the interpreter control value is positive. A control value of zero indicates proper exit; a negative value an error. The switch statement directs program flow based on the value of the bytecode. PyMite implements 64 of the 111 bytecodes in Python 2.0 as seen in Table 1. Some of the remaining bytecodes will be implemented as needed, others will not. For example, the slicing bytecodes might be implemented, but the five bytecodes involved in printing will not. Instead, PyMite will use a native library for printing. It is unlikely that the bytecodes CALL_FUNCTION_VAR, CALL_FUNCTION_KW, CALL_FUNCTION_VAR_KW, and EXTENDED_ARG, will be implemented anytime soon.


Table 1: Python Bytecodes Supported by PyMite.
BINARY_ADD BINARY_AND BINARY_DIVIDE BINARY_LSHIFT
BINARY_MODULO BINARY_MULTIPLY BINARY_OR BINARY_RSHIFT
BINARY_SUBSCR BINARY_SUBTRACT BINARY_XOR BREAK_LOOP
BUILD_CLASS BUILD_LIST BUILD_MAP BUILD_TUPLE
CALL_FUNCTION COMPARE_OP DELETE_SLICE+0 DELETE_SLICE+1
DELETE_SLICE+2 DUP_TOP DUP_TOPX FOR_LOOP
IMPORT_NAME INPLACE_ADD INPLACE_AND INPLACE_DIVIDE
INPLACE_LSHIFT INPLACE_MULTIPLY INPLACE_OR INPLACE_RSHIFT
INPLACE_SUBTRACT INPLACE_XOR JUMP_ABSOLUTE JUMP_FORWARD
JUMP_IF_FALSE JUMP_IF_TRUE LOAD_ATTR LOAD_CONST
LOAD_FAST LOAD_GLOBAL LOAD_LOCALS LOAD_NAME
MAKE_FUNCTION POP_BLOCK POP_TOP RETURN_VALUE
ROT_FOUR ROT_THREE ROT_TWO SET_LINENO
SETUP_LOOP SLICE+0 STOP_CODE STORE_ATTR
STORE_FAST STORE_GLOBAL STORE_SUBSCR UNARY_INVERT
UNARY_NEGATIVE UNARY_NOT UNARY_POSITIVE UNPACK_SEQUENCE


Future

There is plenty of work to be done on PyMite. Short term goals include completing the garbage collector and the exception system. Mid term goals include optimization work and creating an interactive interface. The long term goals involve growing a support community for PyMite and making periodic releases.

During the creation of PyMite several possible optimizations were discovered. Some, such as string caching, are implemented, but some are not. Optimizations that are under consideration are: renumbering and creating new bytecodes; using a goto-lookup structure for the interpreter; and using caching methods that are faster than linear lookups. Profiling information will determine which optimizations are included in PyMite.

Conclusion

PyMite successfully implements a flyweight interpreter that supports a subset of the features of the Python language. PyMite executes sample programs on a real 8-bit microcontroller using only 15 KiB of program memory and 4 KiB of RAM. Fitting the interpreter in such a size-limited device requires completely redesign the internal structures to reduce size and sacrificing of Python's fancier features. Some of the lost features are made up for by new features such as a stackless implementation and an easy method to create and call native code. PyMite is a work-in-progress and its features and abilities will increase with time.

Availability

PyMite is Copyright 2001 Dean W. Hall. All rights reserved. PyMite is distributed under the Artistic License [5]. PyMite releases can be downloaded from http://sourceforge.net/projects/thmonkeeproject/. Access to the Subversion repository is currently restricted.

Bibliography

1
Newton Research Labs, Inc. http://www.newtonlabs.com/ic/.

2
C. Tismer, http://www.stackless.com/.

3
D. Hall, PyMite Interpreter Allows Native Code in Python, http://sourceforge.net/projects/thmonkeeproject/.

4
D. van Heesch, Doxygen, http://www.doxygen.org/.

5
Open Source Initiative, Artistic License, http://www.opensource.org/licenses/artistic-license.php.