fp2.tex

%! suppress = Quote
%! suppress = LineBreak
%! suppress = Makeatletter
%! suppress = TooLargeSection
%! suppress = MissingLabel
\documentclass[12pt]{article}

% Time
\usepackage{datetime}
% ------------------------------------------------

% Fields
\usepackage{geometry}
\geometry{top=25mm}
\geometry{bottom=35mm}
\geometry{left=20mm}
\geometry{right=20mm}
% ------------------------------------------------

% Graphics
\usepackage{color}
\usepackage{tabularx}
\usepackage{tikz}
% https://tikz.dev/tikz-graphs
\usetikzlibrary{positioning, shapes.geometric, arrows, automata, graphs}
\tikzset{
    expr/.style={ellipse, draw=gray!60, fill=gray!5, very thick, minimum size=7mm, yshift=0.7cm},
    hexpr/.style={ellipse, draw=gray!60, fill=blue!15, very thick, minimum size=7mm, yshift=0.7cm},
    stmt/.style={rectangle, draw=gray!60, fill=gray!5, very thick, minimum size=5mm, yshift=0.7cm},
    decl/.style={rectangle, draw=blue!60, fill=gray!5, very thick, minimum size=5mm, yshift=0.7cm},
    hdecl/.style={rectangle, draw=blue!60, fill=blue!15, very thick, minimum size=5mm, yshift=0.7cm},
    subtree/.style={shape border rotate=90, isosceles triangle, draw=gray!60, fill=gray!5, very thick, minimum size=5mm, yshift=0.0cm},
}
\usepackage{blkarray}
\usepackage{graphicx}
\usepackage{forest} % https://tex.stackexchange.com/questions/198405/how-to-change-the-color-of-subtrees-in-tikz-qtree
% ------------------------------------------------

% Math
\usepackage{amsmath, amsfonts}
\usepackage{amssymb}
\usepackage{proof}
\usepackage{mathrsfs}
% Crossed-out symbols
% https://tex.stackexchange.com/questions/75525/how-to-write-crossed-out-math-in-latex
\usepackage[makeroom]{cancel}
\usepackage{mathtools}
% ------------------------------------------------

% Additional font sizes
% https://www.overleaf.com/learn/latex/Questions/How_do_I_adjust_the_font_size%3F
\usepackage{moresize}
% Additional colors
% https://www.overleaf.com/learn/latex/Using_colours_in_LaTeX
\usepackage{xcolor}
% \texttimes
\usepackage{textcomp}
% ------------------------------------------------

% Language
\usepackage[utf8] {inputenc}
\usepackage[T2A] {fontenc}
\usepackage[english, russian] {babel}
\usepackage{indentfirst, verbatim}
\usetikzlibrary{cd, babel}
% ------------------------------------------------

% Fonts
\usepackage{stmaryrd}
\usepackage{cmbright}
\usepackage{wasysym}
% ------------------------------------------------

% Code
% https://tex.stackexchange.com/questions/99475/how-to-invoke-latex-with-the-shell-escape-flag-in-texstudio-former-texmakerx
% Colored, requires --shell-escape compiling option
\usepackage{minted}
\setminted{xleftmargin=\parindent, autogobble, escapeinside=??, linenos, numberblanklines=false}
\usepackage{listings}
% ------------------------------------------------

