Написание компилятора на Haskell + LLVM

На работе я пишу почти исключительно на Python, с университетской скамьи остались некоторые знания C/C++, в одном pet-project использовал Haskell. С таким багажом знаний я взялся за написание компилятора на основе LLVM — зачем и что получилось я уже рассказывал в предыдущей статье.

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

Я кратко расскажу про необходимый минимум знаний Haskell, про свои ошибки и к каким решениям я пришел -, а так же про решения, о которых я узнал позже — и как их можно интегрировать в ваш pet-компилятор. На всё это я по возможности дам ссылки на изучение.

image-loader.svg

Оглавление

  1. Haskell — настраиваем проект и необходимые знания языка

  2. Основы языка — синтаксис, парсер, AST

  3. Кодогенерация с LLVM

  4. Заключение

Код из этой статьи, разложенный по шагам: https://github.com/VoidDruid/habr-hs-llvm

Репозиторий по этой ссылке можно использовать как «интерактивный учебник» в паре со статьей.

Haskell — необходимые знания языка и настройка проекта

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

Благодаря этому проекту и нескольким после него я сильно продвинулся в haskell, но к началу работы над компилятором я успел написать на этом языке только telegram-бота, который помогает мне мониторить личный сервер. Для программистов примерно с такими же базовыми познаниями в хаскеле написана эта статья. В дальнейшем я рассчитываю, что вы знаете (хотя можно разобраться и по ходу):

  • Базовый синтаксис языка

  • Модули и импорты

  • Как работать с монадами (не обязательно уметь писать свои), хотя бы поверхностно

  • do-нотация

  • IO монада

  • Рекурсия, частичное применение функций, объявление типов

  • Желательно: typeclasses, алгебраические типы данных, records

Я попытаюсь объяснить, зачем и как используется каждая фича языка, указанная в пункте »желательно», но будет проще, если вы с ними знакомы.

Собирать проект мы будем с помощью stack — установить его довольно просто (инструкция), пользоваться тоже. Создавать проект с нуля не придется — можно клонировать этот репозиторий, и идти в нем по шагам параллельно со статьей (readme есть в каждой папке плюс глобальный — ознакомьтесь с ними, чтоб упростить сборку и запуск кода). Или можно делать все самостоятельно, все же создав новый проект — с помощью самого stack (инструкция) или используя этот шаблон для cookiecutter.

Неплохая статья для начинающих про stack на русском

Книга про haskell на английском, которую можно использовать как онлайн-справочник

Если вы решили работать со статьей совместно с кодом из репозитория с пошаговым разбором, то перед тем как мы пойдем дальше, зайдите в папку step-00, и запустите stack run. Если программа с вами поздоровалась, то мы готовы идти дальше. Сейчас мы находимся в директории step-00, соответствующей ШАГ 0. В дальнейшем, переходы к следующему шагу (и, соответственно, к другой папке с кодом) будут отмечены именно так — ШАГ Х.

Основы языка — синтаксис, парсер, AST

Базовый парсинг

ШАГ 1

Первое, что мы попробуем сделать — это написать простой парсер. В стандартной библиотеке хаскеля есть отличный модуль Parsec (Parser Combinators — описание и документация; туториал, по которому учился я), позволяющий в декларативном стиле описывать парсеры. Для сборки необходимо добавить его в .cabal файл в секцию build-depends.

Туториал по Parsec на русском

На данном этапе, весь код все еще будет помещаться в модуле Main. Добавим несколько импортов:

import Text.Parsec (parse)
import Text.Parsec.String (Parser)
import Text.Parsec.Language (emptyDef)
import qualified Text.Parsec.Token as Tok

Что мы импортировали:

  • parse — функция, прогоняющая парсер на входном потоке данных

  • Parser — определение типа простого парсера, принимающего на вход строки

  • emptyDef — «пустое» определение синтаксиса языка, на основе которого мы сделаем свое

  • Text.Parsec.Token — основной модуль с функциями-парсерами

Создадим новое определение лексера, с помощью функции makeTokenParser, передав ей на вход определение синтаксиса нашего языка:

