[Перевод] Жизненный цикл кода на Python – модель выполнения CPython
Всем привет! Наступила весна, а это значит, что до запуска курса «Разработчик 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 ") 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 показывают, где токен начинается и заканчивается соответственно.
INDENT и DEDENT токены и указывают на отступы. В других языках блоки обозначаются скобками или операторами begin/end, но в Python используются отступы и разные уровни. Эти токены нужны для построения реляционных деревьев синтаксического анализа и/или абстрактных синтаксических деревьев.
Генерация парсера
Генераторы парсера известны под названием PGen. Генерация парсера –процесс, который генерирует парсер по заданной грамматике. Один – оригинальный (Parser/pgen
) и один переписанный на python (/Lib/lib2to3/pgen2
). В Cpython есть два генератора парсера.
“Оригинальный генератор был первым кодом, который я написал для Python”
-Guido
Когда вы вызываете pgen (в Parser/pgen) он генерирует заголовочный файл и С-файл (сам парсер). Из вышеприведенной цитаты становится ясно, что 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},
};
Первый — это NEWLINE
, второй — simple_stmt
, и последний — compound_stmt
. Здесь arc_0_0
состоит из трех элементов.
Однако даже если if
— это не новая строка, то compound_stmt
все равно может начинаться с if
. Имея начальный набор simple_stmt
можно заключить, что simple_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 есть только один переход, который получает токен двоеточие (:).
Наконец, переходим к arcs_41_4. Так мы получаем набор, который может начинаться с печатного значения (print statement). И мы получаем финальный вид дерева синтаксического анализа. Первый переход в наборе — это выражение 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). Все синтаксические выражения были отброшены для упрощения понимания, но нужно помнить о том, что была потеряна определенная информация.
Для генерации кода из AST деревьев можно использовать сторонние модули, например Astor. Пример
Python предлагает встроенный AST модуль для работы с AST.
Для примера рассмотрим тот же код, что и ранее.
>>> 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 создает директорию, которая называется __pycache__. Байткод на Python – это промежуточный набор инструкций, которые работают на виртуальной машине Python’a. Она хранит скомпилированный код для того, чтобы сберечь время в случае перезапуска компиляции.
Рассмотрим простую функцию на 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)
<class 'function'>
Она имеет атрибут __code__
.
>>> say_hello.__code__
<code object say_hello at 0x7f13777d9150, file "/home/batuhan/blogs/cpython/exec_model/func.py", line 1>
Объекты Кода
Проще говоря, это представления кода на Python. Объекты кода — это неизменяемые структуры данных, которые содержат инструкции или метаданные, необходимые для выполнения кода. Также можно получить объекты кода, компилируя абстрактные синтаксические деревья с помощью метода compile.
>>> 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, '<string>', mode='exec')
>>> type(code)
<class 'code'>
Каждый объект кода имеет атрибуты, которые содержат определенную информацию (с префиксом co_). Здесь мы упомянем лишь несколько из них.
co_name
Если существует функция, то у нее должно быть имя, соответственно, это имя будет именем функции, аналогичная ситуация с классом. Для начала – имя. Пускай они будут просто module
. В примере с AST мы используем модули, и мы точно можем сказать компилятору как мы хотим их назвать.
>>> code.co_name '<module>'
>>> say_hello.__code__.co_name 'say_hello'
co_varnames
Это кортеж, содержащий все локальные переменные, в том числе и аргументы.
>>> say_hello.__code__.co_varnames
('name',)
co_conts
Здесь стоить отметить значение None. Кортеж, содержащий все литералы и константные значения, к которым мы обращались в теле функции. Мы не включали None в тело функции, однако Python указал его, поскольку в случае начала исполнения функции, а потом окончания без получения каких-либо возвращаемых значений, он вернет None.
>>> say_hello.__code__.co_consts
(None, 'Hello', 'How are you ', '?')
Байткод (co_code)
Далее приведен байткод нашей функции.
>>> 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)
<class 'bytes'>
Первый выведенный символ это «t». Если мы запросим его числовое значение, то получим следующее.
>>> ord('t')
116
116 – это то же самое, что и bytecode[0].
>>> assert bytecode[0] == ord('t')
Для нас значение 116 ничего не значит. К счастью, Python предоставляет стандартную библиотеку, которая называется dis (от disassembly). Он полезна при работе с opname списком. Это список всех инструкций байткода, где каждый индекс – это имя инструкции.
>>> 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
Инструкция LOAD_FAST состоит из двух элементов.
>>> dis.opname[bytecode[0]] + ' ' + dis.opname[bytecode[1]] 'LOAD_FAST <0>'
Инструкция Loadfast 0 случит для поиска имен переменных в кортеже и проталкивания элемента с нулевым индексом в кортеж в стеке исполнения.
>>> multiple_it.__code__.co_varnames[bytecode[1]] 'a'
Наш код можно дизассемблировать с помощью dis.dis и преобразовать байткод в привычный для человека вид. Здесь номера (2,3,4) – это номера строк. Каждая строка кода в Python раскрывается как множество инструкций.
>>> 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
Время выполнения
Это значит, что код на Python компилируется для виртуального компьютера со стековой архитектурой. CPython – это стек-ориентированная виртуальная машина, а не набор регистров.
Первый – стек исполнения, а второй – стек блоков. При вызове функции Python использует два стека совместно. Больше всего вызовов происходит в стеке исполнения; стек блоков отслеживает сколько блоков на данный момент активно, а также другие параметры, связанные с блоками и областями видимости.
Ru — Станислав Ступников. Ждём ваши комментарии по материалу и приглашаем на открытый вебинар по теме: «Release it: практические аспекты выпуска надёжного софта», который проведет наш преподаватель — программист рекламной системы в Mail.