% Custom commands
\newcommand{\vocab}[1]{\textbf{#1}} % new word for vocabulary
\newcommand{\point}[1]{{\color{blue}\textit{#1}}} % point out something in text
\newcommand{\sembr}[1]{\llbracket{#1}\rrbracket} % semantic brackets
\newcommand{\positive}{$+$} % item: pros
\newcommand{\negative}{{\color{red} $-$}} % item: cons
\newcommand{\comb}[1]{\mathbf{#1}}
\newcommand{\step}{\rightsquigarrow}
\newcommand{\term}[1]{\mathbf{#1}}
\newcommand{\ap}{~}
\newcommand{\termdef}{\coloneqq}
\newcommand{\subst}[3]{\left[#2 \mapsto #3 \right] #1}
\newcommand{\eqbeta}{=_\beta}
\newcommand{\eqeta}{=_\eta}
\newcommand{\iso}{\cong}
\newtheorem{task}{Упражнение}
% ------------------------------------------------

% Head
\usepackage{hyperref}
\usepackage{fancyhdr}
% ------------------------------------------------

% Bibliography
\usepackage{csquotes}
% https://tex.stackexchange.com/questions/3802/how-to-get-doi-links-in-bibliography
\usepackage{natbib}
\bibliographystyle{unsrtnat}
%\bibliographystyle{apalike}
%\bibliography{bib}
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{bib.bib}
%\addbibresource{bib}
% ------------------------------------------------

% Line numbers
% https://tex.stackexchange.com/questions/16010/number-every-line-of-pages
\usepackage{lineno}
\linenumbers
% ------------------------------------------------

% Enumerations
% https://tex.stackexchange.com/questions/10684/vertical-space-in-lists
\usepackage{enumitem}
\setlist{noitemsep} % nosep
%\renewcommand{\labelitemi}{$\triangleright$}
%\renewcommand{\labelitemii}{$\triangleright$}
%\renewcommand{\labelitemiii}{$\triangleright$}
%\renewcommand{\labelitemiv}{$\triangleright$}
% ------------------------------------------------

% Formatting
\usepackage{multicol}
% https://tex.stackexchange.com/questions/282869/putting-two-figures-side-by-side
\usepackage{subcaption}
% https://tex.stackexchange.com/questions/109467/footnote-in-tabular-environment
\usepackage{footnote}
\makesavenoteenv{tabular}
% ------------------------------------------------



\begin{document}

    \begin{center}
    {\LARGE ФП 2.0}
        \footnote{Автор Андрей Стоян (\texttt{andrey.stoyan.csam@gmail.com}).}\footnote{Спасибо Илье Колегову за первое внимательное прочтение и кучу комментариев. Спасибо моим студентам, которые своим интересом к предмету сделали эту работу возможной.}\footnote{Версия от \today, \currenttime.}
        \\
        осень 2025
    \end{center}

    \tableofcontents

    \newpage

    \section*{Введение}

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

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

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

    В качестве основного языка курса выбран Haskell, так как он, с одной стороны, воплощает в себе многие концепции, часто доведённые до некоторого логического завершения, и достаточно выразителен для кодирования других.
    С другой стороны, всё ещё является прикладным промышленным языком программирования.

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

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

    Пререквизитом к прохождению курса является знание основ функционального программирования: алгебраических типов данных, паттерн-матчинга, свёрток, параметрического полиморфизма, классов типов, базовых монад.
    Дополнительно будет полезным умение читать типовые дроби, знакомство с полиморфным $\lambda$-исчислением и кодированием Чёрча.


    \clearpage


    \section{Воспоминания о ФП}

    \input{fp2-remember}

    \clearpage


    \section{Параметрический полиморфизм} \label{sec:parametric-polymorphism}

    \input{fp2-parametric}

    \clearpage


    \section{Специальный (ad-hoc) полиморфизм} \label{sec:ad-hoc}

    \input{fp2-ad-hoc}

    \clearpage


    \section{Типы данных} \label{sec:data-common}

    \input{fp2-data-types}

    \clearpage


    \section{Интерпретаторы}

    \input{fp2-interpreters}

    \clearpage


    \section{Продолжения (continuations)} \label{sec:continuations}

    \input{fp2-continuations}

    \clearpage


    \section{Эффекты и модульные интерпретаторы} \label{sec:effects}

    \input{fp2-effects}

    \clearpage


    \section{Системы эффектов TODO} \label{sec:effect-systems}

    \input{fp2-effect-systems}

    \clearpage


    \section{Datatype-generic programming TODO} \label{sec:datatype-generic}

    \input{fp2-derivings}

    \clearpage


    \section{Персистентность и оптика TODO}

    \input{fp2-optics}

%    \clearpage


    % todo субструктурность, ресурсы....

    % todo заключение со ссылками на всё


%%    \section{Компилятор GHC и runtime}
%
%    \input{fp2-ghc-internals}

    % todo Perhaps Not The Answer You Were Expecting But You Asked For It

    % todo зависимые типы в Haskell

    % todo рассовать упражнений по конспекту

    % todo Wadler's "Introduction to functional programming"

    % todo coroutines & structured concurrency

    % todo получше про defunctionalization, shallow, fusion...

    % todo "раздел, глава, параграф"

    % todo разметка ссылок на статьи, чтобы контролировать распределение внимания

    \begin{center}
        \vspace{2em}
        \textit{\LARGE To be continued...}
        \vspace{2em}
    \end{center}


    \newpage
    \bibliography{bib}

\end{document}