lexer :: Tok.TokenParser ()
lexer = Tok.makeTokenParser style
  where
  ops = [ "+", "*", "-", "/"]
  names = ["if", "else"]
  style = emptyDef {
  Tok.commentLine = "//"
  , Tok.commentStart = "/*"
  , Tok.commentEnd = "*/"
  , Tok.caseSensitive = True
  , Tok.reservedOpNames = ops
  , Tok.reservedNames = names
  }

Тут мы создали новый record под названием style, в котором описали базовый синтаксис нашего языка, пока что крайне простого — си-подобные комментарии, базовые операции (+, -, *, /) и зарезервированные слова if и else. Получившийся лексер мы теперь можем передать конструкторам парсеров из Tok, чтобы получить конкретный функции-парсеры для нашего языка:

integer    = Tok.integer lexer
float      = Tok.float lexer
-- и так далее, полный код - https://github.com/VoidDruid/habr-hs-llvm/blob/master/step-01/app/Main.hs

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

Для парсеров определены монадные операторы, и если посмотреть определение типа, то видно что мы можем использовать их совместно с собственными монадами, state-ами и т.д. Когда я только начинал работать с Parsec, я этого не знал, и просто использовал do-нотацию, потому что так было написано в туториалах. Выше я вставлял ссылки на документацию, там можно увидеть что ParserT это на самом деле монадный трансформер, для которого определена куча инстансов монадных тайп классов, большинство из которых я до сих пор не понимаю. Для наших целей достаточно знать, что сами парсеры возвращают значения, а парсер-комбинаторы принимают одни парсеры и возвращают новые.

Зная это, определеить парсер для сложения можно так:

sumParse :: Parser Integer
sumParse = do
  first <- integer
  reservedOp "+"
  second <- integer
  return (first + second)

runSumParse = parse sumParse ""

Вернуть из парсера можно по-большому счету что угодно, тип просто поменяется на Parser ЧтоУгодно. Функция sumParse принимает строку, и разбирает ее как бы по инструкции, соответствущей последовательности операции в do-блоке:

  • Берет первое число first <- integer

  • Считывает зарезервированный оператор »+»

  • Берет второе число second <- integer

  • Возвращает результат сложения return (first + second)

У функции runSumParse один входной параметр — строка, которую она передает на разбор sumParse. "" — указание на «источник» входных данных, используется это для сообщений об ошибках, например.

Если войти в ghci (команда stack ghci), и запустить runSumParse "1 + 2" — вернется Right 3. Это значит что наш парсер отработал без ошибок, и вернул результат 3 — у функции parse тип возвращаемого значения Either ParseError a — где a — тип, возвращаемый sumParse, то есть Integer.

В качестве подведения черты под этим этапом, перепишем функцию main так, чтобы она читала строку из консоли, парсила сложение, и выводила результат или ошибку:

main = do
  line <- getLine
  case runSumParse line of
  	Right result -> putStrLn ("Result: " ++ show result)
  	Left error -> print error

Упражнение — парсер инкремента '1++'. Решение под спойлером

Во-первых, нам надо добавить операцию »++» в список зарезервированных операций: ops = [ "++", "+", "*", "-", "/"]. Затем пишем аналогичный парсер:

incrParse = do
	first <- integer
  reservedOp "++"
  return (first + 1)

Описание AST

ШАГ 2

Один из самых интересных этапов в проектировании языка, по-моему опыту — это описание формата синтаксического дерева. Именно тут закладывается фундамент для всех конструкций языка.

В случае с хаскелем, описать «обычное» дерево легко — это рекурсивный алгебраический тип данных:

data Tree a
	= Leaf  -- тупик
	| Node a (Tree a) (Tree a)  -- узел дерева - значение и две "ячейки" под ветки
	deriving Show

Тут Leaf и Node — конструкторы данных типа Tree a, где a — тип данных, которые содержат узлы дерева. Аналогичным образом мы можем описать и структуру выражения в нашем языке (еще раз напомню, что хоть синтаксис и похож на Си, мы пишем не сишный компилятор, а реализацию «учебного» си-подобного языка):

