Интерпретатор языка Python, написанный на языке Python

Оригинал: A Python Interpreter Written in Python
Автор: Allison Kaptur
Дата публикации: July 12, 2016
Перевод: Н.Ромоданов
Дата перевода: февраль 2017 г.

Это пятая часть статьи "Интерпретатор языка Python, написанный на языке Python".
Перейти к началу.

Интерпретатор Byterun

Теперь у нас достаточно знаний, касающихся интерпретатора языка Python, с тем, чтобы можно было приступить к изучению интерпретатора Byterun.

В интерпретаторе Byterun есть четыре вида объектов:

• Класс VirtualMachine (виртуальная машина), который управляет структурой самого высокого уровня, в частности стеком вызовов фреймов, а также хранит отображение инструкций в операции. Это более сложный вариант объекта Intepreter, который был описан выше.
• Класс Frame (фрейм). Каждый экземпляр класса Frame имеет один объект кода и управляет несколькими другими необходимыми битами состояния, в частности, глобальными и локальными пространствами имен, ссылками на вызывающий фрейм и на последнюю инструкцию байт-кода, которая была выполнена.
• Класс /code>Function (Функция), который будет использоваться вместо реальных функций языка Python. Напомним, что вызов функции создает новый фрейм в интерпретаторе. Мы реализуем класс Function так, что можем управлять созданием новых кадров.
• Класс Block (блок), который просто оборачивает три атрибута блоков. Конкретные деталии реализации блоков не столь важны при реализации интерпретатора языка Python, так что мы на них не будем тратить много времени, но благодаря им интерпретатор Byterun может запускать реальный код на языке Python.

Класс VirtualMachine

При запуске программы каждый раз создается только один экземпляр класса VirtualMachine, т. е. у нас только один интерпретатор языка Python. В классе VirtualMachine хранится стек вызовов, исключительное состояние и возвращаемые значения в случаях, если они передаются между фреймами. Точка входа для выполнения кода является методом run_code, который получает в качестве аргумента объект со скомпилированным кодом. Работа начинается с настройки и запуска фрейма. Этот фрейм может создавать другие фреймы; по мере выполнения программы стек вызовов будет увеличиваться и уменьшаться. Когда, в конце концов, управление будет возвращено в первый фрейм, выполнение кода завершается.

class VirtualMachineError(Exception):
    pass

class VirtualMachine(object):
    def __init__(self):
        self.frames = []   # Стек вызовов фреймов.
        self.frame = None  # Текущий фрейм.
        self.return_value = None
        self.last_exception = None

    def run_code(self, code, global_names=None, local_names=None):
        """ Точка входа выполнения кода с помощью виртуальной машины."""
        frame = self.make_frame(code, global_names=global_names, 
                                local_names=local_names)
        self.run_frame(frame)

Класс Frame

Далее мы напишем класс Frame. Фрейм представляет собой коллекцию атрибутов, не имеющую методов. Как уже было упомянуто выше, среди атрибутов есть объект с кодом, созданным компилятором, локальное, глобальное и встроенное в язык пространство имен, ссылка на предыдущий фрейм, стек данных, стек блоков и последняя выполненная команда. Поскольку в языке Python в разных модулях по-разному используется пространство имен, нам для того, чтобы до него добраться, потребуется выполнить некоторые дополнительные действия, но это в частности никак не влияют на работу виртуальной машины.

class Frame(object):
    def __init__(self, code_obj, global_names, local_names, prev_frame):
        self.code_obj = code_obj
        self.global_names = global_names
        self.local_names = local_names
        self.prev_frame = prev_frame
        self.stack = []
        if prev_frame:
            self.builtin_names = prev_frame.builtin_names
        else:
            self.builtin_names = local_names['__builtins__']
            if hasattr(self.builtin_names, '__dict__'):
                self.builtin_names = self.builtin_names.__dict__

        self.last_instruction = 0
        self.block_stack = []

Далее, мы добавим к виртуальной машине возможность обрабатывать фреймы. Для фреймов используются три вспомогательные функции: одна - для создания новых фреймов (которая отвечает за выбор пространства имен для нового фрейма) и по одной функции для того, чтобы поместить фрейм в стек и чтобы вытолкнуть его из стека. Четвертая функция, run_frame, выполняет основную работу в тех случаях, когда фрейм передается на исполнение. В ближайшее время мы к этому вернемся.

