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

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

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

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

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

Тема для D

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

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

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

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

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

OCaml + ADT
Подробнее
- Всё, что есть в теме для D
- алгебраические типы как основной способ проектирования типов; учтите, что
  - в OCaml и Haskell типы int и float -- примитивные (встроенные)
  - тип списков алгебраический и там, и там; в AST не должно быть, что списки отдельно, а алгебраические значения отдельно
  - в OCaml тип bool примитивный, а в Haskell -- алгебраический
- разумеется, объявления типов, паттерн-мэтчинг и типизация
- присваивание не надо
- исключения не надо
OCaml + Extensible variant types
Подробнее
- Всё, что есть в теме для D
- Recursive definitions of values. Плохой синтаксис должен выдавать ошибку типизации. В простенькие бесконечные списки должно быть можно загрянуть.
OCaml + Recursive values
Подробнее
- Всё, что есть в теме для D
- алгебраические типы заменены на extensible variants
OCaml + полиморфные вариантые типы
Подробнее
- Всё, что есть в теме для D
- Глава про полиморфные варианты в мануале OCaml
- Объявления типов можно не делать
- Стандартные типы (пары, списки, option) можно делать, а можно не делать, выразив через полиморфные варианты
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
```
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
```
Haskell + стандартные типы данных + ленивость
Подробнее
- Всё, что есть в теме для D
- С ленивостью надо будет продемонстрировать работоспособность
  - Лямбда-исчисления с call-by-name
  - ленивых списков и операция над ними (в том числе, фибоначчи, решето Эратосфена и т.п.)
  - прочие ленивые задачи (например, за один проход заменить все числа в дереве на их минимум и вернуть новое дерево)
