Введение в разработку собственного языка и компилятора. Создаем на Rust!

Эта публикация создана с целью предоставления систематического введения в разработку собственного языка программирования, основанного на идеях ML, с использованием Rust и библиотек nom и inkwell для интеграции с LLVM. Она предлагает пошаговое описание теоретических и практических аспектов создания компиляторов, включая анализ синтаксиса, семантику, проверку типов и генерацию кода.

Основные задачи публикации

Изложение фундаментальных концепций: Книга подробно рассматривает такие аспекты, как формальное описание грамматик (EBNF), построение абстрактного синтаксического дерева (AST), алгоритмы проверки и вывода типов. Эти концепции реализуются в коде на Rust для демонстрации их практического применения.

Практическая реализация компилятора: Публикация охватывает полный цикл разработки компилятора, включая создание парсера, реализацию системы типов и компиляцию в машинный код через LLVM. Это обеспечивает читателю возможность изучить процесс «с нуля» и применить полученные знания в реальных проектах.

Обзор современных инструментов: Читатель получит информацию о современных библиотеках, таких как nom для парсинга и inkwell для работы с LLVM, что позволяет использовать описанные подходы в профессиональной деятельности.

Целевая аудитория

Новички в программировании: Для лиц, обладающих базовыми знаниями алгоритмов и структур данных, но не имеющих опыта в теориях языков или разработке компиляторов, книга предоставляет структурированное введение в эти области.

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

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

Кто может не найти эту книгу подходящей

Читатели, ищущие базовый курс программирования: Если ваша цель – освоение основ программирования без погружения в теорию языков или компиляторов, данный материал может быть избыточно специализированным. Предполагается базовое понимание синтаксиса какого-либо языка программирования.

Специалисты, ориентированные на углублённое изучение LLVM: Хотя LLVM используется для компиляции, книга фокусируется на базовом создании компилятора, а не на детальном анализе всех возможностей и оптимизаций LLVM. Для углублённого изучения этой темы рекомендуется обратиться к специализированным источникам.

Рекомендации по использованию книги

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

Обратная связь: Ваши замечания, предложения и указание на ошибки или недочёты крайне важны. Пожалуйста, направляйте их на адрес электронной почты, указаный в Главе «Автор» для улучшения качества публикации.

Отказ от ответственности: Информация в этой книге предназначена исключительно для образовательных и информационных целей. Любое использование представленных материалов осуществляется на ваш собственный риск. Автор не несёт ответственности за возможные последствия применения этой информации.

Для получения дополнительной информации обращайтесь: по адресу электронной почты, указанный в Главе «Автор»

Теперь давайте рассмотрим семантику нашего языка. Конечно, можно было бы разработать строгое определение семантики, как это сделано, например, в язык Standard ML, но для простоты в нашем случае мы будем использовать более общее и упрощенное определение. Для понимания семантики мы будем опираться на книгу «Основы языков программирования» [1], которая поможет нам лучше понять, как работает семантика в языках программирования.

1.1.1 Вычисления

Первое, что нужно рассмотреть, это смысл вычислений.

Существует множество типов семантики для вычислений, такие как операционная [1] семантика и денотационная [1] семантика. Однако в нашем случае мы не будем углубляться в подробности этих подходов, а сосредоточимся на том, что означают базовые команды.

Начнем с вычислительных выражений. Мы будем реализовывать операции сложения (+), вычитания (-), умножения (*) и деления (/). Сравнение будет ограничено проверкой на равенство (==), которая проверяет, равны ли значения слева и справа.

Присваивание переменной означает, что в переменную записывается заданное значение.

Оператор if оценивает условие: если оно истинно, выполняется инструкция в ветке then, если ложно – инструкция в ветке else (если она есть).

Оператор print выводит результат вычисления заданного выражения.

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

1.1.2 Типы

В проектировании языка концепция типов является крайне важной. Почти все языки программирования, которые приходят на ум, включают концепцию типов. Почему же эта концепция была введена и стала широко использоваться? Для более подробного объяснения можно обратиться к книгам, таким как «Введение в системы типов» [2], но здесь мы кратко рассмотрим концепцию типов.

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

