Хабрахабр

[Перевод] Жизненный цикл кода на 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.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»