OCaml + ООП
Подробнее
- Всё, что есть в теме для D, кроме n-ок.
- в OCaml есть интересные объекты и их типизация, нужно поддержать объекты+методы+поля.
- (может быть классы и наследование тоже надо будет, но пока не уверен)
- как тесты предлагаю реализовать некоторые структуры данных как камлёвые объекты и посмотреть, что будет
OCaml + effects (2 человека)
Подробнее
- Всё, что есть в теме для D
- Cупер-модное в наши дни движение в мире ФП
- По сути, это исключения, но в момент обработки которых у нас есть функция, которой можно был передать значение, которое должно было бы быть вместо бросания исключения, и продолжить исполнение с места бросания исключения.
- Туториал в контексте OCaml https://github.com/ocamllabs/ocaml-effects-tutorial
- два человека только потому, что хочу чтобы задачу кто-то взял. А так это очень сильно напоминает задачи про delim/cc
OCaml + printf
Подробнее
- Всё, что есть в теме для D
- Поддержка типов char, string и операций с ними
- Поддержка в компиляторе функции форматированой печати (по аналогии с камлёвым модулем Printf/Format). Разумеется, всё должно быть type safe.
OCaml, именованые и опциональные аргументы
Подробнее
- Всё, что есть в теме для D
- Захардкоженный тип option
- Именованные и опциональные аргументы. Функции должны типизироваться и исполняться как в настоящем OCaml.
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 этого нет.
OCaml + weak type variables
- Всё, что есть в теме для D
- https://ocamlverse.net/content/weak_type_variables.html. Присваивание неоходимо, так как без него тема бессодержательна.
F# + Units of Measure
Подробнее
- Всё, что есть в теме для D
- Вещественные числа (обосновано следующим пунктом)
- Возможность объявлять и использовать Units of Measure
OCaml + скомпилированные алгебраические типы
Подробнее
- (задача может показать объёмной, поэтому разрешаю сдавать в одной кодовой базе в месте с задаче про OCaml + ADT)
- Прочитать как окамлёвые алгебаические типы представляются в памяти, разобраться как устроены "блоки" и unboxed immediate values
- Написать парсер (параметризовать уже существующий из другой задачи) который понимает функции для конструирования/заглядывания в блоки
- Интерпретатор
- Алгоритм преобразования программ с алгебраиками и сопоставлением с образцом в низкоуровневое представление.
- Преобразования программ из задачи про ADT, в низкоуровневое представление этой задачи. (По сути надо избавляться от алгебраических значений и сопоставления с образцом. Можно посмотреть алгоритм с матрицами отсюда )
Scheme + call/cc
Подробнее
- относительно легко гуглящаяся особенность Scheme
- call/cc
- целые числа, рекурсия, списки, печать на консоль
- функции обычные и анонимные, замыкания и рекурсия
- присваивание не надо
- quote/unquote
- парсер очень простой
- никаких статических типов, разумеется, нет
- учитывая следующую задачу, получается в некотором смысле на двоих
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
Ассемблер x86_64
Подробнее
- Очень простой язык и для парсинга, не такой простой для реализации интерпретатора.
- Язык должен быть настоящим ассемблером, т. е. входные программы должны компилироваться соответствующим компилятором (nasm) и выдавать ответ как в интерпретаторе. Сделайте cram тесты, демонстрирующие это.
- Примеры в первую очередь берите из первой части книжки И. Жиркова "Low-level programming". Там должен быть helloworld, который требует syscall и память.
- Чтобы задача не была чересчур простой, хочу также в ассемблере SIMD операции и тесты к ним (перемножение вектора/матрицы на вектор/матрицу)
- Опыты прошлых лет показывает, что написание AST в лоб оставляет большое пространство для плохих программ, представимых в AST. Например, 64битные команды никак не должны принимать 32битные операнды-регистры как аргументы. Потребуется обмазаться фантомными-типами и/или GADT, чтобы не нужно было писать гавнокод. Буду следить!
Refal 5
- одскульный отечественный язык программирования, где последовательности можно мэтчить не только с начала, но и с конца
- здесь, есть 22 примера простых программ на рефал-5
- а здесь есть програмки посложнее
Pascal c алгебраическими типами
- Числа, строки и операции с ними. Функции обычные и вложенные, с рекурсией. Вроде как по сравнению с miniML тут не будет вывода типов, только проверка типов. Присваивание не надо.
- алгебраические типы данных variant records (пункт 12).
Cи
Подробнее
- Целые числа разного размера (например, int32_t и int8_t)
- char
- Cтандартные конструкции: циклы, ветвления, прочие
- Указатели и арифметика указателей, malloc / free
- Продемонстрировать стандартные примеры программ на указатели
  - Короткий memcpy и что с ним может пойти не так
  - Реинтерпретировать кусок памяти с массивом int32_t как в 4 раза большее количество чисел int8_t
- Функции и рекурсия: факториал, фибоначчи, и т.п.
- Объявления пользовательских структур не надо.
Lua -- примитивный язык без статических типов
Подробнее
- Вещественные числа, строки
- Функции и функции высшего порядка
- Стандартные конструкции: ветвления, цикл и т.п.
- Присваивание и хитрые ассоциативные массивы с двойной индексацией, специфичные для Lua
Javascript (2 человека)
Подробнее
- Объекты, числа, строки, массивы (т.е. присваивание надо)
- Функции обычные и анонимные, замыкания, рекурсия
- Типичное для Javascript прототипное наследование
- Стрёмные штуки из WAT talk и отсюда. Их будет много (постепенно добавлю)
Моделирование параллельного исполнения
Подробнее
За описание благодарите старшего студента.
- 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 своего кода и получил работающие модели. Поэтому я уверен, что она может сильно помочь, после того, как всё предыдущее будет изучено и что-то будет написано.
Объектно-ориентированый C# c классами и интерфейсами
Подробнее
- Наследование классов и интерфейсов, без generics.
- public/private/protected и override.
- Стандартные конструкции языка + приведение типов объектов.
- Целые числа, строки, стандартные функции работы с ними; массивы и лямбды не надо.
- Функции для печатанья значений переменных в языке.
- Тайпчекер на случай, чтобы отфильтровывать бредовые программы.
- new методы
  - Я слышал, что при их использовании вместе с интерфейсами, там возникает какая-то нетривиальная семантика. Надо будет разобраться. Вот пример.
