Курсовые работы

Тут должны быть перечислены темы и идеи курсовых (и т.п.) работ. Для отдельных направлений может иметься отдельная страница.

Вопросы и просьбы описать тему более подробно засылать в Telegram.

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

Дооформленные

Rukaml

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

Текущий прототип находится здесь. Там есть

• MiniML, где из типов данных только n-ки.
• Typechecker в стиле Hindley-Milner
• Компиляторы в AMD64/RISC-V 64, и в LLVM (отстающий)
• Простой копирующий сборщик мусора.

“Абстрактные” темы, которыми можно позаниматься.

• Исследование альтернативных представлений данных для языка программирования OCaml.

  Сейчас используются “теггированные intы”, интересно понять. какой эффект будет, если базовым представлением значений будет double (NaN boxing как в V8)

• Изучение сборки мусора на платформе LLVM, чтобы научиться делать прототипы компиляторов языков с сборкой мусора.

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

• Можно исследовать оптимизации императивных “числодробилок” в сторону автовекторизации.

  Сейчас в компиляторе OCaml это поддержано вообще никак, может получиться что-то интересное.

• Интересно сделать для OCaml производительный JIT.

  Сейчас есть способ компиляции OCaml в стековый байткод, который уже JITтили, и получали ускорение в 2 раза. К сожалению, это примерно в 5 раз медленнее, чем компиляция OCaml в native код. По-видимому, вначале надо скомпилировать OCaml в регистровый байткод (JVM, .NET или чего попроще), и джиттить уже эту абстрактную машину.

• Было бы неплохо добавить в язык a la OCaml активные паттерны из F#,

  и научиться оптимизировать компиляцию с их участием.

• Можно немного отклониться, и позаниматься добавлением процессорно-специфичных инструкций в настоящий OCaml. На вскидку можно заняться расширениями для RISC-V про bitmanip, про векторные рамширения или про T-HEADовские векторные расширения. Можно вдохновляться ocaml-flambda, где бойцы занимаются чем-то подобным для amd64 и aarch64, но ничего про RISC-V там нет. (Этим уже частично занимался Габдрахманов.)
• TODO: https://player.vimeo.com/video/833791219#t=3h42m48s

Наверно, 3курсниками ПИ, которым сдавать в 5 семестре курс по компиляторам, это будет более интересно. Думаю, что второкурсникам, не знакомым с OCaml, абстрактные темы ещё не по зубам. В таком случае есть более “конкретные” темы.

• Выделения памяти на стеке и хвостовая рекурсия.

  Никакой поддержики хвостовой рекурсии сейчас нет. Для уважающего себя функционального языка она необходимо. Также стоило бы рядом реализовать аннотации (@@local), чтобы выделять некоторые данные на стеке (для простоты – n-ки). Эта идея не с потолка, этим действительно занимаются.

• Алгебраических типов пока совсем нет. Можно придумать общую тему на двух человек, где
  • один защищает алгебраические типы и их компиляцию
  • другой — generalized алгебраические типы и тайпчекер. Даже не знаю, какая из двух половин проще или сложнее. Наверное, это можно как-то скерстить с допуском по курсу ФП.
• Присваивания в языке нет. Хорошо бы добавить его (или сразу массивы) в язык, а также порождение кода. При этом можно сделать
  • relaxed value restriction как в OCaml,
  • или что-то более навороченное.

• Поддержка программ, разбитых на файлы

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

• Объединить порождение кода для RISC-V и AMD64.

  Сейчас там по сути две независимые реализации. Как вариант, можно повторить C– как в OCaml. Про это всё есть статьи, но такое ощущение, что лучше подсмотреть представление в реальном коде и сделать как в OCaml.

• Реализовать промежуточное представление программы с помощью CPS.

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

  • Conversion by Hirrolot Скорее всего самый простой вариант
    • Evaluation by Hirrolot
  • https://wingolog.org/archives/2023/05/20/approaching-cps-soup
  • Reasoning about Programs in Continuation-Passing Style 1993 https://citeseerx.ist.psu.edu/doc/10.1.1.22.7509
  • No-Brainer CPS Conversion (Functional Pearl) by Milo Davis, William Meehan, and Olin Shivers

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

OCaml linter (a.k.a. zanuda)

