Функциональное программирование 23-24 — различия между версиями

Версия 03:45, 20 ноября 2023

Функциональное программирование

Курс по выбору для студентов 3 и 4 курса ФКН ВШЭ, 1 и 2 модуль 2023 г. Функциональное программирование (ФП) представляет собой теоретически изящный, выдержавший проверку временем на практике и оказавший заметное влияние на технологии программирования вообще подход к созданию ПО. Курс посвящен основам ФП в целом и популярного языка Haskell в частности. Попутно сообщаются начальные сведения из области лямбда-исчислений, теории типов, теории категорий.

Преподаватели

Лектор и семинарист: Евгений Дашков, ТГ: @edashkov, edashkov@gmail.com.

Семинарист: Павел Соколов, ТГ: @TurtlePU.

Учебный ассистент: Максим Чурилов, ТГ: @maxchrlv.

Текущая успеваемость

Таблица.

Setting up

1. Если вы пользуетесь Windows, установите WSL2, если ещё не.
2. Установите ghcup — скачайте бинарный файл сами либо введите одну любимую команду:
   • MacOS:

     brew install ghcup

   • Arch-based distros:

     yay -S ghcup-hs-bin

   • WSL2, MacOS >= 10.13, Linux:

     curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh

   • Windows Powershell (cringe): Команда доступна по ссылке
3. Убедитесь, что путь до места установки ghcup содержится в $PATH — запустите ghcup list.
4. Установите recommended версии компилятора, пакетного менеджера и языкового сервера:

   ghcup install ghc recommended
   ghcup install cabal recommended
   ghcup install hls recommended

5. Убедитесь, что путь ~/.ghcup/bin содержится в $PATH. При необходимости добавьте этот путь сами.
6. Создайте символические ссылки на установленные версии программ:

   ghcup set ghc recommended
   ghcup set cabal recommended
   ghcup set hls recommended

7. Настройте LSP client в своей любимой среде разработки:
   • Для VS Code есть плагин, он должен обнаружить HLS самостоятельно.
   • В NeoVim настройте nvim-lspconfig, он знает про HLS.
   • Инструкцию для других сред можно найти здесь.
8. Опционально — установите Hoogle локально:
   1. cabal install hoogle
   2. Допишите в файл ~/.ghci следующее:

      :def hoogle \x -> return $ ":!hoogle \"" ++ x ++ "\""
      :def hdoc \x -> return $ ":!hoogle --info \"" ++ x ++ "\""

   3. Теперь можно пользоваться Hoogle прямо из ghci с помощью команд :hoogle и :hdoc

Листки и код для семинаров

• Листок 1

• Листок 2

• Лекции и семинары Е. Дашкова в 22/23 учебном году

Домашние задания

Домашние задания выдаются приблизительно раз в две недели; при выдаче каждого задания указывается срок его сдачи. Все задания письменные. Каждая задача оценивается 0, ½ или 1 баллом. Все задания в целом оцениваются числом:

ДЗ = (сумма полученных баллов за все задачи) / (количество выданных задач без *).

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

Сдавать решения нужно в Classroom.

Контрольная работа

Письменная Контрольная работа проводится в начале второго модуля. Допускается использование собственных записей студента и явно разрешенных локальных справочных систем. Каждая задача оценивается 0, ½ или 1 баллом. Контрольная оцениваются числом:

КР = (сумма полученных баллов за все задачи) / (количество выданных задач).

Итоговый экзамен

Письменный экзамен проводится в конце курса. Допускается использование собственных записей студента и явно разрешенных локальных справочных систем. Каждая задача оценивается 0, ¼, ½ , ¾ или 1 баллом. Экзамен оценивается числом:

Э = (сумма полученных баллов за все задачи) / (количество выданных задач).

Индивидуальный проект

При желании студенты согласовывают с семинаристом проект для индивидуальной работы. Также допускается работа в группах до трех человек. Проект представляет собой решение достаточно сложной задачи по программированию и предполагает самостоятельное получение недостающих сведений. Проекты должны быть сданы за день до защиты (до 23:59), то есть как минимум до 15 декабря. За проект выставляется (дробная) оценка ПР от 0 до 1 балла.

Некоторые темы для проектов

Варианты от Евгения Владимировича:

• Определить кольцо Z[X1, X2, ...] многочленов над Z c произвольным количеством переменных. Должны поддерживаться методы show, +, -, *, а также операции подстановки одного многочлена в другой (в частности, вычисление значения в целых точках) и дифференцирования по произвольной переменной.
• Определить понятие формулы первого порядка (в заданной сигнатуре) и реализовать алгоритм приведения таких формул к предваренной нормальной форме.
• Определить понятие пропозициональной формулы и реализовать проверку таких формул на выполнимость с помощью метода резолюций. Метод применим только к КНФ, поэтому еще нужно реализовать полиномиальный алгоритм построения КНФ, «равновыполнимой» данной формуле.
• Реализуйте «угадывающую машину» К. Шеннона.
• Вычислите справедливую стоимость опциона методом "двоичного дерева".
• Реализуйте игру "Жизнь" на торе с графикой ASCII

Варианты от Паши:

• DSL для rich text-а (а-ля Markdown, возможно, с поддержкой формул)
• Библиотека для простых символьных вычислений (с упрощением выражений)
• Бот в телеграм с помощью servant
• Model checker для простых моделей и формул (с нуля)
• Автоматическое дифференцирование, линейная регрессия на его основе (с нуля)
• Консольный роглайк
• Интерпретатор Scheme
• Улучшение интерпретатора лямбда-исчисления

Варианты инициативных проектов от некоторых студентов:

• Решение задач на Codeforces на Haskell
• Crafting Interpreters на Haskell
• Криптографическая библиотека
• Raft с нуля
• Консольный мессенджер

Частые Вопросы по проектам

Какой сложности и объёма должен быть проект?

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

Можно ли брать одну и ту же тему проекта?

Да, можно, главное, чтобы проекты выполнялись самостоятельно. Обмениваться идеями можно, копировать код друг у друга — нет.

Можно ли выбирать тему, не предложенную преподавателями?

Да, можно, темы выше — это примерные ориентиры для вдохновения. Можно взять их, можно придумать что-то своё.

Как аппрувнуть тему?

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

Оценивается ли кодстайл?

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

Нужна ли документация проекта?

Haddock не обязателен, но см. комментарий про типы выше

В какой форме можно сдать код проекта?

В любом формате, который не предполагает нахождение вашего кода в открытом доступе и который желающие потом смогут собрать с помощью cabal build и запустить с помощью cabal run. При этом ограничений на версию GHC нет.

Какой дедлайн сдачи проекта?

С выбором темы желательно определиться до начала сессии, защита будет когда-то во время сессии, возможно, в несколько дней. Код нужно прислать за день (до 23:59) до начала Вашей защиты.

Будут ли дополнительные вопросы на понимание кода проекта?

Только в том случае, если мы начнём сомневаться в авторстве проекта.

За что производится оценивание проекта?

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

Как проходит защита?

Скорее всего онлайн. Вы рассказываете, какая у Вас тема, что Вы успели сделать, как устроен код (с высоты птичьего полёта, только основные типы данных, функции и инстансы). Мы можем задать Вам пару вопросов по задаче, возможным расширениям и архитектуре решения. Можно слушать защиты друг друга и задавать свои вопросы, групповые проекты защищаются всей командой сразу.

Полезные библиотеки

• containers, unordered-containers — стандартные коллекции.
• monoidal-containers — некоторые стандартные коллекции с в каком-то смысле более правильными инстансами Semigroup и Monoid.
• lattices — решётки (алгебраическая структура).
• servant — генератор API для веб-серверов и клиентов.
• telegram-bot-simple — немного устаревшая библиотека для ботов в Телеграм.
• haskeline — фреймворк для REPL интерфейсов.
• ansi-terminal — для редактирования вывода (полезно для роглайков и Game of Life).
• megaparsec — фреймворк для написания парсеров.
• async — асинхронное IO.
• data-fix, free — типы данных для обобщённой рекурсии.
• QuickCheck — фреймворк для property-based тестирования.
• HUnit — фреймворк для юнит-тестов.

Материалы

Группа слушателей курса в ТГ

Материалы Е.В. Дашкова

Записи лекций Е. В. Дашкова в МФТИ

Базовые ресурсы

Сайт языка

Haskell Tool Stack

Информация про Cabal

Hoogle

Hackage

Стандартная библиотека языка Haskell на Hackage

Книги и статьи

Learn You a Haskell for Great Good

Real World Haskell

Basic Simple Type Theory

Lectures on the Curry-Howard Isomorphism

Purely Functional Data Structures.

Нет в открытом доступе

Programming in Haskell by Graham Hutton

Basic Category Theory for Computer Scientists by Benjamin C. Pierce

Оценки

Итоговая оценка получается так:

Итог = ОКРУГЛ (2 * ПР + 2 * КР + 3 * ДЗ + 3 * Э).

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