Темы преимущественно про функциональное программирование. Во всех темах de facto консультирует Дмитрий Косарев (записываться на тему у него, добавляйте в копию запасной email ибо случаются казусы), а Семен Григорьев руководит de jure, а de facto читает тексты и презентации.

Такой же документ за прошлый год здесь.

TODO: задачи на допуск к допуску на вход.

Про ReScript/OCaml

Так как погромисты на Java не могут никак осилить синтаксис нормальных функциональных языков программирования, в Bloomberg (а потом и в Facebook) было предложено совершить ход конём и немного исправить испортить синтаксис уже имеющегося языка функционального программирования OCaml, чтобы он был более похож на привычный синтаксис с фигурными скобками и точками с запятой. Получившийся в результате Rescript (ранее известный как BuckleScript/ReasomML), хомячкам вроде понравился.

С таким подходом вроде бы всё хорошо, но есть проблема для чистокровных OCaml программистов: язык действительно сильно похож, но непохожести очень сильно бесят, никак не получается выкинуть из головы выученный синтаксис и пользоваться новым, потому что то, что видно на экране очень сильно напоминает "старый" синтаксис OCaml. В итоге получаются ошибки, которые очень глупые, но компилятор ReasonML всёравно не доволен. И, наоборот, с ReScript может быть сложно пересесть на OCaml по сходным причинам.

Вот пример кода на OCaml:

type 'a expr = Const : int     -> 'a expr
             | App   : 'a * 'a -> 'a expr
             | Lam   : string * 'a -> 'a expr

let foo e = match e with
  | Const n -> n
  | App (l,r) ->
      let () = print_endline "blabla" in
      r
  | Lam (s, b) -> b

А вот, что получается при трансляции в ReScript.