Код на языках прораммирования можно пытаться проверять разными способами и утилитами. Те проверки, которые не делает компилятор часто реализуют с помощью так называемых “линтеров”. Для языка OCaml на языке OCaml мною написан такой линтер, он применяется для проверки домашних заданий обучающихся на 2м курсе ПИ.

Сейчас он кое-что умеет, но есть куда развиваться. Есть небольшое количество инфраструктурных задач, а также большое количество проверок (“линтов”), которые пока не реализованы. Мне нужно найти человек(-а), который реализует большее количество линтов.

По сути задача разбивается на большое количество небольших задач по реализации (иногда исправлению) проверок. Так как из работы сложно выделить цельную большую задачу, то она плохо подходит под ВКР. (Но если Вы найдете формального научника, которых убедит меня, что всё хорошо – посмотрим.) Лучше всего это делать как набор полугодовых учебных практик. Публикация сомнительна (если только после набора большой и интересной статистики; в местах, где обсуждается обучение ФП (например, workshop TFPIE)). Количество линтов/задач, которые нужно реализовать зависит от вредности комиссии, которой вы будете это сдавать.

Если обучающийся уже владеет функциональным программированием (OCaml, Haskell, Scala, F#), то ему будет проще разобраться.

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

В функциональном программиовании часто используется паттерн проектирования, заключающийся в создании встраиваемых предметно-ориентированных языков (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);
• отсутствие страха окунуться в большие проекты.

OCaml + SAIL (предварительно занято)

SAIL — эмулятор процессоров, который запускается на пользовательских машинах. Принимает на вход свой язык (тоже SAIL) описания архитектуры, и компилирует это в эмулятор на Си или OCaml. (Например, вот модель описания архитектуры процессоров RISC-V). Сам компилятор эмуляторов написан на OCaml.

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

• можно подсказывать в программах на SAIL — что описываемые примитивы очень похожи на примитивы обычных процессоров, и поэтому можно генерировать соответсвующие интринзики, а не генерировать код в лоб;
• из общих соображений можно оптимизировать генеренный код (может быть если это скомпилировать в какой-нибудь рантайм с JIT, то оно начнет исполняться быстрее);
• можно оптимизировать генеренный код с учетом имеющихся бенчмарков, чтобы тестирование изменений в программах на SAIL проходило быстрее;
• можно оптимизировать программы на SAIL по ходу дела “хардкорными” методами, на подобие суперкомпиляции.

Темы до магистерской включительно. В 2022 году защищалась уже одна магистерская на эту тему.

OCaml + Embox

Товарищи из Mirage, которые занимаются unikernelами (образы серверов, объединенные с ОС, для развертывания в облаках), как-то решили переписать TLS на OCaml, чтобы не было в реализации ни строчки кода на Си. А следовательно, никаких undefined behaviour, неправильного доступа к памяти, heartbleed и прочих ужасов. Измерения показывают, что всё стало процентов на 20 медленнее, но более безопасно. Предоагается проверить, какие будут результаты, если попробовать запихнуть язык с сборкой мусора в слабое встраиваемое железо, а именно научиться линковать в опрационную систему Embox код на OCaml, сликовать реализацию TLS и провести тестирование производительности. Если интеграция OCaml и Embox пройдет удачно, то это откроет путь к большому количеству будущих курсовых/ВКР в стиле “мы переписали код приложения с Си на OCaml, добились безопасности, мы молодцы”.

По-видимому, содержательная работа будет больше похожа на попытку скомпилировать всё в кучу, чем на написание какого-то кода. Из-за этого выбирать эту тему как ВКР рискованно, как учебную практику – нормально. При этом я планирую помогать разбираться с косяками OCaml. С косяками Embox помогут ембоксёры (Антон Козлов).

Начинать стоит и осознования как именно кросс-компилируется OCaml. На данный момент Embox компилируется с помощью arm-none-eabi-gcc, а скомпилировать его с помощью armv6-unknown-linux-musleabihf-gcc наверное, никто не пробовал. Этим и стоит продолжить.

Думаю, что тут есть что поделать на год. Так как это по сути подготовительная база для будущих работ, то публикабельность сомнительна.

Реинжиниринг системы сборки MyBuild для Embox

Система сборки проекта Embox состоит из мешанины скриптов и Makefileов, которая задает некоторый язык описания проектов, но который на данный момент сложно расширять. Предлагается сделать систему сборки, которая понимаеттекущую кодовую базу, но более вменяемая.

TODO: добавить ссылки

Предпочел бы, чтобы это делал кто-то, покруче второкурсника. Разумеется, пропагандирую лучший в мире язык программирования OCaml :)

