[Перевод] Жизненный цикл кода на Python – модель выполнения CPython01.03.2019 15:47

Всем привет! Наступила весна, а это значит, что до запуска курса «Разработчик Python» остается меньше месяца. Именно этому курсу и будет посвящена наша сегодняшняя публикация.

Задачи:
— Узнать о внутреннем устройстве Python;
— Понять принципы построения абстрактного синтаксического дерева (AST);
— Писать более эффективный код по времени и по памяти.

Предварительные рекомендации:
— Базовое понимания работы интерпретатора (AST, токены и т.д.).
— Знание Python.
— Базовое знание С.

batuhan@arch-pc  ~/blogs/cpython/exec_model  python --version
Python 3.7.0

Модель выполнения CPython

Python компилируемый и интерпретируемый язык. Таким образом компилятор Python генерирует байткоды, а интерпретатор исполняет их. В ходе статьи мы рассмотрим следующие вопросы:

• Парсинг и токенизация:
• Трансформация в AST;
• Граф потока управления (CFG);
• Байткод;
• Выполнение на виртуальной машине CPython

.

Парсинг и токенизация.
Грамматика.

Грамматика определяет семантику языка Python. Она также полезна в указании способа, котором парсер должен интерпретировать язык. Грамматика Python использует синтаксис подобный расширенной форме Бэкуса-Наура. Он имеет свою собственную грамматику для переводчика с исходного языка. Вы можете найти файл грамматики в директории «cpython/Grammar/Grammar».
Далее приведен пример грамматики,

batuhan@arch-pc  ~/cpython/Grammar   master  grep "simple_stmt" Grammar | head -n3 | tail -n1
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE

Простые выражения содержат маленькие выражения и скобки, а заканчивается команда новой строкой. Маленькие выражения выглядят как список выражений, которые импортируют…
Какие-то другие выражения:)

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |
             import_stmt | global_stmt | nonlocal_stmt | assert_stmt)
...
del_stmt: 'del' exprlist
pass_stmt: 'pass'
flow_stmt: break_stmt | continue_stmt | return_stmt | raise_stmt | yield_stmt
break_stmt: 'break'
continue_stmt: 'continue'

Токенизация (Лексический разбор)

Токенизация — это процесс получения текстового потока данных и разбиения на токены значащих (для интерпретатора) слов с дополнительными метаданными (например, где токен начинается и кончается, и каково строковое значение этого токена).

Токены

Токен — это заголовочный файл, содержащий определения всех токенов. Всего в Python 59 типов токенов (Include/token.h).
Ниже приведен пример некоторых из них,

#define NAME            1
#define NUMBER          2
#define STRING          3
#define NEWLINE         4
#define INDENT          5
#define DEDENT          6

Их вы видите, если разбиваете на токены какой-то код на Python.

Токенизация с помощью CLI

Здесь представлен файл tests.py

def greetings(name: str):
    print(f"Hello {name}")

greetings("Batuhan")

Дальше его мы токенезируем с помощью команды python -m tokenize и на выходе получаем следующее:

batuhan@arch-pc  ~/blogs/cpython/exec_model  python -m tokenize tests.py
0,0-0,0:            ENCODING       'utf-8'        
...       
2,0-2,4:            INDENT         '    '         
2,4-2,9:            NAME           'print'        
...        
4,0-4,0:            DEDENT         ''             
...        
5,0-5,0:            ENDMARKER      ''

Здесь номера (например 1,4–1,13) показывают, где токен начался и где он закончился. Токен кодирования (encoding token) — это всегда самый первый токен, который мы получаем. Он дает информацию о кодировке исходного файла и если с ней есть какие-то проблемы, то интерпретатор вызывает exception.

Токенизация с помощью tokenize.tokenize

Если нужно разбить на токены файл из вашего кода, вы можете использовать модуль tokenize из stdlib.

>>> with open('tests.py', 'rb') as f:             
...     for token in tokenize.tokenize(f.readline):
...        print(token)
... 
TokenInfo(type=57 (ENCODING), string='utf-8', start=(0, 0), end=(0, 0), line='')
...
TokenInfo(type=1 (NAME), string='greetings', start=(1, 4), end=(1, 13), line='def greetings(name: str):\n')
...
TokenInfo(type=53 (OP), string=':', start=(1, 24), end=(1, 25), line='def greetings(name: str):\n')
...

