Erhalten Sie Zugang zu diesem und mehr als 300000 Büchern ab EUR 5,99 monatlich.
- Herausgeber: Питер
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Russisch
- Veröffentlichungsjahr: 2024
Компиляторы традиционно считаются одной из самых трудных для понимания и изучения тем. Обычно в книгах каждая глава посвящена отдельному проходу компилятора. Но такая структура не позволяет раскрыть, как языковые средства влияют на решения, принимаемые при проектировании компилятора. Вместо этого в «Основах компиляции» выбран инкрементный подход: компилятор совершенствуется последовательно, и читатель может написать весь код самостоятельно. Книга помогает создать собственный компилятор для небольшого, но достаточно мощного языка программирования, постепенно, шаг за шагом вводя все более сложные языковые средства. Джереми Сик объясняет важнейшие концепции, алгоритмы и структуры данных, лежащие в основе современных компиляторов, и закладывает основу для изучения более сложных тем. Это краткое, но доступное руководство уже давно используют студенты и профессионалы.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 257
Das E-Book (TTS) können Sie hören im Abo „Legimi Premium” in Legimi-Apps auf:
Ähnliche
Переводчики Е. Матвеев
Джереми Сик
Основы компиляции: инкрементный подход. — СПб.: Питер, 2024.
ISBN 978-5-4461-2116-8
© ООО Издательство "Питер", 2024
Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав.
Посвящаю эту книгу Кэти, моему партнеру во всем; моим детям, выросшим за время работы над книгой; студентам, изучающим языки программирования в Университете штата Индиана, чьи острые вопросы сделали эту книгу лучше.
Предисловие
Всем разработчикам знаком тот магический момент, когда при нажатии кнопки run программа начинает выполняться. Программа, написанная на языке высокого уровня, каким-то образом выполняется на компьютере, способном работать только с битами. В этой книге раскрываются секреты волшебства, благодаря которым подобное становится возможным. Начиная с новаторской работы Бэкуса (Backus) и его коллег в 1950-х годах, компьютерные теоретики разработали методы построения компиляторов — программ, автоматически преобразующих код, написанный на языках высокого уровня, в машинный код.
В этой книге мы займемся построением собственного компилятора для небольшого, но мощного языка. Попутно мы разберем важнейшие концепции, алгоритмы и структуры данных, лежащие в основе компиляторов. Вы сможете лучше понять, какая связь существует между программами и аппаратной частью компьютера. Это необходимо, чтобы рассуждать о том, что происходит на стыке аппаратного и программного обеспечения: о времени выполнения, программных ошибках и уязвимостях в области безопасности. Читателям, которые намерены связать с построением компиляторов свою карьеру, книга облегчит переход к таким нетривиальным темам, как JIT-компиляция, анализ программ и оптимизация кода. Читателям, интересующимся проектированием и реализацией языков программирования, мы продемонстрируем связь между решениями, принимаемыми при создании языка, и их влиянием на компилятор и сгенерированный код.
Обычно работа компилятора состоит из серии этапов, которые последовательно преобразуют программу в машинный код, работающий на физическом оборудовании. Мы пойдем дальше и разделим компилятор на множество микропроходов, каждый из которых выполняет отдельную задачу. Это позволит провести изолированное тестирование каждого прохода и сосредоточить внимание на отдельном блоке, благодаря чему логика компилятора станет намного более понятной.
Самый очевидный способ описать работу компилятора — посвятить каждую главу отдельному проходу. К сожалению, при таком подходе остается нераскрытым вопрос, как языковые средства влияют на решения, принимаемые в ходе проектирования компилятора. Поэтому в книге выбран инкрементный подход: в каждой главе строится полный компилятор, начиная с маленького входного языка, поддерживающего только арифметические операции и переменные. По мере продвижения по главам мы будем добавлять новые возможности и расширять компилятор по мере необходимости.
Наш выбор языковых средств продиктован стремлением продемонстрировать фундаментальные концепции и алгоритмы, используемые в компиляторах.
• Мы начнем с целочисленной арифметики и локальных переменных в главах 1 и 2, где будут представлены фундаментальные средства построения компиляторов: абстрактные синтаксические деревья и рекурсивные функции.
• В главе 3 метод раскраски графа применяется для распределения переменных между машинными регистрами.
• В главе 4 добавляются условные выражения, для преобразования которых в условные команды goto будет применен элегантный рекурсивный алгоритм.
• В главе 5 добавляются циклы и изменяемые переменные, а также демонстрируется необходимость анализа потоков данных в распределителе регистров.
• В главе 6 добавляется поддержка кортежей, память для которых выделяется в куче. Новая возможность обусловливает потребность в механизме сборки мусора.
• В главе 7 добавляются функции как первоклассные значения без лексической области видимости, по аналогии с функциями языка программирования C (Kernighan and Ritchie, 1988)1. Читатель познакомится со стеком вызовов процедур и соглашениями о вызовах и их влиянием на выделение регистров и сборку мусора. Вы также узнаете, как генерировать эффективные хвостовые вызовы.
• В главе 8 добавляются анонимные функции с лексической областью видимости, то есть лямбда-выражения. Читатель узнает о преобразовании замыканий, при котором лямбда-выражения преобразуются в комбинацию функций и кортежей.
• В главе 9 добавляется динамическая типизация. До ее появления в языках использовалась статическая типизация. Мы расширим язык со статической типизацией типом Any, который становится признаком применения динамической типизации при компиляции.
• В главе 10 тип Any, представленный в главе 9, используется для реализации языка с постепенной типизацией, в котором в разных частях программы может использоваться статическая или динамическая типизация. Читатель реализует поддержку времени выполнения для заместителей, позволяющих безопасно перемещать значения между разными областями.
• В главе 11 добавляются обобщения с автоматической упаковкой, использующие тип Any и преобразования типов, реализованные в главах 9 и 10.
Книга не охватывает все языковые средства. В своем выборе мы старались выдержать баланс между сложностью, присущей языковому средству, и фундаментальностью концепций, которые оно демонстрирует. Например, мы включили в книгу кортежи вместо записей; хотя и те и другие позволяют изучить механизмы выделения памяти из кучи и сборки мусора, записям присуща более высокая сложность.
С 2009 года черновики этой книги используются в 16-недельном курсе построения компиляторов для студентов старших курсов в Университете Колорадо и Университете штата Индиана. Слушатели этого курса уже владеют основами программирования, структур данных, алгоритмов и дискретной математики. В начале обучения студенты разбиваются на группы от 2 до 4 человек. Группы изучают главы, соответствующие их интересам, начиная с главы 2, по одной примерно за две недели, соблюдая при этом зависимости между главами, показанные на илл. 0.1. Глава 7 (функции) зависит от главы 6 (кортежи) только в реализации эффективных хвостовых вызовов. Последние две недели курса отводятся под курсовой проект, в котором студенты проектируют и реализуют расширение компилятора по своему выбору. Для поддержки таких проектов могут использоваться заключительные главы книги. Во многие главы включены задания повышенной сложности.
Илл. 0.1. Диаграмма зависимостей между главами
Для университетских учебных курсов, строящихся по триместровой системе (около 10 недель), мы рекомендуем завершить курс на главе 6 или 7 и предоставлять студентам часть вспомогательного кода для каждого прохода компилятора. Курс можно адаптировать так, чтобы уделить особое внимание функциональным языкам; для этого целесообразно пропустить главу 5 (циклы) и включить главу 8 (лямбда-выражения). Чтобы адаптировать курс для языков с динамической типизацией, включите в него главу 9.
Книга используется на курсах построения компиляторов в Политехническом университете штата Калифорния, Университете Портленда, Технологическом институте Роуз-Хульман, Университете Фрайбурга, Массачусетском университете Лоуэлла и Вермонтском университете.
Мы используем язык Racket как для реализации компилятора, так и для входного языка, так что от читателя потребуется хорошее знание Racket или Scheme. Существует много отличных ресурсов для изучения Scheme и Racket (Dybvig, 1987a; Abelson and Sussman, 1996; Friedman and Felleisen, 1996; Felleisen et al., 2001; Felleisen et al., 2013; Flatt, Findler, and PLT, 2014). Вспомогательный код книги доступен в репозитории GitHub по следующему адресу:
https://github.com/IUCompilerCourse/
Компилятор генерирует код на языке ассемблера x86 (Intel, 2015), поэтому полезно, но не обязательно изучить работу вычислительных систем (Bryant and O’Hallaron, 2010). В книге представлены части языка ассемблера x86-64, необходимые для компилятора. Мы используем соглашения о вызовах System V (Bryant and O’Hallaron, 2005; Matz et al., 2013), так что генерируемый код на языке ассемблера будет работать с системой исполнения (написанной на C), если он откомпилирован компилятором GNU C (gcc) в ОС Linux и MacOS на оборудовании Intel. В ОС Windows gcc использует соглашения о вызовах Microsoft x64 (Microsoft, 2018, 2020), поэтому сгенерированный код на языке ассемблера не будет работать с системой исполнения в Windows. Одно из возможных решений — использовать виртуальную машину с Linux в качестве гостевой ОС.
Благодарности
Практика разработки компиляторов в Университете штата Индиана восходит к исследованиям и курсам Дэниела Фридмана (Daniel Friedman) по языкам программирования в 1970-х и 1980-х годах. Один из его студентов, Кент Дибвиг (Kent Dybvig), реализовал Chez Scheme (Dybvig, 2006) — эффективный компилятор Scheme коммерческого уровня. В 1990-е и 2000-е годы Дибвиг вел курс проектирования компиляторов и продолжал разработку Chez Scheme. Учебный курс постепенно развивался, в него включались новые обучающие приемы, а также элементы реально существующих компиляторов. Одно из предложений Фридмана заключалось в том, чтобы разбить компилятор на множество мелких проходов. Другое предложение, названное «игра», — тестировать код, сгенерированный при каждом проходе, с применением интерпретаторов.
Дибвиг с помощью своих студентов Дипанвиты Саркар (Dipanwita Sarkar) и Эндрю Кипа (Andrew Keep) разработал инфраструктуру для поддержки этого метода и доработал курс так, чтобы использовать микропроходы (Sarkar, Waddell, and Dybvig, 2004; Keep, 2012). Многие решения в области проектирования компиляторов, представленные в книге, были вдохновлены описаниями Дибвига и Кипа (2010). В середине 2000-х годов студент Дибвига Абдулазиз Гулум (Abdulaziz Ghuloum) заметил, что при строго направленной структуре курса студентам было труднее понять обоснование выбора тех или иных проектировочных решений. Гулум предложил инкрементный подход (Ghuloum, 2006), который был взят за основу в этой книге.
Я благодарен многим студентам, ассистентам кафедры на курсе проектирования компиляторов в Университете штата Индиана, в том числе Карлу Факторе (Carl Factora), Райану Скотту (Ryan Scott), Кэмерону Сордсу (Cameron Swords) и Крису Уэйлзу (Chris Wailes). Спасибо Андре Кюленшмидту (Andre Kuhlenschmidt) за работу над сборщиком мусора и интерпретатором x86, Майклу Воллмеру (Michael Vollmer) за работу над эффективными хвостовыми вызовами и Майклу Витусеку (Michael Vitousek) за помощь с внедрением инкрементного курса проектирования компиляторов в Университете штата Индиана.
Спасибо профессорам Бор-Ю Чану (Bor-Yuh Chang), Джону Клементсу (John Clements), Джею Маккарти (Jay McCarthy), Джозефу Ниру (Joseph Near), Райану Ньютону (Ryan Newton), Нейту Нистрому (Nate Nystrom), Питеру Тиманну (Peter Thiemann), Эндрю Толмачу (Andrew Tolmach) и Майклу Волловски (Michael Wollowski) за учебные курсы, в основу которых были положены черновики этой книги, и за обратную связь. Спасибо Национальному научному фонду за гранты, обеспечившие поддержку этой работы: номера грантов 1518844, 1763922 и 1814460.
Я благодарен Рональду Гарсиа (Ronald Garcia) за то, что он помог мне выжить на курсе Дибвига по проектированию компиляторов в начале 2000-х — и особенно за то, что он нашел ошибку, из-за которой у нашего сборщика мусора сносило крышу!
Джереми Дж. Сик. Блумингтон, штат Индиана
1 Керниган Б., Ритчи Д. «Язык программирования С».
Глава 2. Целые числа и переменные
В этой главе рассматривается компиляция подмножества Racket в код ассемблера x86-64 (Intel, 2015). Это подмножество, называемое LVar, включает целочисленную арифметику и локальные переменные. Для простоты вместо x86-64 мы будем использовать короткое x86. Глава сначала описывает язык LVar (раздел 2.1), после чего представляет язык ассемблера x86 (раздел 2.2). Так как язык ассемблера x86 весьма обширен, мы обсудим только инструкции, необходимые для компиляции LVar. Другие инструкции x86 будут представлены в следующих главах. После знакомства с LVar и x86 мы поговорим о том, чем они отличаются, и построим план преобразования с LVar на x86 за несколько шагов (раздел 2.3). В оставшейся части главы подробно разбирается каждый шаг. Мы постараемся предоставить достаточно информации, чтобы хорошо подготовленный читатель в компании нескольких друзей мог быстро реализовать компилятор с LVar на x86. Чтобы дать представление о масштабе первого компилятора, отметим, что учебный образец решения для компилятора LVar содержит приблизительно 500 строк кода.
2.1. Язык LVar
Язык LVar расширяет язык LInt, добавляя в него переменные. Конкретный синтаксис языка LVar определяется грамматикой, представленной на илл. 2.1, и абстрактным синтаксисом, представленным на илл. 2.2. Нетерминальный элемент var может быть любым идентификатором Racket. Как и в случае с LInt, оператор read является нулевым, оператор «-» — унарным, а «+» — бинарным. По аналогии с LInt абстрактный синтаксис LVar включает структуру Program для обозначения начала программы. Несмотря на простоту языка LVar, его возможностей достаточно для демонстрации некоторых методов компиляции.
Илл. 2.1. Конкретный синтаксис LVar
Илл. 2.2. Абстрактный синтаксис LVar
Познакомимся ближе с синтаксисом и семантикой языка LVar. Конструкция let определяет переменную для использования в теле программы и инициализирует переменную значением выражения. Абстрактный синтаксис let представлен на илл. 2.2. Конкретный синтаксис let выглядит так:
(let ([var exp]) exp)
Например, следующая программа инициализирует x значением 32, а затем вычисляет тело (+10x), что дает результат 42.
(let ([x (+ 12 20)]) (+ 10 x))
Если для одной переменной существуют несколько let, используется ближайший экземпляр let. Иначе говоря, определения переменных замещают предшествующие определения. Перед вами программа с двумя let, определяющими две переменные с именем x. Сможете ли вы предсказать результат?
(let ([x 32]) (+ (let ([x 10]) x) x))
Чтобы вы лучше понимали, какое вхождение переменной соответствует тому или иному определению, в следующем фрагменте вхождения x помечаются круглыми скобками. Убедитесь, что ваш ответ к предыдущему примеру совпадает с ответом из следующей аннотированной версии:
(let ([x1 32]) (+ (let ([x2 10]) x2) x1))
Инициализирующее выражение всегда вычисляется до тела let, так что в следующем примере оператор read для x будет выполнен раньше оператора read для y. Если передать следующей программе 52, а затем 10, она выдаст результат 42 (а не –42).
(let ([x (read)]) (let ([y (read)]) (+ x (- y))))
2.1.1. Расширение интерпретаторов через переопределение методов
Чтобы подготовиться к рассмотрению интерпретатора LVar, сначала объясним, почему мы реализуем его в объектно-ориентированном стиле. В этой книге мы определяем множество интерпретаторов, по одному для каждого изучаемого языка. Так как каждый язык строится на базе предыдущего, у этих интерпретаторов много общего. Конечно, общий код хотелось бы написать только один раз, чтобы обойтись без лишних повторений. Простейший интерпретатор LVar мог бы обрабатывать условия для переменных и let, передавая управление интерпретатору LInt в остальных случаях. Эта идея продемонстрирована в следующем коде (смысл параметра env объясняется в разделе 2.1.2):
(define ((interp_Lvar env) e)
(match e
(define ((interp_Lint env) e) [(Var x)
(match e (dict-ref env x)]
[(Prim '- (list e1)) [(Let x e body)
(fx- 0 ((interp_Lint env) e1))] (define v ((interp_Lvar env) e))
...)) (define env^ (dict-set env x v))
((interp_Lvar env^) body)]
[else ((interp_Lint env) e)]))
Минус такого упрощенного подхода в том, что его недостаточно в ситуациях, когда конструкция LVar (например, переменная) вложена в другую конструкцию LInt — например, оператор «–», как в следующей программе.
(Let 'y (Int 10) (Prim '- (list (Var 'y))))
Если вызвать interp_Lvar для этой программы, то для обработки оператора «–» управление будет передано функции interp_Lint, но она снова рекурсивно вызовет interp_Lint для своего аргумента. Так как в interp_Lint нет варианта для Var, вы получите ошибку!
Чтобы сделать интерпретаторы расширяемыми, нам понадобится механизм открытой рекурсии, при котором завязывание узла рекурсии откладывается до момента компоновки функций. Объектно-ориентированные языки предоставляют функциональность открытой рекурсии через механизм переопределения методов. Следующий код использует переопределение методов для интерпретации LInt и LVar с использованием функциональности классов языка Racket. Мы определяем один класс для каждого языка и метод для интерпретации выражений внутри каждого класса. Класс для LVar наследует от класса для LInt, а метод interp_exp в LVar переопределяет interp_exp в LInt. Обратите внимание: в варианте по умолчанию interp_exp из LVar используется super для вызова interp_exp, а поскольку LVar наследует от LInt, управление передается interp_exp в LInt.
(define interp-Lvar-class
(class interp-Lint-class
(define/override ((interp_exp env) e)
(define interp-Lint-class (match e
(class object% [(Var x)
(define/public ((interp_exp env) e) (dict-ref env x)]
(match e [(Let x e body)
[(Prim '- (list e)) (define v ((interp_exp env) e))
(fx- 0 ((interp_exp env) e))] (define env^ (dict-set env x v))
...)) ((interp_exp env^) body)]
...)) [else
(super (interp_exp env) e)]))
...
))
Вернемся к проблемному примеру — повторим его для удобства:
(Let 'y (Int 10) (Prim '- (Var 'y)))
Для этого выражения, которое мы назовем e0, можно вызвать метод interp_exp из LVar. Для этого создадим объект класса LVar и вызовем метод interp_exp:
((send (new interp-Lvar-class) interp_exp '()) e0)
Чтобы обработать оператор «–», вариант по умолчанию interp_exp из LVar передает управление методу interp_exp в LInt. Но затем для рекурсивного вызова метода управление передается interp_exp в LVar, где узел Var обрабатывается правильно. Таким образом, переопределение методов предоставляет открытую рекурсию, необходимую для реализации интерпретаторов с возможностью расширения.
2.1.2. Определительный интерпретатор для LVar
После обоснования применения классов и методов для реализации интерпретаторов вернемся к определительному интерпретатору для LInt, показанному на илл. 2.3, расширим его и создадим интерпретатор для LVar, показанный на илл. 2.4. Интерпретатор для LVar добавляет два новых условия match для переменных и let. Для let