OCaml API для Telegram

Библотека TDlib является реализацией API Telegram на С++ и позволяет создавать альтернативные клиенты для Telegram. Сама библиотека написана на С++, а также содержит описание API Telegram, по которому можно автоматически генерировать “обвязку” для языков, отличных от С++.

Цель работы: реализовать интерфейс между имеющимся кодом на С++ и OCaml, чтобы получить возможности написания альтернативных клиентов или каких-либо автоматических аггрегаторов на языке OCaml. Конкретнее:

• Надо разбораться с описанием API: что это за формат (ad hoc или общеизвестный), как из него генерируются обвязки для других языков.
• Необходимо разобраться с демкой. Там вручную написана некоторая неполная обвязка и сделано приложение (на основе официального примера), которое может вопрошать у API Telegram кое-чего.
• В MVP из предыдущего пункта всюду использовались обычные алгебраические типы для видов сообщений. Возможно, использование OCaml-овских полиморфных вариантов в некоторых местах будет удобнее. Поэтому, генератор “обвязки” надо делать так, чтобы легко было изменить представление данных на стороне OCaml (сейчас для этого применены макросы С++)
• В конце предлагается сделать новый MVP 2.0, но не такой минимальный. А именно
  • Реализовать слушатель некоторых каналов/чатов телеграм, сообщения должны складировать в базу.
  • MVP 2.0 должен складировать соощения в локальную базу, чтобы отслеживать изменения/исправления и удаления сообщений.

Вполне себе курсовая на полгода. Не публикабельно.

OCaml + Qt/QML

В мире OCaml всё странно с проектированием GUI. Много фреймворков реализуют GUI с помощью реактивного программирования, но они специфичные для OCaml. Из общеприменимого можно называть Melange/ReasonML, который включает в себя поддержку программирования для Web с помощью ReactJS. Но HTML-движок имеет свои недостатки, в частности размер образа и производительность, по этому появились проекты React Native, Revery (свой нативный фреймворк для десктопа, где входной синтаксис повторяет проектирование на ReasonML для React, на данный момент заброшен) и Bogue (чисто OCaml, SDL2, GPU acceleration, по сути клон WinForms/Delphi/Swing).

Qt/QML остался без внимания. Это фреймворк для проектирования кроссплатформенных приложений для десктопа и смартфонов. Если не вдаваться в детали, то в нём три части: язык разметки, скрипты на JavaScript для написания простых преобразований GUI, и большое количество библиотек на С++.

Цель работы: скрестить Qt/QML и OCaml. Из этого можно выделять задачи и подзадачи на неопределенное количество человек.

частично сделано

• Хочется, чтобы была возможность описывать всё (GUI и бизнес-логику) не уходя сильно от языка OCaml. Сейчас в Qt/QML GUI описывается на языке QML, хотелось бы, чтобы всё переехало внутрь OCaml. Как вдохновение можно посмотреть как совмещается Javascript и HTML тэги (так называемый JSX).
  • Я сделал эксперимент на эту тему с Camlp5. Там HTML тэги в коде раскрываются в вызовы функций. Информации о типах там, правда, нет, но может она на превых порах и не нужна. Если таки нужна будет – придется делать как в ReasonML.
• Когда у нас будет поддержка описания разметки GUI в OCaml, нужно будет перегонять эту разметку в вид, понятный Qt/QML. Для начала предлагаю порождать код на QML напрямую, и вставлять в код на OCaml показ окошка с соответствующим кодом. Сложности:
  • Надо придумать, как именно использовать одни QML компоненты в других QML компонентах
  • В QML можно вставлять код на JavaScript, но это можно оставить на потом
• Это частично сделано в рамках учебных практик.

конь не валялся

