Skip to content

Latest commit

 

History

History
158 lines (108 loc) · 8.9 KB

tasks.md

File metadata and controls

158 lines (108 loc) · 8.9 KB

Задачи (и дедлайны для ПИшек)

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

Название Дедлайн
1 Факториал в ANF 4.10
2 ANF 18.10
3 runtime 25.10
4 LL + CC 3.11
5 GC 15.11
6 Tuples
7 LLVM
8 Typechecker
9 Peephole RISC-V
10 Раcпр. регистров
11 Пользовательские операторы
12 tailrec

1. Факториал

Написать компилятор факториала в RISC-V 64. Достаточно, чтобы компилятор работал на одном примере --- факториале.

  • Тайпчекер, ANF, quickcheck --- можно отложить на потом.
  • Ответ можно выдавать как exit code, либо встроить в язык стандартную функцию exit: int -> 'a
  • Разумеется нужны cram тесты

2. ANF

  • Реализовать ANF-преобразование, чтобы уместь писать человеческие вычисления факториалов и чисел Фибоначчи

  • Реализовать в рантайме функцию, которая позволит печатать числа.

  • Тесты. Факториал/фибоначчи + про печать.

      $ cat > test.ml << EOF
  > let large x = if 0<>x then print_int 0 else print_int 1
  > let main =
  >   let x = if (if (if 0
  >                   then 0 else (let t42 = print_int 42 in 1))
  >               then 0 else 1)
  >           then 0 else 1 in
  >   large x
  > EOF

2.99999

За бинари в репо будет ставиться минус, даже если я их уже помержил. Вытирайте

За списанное тоже будет минус

И за орущий линтер тоже (по модулю ложных срабатываний)

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

3. Runtime

Сделать рантайм, который умеет частичное применение. Задумывается, что на 3м дедлайне вы научитесь компилировать программы, которые будут получаться после LL+CC на 4м дедлайне

Тест про факториал и фибоначчи

4. LL+CC

СС --- избавление от замыканий тем или иным способом.

Lambda-lifting --- избавление от вложенных функций

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

N.B. нельзя выключать анализы линтера, если это не согласовано со мною

5. GC

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

  • get_heap_start(get_heap_fin): unit -> int возвращают границы кучи, чтобы их потом распечатывать в компилируемой программе, например, размер кучи
  • collect: unit -> unit чтобы запустить сборку мусора
  • print_gc_status: unit -> unit распечатывает текущий банк памяти, выделенную в куче память на текущий момент, сколько выделилось с начала работы программы, количество проведенных сборок мусора и т.п.

6. Tuples

  • Создание n-ок произвольного размера (например, (1, (2, (fun x -> x+1))))
  • доступ к полями n-oк (например, let (n, (_, f)) = ... )
  • В рантайме понадобятся функции create_tuple и field(value, int)
  • Ну и GC придется потрогать.

P.S. постарайтесь также распилить тесты на несколько cram файлов, чтобы я мог не проверять всё.

7. LLVM

Всё, что выше с кодогеном через LLVM. Если окажется, что для GC придется сделать что-то зверзки сложное, то я его отменю, а пока предполагается, что GC сломаться не должен.

Требование к покрытию тестами >80%.

8. Typecheck c уровнями

Если надо будет выключать зануду, то надо, чтобы это было в минимальном количестве файлов. Так как тайпчекер уже был у вас в том году, то я добавлю к этой задаче требование к покрытию тестами >80%

9. Peephole оптимизации RISC-V

Скорее всего, на данный момент код для RISC-V порождается отвратительно. Например, при использовании стека для локальных переменных пара ANF инструкций

let x = 1+y in
let z = 2*y in ...

приведет к чему-то подобному в ассеблере

li t0, 1
ld t1, 64(sp)   ; смещение на стеке для y
add t0, t1, t0
sd t1, 64(sp)
li t0, 2
ld t1, 64(sp)   ; смещение на стеке для y, повторная загрузка
mul t0, t1, t0
sd t1, 64(sp)

Требует реализовать peephole оптимизацию, что проходит по порожденному коду и делает его написанным по-человечески. Размер окна подберете сами, оптимизировать нужно всё, что найдете стремного, не только указанное выше.

10 Распределение регистров

Хранить все локальные переменные на стеке и двигать туда-сюда --- невероятно неэффективно. Реализуйте какой-нибудь алгоритм распределения регистров, чтобы оно выглядело поффективнее.

11 Пользовательские инфиксные операторы

Разрешите пользователю объявлять и использовать свои собственные операторы. Синтаксис и приоритеты сделайте как в OCaml. Скорее всего это отразится на порождении кода, так как там может быть "захардкожено" поведение для арифметики. Также при lambda-lifting операторов им придется давать буквенные имена, чтобы линкер смог их переварить.

12 Оптимизация хвостовых вызовов

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