Тип токена — это его id в заголовочном файле token.h. String– это значение токена. Start и End показывают, где токен начинается и заканчивается соответственно.
В других языках блоки обозначаются скобками или операторами begin/end, но в Python используются отступы и разные уровни. INDENT и DEDENT токены и указывают на отступы. Эти токены нужны для построения реляционных деревьев синтаксического анализа и/или абстрактных синтаксических деревьев.

Генерация парсера

Генерация парсера –процесс, который генерирует парсер по заданной грамматике. Генераторы парсера известны под названием PGen. В Cpython есть два генератора парсера. Один — оригинальный (Parser/pgen) и один переписанный на python (/Lib/lib2to3/pgen2)

«Оригинальный генератор был первым кодом, который я написал для Python»
-Guido

Из вышеприведенной цитаты становится ясно, что pgen — самая важная вещь в языке программирования. Когда вы вызываете pgen (в Parser/pgen) он генерирует заголовочный файл и С-файл (сам парсер). Если вы посмотрите на сгенерированный код на С, он может показаться бессмысленным, поскольку его осмысленный вид — дело необязательное. Он содержит множество статических данных и структур. Дальше постараемся пояснить его основные компоненты.

DFA (Определенный конечный автомат)

Парсер определяет один DFA для каждого нетерминала. Каждый DFA определяется как массив состояний.

static dfa dfas[87] = {
    {256, "single_input", 0, 3, states_0,
"\004\050\340\000\002\000\000\000\012\076\011\007\262\004\020\002\000\300\220\050\037\202\000"},
    ...
    {342, "yield_arg", 0, 3, states_86,
     "\000\040\200\000\002\000\000\000\000\040\010\000\000\000\020\002\000\300\220\050\037\000\000"},
};

Для каждого DFA существует стартовый набор, который показывает с каких токенов может начинаться специальный нетерминал.

Состояние

Каждое состояние определяется массивом переходов/ребер (arcs).

static state states_86[3] = {
    {2, arcs_86_0},
    {1, arcs_86_1},
    {1, arcs_86_2},
};

Переходы (arcs)

В каждом массиве переходов есть два числа. Первый номер — это название перехода (arc label), он относится к номеру символа. Второе число — это точка назначения.

static arc arcs_86_0[2] = {
    {77, 1},
    {47, 2},
};
static arc arcs_86_1[1] = {
    {26, 2},
};
static arc arcs_86_2[1] = {
    {0, 2},
};

Названия (labels)
Это специальная таблица, которая соотносит id символа с названием перехода.

static label labels[177] = {
    {0, "EMPTY"},
    {256, 0},
    {4, 0},
    ...
    {1, "async"},
    {1, "def"},
    ...
    {1, "yield"},
    {342, 0},
};

Цифра 1 соответствует всем идентификаторам. Таким образом каждый из них получает разные названия перехода даже если они все имеют одинаковое id символа.

Простой пример:

Допустим, у нас есть код, который выводит «Hi» если 1 — верно:

if 1: print('Hi')

Парсер считает этот код как single_input.

single_input: NEWLINE | simple_stmt | compound_stmt NEWLINE

Тогда наше дерево синтаксического анализа начинается с корневого узла разового ввода.

И значение нашего DFA (single_input) получается равным 0.

static dfa dfas[87] = {
    {256, "single_input", 0, 3, states_0,
"\004\050\340\000\002\000\000\000\012\076\011\007\262\004\020\002\000\300\220\050\037\202\000"}
    ...
}

Это будет выглядеть следующим образом:

static arc arcs_0_0[3] = {
    {2, 1},
    {3, 1},
    {4, 2},
};
static arc arcs_0_1[1] = {
    {0, 1},
};
static arc arcs_0_2[1] = {
    {2, 1},
};
static state states_0[3] = {
    {3, arcs_0_0},
    {1, arcs_0_1},
    {1, 

arcs_0_2},
};

Здесь arc_0_0  состоит из трех элементов. Первый — это NEWLINE, второй — simple_stmt, и последний — compound_stmt.