data Expr
  = Int Integer  -- значение типа Integer
  | Var Name  -- обращение к переменной
  | Def ExprType Name  -- объявление переменной
  | Block (CodeBlock Expr)  -- блок кода
  | Call String [Expr]  -- вызов функции с указанными аргументами
  | Function ExprType Name [Expr] (Maybe Name) (CodeBlock Expr)  -- объявление функции (разберем подробно далее)
  | BinaryOp String Expr Expr  -- бинарная операция над двумя выражениями
  | If Expr (CodeBlock Expr) (CodeBlock Expr)  -- if - условие и две ветки исполнения
  deriving (Eq, Ord, Show)

Таким образом, мы объявили самые базовые конструкции (см. комментарии в коде). Можно заметить, что здесь есть ссылки на дополительные типы данных — ExprType, CodeBlock. Первый — это просто «enum» с типами, поддерживаемыми нашей программой. Сейчас это только инты и функции, но оставим задел на будущее и объявим несколько дополнительных:

data ExprType
  = VoidType
  | IntType
  | FloatType
  | BytesType
  | BooleanType
  | CallableType [ExprType] ExprType  -- [типы аргументов] тип возвращаемого значения
  | AutoType  -- тип должен быть выведен автоматически
  deriving (Eq, Ord)

CodeBlock — это массив выражений, определен просто как:

type CodeBlock term = [term]
-- [expr1, expr2] это CodeBlock Expr

Разница между типами [Expr] и CodeBlock Expr чисто формальная — CodeBlock я использую там, где список выражения является «телом» чего-либо (функции, цикла и пр.), а [Expr] — например, как список аргументов функции. Для такого же «семантического» удобства определим тип AST, который будем использовать только в высокоуровневых функциях:

type AST = [Expr]

В отличии от CodeBlock, AST определен строго для Expr . Мне это показалось логичным в контексте того, что каждый из них «представляет» в программе. Однако если читателю это кажется излишним нагромождением типов, от всего этого можно избавиться и просто везде использовать [Expr].

Как можно сделать круче

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

Я осознал это довольно поздно, и решил не переделывать, благо для моих задач мне это не понадобилось, но в хаскеле для подобных «многослойных» структур часто используется подход «Recursion Schemes». Вот неплохая статья про него — как можно видеть, от структуры того, что я делаю в этой статье, отличается не сильно, однако для применения этого подхода требуется существенно более высокий уровень знания языка.

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

После описания структуры языка можно перейти к написанию функций-парсеров. Пока у нас нет кодогенерации, смотреть что выдает парсер можно будет только распечатывая дерево Expr. Если положиться на derive Show, то в консоль будет вываливаться просто стена текста, так что попробуем определить для наших типов инстанс Show такой, чтоб можно было легко понимать структуру полученной программы.

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

Определить Show для типов довольно просто:

instance Show ExprType where
	show VoidType = "void"
	show IntType = "int"
	-- и т.д.

Гораздо интереснее его определять для Expr. Довольно быстро я понял, что определять именно Show не слишком правильно — например, красиво распечатанный If может занимать несколько строк, что не подходит для Show, поэтому я создал аналогичный тайп класс:

{- 
тайп класс Pretty определяет функцию prettify, возвращающую массив строк -
для выражений, "красивая" распечатка которых может не помещаться в одну
-}
class Show e => Pretty e where
	prettify :: e -> [String]

Я хотел иметь функцию prettifyAST, которой я мог бы передать AST (массив выражений) и получить список отформатированных строк — дальше их можно печатать отдельно или соединить в большое текстовое представление структуры программы (intercalate "\n" — каждый String на отдельной строке). Определил я эти функции так:

joinN = intercalate "\n"

prettifyAST :: Pretty e => [e] -> [String]
prettifyAST = map (joinN . prettify)

joinedPrettyAST :: Pretty e => [e] -> String
joinedPrettyAST = joinN . prettifyAST

Теперь дело осталось только за определением инстанса Pretty Expr. Как это сделал я, можете посмотреть тут (некоторые используемые функции определены в модуле StringUtils), общая структура такая:

instance Pretty Expr where
  prettify expr = case expr of
    (Int i) -> [joinS ["Int", show i]]
    -- и так для каждого Expr

Парсинг

Все еще ШАГ 2