Типы также выполняют роль гарантии правильности вычислений, основываясь на этой классификации.

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

Правила типов

Как же определяются правила типов?

Давайте рассмотрим, как можно определить правила для типов и какие типы присваиваются выражениям.

Запись и значение правил типов

Для записи правил типов в этой книге будет использоваться следующая запись если у выражения e тип τ, то это записывается как:

e:τ

Кроме того, для анализа типа выражений, которые содержат переменные, может потребоваться сделать предположения о типах этих переменных. Такие

предположения называют типовой средой. Для выражения e, чьё типовое предположение в среде Γ равно τ, запись будет выглядеть как:

Γ ⊢ e:τ

Пример:

Рассмотрим выражение 1. В языке, который мы проектируем, числа будут иметь тип int. Следовательно, тип этого выражения будет записан как:

1: int

Теперь рассмотрим тип переменной. Если типовая среда {x: τ} указывает, что переменная x имеет тип τ, то это будет записано как:

{x: τ} ⊢ x: τ

Типовая среда Γ, содержащая x: τ, будет записана как:

Γ ⊢ x: τ

Новая запись для правил:

Для описания правил типизации в книге будет использоваться следующая запись. Если выполняются условия A1, A2, …, An, то выполняется правило A0. Это будет записано как:

A₁, A₂, …, Aₙ

A₀

С помощью этой записи мы будем определять типовые правила для различных выражений в нашем языке.

Определение правил типизации

Теперь давайте определим правила типизации для нашего собственного языка программирования.

Если в типовой среде Γ выражение e1 имеет тип int, а выражение e2 имеет тип int, то тип выражения a + b также будет int. Это можно записать следующим образом:

Γ ⊢ e1:int Γ ⊢ e2:int

Γ ⊢ e1+e2: int

Аналогично, для выражения e1 – e2 тип также будет int:

Γ ⊢ e1:int Γ⊢e2:int

int Γ ⊢e1 – e2: int

Для умножения e1 * e2

Γ ⊢ e1:int Γ⊢e2:int

Γ ⊢ e1 ∗ e2: int

Для деления e1 / e2

Γ ⊢ e1:int Γ⊢e2:int

Γ ⊢ e1 / e2: int

Теперь рассмотрим оператор сравнения на равенство. Мы будем использовать оператор == для проверки равенства целых чисел, и его тип будет bool. Это можно записать так:

Γ ⊢ e1:int Γ⊢e2:int

Γ ⊢ e1 == e2: int

Таким образом, мы можем типизировать основные выражения для арифметики и сравнения.

Пример:

Предположим, что у нас есть выражение x == (1 +2). Типовое заключение будет следующим:

1. Выражение 1 имеет тип int.

2. Выражение 2 имеет тип int.

3. В типовой среде Γ переменная x имеет тип int.

4. Выражение 1 + 2 имеет тип int.

5. Следовательно, выражение x == (1 + 2) будет иметь тип bool.

Это можно записать как (пример 1):

пример 1

Типизация с выводом типов

Типизация с выводом типов (type inference) – это процесс, при котором типы, явно не указанные в выражении, выводятся на основе контекста и других выражений.

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

В качестве примера рассмотрим язык Standard ML, который известен своей мощной системой вывода типов. Рассмотрим определение функции для сложения:

fun add a b = a + b;

Когда эта функция вводится в интерпретатор Standard ML of New Jersey (SML/NJ) [3], система типов автоматически выводит, что функция add принимает два аргумента типа int и возвращает значение типа int.

val add = fn: int -> int -> int

Это означает, что функция add принимает два аргумента типа int и возвращает значение типа int. В Standard ML функции каррируются, то есть, int -> int -> int эквивалентно int -> (int -> int).

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

Вопрос для размышления:

Хотя человеку достаточно просто понять, как работает вывод типов, как именно компьютер выполняет этот процесс и какие алгоритмы используются для вычисления вывода типов в таких языках, как Standard ML?

Вывод типов

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

