Skip to content

tasks.md

Latest commit

 

History

History
781 lines (719 loc) · 67.6 KB

tasks.md

File metadata and controls

781 lines (719 loc) · 67.6 KB
Raw

Темы задач на самостоятельную работу

Ниже нарочито неформально даны описания мини-языков, интерпретатор которых вам предстоит реализовать на OCaml, чтобы получить допуск к финальной аттестации (экзамену). Темы задач выдаются на одного человека (если не оговорено иное), т.е. почти у всех самостоятельная работа будет разная. Сдавать её надо как PR в этот репозиторий. Скопируйте шаблон из директории Lambda, под новым неповторяющимся именем, поменяйте название проекта и автора, и вперед.

Запись на тему делается добавлением в этот репо PR (желательно, проходящего CI). Кто первый успел, того и тапки. Не забудьте ФИО.

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

Потом можно передумать и переписаться на другую незанятую задачу, или на задачу на максимум D.

Во всех задачах нужно, чтобы

  • код в Git должен быть автоматически отформатирован с помощью ocamlformat.
  • К дереву абстрактного синтаксиса (AST) должны быть написаны комменты, какой конструтор за что отвечает.
  • Были тесты, измерялось тестовое покрытие в процентах. Чем больше покрытие -- тем лучше. Больинство тестов будут интеграционные: запустил интерпретатор миниязыка и сравнил с результатом. Если код не вызывается в тестах, то либо он не нужен, либо на него не написан тест, либо (в редких случаях) это бага ppx_bisect, который измеряет покрытие.
  • Код будет проверяться линтером в CI, и замечания должены исправляться.
    • Да, объекты и присваивание запрещены.

Во всех работах, где надо писать инерпретатор типизированного языка, надо писать тайпчекер тоже. Скорее всего он будет запускаться до интерпретатора.

Разработку рекомендуется вести итеративной моделью, а не водопадной.

Тема для D

Задача выдается, если вас устраивает итоговая оценка не выше D. Данная тема выдается неограниченному кругу студентов.

Реализовать синтаксический анализатор (парсер), type checker и интерпретатор языка miniML, в котором поддерживаются следующие конструкции.

  • Функции как объекты первого класса (first class citizens): их нужно уметь передавать и возвращать из функций. Замыкания также нужны
  • Стандартные типы данных: bool, int и n-ки (англ. tuples)
  • Стандартные функции, чтобы что-нибудь напечатать по ходу интепретации (печать строки, печать числа и т.п.).
  • Захардкоженный тип связного списка, сопоставление с образцом по нему. Полноценные алгебраические типы не надо.
  • Во всех задачах про OCaml, аргумент анонимной функции является так называемым паттерном (англ. pattern). Выражения там разрешать писать нельзя!

Для этой задачи выбирайте имя директории в виде ``DФамилия'' латиницей.

Основные домашки

  1. OCaml + ADT
    Подробнее
    • Всё, что есть в теме для D
    • алгебраические типы как основной способ проектирования типов; учтите, что
      • в OCaml и Haskell типы int и float -- примитивные (встроенные)
      • тип списков алгебраический и там, и там; в AST не должно быть, что списки отдельно, а алгебраические значения отдельно
      • в OCaml тип bool примитивный, а в Haskell -- алгебраический
    • разумеется, объявления типов, паттерн-мэтчинг и типизация
    • присваивание не надо
    • исключения не надо
  2. OCaml + полиморфные вариантые типы
    Подробнее
  3. OCaml + bidirectional records
    Подробнее
    • Всё, что есть в теме для D
    • поддержать синтаксис приписывания (англ. ascription) типов переменным
    • records (a.k.a. записи, структуры) c полями из базовых типов или других записей.
      • в случае перекрытия имен интерпретатор должен учесть приписанные типы. В примере ниже без аннотаций типов результат вывода будет другой
      type t = { aa: int; bb: bool }