Теперь рассмотрим написание парсера. Для этого мы будем использовать лексер, объявленный в шаге 1. Для парсера я создал отдельный модуль Parser (parser.hs) и вынес все связанное с лексером из первого шага в модуль Lexer (lexer.hs). Тут не будет ничего принципиально нового, просто продолжение принципов парсер-комбинаторов, которые я уже показывал.

Вот что мы будем использовать (есть еще импорты из стандартной библиотеки, их я опускаю):

import qualified Text.Parsec.Expr as Ex
import qualified Text.Parsec.Token as Tok

import Lexer
import Syntax

Первая и самая запутанная часть — объявить парсеры операций. Её я вынес под спойлер, кому интересно — можете посмотреть, а остальным предлагаю сразу переходить к парсерам выражений, я до сих пор под впечатлением, насколько элегантно это можно сделать.

Как всегда, полный код этого модуля (для данного этапа) в репозитории.

Парсеры операций

Для начала объявим парсер для операторов вида » + »,» * » и так далее:

op :: Parser String
op = do
  whitespace
  o <- operator
  whitespace
  return o

Результат работы op это String для стуктуры

data Expr
=
  -- ...
  BinaryOp String Expr Expr  -- операция с двумя операндами

Затем нам надо объявить валидные операторы, ассоциативность операций и их приоритет:

{-
binary - конструктор бинарных операций, вернет частично созданный BinaryOp
(без операндов типа Expr и Expr)
Принимает сам оператор (s) и ассоциативность (у нас - Ex.AssocLeft)
-}
binary s assoc = Ex.Infix (reservedOp s >> return (BinaryOp s)) assoc

-- Функция, возвращающая функцию-генератор парсеров с указанной ассоциативностью для списока операторов
opList arity = opList'
	where 
    opList' [op] = [arity op Ex.AssocLeft]
    opList' (op:ops) = arity op Ex.AssocLeft : opList' ops

binList = opList binary

-- Доступные бинарные операторы (точнее уже парсеры для них - применяется binList), в порядке убывания приоритета
binops = [
  binList ["*", "/", "//", "%"]
  , binList ["+", "-"]
  , binList ["<", "=", "<=", ">=", "==", "!="]
	]

Объявим сначала верхнеуровневую функцию-парсер для любого выражения — она нам понадобится для использования внутри других:

{-
Сгенерированния парсеком функция-парсер, возвращаящая Expr.
factor - функция которую мы объявим далее, она парсит "обычные" Expr
binops - таблица операторов (+, *, <, != и пр.), которая позволяет нам правильно парсить и операции над Expr (в нашем случае только бинарные - BinaryOp)
-}
expr :: Parser Expr
expr =  Ex.buildExpressionParser binops factor

Функция factor — это комбинация парсеров для всех существующих Expr. Она должна попытаться их применить с помощью try, и вернуть первый получившийся результат:

factor :: Parser Expr
factor = try cast
      <|> try block
      <|> try function
      -- и т.д.

Уже известным нам способом объявим утилитарные функции для прогона парсера, и можно переходить к написанию парсеров самих выражений.

Функции для запуска парсинга

-- парсит все до eof с помощью переданной функции
contents :: Parser a -> Parser a
contents p = do
  Tok.whiteSpace lexer
  r <- p
  eof
  return r

-- парсит верхнеуровневые объявления файла (в нашем случае - только функции)
toplevel :: Parser [Expr]
toplevel = many $ do
  def <- function
  reservedOp ";"
  return def

-- парсит одно выражение
parseExpr :: String -> Either ParseError Expr
parseExpr s = parse (contents expr) "" s

-- парсит много выражений (файл с кодом)
parseCode :: String -> Either ParseError AST
parseCode s = parse (contents toplevel) "" s

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

Самый простой пример — парсер интов. Библиотечной функцией integer мы достаем из входного потока число и создаем Exprс помощью конструктора Int:

int :: Parser Expr
int = Int <$> integer

Так же мы можем использовать парсеры внутри парсеров, совмещая их с библиотечными комбинаторами:

codeBlock :: Parser [Expr]
codeBlock = braces $ many $
  do e <- expr
  reserved ";"
  return e

Объединив все вместе, разберем чуть более сложный парсер:

ifelse :: Parser Expr
ifelse = do
  reserved "if"  -- ищем в потоке ключевое слово if
  cond <- parens expr  -- затем любое заключенное в круглые скобки выражение
  tr <- codeBlock  -- парсим codeBlock, это true-ветка ифа
  fl <- optionMaybe $ do  -- ветка else необязательная, поэтом maybe мы сможем найти "else" и еще один codeBlock
    reserved "else"
    code <- codeBlock
    return code
  return $ If cond tr (fromMaybe [] fl)  -- конструируем и возвращаем Expr

Осталось попробовать что-нибудь распарсить. Переопределим main так, чтоб он принимал на вход имя файла, и печатал результат парсинга кода в нем. Импорты я опускаю, а сам main выглядит теперь так:

main = do
  args <- getArgs  -- аргументы командной строки
  case args of
    []   -> putStrLn "Provide file name!"
    [filename] -> do  -- если получили один аргумент
      code <- readFile filename  -- читаем файл
      case parseCode code of  -- и парсим его содержимое
        Left err -> print err
        -- если успех - используем нашу joinedPrettyAST чтоб сделать результат читаемым
        Right ast -> putStrLn (joinedPrettyAST ast)  
    _ -> putStrLn "Provide one file name!"

Вот как выглядит main.hs и main.grt (файл с кодом) у меня (и у вас, если вы идете по шагам). Запустим это с помощью

stack run -- main.grt

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

Текстовое представление AST

Function "main" int ; args [] ; returns Nothing {
  BinaryOp = (Def int "i") (Int 0)
  If (BinaryOp < (Var "i") (Int 1)) {
    Int 0
  }
  else {
    Int 1
  }
}

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

Типизация

ШАГ 3

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

{- Конструктор типизированного выражения, принимающий тип и 
собственно выражение - одно из тех, что мы объявляли ранее -}
data TypedExpr = TypedExpr ExprType Expr

Но такой код, естественно, не делает то что нужно — «внутри» TypedExpr все еще лежит обычный Expr. Решение, которое придумал я — не оптимальное, но делает все, что надо. Это добавление «промежуточного контейнера» TExpr и собственно определение TypedExpr. Исходники — тут. Прелесть такого способа в том, что он также позволяет добавлять любые аннотации (в том же месте где и ExprType), однако многословен и не совсем идиоматичен. Описание моего тернистого пути под спойлером, а мы идем дальше.

Мои ошибки с добавлением типов

Тут-то и оказываются нужен тот самый подход рекурсивных схем.

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

Пробовал делать что-то типо:

data Expr' e
= Int Integer
| Call String [e]

