Skip to content

Latest commit

 

History

History
94 lines (70 loc) · 8.8 KB

README.md

File metadata and controls

94 lines (70 loc) · 8.8 KB

Реализации miniML коммитить сюда

Придумайте на двоих уникальное название дирекории и создавайте там проект с уникальным называнием. Запишитесь в pairing.md, чтобы я не забыл кто есть кто. (В коммит припишите [skip ci], чтобы он не пытался запускать CI.) Я 28 сентября явно прописал требование, чтобы оценки за ФП не отличались более, чем на 2 буквы. Пытаюсь балансировать команды. Если кто уже успел записаться (и я успел помержить) с каким попало напарником, ладно, пусть будет.

Зачача на допуск к экзамену

Выдается на двоих и сдается частями в виде PR в этот репо. Разумеется, там должно быть адекватное покрытие тестами, более-менее документация, использование линтера и нормальный функциональный код (на OCaml/Haskell).

Если вы не хотите ничего знать, то можно помечать PRы заклинанием "[D] ...", и CI не будет запускать линтер, а я буду проверить только тесты, без кода. На экзамене сможете рассчитывать максимум на D.

Описание задач

На всякий случай, скажу, что фичи не нужно реализовывать все сразу. Итеративная модель разработки подойдет лучше водопадной.

Задание можно разбивать на следующие части.

  • Парсер+тайпчекер. (10 баллов)
    • Автоматическое тестирование парсера стоит осуществлять в том числе QuickCheck-подобным способом.
  • Трансляция в ANF представление (15 баллов)
    • Если кто-то захочет сделать CPS представление --- не возражаю.
  • Порождение кода для LLVM разумной версии (в том году это была 16я). (15 баллов)
    • Код затем должен компилироваться в ELF и запускаться (QEMU). Интерпретировать LLVM биткод нельзя.
    • Печатать в тестах биткод, чтобы его можно было проверить глазами на (не)адекватность.
  • Порождение ассемблерного листинга для RISC-V 64. (25 баллов)
    • Код должен затем компилироваться в ELF стандартным RISC-V тулчейном.
    • Скомпилированные программы должны запускаться (что-то кроме QEMU --- запрещено).
    • Аналогично печатать ассемблер в тестах
  • Интегрировать в язык реализацию сборки мусора. (10 баллов)
    • В идеале, одну и туже и для LLVM, и для RISC-V.

Итого: 10+15+15+25+10 + 20(за экзамен) даст вам примерно 100 баллов, которые пересчитаются в оценку стандартным для универа способом. N.B. За экзамен нужно получить хотябы 10 из 20, иначе на пересдачу.

Описание MiniML

  1. Целые числа, булевы значения и сравнения чисел и прочая арифметика
    1. Идентификаторы должны быть как в OCaml, запрещено резервировать какие-то имена, чтобы их порождать по ходу дела.
  2. Парсер должен работать шустро, а не парсить объявления факториала 10 секунд
  3. К идентификатором разрешено приписывать типы явно: fun (x: int) -> ...
  4. В процессе построения ANF должно быть адекватным. Стоит его распечатывать обратно в исходный синтаксис, и проверять, что типы (не) разъехались.
  5. Рекурсивные функции на верхнем уровне (в компиляторе назвается structure_item).
    1. Разрешено ыпереопределять операторы как функции: let (+) = ...
    2. First-class функции, в том числе с частичным примерением и взаимной рекурсией.
      1. Вызовы функций должны быть efficient: если 3-арная функция вызывается от трёх аргументов, то нельзя делать 3 частичных применения под одному аргументу.
      2. Взаимная рекурсия через let rec ... and .... Делать let ... and ... без rec --- не надо
    3. Вложенные let-определения
    4. Не должно быть никакого ограничения сверху на количество аргументов у функций.
      1. В том году бойцы нагенерили большой switch на 100 арностей функций, а в случае >100 --- рантайм падал. так делать не надо
  6. Сопоставление с образцом для кортежей и списков
    1. Полноценные алгебраические типы не обязательно
  7. Рантайм: печать чисел, примитивы частичного применения и сборки мусора.
  8. Должны обрабатываться ошибки в процессе компиляции: компилятор не должен крешиться.
  9. Что-нибудь ещё, что я забыл :)

В директории demo --- рыба

В manytests --- тесты. Стоит сделать символическую ссылку на них у себя, и тестировать на этом коде свой компилятор. Когда буду находить особую ересь в решениях --- буду добавлять новые тесты.

В каком порядке это делать?

Зависимости между подзадачами

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

  1. AST (MiniML без структур данных: пар и списков)
  2. QuickCheck
  3. Компиляция в RISC-V факториала
  4. Компиляция в LLVM факториала
  5. ANF (нужен в первую очередь для LLVM)
  6. Избавление от вложенных функций (lambda lifter + closure conversion). Нужно для интересных примеров
  7. Сложные структуры данных (n-ки, списки) можно не делать (если не надо А), или оставить на потом
  8. Доделывание компилятора в RISC-V (тут уже появится содержательный рантайм)
  9. Доделывание компилятора в LLVM
  10. Сборка мусора для двух бекендов.

Доклады

Выдаются на человека. В случае успеха он получает + 10 баллов, и напарник тоже. После напарник может взять какой-нибудь другой доклад.

Ориентировочно 45 минут + вопросы. Материалы (слайды) должны быть в техе с хорошей лицензией (шаблн в ветке talks), чтобы можно было на следующий год расширить и дополнить.

Темы:

  • Зачем нужны E-graph в компиляторах и не только? Примеры оптимизаций, которые выразимы с ними.
  • SSA book 7-9 главы Павлушкин
  • SSA book 10-11 главы Шишин