class VirtualMachine(object):
    [... snip ...]

    # Работа с фреймом
    def make_frame(self, code, callargs={}, global_names=None, local_names=None):
        if global_names is not None and local_names is not None:
            local_names = global_names
        elif self.frames:
            global_names = self.frame.global_names
            local_names = {}
        else:
            global_names = local_names = {
                '__builtins__': __builtins__,
                '__name__': '__main__',
                '__doc__': None,
                '__package__': None,
            }
        local_names.update(callargs)
        frame = Frame(code, global_names, local_names, self.frame)
        return frame

    def push_frame(self, frame):
        self.frames.append(frame)
        self.frame = frame

    def pop_frame(self):
        self.frames.pop()
        if self.frames:
            self.frame = self.frames[-1]
        else:
            self.frame = None

    def run_frame(self):
        pass
        # Мы вскоре сюда возвратимся

Класс Function

Реализация класса Function слегка запутана, но большинство деталей не имеют решающего значения для понимания работы интерпретатора. Важно отметить, что при вызове функции вызывается метод __call__, который создает новый объект Frame и запускает его на исполнение.

class Function(object):
    """
    Создается реальный объект function, в котором есть все, что нужно интерпретатору.
    """
    __slots__ = [
        'func_code', 'func_name', 'func_defaults', 'func_globals',
        'func_locals', 'func_dict', 'func_closure',
        '__name__', '__dict__', '__doc__',
        '_vm', '_func',
    ]

    def __init__(self, name, code, globs, defaults, closure, vm):
        """Для того, чтобы понять, как работает интерпретатор, 
		вам не нужно глубоко вдаваться в подробности."""
        self._vm = vm
        self.func_code = code
        self.func_name = self.__name__ = name or code.co_name
        self.func_defaults = tuple(defaults)
        self.func_globals = globs
        self.func_locals = self._vm.frame.f_locals
        self.__dict__ = {}
        self.func_closure = closure
        self.__doc__ = code.co_consts[0] if code.co_consts else None

        # Иногда нам нужно использовать настоящую функцию языка Python.  
	# Этот фрагмент кода для таких случаев.
        kw = {
            'argdefs': self.func_defaults,
        }
        if closure:
            kw['closure'] = tuple(make_cell(0) for _ in closure)
        self._func = types.FunctionType(code, globs, **kw)

    def __call__(self, *args, **kwargs):
        """Когда функция вызывается,то создается новый фрейм, который передается на исполнение."""
        callargs = inspect.getcallargs(self._func, *args, **kwargs)
        # Используйте callargs для отображения аргументов 
	# значения будут переданы в новый фрейм.
        frame = self._vm.make_frame(
            self.func_code, callargs, self.func_globals, {}
        )
        return self._vm.run_frame(frame)

def make_cell(value):
    """Создает реальное замыкание на языке Python и использует его."""
    # Спасибо Алексу Гейнору (Alex Gaynor) за помощь в 
	# написании этого куска кода.
    fn = (lambda x: lambda: x)(value)
    return fn.__closure__[0]

Затем, вернувшись обратно в объект VirtualMachine, мы добавим несколько вспомогательных методов для работы со стеком данных. Байт-код, который обрабатывает этот стек, всегда работает со стеком данных текущего фрейма. Это сделает нашу реализацию инструкций POP_TOP, LOAD_FAST и всех других инструкций, которые работают со стеком, более удобной для чтения.

class VirtualMachine(object):
    [... snip ...]

    # Работа со стеком данных
    def top(self):
        return self.frame.stack[-1]

    def pop(self):
        return self.frame.stack.pop()

    def push(self, *vals):
        self.frame.stack.extend(vals)

    def popn(self, n):
        """Выталкивает из стека указанное количество элементов.
        Будет возвращен список из `n` значений, первым значением будет то, 
	которое в стеке находилось глубже других.
        """
        if n:
            ret = self.frame.stack[-n:]
            self.frame.stack[-n:] = []
            return ret
        else:
            return []