type expr('a) =
  | Const(int): expr('a)
  | App('a, 'a): expr('a)
  | Lam(string, 'a): expr('a);

let foo = e =>
  switch (e) {
  | Const(n) => n
  | App(l, r) =>
    let () = print_endline("blabla");
    r;
  | Lam(s, b) => b
  };

Парсер синтаксиса ReScript, с восстановлением от ошибок

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

Замечание: в ReScript есть также старый парсер, который разбирает язык похожий на OCaml. Можно исправлять его (ссылку найдете сами).

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

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

Парсер ReScript, с использованием подхода парсер-комбинаторов

На данный момент парсер ReScript написан методом рекурсивного спуска. Скорее всего от парсер-комбинаторов отказались из-за опасений недостаточной производительности (хотя видео Джонатана Блоу, создателя Braid, я не смотрел). Хочется:

  1. Подтвердить или опровергнуть, что парсер-комбинаторы торомозят.

  2. Проверять, что с ними писать более удобно не нужно (потому, что это вроде как очевидно).

  3. Скорее всего, придется проверять, что с парсер-комбинаторами сложнее делать восстановление от ошибок.

  4. Предъявить техники написания парсер-комбинаторов, которые повышают производительность итогового парсера. Например,

    1. В таких-то случаях нам нужна мемоизация, а в таких-то она не поможет.

    2. Тогда-то стандартный подход лучше как-то видоизменить.

    3. Здесь лучше рекурсию сменить на итерацию.

    4. А тут аппликативные парсеры работают шустрее, чем монадические.

    5. Ну или "мы тупо пишем с парсер-комбинаторами, код в 10 раз короче, работает всего лишь на 10% медленнее. Победа"

Уровень: курсовая/ВКР в зависимости от поставленных задач.

С чего начинать:

  1. посмотреть на библиотеки парсер-комбинаторов;

    1. Angstrom

    2. Ostap и т.п.

    3. или какие-то библиотеки, задизайненные специально под ReScript (найдёте сами).

  2. разобраться с особенностями-недостатками похода: левая рекурсия, longest match first.

  3. начать переписывать парсер на основе кодовой базы ReScript

  4. готовить текст курсовой записки для зимнего зачета

Требования к обучающемуся:

  • желательно знакомство с ФП языками (OCaml, Haskell, Scala 3);

  • желателен общий кругозор в области синтаксического анализа (LL, LR, GLR, GLL, Packrat, Meerkat).

Подробнее (спойлер)

Тип работы: эксперимент.

В результате не должно казаться так, что это работа на выходные про "закодить парсер какого-то подмножества ReScript".

  1. В OCaml/ReScript существует много библиотек парсер-комбинаторов. Обучающийся должен выбрать одну, быть способен обосновать выбор и кратко сказать в чем преимущества и недостатки остальных реализаций парсер-комбинаторов.

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

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

  4. Если новый парсер будет

    1. занимать меньше строк

    2. не сильно проседлать по производительности

    3. поддерживать всё, что умеет предыдущий парсер (фичи языка, восстановление от ошибок)

      то это тоже будет существенным плюсом работы.

Про интеграцию OCaml с IDE

На данный момент интеграцию с IDE для языка OCaml предоставляет проект merlin. Также существует надстройка над ним OCaml Language Server, реализующая Language Server Protocol, которая позволяет соединять бэкэнд интеграции IDE c любимым текстовым редактором. Фронт работ в этой области связан с

  • добавлением новых рефакторингов и т.п.

  • поддержка модификаций синтаксиса, а также восстановление от ошибок синтаксиса.

TODO: видео с Spb Rust Meetup 2019 от matklad.

Публикации из этой области могут выглядеть так:

Семантическая подсветка (и/или) идентация

В функциональном программиовании часто используется паттерн проектирования, заключающийся в создании встраиваемых предметно-ориентированных языков (Embedded Domain Specific languages, EDSLs) для некоторых видов API, например:

  • eDSL для создания запросов к реляционной базе данных

  • для описания XML

Такие встраиваемые языки часто требуют особых правил подстветки и отступов по сравнению с host-языком, куда они встроены. Сейчас в LSP уже ведется работа по добавлению в спецификацию возможностей semantic highlighting. (P.S. Похоже её таки уже добавили в спецификацию: вот про цвета и вот про форматирование)

Что надо сделать:

  • в реализации OCaml Language Server сделать/доделать поддержку раскрашивания синтаксиса и форматирования с отступами.

  • сделать возможность описывать правила подстветки кода библиотекам на OCaml

  • доделать редактор кода, который умеет общаться с LSP сервером (например, VS Code), чтобы он научился показывать то, что прислал сервер.

Текущее состояние дел:

  • ocaml-lsp-server вызывает стороннее приложение для форматирования кода (ссылки раз и два, надеюсь номера строк не уедут со времененем)

  • для подсветки синтаксиса в ocaml-lsp-server реализованы только заглушки.

Замечание: настраиваемое форматирование можно выделить в одну тему, а подсветку — в другую похожую тему.

Уровень: курсовая; возможен последующий апгрейд до бакалаврской.

Пожелания к обучающемуся:

  • знакомство с OCaml;

  • знакомство с eDSL;

  • знакомство с технологией разработки/расширения соответствующего редактора (для VS Code это язык TypeScript);

  • отсутствие страха окунуться в большие проекты.

Поддержка синтаксических расширений на основе Camlp5

На данный момент в OCaml/Merlin поддерживаются синтаксические расширения на основе PPX. Последовательность обработки примерно такая:

  • входной код на OCaml разбирается парсером merlin в абстрактное синтаксическое дерево (AST)

  • merlin’у объяснены используемые compile-time синтаксические расширения, он их применяет, чтобы преобразовать OCaml AST в другое OCaml AST

  • после всех преобразований запускается проверка типов, поиск рефакторингов и т.п.

Особенности данного подхода:

  • синтаксический анализ проводится только над AST OCaml, что не дает расширять синтаксис произвольным способом.

При этом в экосистеме OCaml присутствует альтернативный способ расширения синтаксиса с помощью Camlp5. Его особенности

  • расширяемый парсер, отличный от используемого в компиляторе OCaml, позволяет описывать модификации синтаксиса на интересном eDSL.

  • позволяет изменять грамматику очень сильно; у этого есть как особенности, так и недостатки.

Что надо сделать. Необходимо добавить в OCamlMelrin+OCamlLSP поддержку синтаксических расширений на основе Camlp5:

  • научить merlin понимать информацию о подключенных синтаксических расширениях Camlp5

  • изменить логику так, чтобы в присутствии Camlp5 сначала применялся парсер Camlp5, который на выходе даст AST компилятора OCaml, уже после это применять расширения синтаксиса на основе PPX.

  • уже после этого запускать поиск рефакторингов и т.п.

Начинать эксперименты стоит c этого файла. Например, в зависимости от переменной окружения и/иди имени файла надо запускать синтаксический анализ с помощью camlp5, а не то, что там сейчас есть.

Уровень: курсовая; возможен последующий апгрейд до бакалаврской.

Пожелания к обучающемуся:

  • знакомство с OCaml;

  • отсутствие страха окунуться в большие проекты.

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

miniKanren

У нас в лаборатории есть некоторая "тусовка" на тему реляционного (логического) программирования на miniKanren. Если кратко, то это DSL, чтобы относительно естественно решать переборные задачи, например, "перебери мне все программы, и дай те, которые возвращают свой текст". Есть ещё своя реализация miniKanren, которая называется OCanren, на функциональном языке программирования OCaml (он более дружелюбен к новичку, чем Haskell, ИМХО, конечно же).

Скажу сразу, miniKanren — это околонаучная штука на любителя.

TODO: добавить мотивирующее видео от Matthew Might’а с miniKanren Workshop 2020

Про мемоизацию

Евгений Моисеенко сделал tabling (связанные понятия: мемоизация и кеширование) для OCanren некоторым способом, но есть ещё и другой, на основе Substitution Tree Indexing by Peter Graph. Разумеется, всё придумали до нас, и нужно только прочитать и реализовать.

Уровень: курсования

От студента требуется:

  • отсутствия страха читать статьи на английском

  • желание попрограммировать немного на OCaml.

Pandoc

Сегодня СПбГУ засталвляет преподов создавать документ "РПУД" (Рабочая программа учебной деятельности) в DOCX формате. Редактировать такое в Word — это боль, поэтому преподы хотели бы использовать LaTeX для этого (или какой-либо другой текстовый формат, где хорошо работает версионирование и облегчено комментирование изменений). Поэтому, надо научиться преобразовывать документы из LaTex в DOCX.

Проект Pandoc (написанный на Haskell) существует как раз для этого. Он уже умеет преобразоывать заголовки и прочий кириллический текст в DOCХ (и в большое количество других форматов документов), но, по-видимому, поддержка таблиц и тутульной страницы не реализована никак.

Задача: доработать Pandoc до состояния, при котором можно адекватно преобразовать проект РПУДа из LaTeХ в DOCX.

В общем виде преобразовывать произвольный LaTeX нереально, так как там есть даже встроенный язык программирования. Необходимо поддержать только те фичи, которые нужны для преобразования документов РПУД.

Уровень: курсовая.

Инкрементальные вычисления с матрицами

Существует некоторая тусовка инженеров-исследователей, которые сводит все задачи (например, синтаксический анализ графов) к перемножению матриц (например, инциденций) на GPU. При этом, если меняется одна ячейка в матрице (доабвляется новое ребро в графе) или появляются новые строки/столбцы в матрице (добавляется новая вершина в граф), то новые результаты перемножения матриц получаются повторным перемножением на GPU.

Есть предложение оптимизировать это стандартными способами, например применением инкрементальных вычислений. Идея инкрементальных вычислений заключается в том, что по вычисляемой функции строится некоторая модель вычисления, зависящая от входных аргументов, и когда меняется один из аргументов, то перевычисляются только те подвыражения, которые зависят от этих изменившихся аргументов. Например, для случая изменения одной ячейки матрицы, нам нужно перевычислить некоторое количетсво сумм, линейно пропорциональное размерам матрица, в то время как перемножение матриц заново имеет квадратичную сложность (пусть и на GPGPU).

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

Уровень: курсовая

В планах лежит попытка это опубликовать на тематическм воркшопе GRADES NDA (ну или на нашем родном SEIM).

Про Eldarica и IC3

Как-то один человек попросил меня придумать тему про Scala, но ничего лучше, чем это у меня не получилось.

Eldarica --- это SAT/SMT солвер написанный на Scala. Идея работы заключается в добавлении туда чего-нибудь. В код я особо не лазал, в чем Эльдарика особенно хороша я не знаю, по хорошему надо бы написать письмо Рюммеру и поинтересоваться куда он хочет её развивать.

Предлагается в каком-то виде прикрутить алгоритм IC3 к Эльдарике. Вот какие-то слайды про алгоритм, умные научные статьи сможете найти сами. Алгоритм мудрёный, там замешана мат. логика, так что пока разберётесь, то придется пострадать.

  1. Как минимум, должен быть реализован рабочий алгоритм на Scala.

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

  3. Алгоритм должен получиться максимально аккуратно реализован и хорошо читаем. Основная цель работы: полшучить реализацию, с помощью которой можно максимально быстро объяснить новым людям (базово знакомым с мат. логикой) "потроха".

  4. В идеале алгоритм должен параметризовываться модулем, который

    1. либо ничего интересного не делает и на производительность не влияет

    2. либо логгирует трассировку промежуточных состояний (графически отображает, что происходит) для облегчения понимания того, что происходит.

  5. Совсем идеальный вариант: алгоритм должен работать не сильно медленнее, чем аналогичная реализация на С++.

https://theory.stanford.edu/~arbrad/papers/Understanding_IC3.pdf