Унификация – это процесс, при котором для двух терминов s и t находится такая замена, что, применяя её к этим терминам, мы получаем одинаковые термины.

1.1.3 Унификация

Одним из ключевых инструментов для реализации системы вывода типов является алгоритм унификации, предложенный Джоном А. Робинсоном в 1965 году [5]. Этот алгоритм играет центральную роль в определении типов переменных и выражений, позволяя находить наименьшую общую подстановку (унификатор) для двух выражений или устанавливать, что такая подстановка невозможна. Он стал основой для логического программирования, например, в языке Prolog, а также для автоматических систем вывода в искусственном интеллекте, и может быть полезен при проектировании нашего собственного языка.

Как работает алгоритм унификации?

Алгоритм унификации Робинсона анализирует два терма (выражения или типовые конструкции) и пытается найти такую подстановку, которая сделает их идентичными. Процесс выполняется пошагово следующим образом:

• Разбор на подвыражения: Алгоритм разбивает входные термы на их составные части, такие как функции, переменные и константы, чтобы сравнить их структуру.

• Пошаговая унификация: Алгоритм последовательно проверяет термы и переменные, начиная с их корневых элементов. Если термы имеют одинаковую структуру (например, оба являются вызовами функции с одинаковым именем), унификация продолжается для их аргументов.

• Применение подстановок: Если в одном терме встречается переменная, а в другом – конкретное значение, алгоритм заменяет переменную этим значением. Например, если у нас есть переменная X и значение a, подстановка X -> a применяется ко всем вхождениям Х.

• Проверка совместимости: Алгоритм оценивает, можно ли сделать термы идентичными с помощью подстановок. Если подстановка успешно приводит к равенству термов, унификация завершается успешно. Если же обнаруживается противоречие, процесс завершается с ошибкой.

Рассмотрим пример унификации двух термов:

𝑓 (𝑎,𝑥) =𝑓 (y,b)

Алгоритм выполняет следующие шаги:

• Сравниваем корневые функции: обе стороны имеют функцию 𝑓 значит, структура совпадает, и мы продолжаем анализ аргументов.

• Сравниваем первый аргумент: а = y. Это предполагает подстановку y -> a

• Сравниваем второй аргумент: Это предполагает подстановку x-> b

• Итоговая подстановка: {y-> a, x-> b}. С этой подстановкой термы становятся идентичными: 𝑓 (𝑎,𝑏) =𝑓 (𝑎,𝑏) Таким образом, унификация успешна.

Когда алгоритм завершается с ошибкой?

Алгоритм не может найти унификатор, если термы имеют несовместимую структуру. Например, рассмотрим термы:

f (a) =g (b)

Здесь корневые функции 𝑓 и 𝑔 различаются, что делает унификацию невозможной. Алгоритм завершиться с ошибкой, поскольку подстановка, которая могла бы сделать эти термы идентичными, не существует.

В языке, который мы проектируем, алгоритм унификации Робинсона может быть использован для вывода типов выражений, таких как x+1 или x == (1+2), где типы переменных могут неизвестными на момент анализа. Например, если переменная x используется в выражении x+1, алгоритм проверит, что оба операнда имеют тип int, и свяжет тип x с int, если это возможно. Такой подход позволит нашей системе типов автоматически определять типы, минимизируя необходимость явного их указания, и обеспечит строгую типизацию, как описано в разделе 1.1.2.

Этот алгоритм станет важным компонентом нашей системы вывода типов, особенно при реализации проверки типов и компиляции, которые мы рассмотрим в последующих главах. Для более глубокого понимания можно обратиться к работам Робинсона [5] и его последователи, включая улучшенные версии алгоритма, приложенные Мартелли и Монтанари [4] которые оптимизируют процесс унификации для более сложных выражений.

Алгоритм унификации Мартелли и Монтанари

В 1982 году Альберто Мартелли и Уго Монтанари предложили улучшенную версию алгоритма унификации Робинсона, адаптированную для работы с более сложными выражениями и множествами уравнений типов.

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

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