type s = { aa: float; cc: int }
let f (x : t) = x.aa
let g (x : s) = x.aa
  4. F# + active patterns
    Подробнее
    • Всё, что есть в теме для D
    • возможность описывать активные паттерны, которые выглядят как алгебраические конструкторы 
      let (|Even|Odd|) input = if input % 2 = 0 then Even else Odd
    • Возможность использования активных паттернов в сопоставлении с образцом 
      let TestNumber = function
| Even -> printf "%d is even\n" input
| Odd -> printf "%d is odd\n" input
  5. Haskell + стандартные типы данных + ленивость
    Подробнее
    • Всё, что есть в теме для D
    • С ленивостью надо будет продемонстрировать работоспособность
      • Лямбда-исчисления с call-by-name
      • ленивых списков и операция над ними (в том числе, фибоначчи, решето Эратосфена и т.п.)
      • прочие ленивые задачи (например, за один проход заменить все числа в дереве на их минимум и вернуть новое дерево)
  6. OCaml + ООП
    Подробнее
    • Всё, что есть в теме для D, кроме n-ок.
    • в OCaml есть интересные объекты и их типизация, нужно поддержать объекты+методы+поля.
    • (может быть классы и наследование тоже надо будет, но пока не уверен)
    • как тесты предлагаю реализовать некоторые структуры данных как камлёвые объекты и посмотреть, что будет
  7. OCaml + effects (2 человека)
    Подробнее
    • Всё, что есть в теме для D
    • Cупер-модное в наши дни движение в мире ФП
    • По сути, это исключения, но в момент обработки которых у нас есть функция, которой можно был передать значение, которое должно было бы быть вместо бросания исключения, и продолжить исполнение с места бросания исключения.
    • Туториал в контексте OCaml https://github.com/ocamllabs/ocaml-effects-tutorial
    • два человека только потому, что хочу чтобы задачу кто-то взял. А так это очень сильно напоминает задачи про delim/cc
  9. OCaml + printf
    Подробнее
    • Всё, что есть в теме для D
    • Поддержка типов char, string и операций с ними
    • Поддержка в компиляторе функции форматированой печати (по аналогии с камлёвым модулем Printf/Format). Разумеется, всё должно быть type safe.
  10. OCaml, именованые и опциональные аргументы
    Подробнее
    • Всё, что есть в теме для D
    • Захардкоженный тип option
    • Именованные и опциональные аргументы. Функции должны типизироваться и исполняться как в настоящем OCaml.
  11. OCaml с типизированными эффектами (2 человека)
    Выглядит страшно, но в 2021 году человек в одиночку справился

    • Всё, что есть в теме для D

    • C эффектами: присваивание, печать на консоль и try/catch/raise для пары захардкоженных в язык исключений. Из-за присваивания -- два человека

    • С системой типов в описанном выше смысле.

    • https://www.janestreet.com/tech-talks/effective-programming

    • Идея заключается в том, что теперь мы будем перечислять в типе функции-стрелке эффекты, которые совершает функция

      • Обычная стрелка -> делает что угодно
      • Длинная стрелка --> (или -[]->) -- это чистая функция: ни присваиваний, ни ввода-вывода. Ничего не делает такого.
      • Над стрелкой можно перечислять, что она делает:
        • -[IO]-> делает ввод-вывод
        • -[exc Not_found]-> кидает исключение Not_found
        • -['a]-> совершает какой-то эффект, но он не указан (полиморфизм)
      • Пример:
        val id : 'a --> 'a
  val print_int: int -[IO]-> unit

  let map : ('a -['e]-> 'b) --> 'a list -['e]-> 'b list = fun f xs ->
    match xs with
    | [] -> []
    | x::xs -> (f x) :: (map f xs)

  let _ : 'a list --> 'b list = map id
  let _ : int list -[IO]-> int list =
    map (fun n -> print_int n; n+1)

      Фунция id чистая, поэтому над стрелочкой ничего не написано.

      Функция print_int совершает ввод-вывод, что указано в типе.

      List.map полиморфна (как обычно) по типу элементу списка, но также полиморфная по типу эффекта переданной функции, что указано в стрелке, которая выдает результат. Первая стреклка в типе map чистая, так как при передаче аргументов ничего не вычисляется и эффектов не совершается. В map id не совешается эффектов, поэтому типовая переменная 'e сунифицировалась с отсутсвием эффектов. Во втором примере из-за того, что переданная функция совершает ввод-вывод, система типов догадывается, что и вычисление map совершает ввод-вывод.

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

  13. OCaml + weak type variables
  14. F# + Units of Measure
    Подробнее
    • Всё, что есть в теме для D
    • Вещественные числа (обосновано следующим пунктом)
    • Возможность объявлять и использовать Units of Measure
  15. OCaml + GADT (2 человека, т.к. напоминает гроб)
    Подробнее
    • Всё, что есть в задаче OCaml+ADT
    • OCaml где алгебраические типы заменены на обобщенные (generalized) алгебраические типы
    • Интерпретатор точно будет такой же, как в задаче про обычные алгебраические типы
    • Вывод/проверка типов (сильно) сложнее, чем для обычных алгебраических, поэтому два человека
      • Нужно поддержать явные аннотации типов, потому что автоматический вывод типов не могёт
      • Типовые переменные могут убегать из области видимости и т.д.
    • Умная сслыка, описывающая что примерно вас ждет
  17. OCaml + скомпилированные алгебраические типы
    Подробнее
    • (задача может показать объёмной, поэтому разрешаю сдавать в одной кодовой базе в месте с задаче про OCaml + ADT)
    • Прочитать как окамлёвые алгебаические типы представляются в памяти, разобраться как устроены "блоки" и unboxed immediate values
    • Написать парсер (параметризовать уже существующий из другой задачи) который понимает функции для конструирования/заглядывания в блоки
    • Интерпретатор
    • Алгоритм преобразования программ с алгебраиками и сопоставлением с образцом в низкоуровневое представление.
    • Преобразования программ из задачи про ADT, в низкоуровневое представление этой задачи. (По сути надо избавляться от алгебраических значений и сопоставления с образцом. Можно посмотреть алгоритм с матрицами отсюда )
  18. Scheme + call/cc
    • относительно легко гуглящаяся особенность Scheme
    • call/cc
    • целые числа, рекурсия, списки, печать на консоль
    • функции обычные и анонимные, замыкания и рекурсия
    • присваивание не надо
    • quote/unquote
    • парсер очень простой
    • никаких статических типов, разумеется, нет
    • учитывая следующую задачу, получается в некотором смысле на двоих
  19. Scheme + delim/cc
    Подробнее
    • почти как предыдущая задача, только понятней
    • Кратко про delim/cc
      • есть две новые конструкции в языке: reset (fun () -> M) и shift (fun k -> M)
      • Пример: reset (fun () -> 2 + 2 * shift (fun k -> k 20))
        • Наличие одинокого reset не влияет на вычисление
        • Когда исполнение доходит до shift, то вместо аргумета подставляется функция, которая "зажата" между этим shift и ближайшим reset, В даннои случае это fun y -> 2 + 2 * y
        • таким образом, выражение выше вычисляется в 42
  20. Ассемблер x86_64 --- очень простой язык и для парсинга, и для реализации интерпретатора.
    Подробнее
    • Язык должен быть настоящим ассемблером, т. е. входные программы должны компилироваться соответствующим компилятором (nasm) и выдавать ответ как в интерпретаторе. Сделайте cram тесты, демонстрирующие это.
    • Примеры в первую очередь берите из первой части книжки И. Жиркова "Low-level programming". Там должен быть helloworld, который требует syscall и память.
    • Чтобы задача не была чересчур простой, хочу также в ассемблере SIMD операции и тесты к ним (перемножение вектора/матрицы на вектор/матрицу)
    • Опыты прошлых лет показывает, что написание AST в лоб оставляет большое пространство для плохих программ, представимых в AST. Например, 64битные команды никак не должны принимать 32битные операнды-регистры как аргументы. Потребуется обмазаться фантомными-типами и/или GADT, чтобы не нужно было писать гавнокод. Буду следить!
  21. Refal 5
    • одскульный отечественный язык программирования, где последовательности можно мэтчить не только с начала, но и с конца
    • здесь, есть 22 примера простых программ на рефал-5
    • а здесь есть програмки посложнее
  22. Pascal c алгебраическими типами
    • Числа, строки и операции с ними. Функции обычные и вложенные, с рекурсией. Вроде как по сравнению с miniML тут не будет вывода типов, только проверка типов. Присваивание не надо.
    • алгебраические типы данных variant records (пункт 12).
  23. Cи
    Подробнее
    • Целые числа разного размера (например, int32_t и int8_t)
    • char
    • Указатели и арифметика указателей, malloc
    • Продемонстрировать стандартные примеры программ на указатели
      • Короткий memcpy и что с ним может пойти не так
      • Реинтерпретировать кусок памяти с массивом int32_t как в 4 раза большее количество чисел int8_t
    • Функции и рекурсия: факториал, фибоначчи, и т.п.
    • Объявления пользовательских структур не надо.
  24. Lua -- примитивный язык без типов
    • Вещественные числа, строки
    • Функции и функции высшего порядка
    • Стандартные конструкции: ветвления, цикл и т.п.
    • Присваивание и хитрые ассоциативные массивы с двойной индексацией, специфичные для Lua
  25. Javascript (2 человека)
    • Объекты, числа, строки, массивы (т.е. присваивание надо)
    • Функции обычные и анонимные, замыкания, рекурсия
    • Типичное для Javascript прототипное наследование
    • Стрёмные штуки из WAT talk и отсюда. Их будет много (постепенно добавлю)
  26. Моделирование параллельного исполнения
    Подробнее За описание благодарите старшего студента.

    • Ast Программа состоит из N параллельных участков. В них бывает арифметика, присваивание, thread-local registers (отдельный для каждого потока набор регистров, например EAX, EBX или r1, r2), shared variables (переменные в которые могут писать и из которых могут читать сразу несколько потоков), ветвления и барьеры чтения/записи.

    • Parser Код потока записывается в столбик, код разных потоков разделен с помощью значка |||. Потоки исполняются параллельно. Если нет идей как такое парсить, то попробуйте следующий способ. Научитесь парсить один конкретный поток по его индексу (нулевой, первый, …, N-1й), потом используя эту функцию распарсите все потоки по очереди и получите список распаршеных потоков. Пример кода на этом языке: x <-1 ||| y<-1 smp_mb ||| smp_mb r1 <-y ||| r2<-x

      Здесь x,y это shared переменные. r1,r2 – локальные для потока регистры. smp_mb – барьер памяти. В этом примере 2 параллельных потока, в каждом потоке 3 инструкции.

    • Интерпретатор Не стоит пугаться, на самом деле вы будете исполнять по одной инструкции за раз чередуя потоки из которых эта инструкция берётся. Модель же памяти будет влиять на операции чтения и записи: эффекты этих операций могут проявляться не в те моменты времени, как вам подсказывает интуиция, из-за этого возникают интересные поведения. Отмечу, что интерпретатор должен осуществить всевозможные исполнения переданной ему на вход программы, с этим поможет монада List (или другая монада для недетерминизма).

    • Описание моделей памяти:

      • Sequential Consistency – простейшая модель, выбираете произвольный поток и исполняете в нем одну инструкцию. Повторяете пока есть неисполненные инструкции. Барьеры памяти в этой модели не оказывают эффекта на исполнение программы.
      • TSO – модель памяти процессоров x86. Здесь возможны интересные поведения. Если в примере выше изначально в переменных x и y хранятся значения ноль, а также из кода будут удалены инструкции барьеров памяти (smp_mb), то возможны поведения, в которых после исполнения будет x == 0 и y == 0. При наличии барьеров памяти после исполнения хотя бы одна переменная всегда будет иметь значение один. Вообще этот код называется store buffering test о нём и не только о нём можно прочесть в статье a better x86 memory model.

    • Полезные материалы:

      • Открытая лекция «weak memory models» от Антона Подкопаева. В CSC тоже были лекции на эту тему: раз и два.
      • К двум лекциям от CSC необходимо добавить статью Memory Barriers: a Hardware View for Software Hackers (http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)
      • Статья расскажет о том, что такое store buffer(write buffer) и как работают барьеры памяти. A better x86 memory model: x86-TSO (extended version). В ней можно найти тесты (litmus tests) для модели x86 и проверить свой интерпретатор
      • СТАТЬЯ, КОТОРАЯ МЕНЯЕТ ВСЁ! После прочтения этой статьи в конце 3й недели работы над домашкой. Я за 2 часа удалил 2/3 своего кода и получил работающие модели. Поэтому я уверен, что она может сильно помочь, после того, как всё предыдущее будет изучено и что-то будет написано.
  27. Объектно-ориентированый C# c классами и интерфейсами
    Подробнее
    • Наследование классов и интерфейсов, без generics.
    • public/private/protected и override.
    • Стандартные конструкции языка + приведение типов объектов.
    • Целые числа, строки, стандартные функции работы с ними; массивы и лямбды не надо.
    • Функции для печатанья значений переменных в языке.
    • Тайпчекер на случай, чтобы отфильтровывать бредовые программы.
    • new методы
      • Я слышал, что при их использовании вместе с интерфейсами, там возникает какая-то нетривиальная семантика. Надо будет разобраться. Вот пример.
  28. C# с исключениями
    Подробнее
    • С#, один класс в котором Main, другие методы и поля. Рекурсия, стандартные конструкции, присваивание. Анонимные лямбды не надо.
    • Синтаксис задания исключений. Наследование рудиментарное, только для исключений на 2 уровня глубины
    • Try/Catch/finally, фильтры исключений
      • API для открытия и записи в файл, чтобы можно было проверить, что в finally файл действительно закрывается.
  29. Python
    Подробнее
    • Cтандартные конструкции: циклы, ветвления, прочие
    • Стандартные типы: числа, строки, списки
    • Функции, анонимные функции, рекурсия и т.п.
    • Интерполяция строк
    • Классы и методы. Динамическое дополнение методов
    • Учитывать отступы и отсутствие отступов тоже надо 
      >>> {
...     "this": True,
...     "that": False,
...     "them": [1, 2,
... 3, 4, 5,
... 6, 7, 8,
... 9, 10, 11, 23]
... }
{'this': True, 'that': False, 'them': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23]}
  30. Menhir + рекурсивный спуск
    Подробнее
    • Такой своеобразный DSL для написания парсеров. По умолчанию он парсит LR-способом (вам не обязательно знать, что это такое)
    • без action кода, ассоциативность и приоритеты нужны
    • устранение левой рекурсии
  31. Go
    Подробнее
    • Стандартные типы данных (int, bool, string, char)
    • Функции (обычные, рекурсивные, first-class, замыкания (в том числе с поддержкой присваивания))
    • Циклы, условный оператор (if)
    • Массивы и присваивание можно не делать
    • Прочее
      • ключевые слова: break func if else continue for return var
      • предопределенные идентификаторы: bool int string true false nil len panic print println recover
Прочие замечания

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

Если у Вас есть предложения по добавлению других языков -- пишите.