И определять:

  • type Expr = Expr' Expr — ругается на цикл в определении

  • type Expr = Expr' Expr' — ругается, вполне очевидно, что для последнего Expr' не хватает аргумента

  • newtype Expr = Expr (Expr' Expr) -, а это уже близко к тем самым рекурсивным схемам, не хватает только правильно заиспользовать Fix, но на этом моменте я сломался

В общем, не повторяйте моих ошибок и сразу используйте параметризованные типы, Data.Fix и прочие прелести. Я же решил — сделаем TypedExpr аналогом Expr, но с типами и соответствущими поправками. Идея такая — сначала получив дерево из Expr, применим алгоритм, который трансформирует его в дерево типа TypedExpr — в котором все выражения будут аннотированы.

Есть несколько способов это сделать:

  • Можно перенести все конструкторы (с заменой Expr на TypedExpr) в определение TypedExpr, и добавить во все типы — data TypedExpr = ... | TBlock ExprType (CodeBlock TypedExpr), но в таком случае «тип» это не аннотация, а «часть» объявления синтаксиса — мне это не понравилось

  • Можно сделать аналогично, но добавить тип не во все конструкторы, а в один, «главный» — data TypedExpr = ... | TypedExpr ExprType TypedExpr -, но тогда функции принимающие TypedExpr смогут принимать как «главное» объявление, так и инстансы без типов

  • Вариант, на котором я остановился — промежуточный тип TExpr, с конструкторами аналогичными Expr, но ссылающимися на TypedExpr (т.е. определение дерева, с «узлами» из TypedExpr), и тип data TypedExpr = TypedExpr ExprType TExpr. Вместе с view-паттернами это в коде выглядит не так многословно, как может показаться, это будет видно далее.

Механизм аннотирования типами

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

На этом шаге мы добавляем модуль AST, в котором находятся все функции для обработки синтаксического дерева. «Верхнеуровневая» функция — processAST — объявлена тут и либо превращает AST в типизированные дерево (TAST), либо возвращает список ошибок. Все, что она делает сама — это применяет по очереди функции-обработчики обычного AST (сейчас это только desugarFunc — удаление из определения функций «сахара» в виде объявления имени возвращаемой переменной и явного ее указания в конце тела), а затем передает получившееся в annotateTypes (которая просто делает deduceType рекурсивно для каждого expr), и возвращает ее результат.

Логика deduceType довольно простая — она принимает аннотируемый expr, который, если все пройдет успешно, «заменится» своим typed-аналогом, и «карту типов» — ассоциативный массив известных «языковых единиц» (переменных, функций) с их типами — изначально пустой, и заполняющйся по мере углубления в дерево. Большая часть типов просто подсматиривается в определении, либо выводится из операций (int + int = int, int / int = float и т.д.). auto разрешается максимально просто — если известно значение присваемого выражения (арифметическая операция или вызов функции), то назначается этот тип, иначе возвращается ошибка.

Полные исходники — тут, либо в файле step-03/AST/Typing.hs.

Добавим processAST в main и посмотрим что нам выведет наша программа теперь для простейшей функции.

Исходник:

int main() = {
    int i = 0;
    if (i < 1) {
        0;
    }
    else {
         1;
    };
};

Типизированное представление:

Function (() -> int) main [] {
  BinaryOp i= (Def int "i") (int 0)
  If int (BinaryOp b< (Var int "i") (int 1)) {
    int 0
  }
  else {
    int 1
  }
}

Тут i= — интовое присвоение, а b< — операция сравнения, которая (очевидно) возвращает bool.

Кодогенерация с LLVM

ШАГ 4

В этом разделе мы воспользуемся инфраструктурой LLVM для создания машинного когда из нашего синтаксического дерева. Для этого нам нужна библиотека llvm-hs (github, hackage), которую, вместе с некоторыми другими, надо добавить в зависимости нашего проекта. В моем stack.yaml это выглядит так:

extra-deps:
- llvm-hs-9.0.1
- llvm-hs-pure-9.0.0
- llvm-hs-pretty-0.9.0.0

Если же вы идете по туториалу по шагам из репозитория, то переходите в step-04.

Необходимо установить и саму LLVM — как это сделать, описано в документации llvm-hs. Инструкция. Соответствущие изменения в конфигурационных файлах проекта — stack.yaml и habrhs.cabal

Из TAST в IR

Это — финишная прямая. Тут мы добавим модуль Codegen, главная его функция — buildIR, выдающая промежуточное представление LLVM IR. Сразу добавим этот этап в main следующим образом, чтобы сосредоточиться только на кодогенерации (обратите внимание — появилось много импортов и флаг --emit).

Codegen состоит из трех файлов, главный — Builder.hs, где и происходит генерация IR, остальные содержат утилиты, по которым я предлагаю быстро пройтись (обратите внимание, что тут везде импортированы модули LLVM.*, функции с разными «компиляторными» названиями типо allocate или reference — это оттуда).

1) ASTBridge — разные утилиты для перевода типов и операции нашего TAST в соответствущие для LLVM

  • typeMap — словарь из пар «наш идентификатор типа» — «тип в LLVM»

  • функции вида allocateX — генераторы вызовов LLVM для аллокации памяти под сам тип или указатель на него.

  • функции вида referenceX — генерации LLVM-ных «обращений» к ячейке памяти под какой-либо тип напрямую или по указателю

  • convert — по нашим IntType и FloatType генерирует операции приведения типов для LLVM

  • opTable и findOperation — соответственно словарь и функция для поиска в нем соответствующих операций. Словарь содержит для IntType и FloatType еще по вложенному словарю, с парами «строка операции» (+, -, …) — «LLVM операция соответствующего типа» (интовое умножение, дробное умножение и т.д.)

