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

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

Я рассчитываю, что сами разделите темы с помощью Excel-подобной таблички.

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

В том году темы выдавались на одного, потому хвостисты страдают.

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

Тема для допуска на E

Задача выдается, если вас устраивает итоговая оценка не выше E. Данная тема выдается неограниченному кругу студентов. Я в свою очередь не буду смотреть код и запускать линтер --- проверяться будет только прохождение тестов.

Реализовать для языка miniML:

синтаксический анализатор (парсер),
- Он должен работать шустро, а не парсить объявления факториала 10 секунд.
type checker
интерпретатор.

Должны обрабатываться ошибки процессе парсинга/типизации/интерпретации (ДЗ не должно крешиться).

Описание MiniML

В язык включаются:

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

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

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

OCaml + ADT
Подробнее
- Всё, что есть в теме для E
- алгебраические типы как основной способ проектирования типов; учтите, что
  - в OCaml и Haskell типы int и float -- примитивные (встроенные)
  - тип списков алгебраический и там, и там; в AST не должно быть, что списки отдельно, а алгебраические значения отдельно
  - в OCaml тип bool примитивный, а в Haskell -- алгебраический
- разумеется, объявления типов, паттерн-мэтчинг и типизация
- присваивание не надо
- исключения не надо
OCaml + Extensible variant types
Подробнее
- Всё, что есть в теме для E
- алгебраические типы заменены на extensible variants
OCaml + Recursive values
Подробнее
- Всё, что есть в теме для E
- Recursive definitions of values. В простенькие бесконечные списки должно быть можно заглядывать.
  - Плохой синтаксис должен выдавать ошибку типизации: this expression is not allowe on RHS of let rec