Прежде, чем мы перейдем к исполнению фрейма, нам потребуются еще два метода.

Первый метод, parse_byte_and_args, берет байт-код, проверяет, есть ли у него аргументы, и анализирует их, если таковые имеются. Этот метод также обновляет атрибут фрейма last_instruction, который является ссылкой на последнюю выполненную инструкцию. Длина одной инструкции равна одному байту в случае, если у команды нет аргумента, и трем байтом в случае, если у нее есть аргумент; последние два байта являются аргументом. Смысл аргумента каждой инструкции зависит от того, какая это инструкция. Например, как уже упоминалось выше, для инструкции POP_JUMP_IF_FALSE, аргументом инструкции является целью, куда произойдет переход. Для инструкции BUILD_LIST, это количество элементов в списке. Для инструкции LOAD_CONST, это указатель в списке констант.

Некоторые инструкции используют в качестве своих аргументов обычные числа. Для других, виртуальная машина должна выполнить некоторые действия для того, чтобы выяснить, что означают аргументы. Модуль dis, который есть в стандартной библиотеке, выдает описание, объясняющее, какие используются аргументы и что они означают; благодаря этому наш код будет выглядеть более компактным и более понятным. Например, список dis.hasname говорит нам о том, что аргументы в инструкциях LOAD_NAME, IMPORT_NAME, LOAD_GLOBAL и еще в девяти других инструкциях означают одно и тоже: для этих инструкций, аргумент представляет собой указатель на список имен в объекте кода.

class VirtualMachine(object):
    [... snip ...]

    def parse_byte_and_args(self):
        f = self.frame
        opoffset = f.last_instruction
        byteCode = f.code_obj.co_code[opoffset]
        f.last_instruction += 1
        byte_name = dis.opname[byteCode]
        if byteCode >= dis.HAVE_ARGUMENT:
            # указатель на байт-код
            arg = f.code_obj.co_code[f.last_instruction:f.last_instruction+2]  
            f.last_instruction += 2   # указатель на инструкцию
            arg_val = arg[0] + (arg[1] * 256)
            if byteCode in dis.hasconst:   # Поиск константы
                arg = f.code_obj.co_consts[arg_val]
            elif byteCode in dis.hasname:  # Поиск имени
                arg = f.code_obj.co_names[arg_val]
            elif byteCode in dis.haslocal: # Поиск локального имени
                arg = f.code_obj.co_varnames[arg_val]
            elif byteCode in dis.hasjrel:  # Вычисление относительного перехода
                arg = f.last_instruction + arg_val
            else:
                arg = arg_val
            argument = [arg]
        else:
            argument = []

        return byte_name, argument

Следующим методом является метод диспетчеризации dispatch, который ищет операции для заданной инструкции и выполняет их. В интерпретаторе CPython, эта диспетчеризация осуществляется с помощью гигантского переключателя, размер которого 1500 строк! К счастью, поскольку мы пишем интерпретатор для языка Python, наш результат может быть более компактным. Мы для каждого однобайтового имени определим метод, а затем для поиска воспользуемся методом getattr. Точно также, как и в нашем игрушечном интерпретаторе, который мы рассматривали выше, если наша инструкция называется FOO_BAR, то соответствующий метод будет называться byte_FOO_BAR. На данный момент, мы будем считать содержимое этих методов черным ящиком. Каждый метод будет возвращать либо None, либо строку с названием why, которая представляет собой дополнительную информацию о состоянии интерпретатора, которая необходима в некоторых случаях. Такие возвращаемые значения методов для отдельных инструкций используются только в качестве дополнительных индикаторов состояния интерпретатора - не путайте их со значениями, возвращаемыми из исполняемых фреймов.