Каждая из этих функций (за исключением последней) возвращает Operand — это LLVM-примитив, обозначающий, как ни странно, операнд — не самостоятельное выражение, а некий объект, который должен быть или «записан в переменную» (store в llvm), или использован в составе другого операнда. findOperation же возвращает (а opTable — содержит) функции, принимающие два операнда и возвращающие третий — то есть бинарные операции.

Кроме уже упомянутых reference и allocate, тут используется еще несколько часто встречаемых конструкций из LLVM. Это named, генерирующий именованные выражения и AST.PointerType, оборачивающий любой другой LLVM-тип и объявляющий указатель. Особенно стоит отметить, что такое qualified имя обозначает что это не из «нашего» AST, а из модуля LLVM.AST.

2) Primitives — содержит сокращенные объявления функций LLVM. Например, объявлние типа указателя на int требует определить адресное пространство и вид инта (i16, i32, i64). Мы для простоты используем выравнивание по 4, i32 и дефолтное адресное пространство — поэтому удобно создать утилитарные функции, которые подобные параметры проставляют сразу. Такие сокращения и содержит этот модуль.

И, наконец, то, ради чего мы тут собрались — генерация IR из AST, модуль Builder.

Благодаря рекурсивному объявлению синтаксического дерева, по сути нам надо лишь описать функцию, обрабатывающую единственный тип TypedExpr со специализациями под конкретные конструкторы (выражения) — emit (по ссылке — ее исходный код). Мы также гарантировали, что все верхнеуровневые выражения — это функции, так что сделаем их особым кейсом, и тогда вся схема кодогенерации выглядит так:

TAST (то есть [TypedExpr]) -> buildIR -> LLVM Module, где

1) buildIR: применяет к каждому TypedExpr (который гарантированно фукция) buildFunction 
2) buildFunction: генерирует IR функции, то есть создает ее объявление, аллоцирует аргументы,
   и затем генерирует тело с помощью funcBodyBuilder -> buildCodeBlock
3) buildCodeBlock: применяет emit к каждому выражению и его частям рекурсивно, и делает возвращаемым значением последнее выражение
   (мы сделали возвращаемые переменные переменные "последним выражением" в блоке на этапе обработки AST, помните?)

Тип функции emit следующий — emit :: (MonadFix m, MonadIRBuilder m) => TypedExpr -> m Operand. То есть это функция, которая работает с монадой IRBuilder из LLVM — это крайне удобно, т.к. с помощью do-блока и специальных фунций LLVM мы, по сути, просто объявляем (с помощью паттерн-матчинга) для каждого нашего выражения какой ему соответствует IR-код почти один-в-один для человеческого глаза. Т.к. большинство из того что «возвращают» функции LLVM можно передать далее по монаде, написание emit — довольно тривиально.

Разберем пример (тут используется функция view в паттерне для удобства — она сразу достает тип и составные части выражения) — генерация для If:

-- type_ - тип результата блока
emit (view -> (type_, TIf cond blockTrue blockFalse)) = mdo
  -- генерируем IR для условия If (рекурсивно используем emit), например для выражения вида "x < y"
  condition <- emit cond
  -- создаем указатель на будущий результат, он будет результатом блока
  -- и в него запишется результат выполненной ветки
  resultPointer <- allocateT type_
  -- проверка условия и выбор ветки
  condBr condition trueBranch falseBranch
  -- генерация IR для ветки if (...) { }
  trueBranch <- buildBranch "true" blockTrue resultPointer $ Just mainBr
  -- генерация IR для ветки else { }
  falseBranch <- buildBranch "false" blockFalse resultPointer $ Just mainBr
  -- возвращаемся в "главную ветку" исполнения и возвращаем результат
  (mainBr, result) <- emitExit resultPointer
  return result

Тут есть несколько утилитарных функций. Самая простая — emitExit, она просто генерирует код выхода из блока с сохранением результата:

emitExit resultPointer = do
  mainBr <- block `named` bodyLabel
  result <- load resultPointer
  return (mainBr, result)

Вторая — buildBranch. Аналоги веток есть не только у If, но в некотором смысле и у циклов, просто там в конце происходит прыжок в начало.