Из множества уравнений E выбирается одно уравнение. Если уравнение имеет форму X = t, где переменная X не появляется в других уравнениях множества E, оно не выбирается. Если множество E состоит из уравнений вида:

X1 = r1, X2 = r2, …, Xm = rm

и переменные X1, X2, …, Xm не появляются в терминах r1, r2, …, rm, то унификация завершена успешно.

Выбираем уравнение и выполняем следующие шаги:

· Если уравнение имеет форму f (l1, …, lk) = f (m1, …, mk), то оно удаляется из множества E, а уравнения l1 = m1, …, lk = mk добавляются в множество E.

· Если уравнение имеет форму f (l1, …, lk) = g (m1, …, mk), и f и g различны, то алгоритм завершится неудачей.

· Если уравнение имеет форму X = X, то оно удаляется из множества E.

· Если уравнение имеет форму X = t, и термин t не содержит переменной X, и X не появляется в другом уравнении, то применяется замена [t/X] ко всем остальным уравнениям в E.

· Если уравнение имеет форму X = t, и t содержит переменную X, алгоритм завершится неудачей (это называется проверкой на самопоявление – occurs check).

· Если уравнение имеет форму t = X, и t не является переменной, то уравнение t = X удаляется из множества E, и добавляется уравнение X = t (меняем местами левую и правую часть уравнения).

· Возвращаемся к множеству уравнений E.

Когда алгоритм завершится успешно, множество E будет иметь вид:

X1 = r1, X2 = r2, …, Xm = rm

И эта замена будет являться наиболее общим унификатором для множества уравнений E.

Рассмотрим следующий пример на языке Standard ML:

val x = 1;

val y = x +2;

val z = y * 3;

Пусть X – тип x, Y – тип y, Z – тип z. Тогда:

x = 1 → X = int

y = x +2 → Y = int (так как + требует int для x и 2)

z = y * 3 → Z = int (так как * требует int для y и 3)

Итог: X = int, Y = int, Z = int.

В этой программе тип очевиден только для числа 1, который имеет тип int. Чтобы выполнить вывод типов, заменим неизвестные части на переменные типов. Пусть тип переменной x будет X, тип переменной y – Y, а тип переменной z – Z. Тогда множество типовых уравнений E будет следующим:

E = {X = Y, Y = Z, Z = int}

Теперь проведем унификацию для типов Z и int. Поскольку они совпадают, замена [int/Z] будет применена. После этого множество уравнений будет выглядеть так:

E = {X = Y, Y = int, Z = int}

Далее, рассматривая типы Y и int, мы применяем замену [int/Y]. После применения этой замены множество уравнений становится:

E = {X = int, Y = int, Z = int}

Теперь мы можем сделать вывод, что тип переменной x (то есть X) – это int.

В языке, который мы проектируем, алгоритм Мартелли и Монтанари может быть использован для расширения системы вывода типов, особенно при обработке более сложных выражений, включающих несколько переменных и операций. Хотя наш язык ограничивается типами int и bool, этот подход позволит нам автоматически определять типы переменных и выражений, таких как x+y или x == (1+2), минимизируя необходимость явного указания типов. Такой механизм обеспечит строгую типизации и упростит разработку компилятора, который мы реализуем в последующих главах .

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

До сих пор мы рассматривали семантику языка, который мы создаём. Теперь давайте подумаем, какой синтаксис будет достаточно хорош для того, чтобы выразить эту семантику.

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

1.2.1 Определение синтаксиса

Давайте начнем с определения синтаксиса для языка, который мы собираемся создать.

Элементы, которые мы хотим реализовать, это: сложение, вычитание, умножение, деление, сравнение на равенство*¹, присваивание, оператор if с ветками then и else, а также оператор print.

Что касается сложения, вычитания, умножения и деления, то здесь нет необходимости сильно углубляться. Для двух выражений просто используем операторы +, -, * или / как инфиксные операторы.

Оператор if в большинстве языков позволяет создавать блоки и помещать несколько инструкций внутри одного оператора if. Но для нашего языка мы примем более простое решение: if будет принимать выражение и одну инструкцию для ветки then, а также опциональную инструкцию для ветки else, если она указана.