Имея начальный набор simple_stmt можно заключить, что simple_stmt не может начинаться с if. Однако даже если if — это не новая строка, то compound_stmt все равно может начинаться с if. Таким образом мы переходим с последнему arc ({4;2}) и добавляем узел compound_stmt к дереву синтаксического анализа и перед тем, как перейти к номеру 2, переключаемся на новый DFA. Мы получаем обновленное дерево синтаксического анализа:

Новый DFA парсит составные высказывания (compound statements).

compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated | async_stmt

И у нас получается следующее:

static arc arcs_39_0[9] = {
    {91, 1},
    {92, 1},
    {93, 1},
    {94, 1},
    {95, 1},
    {19, 1},
    {18, 1},
    {17, 1},
    {96, 1},
};
static arc arcs_39_1[1] = {
    {0, 1},
};
static state states_39[2] = {
    {9, arcs_39_0},
    {1, arcs_39_1},
};

Только первый переход может начинаться с if. Мы получаем обновленное дерево синтаксического анализа.

Дальше мы снова меняем DFA и следующее DFA парсит if«ы.

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

В итоге мы получаем единственный переход с обозначением 97. Он совпадает с if токеном.

static arc arcs_41_0[1] = {
    {97, 1},
};
static arc arcs_41_1[1] = {
    {26, 2},
};
static arc arcs_41_2[1] = {
    {27, 3},
};
static arc arcs_41_3[1] = {
    {28, 4},
};
static arc arcs_41_4[3] = {
    {98, 1},
    {99, 5},
    {0, 4},
};
static arc arcs_41_5[1] = {
    {27, 6},
};
static arc arcs_41_6[1] = {
    {28, 7},
};
...

Когда мы переключаемся к следующему состоянию, оставаясь в том же самом DFA, следующий arcs_41_1 имеет также только один переход. Это справедливо для тестового нетерминала. Он должен начинаться с номера (например, 1).

В arc_41_2 есть только один переход, который получает токен двоеточие (:).

Так мы получаем набор, который может начинаться с печатного значения (print statement). Наконец, переходим к arcs_41_4. Первый переход в наборе — это выражение elif, второй — else и третий для последнего состояния. И мы получаем финальный вид дерева синтаксического анализа.

Интерфейс Python для парсера.

Python позволяет редактировать дерево синтаксического анализа для выражений, с помощью модуля, который называется parser.

>>> import parser
>>> code = "if 1: print('Hi')"

Можно сгенерировать конкретное синтаксическое дерево (Concrete Syntax Tree, CST) с помощью parser.suite.

>>> parser.suite(code).tolist()
[257, [269, [295, [297, [1, 'if'], [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [2, '1']]]]]]]]]]]]]]]], [11, ':'], [304, [270, [271, [272, [274, [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [1, 'print']], [326, [7, '('], [334, [335, [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [3, "'Hi'"]]]]]]]]]]]]]]]]]], [8, ')']]]]]]]]]]]]]]]]]]], [4, '']]]]]], [4, ''], [0, '']]

Выходным значением будет вложенный список. Каждый список в структуре имеет 2 элемента. Первый — это id символа (0–256 — терминалы, 256+ — нетерминалы) и второй — это строка токенов для терминала.  

Абстрактное синтаксическое дерево

На самом деле абстрактное синтаксическое дерево (AST) — это структурное представление исходного кода в виде дерева, где каждая вершина обозначает различные типы конструкций языка (выражение, переменную, оператор и т.п.)

Что такое дерево?

Дерево — это структура данных, которая имеет корневую вершину, как начальную точку. Корневая вершина опускается ветвями (переходами) вниз к другим вершинам. Каждая вершина, кроме корневой, имеет одну уникальную родительскую вершину.
Между абстрактным синтаксическим деревом и деревом синтаксического анализа есть определенная разница.

Справа находится дерево синтаксического анализа выражения 2×7+3. Это буквально один к одному изображение исходного кода в виде дерева. На нем видны все выражения, слагаемые и значения. Однако такое изображение слишком сложно для простого кусочка кода, поэтому мы имеем возможность просто убрать все синтаксические выражения, которые мы должны были определять в коде для проведения вычислений.
Такое упрощенное дерево называется абстрактным синтаксическим деревом (AST). Слева на рисунке изображено именно оно для того же самого кода. Все синтаксические выражения были отброшены для упрощения понимания, но нужно помнить о том, что была потеряна определенная информация.