-- тут мы получаем имя, список expr для генерации (codeBlock), и уже известный resultPointer - куда сохранить результат
buildBranch name codeBlock resultPointer mNext =
  do
    -- начинаем ветку - метка для LLVM
    branch <- block `named` name
    -- опять рекурсивно применяем emit, скрывающийся под buildCodeBlock
    blockR <- buildCodeBlock codeBlock
    -- сохраняем результат по указателю
    store resultPointer blockR
    -- если надо выйти из ветки - генерируем прыжок, иначе пропускаем
    case mNext of
      Nothing -> pure ()
      Just label -> br label
    -- возвращаем получившийся блок
    return branch

Расписав таким образом emit для каждого вида выражений (некоторые реализации занимают одну строку), мы получаем генератор IR кода. Посмотрим, что у нас получилось в итоге для все той же простейшей функции (те кто следуют по туториалу — это main.grt). Запустим stack run -- -e main.grt еще раз и полюбуемся на результат (флаг -e нужен для печати IR — ведь на этом этапе мы уже расчитываем скоро иметь компилятор, а они обычно не выводят на экран IR):

; ModuleID = 'program'

define external ccc  i32 @main()    {
Body_0:
  %i_0 = alloca i32, align 4 
  store  i32 0, i32* %i_0, align 4 
  %0 = load  i32, i32* %i_0, align 4 
  %1 = icmp slt i32 %0, 1 
  %2 = alloca i32, align 4 
  br i1 %1, label %true_0, label %false_0 
true_0:
  store  i32 0, i32* %2, align 4 
  br label %Body_1 
false_0:
  store  i32 1, i32* %2, align 4 
  br label %Body_1 
Body_1:
  %3 = load  i32, i32* %2, align 4 
  ret i32 %3 
}

Этот код сгенерирован без каких-либо оптимизаций, поэтому он многословнее чем «должен быть», но для нас это только лучше — нагляднее. Ура, мы наконец имеем LLVM IR из исходников нашей программы. Запустить его уже можно, например перенаправив вывод в файл, который затем дать на вход lli — интерпретатору IR.

Если хочется создать исполняемый файл, то дело за малым — обратиться к встроенному в LLVM функционалу компиляции модулей.

Бонус: создаем бинарник

Это уже ШАГ 5, директория step-05.

Чтобы максимально быстро получить результат, будем использовать все параметры по умолчанию — благо, для этого в llvm-hs есть готовые обертки. По большому счету, все что нам надо сделать — это склеить пустой контекст, настройки хостовой машины по умолчанию, создать llvm-модуль из нашего LLVM.AST.Module с помощью соответствущей функции, и скормить финальный результат билдеру объектников, после чего этот файл слинковать.

Код для дешёвого и сердитого создания объектных файлов выглядит так (полный файл):

writeWithDefaultTarget :: File -> Module -> IO ()
writeWithDefaultTarget file mod = withHostTargetMachineDefault (\t -> writeObjectToFile t file mod)

writeWithModuleFromAST :: File -> Context -> LLVM.AST.Module -> IO ()
writeWithModuleFromAST f c m = withModuleFromAST c m (writeWithDefaultTarget f)

writeObject :: File -> LLVM.AST.Module -> IO ()
writeObject file mod = withContext (\c -> writeWithModuleFromAST file c mod)

И так добавляется в main (полный файл):

writeObject (File ("output.o" :: FilePath)) ir

С добавлением этого, наша программа после запуска сгенерирует файл output.o, который только останется слинковать вашим любимым линкером — у меня на маке это выглядит как ld -lSystem output.o -o output.

Так как ввод/вывод мы не реализовали, наша программа просто возвращает числа, которые будут выходными кодами. Соответствено, посмотреть результат исполнения можно распечатав exit code последней команды. Я написал утилитарный скрипт (проверял только на macOS) для упрощения этого процесса, который запускает наш комплиятор, линкует объектный файл, запускает получившуюся программу и печатает результат:

#!/usr/bin/env bash
stack run -- main.grt

ld -lSystem output.o -o output
chmod +x output
./output

echo $?

Заключение

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

Буду рад комментариям (постараюсь ответить на них), а также PR-ам в репозиторий туториала — версия кода, используемая в этой стате, зафиксирована в README и самой ссылке в начале, так что перепройти туториал можно в любой момент.

© Habrahabr.ru