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

Версия 19:04, 2 декабря 2022

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

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

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

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

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

Учебный ассистент: Олег Мкртчян, ТГ: @unwishfulthinking.

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

https://docs.google.com/spreadsheets/d/e/2PACX-1vTGKTtVAvjvCheX-dky3tB_W-GQnKunxccajwMziHquQvTDA7pqOGOZUfajFtO20dQhPkx0rurScFju/pubhtml

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

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

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

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

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

Ссылка на классрум: https://classroom.google.com/c/OTM4MjAyNzk1MTda?cjc=xbblft6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Q: Нужна ли документация проекта? A: Haddock не обязателен, но см. комментарий про типы выше

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

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

Q: Будут ли дополнительные вопросы на понимание кода проекта? A: Только в том случае, если мы начнём сомневаться в авторстве проекта.

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

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

Материалы

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

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

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

Сайт языка

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 * Э).

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