• В Qt/QML можно писать мелкие скрипты на Javascript. Очень не хотелось бы, чтобы код на OCaml перемешивался с нетипизированным кодом на Javasctript. Гораздо лучше, если бы эти GUI-ориентированные скрипты писались на OCaml, и конвертировались в JavaScript вместе с получением QML файлов. ReasonML уже научился порождать по файлу на OCaml модуль на JavaScript, надо попробовать прикрутить это всё к Qt/QML и понять какие подводные камни там будут.
• На данный момент Qt/QML с JavaScript частично интепретируется и частично JITится. Из-за этого могут возникать некоторые проблемы с производительностью кода и скоростью старта программы. На практике это решается несколькими способами:
  • компилировать всё ahead-of-time;
  • перегонять QML в С++ и потом запускать, частично или целиком (раз, два).

  В принципе можно сразу порождать С++ из OCaml, но из соображений

  • отладки и,
  • трудностей и неожиданных подводных камней, связанных с таким подходом думаю, что целесообразней начать с порождения QML

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

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

Ознакомительная задача про lablqml

Можно заниматься менее абициозными задачами, а именно обязать пользователя писать на QML на QML, а логику на OCaml. Такой подход предлагается в проекте lablqml. Там осталось некоторое количество не очень сложных задач, я вижу их как ознакомительные или вводные для постепенного погружения в мир Qt/QML и OCaml. По сути надо взять некоторые прикольные особенности QML последних версий и поддержать примеры с оными в lablqml.

На семестр, для второго курса.

OCaml + .NET