class VirtualMachine(object):
    [... snip ...]

    def dispatch(self, byte_name, argument):
        """ Привязка бата-имени к соответствующим методам.
        Перехват и инициация исключений происходит в виртуальной машине."""

        # Когда позже стек блоков будет разматываться,
        # нам нужно будет помнить, почему мы это делаем.
        why = None
        try:
            bytecode_fn = getattr(self, 'byte_%s' % byte_name, None)
            if bytecode_fn is None:
                if byte_name.startswith('UNARY_'):
                    self.unaryOperator(byte_name[6:])
                elif byte_name.startswith('BINARY_'):
                    self.binaryOperator(byte_name[7:])
                else:
                    raise VirtualMachineError(
                        "unsupported bytecode type: %s" % byte_name
                    )
            else:
                why = bytecode_fn(*argument)
        except:
            # Обработка исключения, которое возникло при выполнении операции.
            self.last_exception = sys.exc_info()[:2] + (None,)
            why = 'exception'

        return why

    def run_frame(self, frame):
        """Выполнение фрейма до тех пор, пока не будет возвращено управление.
        Возникает исключение, возвращаемое значение получено.
        """
        self.push_frame(frame)
        while True:
            byte_name, arguments = self.parse_byte_and_args()

            why = self.dispatch(byte_name, arguments)

            # Deal with any block management we need to do
            while why and frame.block_stack:
                why = self.manage_block_stack(why)

            if why:
                break

        self.pop_frame()

        if why == 'exception':
            exc, val, tb = self.last_exception
            e = exc(val)
            e.__traceback__ = tb
            raise e

        return self.return_value

Класс Block

Прежде, чем реализовывать методы для каждой инструкции, мы кратко рассмотрим блоки. Блок используется в определенных случаях для управления последовательностью действий, в частности при обработке исключений и зацикливании. На блок возлагается ответственность проверять, что после того, как выполнение операции будет закончено, стек данных будет находиться в соответствующем состоянии. Например, в случае цикла все то время, пока работает цикл, в стеке остается специальный объект итератора, но он выталкивается из стека в случае, когда цикл будет завершен. Интерпретатор должен следить за тем, продолжается ли цикл или он уже завершен.

Чтобы следить за этой дополнительной информацией, интерпретатор устанавливает флаг, который указывает его состояние. Мы реализуем этот флаг в виде переменной, называемой why, значение которой может быть None или одним из строковых значений "continue" ("продолжено"), "break" ("прервано"), "exception" ("исключение") или "return" ("возврат"). Оно указывает на то, какие действия со стеком блоков и стеком данных нужно выполнить. Если вернуться к примеру с итератором, то если на вершина стека блоков находится блок-цикл loop, а код why содержит значение continue, то объект итератора должен оставаться в стеке данных, но если код why будет содержать значение break, то он должен быть вытолкнут.

Конкретные особенности работы с блоками довольно запутаны, и мы на них не будем больше тратить времени, а заинтересованным читателям рекомендуем внимательно посмотреть код.

Block = collections.namedtuple("Block", "type, handler, stack_height")

class VirtualMachine(object):
    [... snip ...]

    # Работа со стеком блоков
    def push_block(self, b_type, handler=None):
        stack_height = len(self.frame.stack)
        self.frame.block_stack.append(Block(b_type, handler, stack_height))

    def pop_block(self):
        return self.frame.block_stack.pop()

    def unwind_block(self, block):
        """Размотка значений из стека данных, соответствующих данному блоку."""
        if block.type == 'except-handler':
            # The exception itself is on the stack as type, value, and traceback.
            offset = 3  
        else:
            offset = 0

        while len(self.frame.stack) > block.level + offset:
            self.pop()

        if block.type == 'except-handler':
            traceback, value, exctype = self.popn(3)
            self.last_exception = exctype, value, traceback

    def manage_block_stack(self, why):
        """ """
        frame = self.frame
        block = frame.block_stack[-1]
        if block.type == 'loop' and why == 'continue':
            self.jump(self.return_value)
            why = None
            return why

        self.pop_block()
        self.unwind_block(block)

        if block.type == 'loop' and why == 'break':
            why = None
            self.jump(block.handler)
            return why

        if (block.type in ['setup-except', 'finally'] and why == 'exception'):
            self.push_block('except-handler')
            exctype, value, tb = self.last_exception
            self.push(tb, value, exctype)
            self.push(tb, value, exctype) # yes, twice
            why = None
            self.jump(block.handler)
            return why

        elif block.type == 'finally':
            if why in ('return', 'continue'):
                self.push(self.return_value)

            self.push(why)

            why = None
            self.jump(block.handler)
            return why
        return why

Перейти к следующей части статьи.

Перейти к началу статьи.

---

---

---