Пример

Python предлагает встроенный AST модуль для работы с AST. Для генерации кода из AST деревьев можно использовать сторонние модули, например Astor.
Для примера рассмотрим тот же код, что и ранее.

>>> import ast
>>> code = "if 1: print('Hi')"

Для получения AST мы используем метод ast.parse.

>>> tree = ast.parse(code)
>>> tree
<_ast.Module object at 0x7f37651d76d8>

Попробуйте использовать метод ast.dump для получения более читаемого абстрактного синтаксического дерева.

>>> ast.dump(tree)
"Module(body=[If(test=Num(n=1), body=[Expr(value=Call(func=Name(id='print', ctx=Load()), args=[Str(s='Hi')], keywords=[]))], orelse=[])])"

AST в принципе считается более наглядным и удобным для понимания, чем дерево синтаксического анализа.

Граф потока управления (Control Flow Graf, CFG)

Графы потока управления — это направленные графы, которые моделируют поток программы, используя базовые блоки, которые содержат промежуточное представление.
Обычно CFG — это предыдущий шаг перед получением выходных значений кода. Код генерируется напрямую из базовых блоков с помощью обратного поиска в глубину в CFG, начиная от вершин.

Байткод

Байткод на Python — это промежуточный набор инструкций, которые работают на виртуальной машине Python«a. Когда вы запускаете исходный код, Python создает директорию, которая называется __pycache__. Она хранит скомпилированный код для того, чтобы сберечь время в случае перезапуска компиляции.
Рассмотрим простую функцию на Python в func.py.

def say_hello(name: str):
    print("Hello", name)
    print(f"How are you {name}?")

>>> from func import say_hello
>>> say_hello("Batuhan")
Hello Batuhan
How are you Batuhan?

Тип объекта say_hello — это функция.

>>> type(say_hello)

Она имеет атрибут __code__.

>>> say_hello.__code__

>>> import ast
>>> code = """
... def say_hello(name: str):
...     print("Hello", name)
...     print(f"How are you {name}?")
... say_hello("Batuhan")
... """
>>> tree = ast.parse(code, mode='exec')
>>> code = compile(tree, '', mode='exec')
>>> type(code)

>>> code.co_name
''
>>> say_hello.__code__.co_name
'say_hello'

>>> say_hello.__code__.co_varnames
('name',)

>>> say_hello.__code__.co_consts
(None, 'Hello', 'How are you ', '?')

>>> bytecode = say_hello.__code__.co_code
>>> bytecode
b't\x00d\x01|\x00\x83\x02\x01\x00t\x00d\x02|\x00\x9b\x00d\x03\x9d\x03\x83\x01\x01\x00d\x00S\x00'

>>> type(bytecode)

>>> ord('t')
116

>>> assert bytecode[0] == ord('t')

>>> dis.opname[ord('t')]
'LOAD_GLOBAL'

>>> def multiple_it(a: int):
...     if a % 2 == 0:
...         return 0
...     return a * 2
... 
>>> multiple_it(6)
0
>>> multiple_it(7)
14
>>> bytecode = multiple_it.__code__.co_code

>>> dis.opname[bytecode[0]]
'LOAD_FAST

>>> dis.opname[bytecode[0]] + ' ' + dis.opname[bytecode[1]]
'LOAD_FAST <0>'

>>> multiple_it.__code__.co_varnames[bytecode[1]]
'a'

>>> dis.dis(multiple_it)
  2           0 LOAD_FAST                0 (a)
              2 LOAD_CONST               1 (2)
              4 BINARY_MODULO
              6 LOAD_CONST               2 (0)
              8 COMPARE_OP               2 (==)
             10 POP_JUMP_IF_FALSE       16

  3          12 LOAD_CONST               2 (0)
             14 RETURN_VALUE

  4     >>   16 LOAD_FAST                0 (a)
             18 LOAD_CONST               1 (2)
             20 BINARY_MULTIPLY
             22 RETURN_VALUE