Много кто пытался сделать ML-подобный язык в мире .NET (F#, SML.NET, OCamIL). Предлагается попробовать повторить их успех вначале для какого-то подмножетсва OCaml, в идеале для полноценного языка. По сравнению с F# предлагается отказаться от удобного вызова кода на новом языке из, например, C#, потому что мы не делаем новый язык, чтобы потом писать на C#, а не на нем. Это позволит (предположительно) сделать некоторые вещи по-другому, и вероятно поддержать больше возможностей OCaml, которые были выкинуты при создании F#. Также это даст языку OCaml другой backend, и в идеале позволить сравнить производительность официального “ванильного” компилятора с .NET + JIT.

Скорее всего будет сложно и интересно.

TODO: объединить в группу тем про rukaml

OCaml + ANTLR

ANTRL – генератор синтаксических анализаторов, написанный на Java. Он позволяет генерировать код для большого количества языков. Было бы круто, чтобы OCaml в этом списке тоже был.

При этом можно научиться соединять OCaml со сгенерированным кодом для С++, или делать полноценный backend (предпочтительно).

Недооформленные/Идеи

Проект https://github.com/simdjson/simdjson сделан для ускорения парсинга JSON м помощью интринскиов процессора. Сейчас есть SIMD Х86/64 и через ARM расширения. Не хватает поддержки RISC-V с интринсиками.

Технологии: С++

Публикабельность: если будет результат, который даст ускорение; и будет поддержан весь JSON; то вполне на местячковой студенческой конфе

Исследовать, на сколько сложно портировать подход со специализацией парсер-комбинаторов с Haskell на OCaml. Всё придумано для того, чтобы порождать из парсер-комбинаторов код, похожий по виду (т.е. и по эффективности) на рукописный. Для х-я исследовали API для анализа контекстно-зависимых языков: Parsley, в OCaml пока только ограничивались контекстно свободными.

Доработка плагина Obsidian Timelines

Требудется улучшить поддержку плагина Timelines для системы ведения заметок Obsidian. Суть таймлайнов – раскладка событий по шкале времени и визуализация этой шкалы. Может быть полезно для сопоставления различных событий в разных точках планеты на одной шкале времени. С этим имеющийся плагин справляется.

Хочется доработать плагин в сторону обсуждения имеющихся событий на таймлайне. Например, выбирается некоторая “интерпретация”, которая объясняет имеющиеся события в парадигме данной интепретации. Интересным это становится, когда появляются две конкурирующие интепретации, которые объясняют одни и те же события очень по-разному. Каноничным примером здесь будут исторические события, например, конкурирующие интепретации двух сторон, имеющих территориальные конфликты. Или, если отказаться от привязки событий ко времени, то можно выписать особенности некоторого языка программирования, и проинтерпретировать их с точки зрения двух конкурирующих парадигм.

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

(Официальный плагин поддерживается так себе. Экспериментировать надо с вот этим форком). Тут написано как их дебажить. А вот ссылка как создать первый плагин и запустить его.

Технологии: electron, typescript, npm.

Публикабельность нулевая. На полгода. Предпочтительно 2 курс.

P.S. Возможно, стоит сделать веб-приложение, а не плагин к Obsidian

Parsing with SIMD

На идеях и статьях этой либы: https://github.com/simdjson/simdjson добавитьэ

• Вариант для JSON с векторными расширениями RISC-V
• парсинг дригих языков: s-expressions, OCaml (?), etc.

Marknote

KDE делают свою поделку для ведения заметок. Я сейчас пользуюсь Onsidian.md, написанной на Electron. Хотелось бы от него избавиться. Для этого надо дополнить фичами Marknote

• Поддержка заметок из Git
• древовидные заметки
• поиск по тегами
• прочие мелочи: раз и два

Технологии: С++ и Qt

OCaml + Meson

В мире много build-систем, OCaml традиционно пользуется своей (dune), где поддержка других языков так себе. Предлагается взять известную билд-систему и научиться собирайть ею OCaml проекты. В конце сделать сранение с dune

Семестр, не публикабельно.

Профилирование программ на miniKanren

Частенько, для оптимизации программы нужно её профилировать, чтобы найти места, где оптимизация принесет максимум пользы. Для реализаций miniKanren на Scheme уже разработан некоторый профилятор, хочется повторить эту работу для реализации miniKanren на OCaml. Ожидается, что профилятор будет подсвечивать наиболее и наименее “горячие” унификации в коде. В перспективе собирать какую-то статистику о реляциях, которые профилируются, например, как часто тот или иной аргумент является свободной переменной и т.п.

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

Визуализатор/отладчик miniKanren (понять, что с этим делать)

Встраиваемый язык miniKanren – по сути реализация поиска перебором по некоторому (потенциально бесконечному) дереву, где поиск в одних ветвях не зависит от поиска в других. Чтобы этот поиск был полный, в miniKanren реализована стратегия поиска interleaving search. Её суть заключается в том, что процесс поиска скачет между текущими узлами дерева и потихоньку углубляет посещенную часть его, производя поиск. Из преимуществ можно назвать, что это поиск полон (в отличие от поиска в глубину) и быстрее работает чем банальный поиск в ширину. Из недостатков: это очень сложно отлаживать с помощью дебажной печати, потому что контекст текущего исполнения постоянно меняется.

Предлагается взять игрушечный вариант miniKanren и реализовать визуализатор его исполнения. В частности, надо будет запускать программы на miniKanren на определенное число шагов, поддерживать шаг назад/вперед. Разумеется как-то визуализировать дерево поиска и переменные miniKanren, появляющиеся по ходу дела.

Конкретный GUI framework не очень принципиален, но как минимум он должен легко запускаться на GNU/Linux. Из личных предпочтений мы будем рекомендовать Qt/QML.

C Qt/QML могут быть два подхода к решению.

1. Взять игрушечный вариант miniKanren, скомпилировать его в Javascript и запихнуть в Qt/QML, в который уже встроен движок Javascript. Просто и прямолинейно, но потом писать визуализатор и перемешивать его код с интерпретатором miniKanren будет неприятно. Какую-то поделку, использующая данный подход можно найти здесь.

2. Взять грядущую версию OCaml версии 5, где поддержана концепция алгебраических эффектов, которая позволяет прерывать исполнение кода, в более-менее произвольном месте, а потом продолжать исполнение с прерванного места. Это не поддерживается в Javascript (OCaml кусок должен компилироваться в нативный код), что может усложнить интеграцию визуализатора с игрушечным miniKanren. Но это в перспективе должно позволить разделить визуализацию и пошаговое исполнение, что сильно упростит код. Может быть, их этого получится сделать какую-нибудь студенческую статью.

От исполнителя требуется знакомство (или же возможность достаточно быстро разобраться):

• c функциональным программированием на OCaml
• c miniKanren

OCaml games (частично занята, не уверен, что стоит раздавать дальше…)

Сейчас на 2м курсе выдается куча домашек про реализации языков программирования. Хочется это как-то разбавить, и выдавать домашние задания на тему реализации игрушек на OCaml/ReasonML/Rescript с компиляцией в Javascript. Надежда в том, что студентам будет более интересно их разрабатывать, чем писать компиляторы.

За год планируется:

• обозреть имеющиеся учебные примеры в мире Javascript (например, RPGJS, поделки на основе Phaser движка и т.п.), а также уже сделанные игры на ReasonML;
• спланировать как такого рода задачу можно поварьировать в 10 (желательно в большее количество) неповторяющихся (вернее одинаковых только частично) домашних заданий;
• реализовать прототип (на сколько я знаю, игр на ReasonML довольно мало, потому что технология новая, и найти достаточно изменчивую реализацию может быть непросто);

• найти аспекты реализации, которые особенно хорошо продемонстрируют превосходство (в данном конкретном случае) OCaml над Javascript, подготовить примеры на эту тему для использования в лекциях; например:

  • удобство применения полиморфных вариантных типов для типизации клиент-сервеных сообщений
  • использования паттерна проектирования entity component system
• также найти аспекты реализации, специфичные для геймдева, и примеры того как их можно продемонстрировать на OCaml/ReasonML/Rescript. Например:
  • использование Structure-of-Arrays вместо Array-of-Structures, для получение лучшей производительности

В качестве не очень сложной учебной практики на год, может быть, можно давать только пункт про реализацию прототипа. Но для ВКР это совершенно точно будет не достаточно, последний пункт необходимо будет сделать. Думаю, что обучающемуся, который раньше не видел классического функционального программирования (классического – это не то, что добавили в C# и называют функциональным программированием), будет сложно понять в каком стиле реализацию надо писать и какие приёмы надо будет применять. Скорее всего это придется изучить по ходу дела, что может быть трудоёмко.

не OCaml, но games

Возродить ремек игры “Космические рейнджеры 2” https://github.com/ObKo/OpenSR

Технологии: С++/Qt

Доработка IDE для OCaml

Tема с прошлого года.

• Семантическая подсветка (и/или) форматирование
• Поддержка синтаксических расширений на основе Camlp5

• Inlay hints

• Что-нибудь ещё (можно спросить 2курсников ПИ, что их больше всего раздражало в IDE)

Совсем неформально описанное

• YAML parser in pure OCaml https://discuss.ocaml.org/t/ocaml-yaml-library/4297/2
• lamlqml?
• Remake Turbo Vision
  • для 2го курса
  • Тема нужна для обучения проектированию GUI рективным способом.
  • предлагается взять OCaml+ncurses+notty и сделать поделку в стиле Borland Turbo Vision
• Десктопная приложенька, чтобы слушать музыку из ВК. API для ВК известно, есть демки доставания лайков на JS и python.
  • Надо доставать залайканное, показывать, и играть музыку из постов.
  • Как именно расшифровывать симметричное зашифрованные треки тоже известно.
  • Планируется десктопная приложенька на Qt/QML, чтобы легко её можно было превратить в мобильную.

• Апгрейд stremio для превращения его в PopcornTime

• про вывод типов с уровнями (TODO: переосмыслить, может выкинуть)
  • тема для второго курса
  • надо реализовать навороченный почти линейный алгоритм вывода типов на основе работы Д.Реми и описания Олега
  • в текст работы должно попасть подробное понятняное описание алгоритма для новичков
  • оценивать текст надо на основе отзывов студентов разных курсов

Завершенные и полузавершенные (не выдаются)

Транслятор OCaml в Lua

Type debugger для OCaml

Графическая утилита для отладки вывода типов в программах на OCaml. Скорее всего будет полезна только новичкам. Есть подобная поделка для Haskell: https://chameleon.typecheck.me/playground

Визуальный отладчик проверки типов должен быть полезен новичкам. Уже есть аналогичная поделка для Haskell, которая поддерживает некоторое подмножество языка Haskell, и делает отладчик типов. Частичное описание есть в PDF c этой страницы. Под капотом собираются ограничения (constraint) на типы, которые потом решается отдельным шагом. Из этого получается доставать в каких местах уточнились типовые переменные, что в классическом подходе делать не удается.

Можно делать как игрушечное веб-приложение, а можно интегрировать в VsCode. Скорее всего придется видоизменить/повторить вывод типов для всего OCaml.

Если аккуратно и глубоко закопаться в теорию, то может получиться учебная практика (или ВКР) на год. Если получится найти какие-нить отличия OCaml от Haskell при реализации, то можно попробовать написать на местячковую конфу.

Реализация miniKanren с параллелизмом (была занята, сделана в некоторой степени, но не до конца)

Встраиваемый язык miniKanren – по сути реализация поиска перебором по некоторому дереву, где поиск в одних ветвях не зависит от поиска в других. В теории это должно хорошо распараллеливаться, на практике никто этого сделать не пробовал. Предлагается взять текущий вариант будущего релиза OCaml 5, где планируют добавить поддержку параллелизма в рантайм, и попробовать реализовать поиск в миниканрене, который будет как-то параллелиться.

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

Ранее была проведена некоторая работа по интеграции unicanren и OCaml 5. Несколько реляций можно запустит параллельно, и объединять ответы из них по мере их поступления. Следующим шагов будет добавление параллельной дизъюнкции в представление программ на миниканрене и внесение изменений в интерпретатор.

От исполнителя требуется знакомство (или же возможность достаточно быстро разобраться):

• c ФП на OCaml
• с параллельным программированием
• c miniKanren

OCaml и полиморфные варианты (занято, но чел слился, так что нет)

Возможно не актуально уже, переделать

В языке OCaml присутствует фича под названием “полиморфные вариантные типы”, которая позволяет типизировать значения алгебраического типа данных не номинально (т.е. указание к какому типу они принадлежат), а структурно (т.е. указание того, с каких конструкторов данное значение начинается). Эта фича появилась в языке в начале нулевых, но снискала только умеренную популярность из-за чересчур длинных сообщений об ошибках, а также из-за несколько неинтуитивного автоматического вывода типов для полиморфных вариантов.

В работе “Set-Theoretic Types for Polymorphic Variants” 2016 года авторы показывают примеры программ, где типизацию полиморфных вариантов можно было бы улучшить, а также формальное описание как это сделать и возможные последствия для языка OCaml. Важным является третий пример, из которого следует, что для качественной поддержки новых set-theretic полиморфных вариантов необходимо, чтобы среда выполнения языка имела поддержку RTTI (runtime type information). Так как OCaml оной не имеет, то статья в том виде, в каком она есть, едва ли будет реализована для “ванильного” OCaml.

В качестве учебной практики предлагается:

• разобраться в статье
• реализовать минимальный язык, оснащенный set-theoretic полиморфными вариантными типами
  • функции, сопоставление с образцом, пару базовых типов
• реализовать компилятор/транслятор из этого миниязыка в среду выполнения, где RTTI поддержана
  • а именно, .NET
  • или JVM

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

Мета-цель работы: запустить на матмехе тусовку, которая занимается компиляторами в широком смысле этого слова.

Занятые или не выдаются под другим причинам

miniKanren + Расписание (занято)

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

• число обучающихся не должно превышать вместимость аудитории;
• преподаватель не может одновременно вести занятия в двух разных аудиториях;
• “окна” в расписании не желательны;
• в день не может быть более 4х пар.

В бывшей Лаборатории языковых инструментов JetBrains Research занимаются реляционным программированием на miniKanren, которое включает в себя область под названием программирование в ограничениях. По сути, это предметно-ориентированный язык, который позволяет удобно (хотя кто-то счиатет, что неудобно) писать переборные задачи с ограничениями. Предлагается либо взять оригинальный miniKanren для языков семейства Scheme, или лабораторный OCanren, встроенный в язык OCaml, и заняться сбором ограничений к расписанию на матмехе, а затем и автоматическим построением расписаний.

На первых порах miniKanren должно хватать. На данный момент он строго проверяет ограничения (если они нарушены, то он прерывает поиск в текущей ветке и ищет решение в другой) и отсутсвует возможность посчитать констрейнты “не очень важными”. Например 1: номинальная вместимость аудитории 20 человек; посадить 25 можно, но будет душновато; 30 уже никак нельзя, потому что будем сидеть на коленках друг друга или задохнемся. Пример 2: за каждой группой должна быть закреплена аудитория на день, но в здании недостаточно аудиторий для всех групп, поэтому 100% корректного расписания не может существовать. Надо как-то позволить программисту указывать, что для этих групп надо строго выполнять, на какие группы можно подзабить и т.п.

В общем и целом, сделать генератор расписания – очень полезная учебная практика, относящаяся к классу “продуктовых”. Не смотря на очевидную полезность, если в процессе работы существующая реализация miniKanren не будет как-то доделана/расширена/обогащена, то генератор расписания может выглядеть несколько слабой ВКР, и рисковать не стоит. В случае расширения выразительной мощи miniKanren рекомендуется написать и заслать англоязычный доклад на miniKanren workshop (дедлайн в мае-июне), что формально засчитывается как выступление на конференции. Для полноценных публикаций стоит обратить внимание на отечественные площадки: SEIM, журнал “Вестник ИТМО” и т.п.

План:

• Первый семестр. Собираем требования, делаем прототип на Scheme, который ищет расписание, подходящее под все условия.
• Второй семестр. По результатам первого допиливаем прототип и miniKanren, чтобы он умел некоторые ограничения игнорить, если соблюсти все нельзя.

Околопродуктовый, на ВКР не тянет.

Метрики кода для OCaml (в какой-то степени сделано)

В мейнстримном промышленном программировнии принято использовать так называемые метрики кода, чтобы автоматически и численно отличать хороший код от плохого. В мире функционального программирования такое распространено существенно реже, причины чего не вполне очевидны: адепты ФП скажут, что метрики нужны только для плохих языков, адепты ООП скажут, что ФП не годится для промышленного программирования; ещё кто-то – что на ФП ничего невозможно написать, а если возможно, то не возможно прочитать; четвертые – что метрики для ФП нужны сильно другие, а мейнстримные не применимы и т.д.

В мире OCaml метрик кода нет. Совсем. (Есть очень старая поделка, которую никто не использует). Предлагается

• взглянуть на метрики которые есть в мире (по статье “A Taxonomy of Metrics for Software Fault Prediction (2020)”, картинка слева);
• понять какие можноxтают метрики в других функциональных языках (например, Haskell);
• сделать тулзень, которая их считает;
• выбрать opensource проекты на OCaml, и посчитать метрики.

Если в конце получится с помощью метрик показать, что ФП круче чем всё остальное – будет очень круто.

Предсказываю, что придется поразбираться в уже имеющихся метриках, программирование подсчета метрик если и будет, то не сложное. Вообще, тема идеально подходит под категорию “software engineering”.

P.S.

• Вот какая-то умная книга про метрики для Haskell
• У ПИ пары про метрики будут в 7м семестре.

OCaml ORM (как-то сделано: https://github.com/Tozarin/mrm)

В промышленном программирование для облегчения работы с реляционными базами данных часто применяется подход object-relational mapping (ORM). Суть подхода заключается в том, что каждой строке в результате запроса к базе соответсвует объект, который можно изменять и заливать обратно в базу. Это освобождает программиста от написания SQL запросов, которые порою сложно писать, они согут быть уязвимы к атакам и могут быть не переносимы между разными базами данных.

Этот подход подвержен определенной критике. Рекомендуется почитать её, а также ссылки из этой статьи. Также в будущей записке к учебной практике надо будет коснуться антипаттернов.

На данный момент в программировании на OCaml подход ORM не пользуется популярностью, как минимум, потому что нельзя просто так взять найти библиотеку с реализацией данного подхода. Заслуживают упоминания:

• https://github.com/mirage/orm не поддерживается
• https://github.com/darioteixeira/pgocaml генерирует типы-записи для данных во время компиляции.
• https://github.com/roddyyaga/ppx_rapper расширение синтаксиса для типобезопасных SQL запросов
• Подходы (раз и два) от Олега, суть которых в типобезопасном построении запросов и оптимизации оных

В данной работе предлагается реализовать/воскресить библиотеку для ORM запросов на функциональном языке программирования OCaml. Он выбран отчасти потому, что там есть синтаксическая поддежка объектов, и это может сделать результат данной работы более естественным, чем, например, на Haskell, где синтаксической поддержки объектов нет.

От исполнителя ожидается:

• знакомство с функциональным программированием;
• знакомство с ORM, его недостатками и альтернативами (например, упомянутые по ссылкам выше SQL-speaking objects);
• умение искать библиотеки для баз данных в мире OCaml и прочего ФП (есть вероятность, что после написания данного текста появится реализация ORM, что сделает данную работу бессмысленной);
• готовность сделать библиотеку, которая будет поддерживать хотя бы два backend’a баз данных;
• готовность описать и сделать подход для mock-тестирования баз данных (без него это будет максимум “удовлетворительная” работа).

Эту работу можно нарезать и на полугодовую, и на годовую курсовую 3го курса. Если меня кто-то из преподов убедит, что это бакалаврская ВКР – пусть будет ВКР.