OCaml + полиморфные вариантые типы
Подробнее
- Всё, что есть в теме для E
- Глава про полиморфные варианты в мануале OCaml
- Объявления типов можно не делать
- Стандартные типы (пары, списки, option) можно делать, а можно не делать, выразив через полиморфные варианты
OCaml + bidirectional records
Подробнее
- Всё, что есть в теме для E
- поддержать синтаксис приписывания (англ. 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
```
OCaml + labelled tuples
F# + active patterns
Подробнее
- Всё, что есть в теме для E
- возможность описывать активные паттерны, которые выглядят как алгебраические конструкторы
```
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
```
F# + Units of Measure
Подробнее
- Всё, что есть в теме для E
- Вещественные числа (обосновано следующим пунктом)
- Возможность объявлять и использовать Units of Measure
Haskell + стандартные типы данных + ленивость
Подробнее
- Всё, что есть в теме для E
- С ленивостью надо будет продемонстрировать работоспособность
  - Лямбда-исчисления с call-by-name
  - ленивых списков и операция над ними (в том числе, фибоначчи, решето Эратосфена и т.п.)
  - прочие ленивые задачи (например, за один проход заменить все числа в дереве на их минимум и вернуть новое дерево)
Haskell + Pattern Synonyms + View Patterns
Подробнее
- Всё, что есть в теме для E
- Два расширения Haskell на тему сопоставления с образцом.
- Это очень похоже на тему про F# + Active patterns.
- Хоть это и хаскель, для упрощения жизни, я не планирую проверять ленивость стратегии. Можете делать вид, что это скорее PureScript
Purescript + простые классы типов
Подробнее
- Всё, что есть в теме для E
- Синтаксис не как в OCaml, а скорее как в Haskell, вычисления строги
- Простая поддержка классов типов --- средства для overloading.
OCaml + ООП
Подробнее
- Всё, что есть в теме для E, кроме n-ок.
- в OCaml есть интересные объекты и их типизация, нужно поддержать объекты+методы+поля.
- (может быть классы и наследование тоже надо будет, но пока не уверен)
- как тесты предлагаю реализовать некоторые структуры данных как камлёвые объекты и посмотреть, что будет
OCaml + printf
Подробнее
- Всё, что есть в теме для E
- Поддержка типов char, string и операций с ними
- Поддержка в компиляторе функции форматированой печати (по аналогии с камлёвым модулем Printf/Format).
  - printf, sprintf, ksprintf, конкатенация форматированных строк
  - Разумеется, всё должно быть type safe.
OCaml, именованые и опциональные аргументы
Подробнее
- Всё, что есть в теме для E
- Захардкоженный тип option
- Именованные и опциональные аргументы. Функции должны типизироваться и исполняться как в настоящем OCaml.
OCaml + weak type variables
Подробнее
- Всё, что есть в теме для E
- https://ocamlverse.net/content/weak_type_variables.html. Присваивание неоходимо, так как без него тема бессодержательна.
SML + equality types + value restriction
Подробнее
- Почти предыдущая задача, но проще
- Немножко другой парсер, потому что SML немножко отличается
- Еquality types:
  - в типах функций появляются типовые переменные с двумя апострофами, что означает, что туда можно подставлять только типы, на которых работает функция проверки на равенство (функции и вещественные числа нельзя сравнивать)
- Value restiction
  - Заставляет выводить менее полиморфные типы, потому что присваивание может нарушать типовую безопасность
  - https://users.cs.fiu.edu/~smithg/cop4555/valrestr.html
Scala + By-name Parameters
Подробнее
- Всё, что есть в теме для E
- Другой парсер (!)
- Параметры функций, которые не Call-by-Value (как в OCaml/Scala), а call-by-name (как в Haskell)
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
Ассемблер RISC-V 64
Подробнее
- Очень простой язык и для парсинга, не особо сложный для интерпретации.
- Язык должен быть настоящим ассемблером, т.е. входные программы должны компилироваться соответствующим (кросс)компилятором и выдавать ответ как в интерпретаторе. Сделайте cram тесты, демонстрирующие это.
- Нужно поддержать некоторые системные вызовы Linux для отладки программ, на подобие выхода и печати в stdout.
- Так как язык простой, нужны расширения Bitmanip и RVV, в мере, достаточной для интересных тестов.
- Опыты прошлых лет показывает, что написание AST в лоб оставляет большое пространство для плохих программ, представимых в AST. Например, 64битные команды никак не должны принимать 32битные операнды-регистры как аргументы. Потребуется обмазаться фантомными-типами и/или GADT, чтобы не нужно было писать гавнокод. Буду следить!
Go с горутинами
Подробнее
- Стандартные типы данных (int, bool, string)
- Циклы
- Условный оператор (if)
- Массивы
- Функции (обычные, рекурсивные, замыкания (в том числе с поддержкой присваивания))
- Каналы (достать, положить, закрыть)
- Горутины (переключение по ожиданию данных из канала)
- Замечания:
  - используется урезанная версия Go 1.17
  - в string нету доступа по индексу (т.к. нету символьного типа)
  - ключевые слова: break func defer go chan if else continue for return var
  - предопределенные идентификаторы: bool int string true false nil make close len panic print println recover

Посложнее

OCaml с типизированными эффектами
Подробнее
- Всё, что есть в теме для E
- 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 + GADT
Подробнее
- Всё, что есть в задаче OCaml+ADT
- OCaml где алгебраические типы заменены на обобщенные (generalized) алгебраические типы
- Интерпретатор точно будет такой же, как в задаче про обычные алгебраические типы
- Вывод/проверка типов (сильно) сложнее, чем для обычных алгебраических, поэтому два человека
  - Нужно поддержать явные аннотации типов, потому что автоматический вывод типов не могёт
  - Типовые переменные могут убегать из области видимости и т.д.
- Умная сслыка, описывающая что примерно вас ждет
- Если будут работать гетерогенные списки и равенство по Лейбинцу, то можно и С поставить без экзамено обоим
OCaml + effects
Подробнее
- Всё, что есть в теме для E
- Cупер-модное в наши дни движение в мире ФП
- По сути, это исключения, но в момент обработки которых у нас есть функция, которой можно был передать значение, которое должно было бы быть вместо бросания исключения, и продолжить исполнение с места бросания исключения.
- Туториал в контексте OCaml https://github.com/ocamllabs/ocaml-effects-tutorial

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

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

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

tasks.md

tasks.md

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

Тема для допуска на E

Описание MiniML

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

Посложнее

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

Files

tasks.md

Latest commit

History

tasks.md

File metadata and controls

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

Тема для допуска на E

Описание MiniML

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

Посложнее

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