Running (a subset) of python on the BBC Micro

Yes, the one from the 80's. Yes, I'm a little mad.

Q Misell @TheEnbyperor

Last year

Python on a Beeb?!?!?! You're joking right?

5.0MiB

32KiB or 0.03125MiB (~16KiB usable)

MicroPython?

How does python actually work?

Interpreted

BASIC

¯\_(ツ)_/¯

Python

Compiled

C

Sophie Wilson


                    >>> import dis
                    >>> dis.dis("40+2")
                      1           0 LOAD_CONST               0 (40)
                                  2 LOAD_CONST               1 (2)
                                  4 BINARY_ADD
                                  6 RETURN_VALUE
                    >>>
                

The python virtual machine

Internal representation


                    >>> import dis
                    >>> code = compile("40+2", '', 'eval')
                    >>> list(code.co_code)
                    [100, 0, 100, 1, 23, 0, 83, 0]
                    >>> code.co_consts
                    (40, 2)
                    >>> dis.dis(code)
                      1           0 LOAD_CONST               0 (40)
                                  2 LOAD_CONST               1 (2)
                                  4 BINARY_ADD
                                  6 RETURN_VALUE
                    >>>
                

The virtual machine stack

| Instruction | Stack | | |:---------------:|:-----:|:-:| | *START* | | | | LOAD_CONST (40) | 40 | | | LOAD_CONST (2) | 40 | 2 | | BINARY_ADD | 42 | | | RETURN_VALUE | | |

Implementing a virtual machine

Storing the bytecode


                    typedef struct {
                      uint8_t insts[8]; // Fixed size
                    } Code;
                

                    typedef struct {
                      uint8_t insts[]; // Invalid - incomplete type as struct member
                    } Code;
                

Dynamic arrays


                    typedef struct {
                      unsigned int count;
                      unsigned int capacity;
                    } ArrayMeta;

                    typedef struct {
                      ArrayMeta meta;
                      uint8_t* data;
                    } DynamicArray;
                

                    DynamicArray array;
                    uint8_t val = array.data[3];
                

                    void* reallocate(void* previous, size_t newSize) {
                      if (newSize == 0) {
                        free(previous);
                        return NULL;
                      }

                      return realloc(previous, newSize);
                    }

                    void writeArray(DynamicArray* array, size_t elmSize,
                                    void *value) {
                      if (array->meta.capacity < array->meta.count + 1) {
                        int oldCapacity = array->meta.capacity;
                        array->meta.capacity = growCapacity(oldCapacity);
                        array->data =
                          reallocate(array->data, array->meta.capacity * elmSize);
                      }

                      size_t offset = array->meta.count * elmSize;
                      for (unsigned int i = 0; i < elmSize; ++i)
                        array->data[offset+i] = *(((uint8_t *)value)+i);
                      array->meta.count++;
                    }
                

                    > python main.c memory.c
                    
... TypeError: realloc is not defined

A memory allocator

danluu.com/malloc-tutorial/

Running the VM code

From: Python/ceval.c

                    switch (opcode) {
                        TARGET(NOP)
                            FAST_DISPATCH();

                        TARGET(LOAD_FAST) {
                            PyObject *value = GETLOCAL(oparg);
                            if (value == NULL) {
                                ...
                                goto error;
                            }
                            Py_INCREF(value);
                            PUSH(value);
                            FAST_DISPATCH();
                        }

                        PREDICTED(LOAD_CONST);
                        TARGET(LOAD_CONST) {
                            PyObject *value = GETITEM(consts, oparg);
                            Py_INCREF(value);
                            PUSH(value);
                            FAST_DISPATCH();
                    ...
                

                    uint8_t instruction = readByte(vm);

                    if (instruction == OP_CONSTANT) {
                        struct Value *constant = readConstant(vm);
                        pushStack(&vm->stack, constant);
                    } else if (instruction == OP_NEGATE) {
                        valuePtr = peek(vm, 0);
                        if (!isInt(valuePtr)) {
                            runtimeError(vm, "Operand must be a number.");
                            return INTERPRET_RUNTIME_ERROR;
                        }
                        intVal(-asInt(valuePtr), valuePtr);
                    } else if (instruction == OP_ADD) {
                        if (isString(peek(vm, 0)) && isString(peek(vm, 1))) {
                            concatenate(vm);
                        } else if (isInt(peek(vm, 0)) && isInt(peek(vm, 1))) {
                            valuePtr = peek(vm, 1);
                            popStack(&vm->stack, &value);
                            a = asInt(valuePtr);
                            b = asInt(&value);
                            intVal(a + b, valuePtr);
                    ...
                

Dynamic typing with tagged unions


                    typedef uint8_t ValueType;
                    #define VAL_NONE 0
                    #define VAL_INT 1
                    #define VAL_BOOL 2
                    #define VAL_OBJ 3

                    typedef struct {
                        ValueType type;
                        union {
                            bool boolean;
                            int number;
                            struct Obj *obj;
                        } as;
                    } Value;
                

Variable length objects


                    struct sObj {
                        ObjType type;
                        Obj* next;
                    };

                    typedef struct {
                        struct sObj object;
                        int length;
                        char *chars;
                    } ObjString;
                

Side note: Not enough memory

Parsing python to the bytecode

A lexer


                    typedef struct {
                      TokenType type;
                      const char* start;
                      int length;
                      int line;
                    } Token;
                

                            40 + 2
                        
| Token type | Value | |:------------:|:-----:| | TOKEN_NUMBER | 40 | | TOKEN_PLUS | + | | TOKEN_NUMBER | 2 |

A Pratt parser


                            typedef struct {
                              ParseFunc prefix;
                              ParseFunc suffix;
                              Precedence precedence;
                            } ParseRule;
                            struct ParseRule rules[61];
                        
Image credit: Bob Nystrom (craftinginterpreters.com)

Thank you

Any questions?

Q Misell @TheEnbyperor