C# с исключениями
Подробнее
- С#
  - Int, string, bool (без array, double)
  - тип var по желанию (если не считаете C# *** языком)
- один класс в котором Main, другие методы и поля. Рекурсия, стандартные конструкции, присваивание.
  - Анонимные лямбды не надо.
  - ovarride/virtual не надо (бессмысленно)
- Без вложенных классов и методов
- Синтаксис задания исключений. Наследование рудиментарное, только для исключений на 2 уровня глубины
- Try/Catch/finally, фильтры исключений
  - API для открытия и записи в файл, чтобы можно было проверить, что в finally файл действительно закрывается.
С# с мультиметодами
Подробнее
- По сслыке есть пример из Вики, который показывает их в действии.
- Поддержать нужно в языке как минимум всё то, что нужно для этого примера
- присваивание надо, функции как first class citizens -- нет.
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]}
```
Ruby (все фичи, что есть в Питоне, но Руби)
Menhir + рекурсивный спуск
Подробнее
- Такой своеобразный DSL для написания парсеров. По умолчанию он парсит LR-способом (вам не обязательно знать, что это такое)
- без action кода, ассоциативность и приоритеты нужны
- устранение левой рекурсии
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
Prolog/Datalog Solving murder with prolog
Cypher
Подробнее
- мини-язык для доступа к графовым базам данных
- простой парсер, простой интепретатор, который исполняет запросы на конкретных графах
- Пример возьмите отсюда и отсюда, их там много
- Использовать свой тип данных для представления графов запрещено. Возьмите какую-нибудь библиотеку.
Производительный SQL
Подробнее
- Минимальный язык запросов к базам данных: SELECT, JOIN WHERE и может что-то ещё
- Интерпретатор запросов на этом языке
- Эти запросы должны исполняться на больших данных, автогенеренных с помощью https://github.com/NetApp/SQL_Storage_Benchmark. Постарайтесь не складывать большие файлы в Git, а придумать, чтобы они докачивались при билде.
- Большие входы должны заставить интерпретатор исполняться запросы эффективно, а не как попало.
LLVM IR
Подробнее
- Типы:
  - int'ы разной битности (i1 - int из одного бита = bool)
  - half, float, double
  - указатели
  - вектора, массивы, структуры
  - функции
  - токены, метки
- Весь набор инструкций
- High level structure реализовывать не нужно, но нужно уметь их отбрасывать, чтобы можно было запускать программы включающие их

Гробики

OCaml + GADT (2 человека, т.к. напоминает гроб)
Подробнее
- Всё, что есть в задаче OCaml+ADT
- OCaml где алгебраические типы заменены на обобщенные (generalized) алгебраические типы
- Интерпретатор точно будет такой же, как в задаче про обычные алгебраические типы
- Вывод/проверка типов (сильно) сложнее, чем для обычных алгебраических, поэтому два человека
  - Нужно поддержать явные аннотации типов, потому что автоматический вывод типов не могёт
  - Типовые переменные могут убегать из области видимости и т.д.
- Умная сслыка, описывающая что примерно вас ждет
OchaCaml (Caml Light + delim/cc) (2 человека, т.к. напоминает гроб)
Подробнее
- стандартные типы (числа, списки),
- функции обычные и анонимные, замыкания и рекурсия
- конструкции для отладочной печати
- delim/сс
- полиморфные типы для всего этого
  - типизация там необычная, надо по одной ссылке долистать до описания того, как это типизировать; по другой ссылке долистать до способов написания интерпретатора/компиляции
- По сути эта задача и две предыдущие про */сс -- суть одно и то же

Прочие замечания

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

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

tasks.md

tasks.md

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

Тема для D

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

Гробики

Прочие замечания

Files

tasks.md

Latest commit

History

tasks.md

File metadata and controls

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

Тема для D

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

Гробики

Прочие замечания