edu-fp

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

## Лекция 1

## Введение. Обзор курса. Особенности ФП

Пенской А.В., 2024

----

## План лекции

- Ссылки
- Рационализация
- Содержание курса
- Лабораторные работы
- Обзор функциональных языков
- Проекты для участия
- Идея функционального программирования

</div><div class="col">

![](figures/sign-for-programming.jpg)

</div></div>

---

## Ссылки

### Telegram чат

<https://t.me/+qSLHWqMAAgE2ZmM0>

### Материалы курса

<https://gitlab.se.ifmo.ru/functional-programming/main>

### Ведомость

<https://docs.google.com/spreadsheets/d/1xx0OW1P2IBy_2-dyahEjppXeMbZ6GqO0Q2X_PUFFU_I/edit?usp=sharing>

---

## Рационализация

- Низкоуровневые ЯП (машинные), почти не используются.
- Современные ЯП — структурные. Эффективность — доказана.
- ООП получило широкое распространение, хотя:
    - Имеет концептуальные проблемы.
    - Заявлена "интуитивная понятность", но книги по Design Patterns.
    - Эффективность не доказана.
    - Получило распространение вместе с GC и полиморфизмом.
- Молодые ЯП часто далеки от ООП.
- Изменение вычислительных платформ:
    - много ядер, параллелизм;
    - облака, распределённые вычисления.
- Рефакторинг, верификация, оптимизация, поддержка, автоматизация этих процессов.

---

## Содержание курса (теория)

(предварительное)

1. Введение. Языки. Ключевые особенности ФП
1. Основы ФП. Рекурсия. Функции высшего порядка. Замыкания...
1. Верификация. Типизация. Indirections. Полиморфизм. Certified Programming. Тестирование. Functors
1. Элементы истории языков программирования. Лямбда исчисление
1. Изменяемое состояние считать вредным. Валидация и верификация
1. Монады. Парсер-комбинаторы

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

---

## Лабораторные работы

- 1 + 4 лабораторные работы
- Делаются индивидуально (кроме последней)
- Результат необходимо залить на Github, Gitlab, etc.
- Настроить CI, включая тесты и lint tools
- Отчёт в `README.md`.
- Весь код в идеоматичном стиле для выбранного языка.
    - Использование изменяемых состояний следует избегать.

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

----

### Лабораторная работа 0

- Выбрать свой ЯП
- Выбрать lint-tools
- Выбрать книгу для изучения ЯП (будет на зачёте)
- Написать и защитить эссе (пол странички текста)
- Возможен отказ, в случае сильного "излишнего перекоса"

----

### Лабораторная работа 1

Простые алгоритмы и встроенные структуры данных. Задачи проекта Эйлер с разными способами реализации.

Пример:

> If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
>
> Find the sum of all the multiples of 3 or 5 below 1000.

Необходимы:

1. рекурсия, хвостовая рекурсия;
2. с явным разделением генерации последовательности, фильтрации и свёртки;
3. генерация последовательности при помощи отображения `map`.

----

### Лабораторная работа 2

Реализация чисто функциональных структур данных. Функции высшего порядка, ленивые вычисления и бесконечные структуры данных. Тестирование.

1. Функции:
   - добавление и удаление элементов;
   - фильтрация;
   - отображение `map`;
   - свертки (левая и правая);
   - структура должна быть моноидом.
2. Библиотека должна быть протестирована в рамках unit testing.
3. Библиотека должна быть протестирована в рамках property-based тестирования.
4. Структура должна быть полиморфной.

----

#### Моноид

A set $S$ equipped with a binary operation $S × S → S$, which we will denote $•$, is a monoid if it satisfies the following axioms:

- Associativity

For all $a$, $b$ and $c$ in $S$, the equation $(a • b) • c = a • (b • c)$ holds.

- Identity element

There exists an element $e$ in $S$ such that for every element $a$ in $S$, the equalities $e • a = a$ and $a • e = a$ hold.

Примеры:

- натуральные числа ($*$, $1$) и ($+$, $0$);
- строки (`++`, `""`);
- список (`++`, `[]`).

----

### Лабораторная работа 3

Реализация лабораторной работы по предмету "Вычислительная математика" с использованием ФП (аппроксимация функций). А также:

- дополнительно должна быть реализована "аппроксимация" отрезками;
- настройки алгоритма аппроксимирования и выводимых данных должны задаваться через аргументы командной строки;
- входные данные должны подаваться на стандартный ввод;
- выходные данные должны подаваться на стандартный вывод;
- программа должна работать в потоковом режиме (пример: `cat | grep 11`).

----

### Лабораторная работа 4

Разработка приложения с учетом особенностей выбранного языка программирования.

- Можно объединиться в группу.
- Можно самостоятельно предложить задание.

Примеры:

- Встроенный специализированный язык (eDSL).
- Библиотека парсер-комбинаторов.
- Система управления вычислениями на кластере.
- Решение задач в проектах преподавателя.
- Тест фреймворк с тест раннером.

---

## Проекты для участия

- Размещены на GitHub
- Лицензия — BSD
- Небольшие задачи проектов могут стать вашей лаб. 4
- Крупные задачи проектов могут стать вашими дипломами и практиками

Подробнее: [Aleksandr Penskoi](https://ryukzak.github.io)

![](figures/penskoi-qr.png)

----

### NITTA (Haskell, Verilog, TypeScript)

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

- обеспечить высокую скорость и уровень параллелизма для нерегулярных алгоритмов (где не используют GPU) и жесткое реальное время (с точностью до такта);
- сделать процессор реконфигурируемым под разные прикладные области;
- предоставить язык высокого уровня для прикладных разработчиков и быструю компиляцию.

Технологии: Haskell, Verilog, TypeScript, React, GitHub.

----

### Course-bot (Telegram, Clojure)

Features:

- Quiz in test form
- Essay submissions by the students with cross-review
- Scheduling in-class presentations, including topic reviews by the teacher, agenda generation, and evaluation by the teacher and students.

Technical details:

- Async based helper for dialog description
- eDSL for describing bot in dialogue form
- Possible topics for bachelor’s or master’s thesis:
    - eDSL for dialogue system descriptions
    - Automated testing for dialogue systems based on a property-based approach

----

### ca-wrench (Haskell)

Транслятор ассемблера / симулятор процессоров разных систем команд для курса архитектура компьютера.

Примеры задач:

- Поддержка новой системы команд.
- Сообщения об ошибках.
- Отладчик.
- И т.п.

---

## Обзор функциональных языков

- неполный и в основном неверный;
- лабораторные работы могут адаптироваться под выбранный язык.

Выборы:

- Динамические/Статические.
- Минималистичные/Стероидные.
- Практические/Теоретические.
- Область применения.

----

### Lisp family since 1958

- Conditionals not limited to goto
- First-class functions
- Recursion
- Treating variables as pointers, leaving types to values
- Garbage collection
- Programs made entirely expressions with no statements
- The symbol data type, distinct from the string data type
- Notation for code made of trees of symbols, Гомоиконичность
- Full language available at load-, compile-, and run-time

</div><div class="col">

![The Fancy Logo](figures/lisp-logo.png)
![The Fancy Logo](figures/lisp-parentheses.png)

</div></div>

----

#### Scheme

- Minimalism
- Lambda calculus yields an extremely small core
- Конструктор "собери сам"

#### Common Lisp

- Очень большой язык программирования
- Common Lisp Object System, много больше чем ООП
- Conditional System
- The hard way: [Лисп — философия разработки](https://fprog.ru/2010/issue5/vsevolod-dyomkin-lisp-philosophy/)

----

#### Clojure

- Modern language
- Symbiotic with an established Platform (JVM)
- Polymorphism without OOP, multimethods
- Defaults to immutability
- Designed for Concurrency (atom, STM, actors)
- Clojure Script
- [2010, Clojure, или «Вы все еще используете Java? Тогда мы идем к вам!»](https://fprog.ru/2010/issue4/alex-ott-clojure/)

*Offtopic:* И это далеко не всё. Откуда этот зоопарк?

*Offtopic:* На самом деле это очень разные языки попавшие в одну группу в основном из-за скобочек/программирования в AST.

----

### Erlang/OTP

- Язык старой школы с нотками Пролога. Разработан для телекома (Open Telecom Platform).
- Динамический функциональный язык.
- Concurrency and distribution orientation. Actor model (самый объектно-ориентированный ЯП).
- Soft real-time
- "Let it crash" coding style. Supervisor trees
- Hot code loading and modules.

![](figures/erlang-supervisors.png)

</div><div class="col">

### Elixir

- Совместимый reboot Erlang
- Испытал влияние Ruby
- Metaprogramming
- Polymorphism via protocols

</div></div>

----

### OCaml

- Compiled. High-efficient.
- Static type systems and type-inferring
- Object-oriented programming
- Algebraic data types and pattern matching
- Parametric modules
- [8 months of OCaml after 8 years of Haskell in production](https://dev.to/chshersh/8-months-of-ocaml-after-8-years-of-haskell-in-production-h96)

### F-sharp

*Disclaimer:* (не работал, могу наговорить глупостей)

- Static type systems and type-inferring. Strict.
- .net integration
- Object-oriented programming
- Asynchronous programming
- Parallel programming
- Agent programming

----

### Haskell

- Statically typed
- Purely functional
- Type inference
- Concurrent
- Lazy
- Квадратно-гнездовое программирование
- Богатая библиотека
- Язык активно развивается

</div><div class="col">

![](figures/haskell-yes-but.jpg)

![](figures/holdmybeer.jpg)

</div></div>

----

*Disclaimer:* (не работал, могу наговорить глупостей)

### Coq/Gallina

- Not a programming language, but a formal proof management system.
- Allows:
    - to define functions or predicates, that can be evaluated efficiently;
    - to state mathematical theorems and software specifications;
    - to interactively develop formal proofs of these theorems;
    - to machine-check these proofs by a relatively small certification "kernel";
    - to extract certified programs to languages like OCaml, Haskell or Scheme.
- Tactic based interactive theorem prover

----

*Disclaimer:* (не работал, могу наговорить глупостей)

### Agda

- Dependently typed functional programming language
- Proof assistant
- Total language (all expressions are finite).
- mixfix for operators

```agda
if_then_else_ : {A : Set} -> Bool -> A -> A -> A
if true then x else y = x
if false then x else y = y
```

</div><div class="col">

![](figures/mixfix.jpg)

</div></div>

----

*Disclaimer:* (не работал, могу наговорить глупостей)

### Idris

- Dependently typed functional programming language
- Designed to be a general purpose programming language
- Tactic based interactive theorem prover

---

## Источники прямых заимствований

- [Pascal — Procedures — Tutorials Point](https://www.tutorialspoint.com/pascal/pascal_procedures.htm)
- [Function (mathematics) — Wikipedia](https://en.wikipedia.org/wiki/Function_(mathematics))
- [The Hitchhiker's Guide to the Unexpected](https://ferd.ca/the-hitchhiker-s-guide-to-the-unexpected.html)
- [Purely functional data structure — Wikipedia](https://en.wikipedia.org/wiki/Purely_functional_data_structure)
- [Purely functional data structures — Pedro Vasconcelos, DCC/FCUP](https://www.dcc.fc.up.pt/~pbv/aulas/tapf/handouts/datastructures.html)
- [Equality in Lisp — Eli Bendersky's website](https://eli.thegreenplace.net/2004/08/08/equality-in-lisp)

---

## Идея ФП

### Типичный нефункциональный язык

```pascal
procedure inc(var m: integer);
begin
    m := m + 1;
end;

var x: integer = 0;
begin
  inc(x);
  writeln ('Result: ', x);
end.
```

----

### Функциональный язык

```c
#include<stdio.h>

int inc(int m) {
    return m + 1;
}

int main(void) {
    int x = 0;
    x = inc(x);
    printf("Result: %i", x);
}
```

---

## От процедур к функциям

### Procedures
<dl>
  <dt>  </dt>
  <dd>  are subprograms that, instead of returning a single value, allow to obtain a group of results. </dd>
</dl>
 
Что такое "results" обычно не поясняется. Считаем, что это побочные эффекты:

- запись в память/чтение из памяти;
- ввод/вывод.

*Вопрос:* корректно ли данное разделение результатов?

----

### Function (in math)
<dl>
  <dt>  </dt>
  <dd>  a function from a set $X$ to a set $Y$ assigns to each element of $X$ exactly one element of $Y$. </dd>
</dl>
 
В переводе для программистов:

- вход однозначно определяет выход;
- отсутствие побочных эффектов (чистые функции);
- невыразимость ввода-вывода.

![A function that associates any of the four colored shapes to its color.](figures/function-in-math.png)

----

Функциональное программирование стремится к математическому пониманию функции:

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

стремиться $\neq$ являться

*Offtopic:* место стековых языков программирования, таких как Forth.

----

Преимущества:

- локализация проблем, тестирование, отладка;
- относительная простота параллельного программирования;
- больше формальных свойств (оптимизация, порядка вычислений);
- функции высшего порядка (модульность, конфигурируемость).

Недостатки:

- не позволяет программировать алгоритмы и структуры "в лоб";
- многие задачи требуют изменяемого состояния;
- вычислительный контекст приходится таскать самому;
- трудности ввода-вывода и "нелинейность" процессов;
- на пустом месте: "И как сюда `printf` воткнуть?";
- программисты с математическим складом ума.

*Offtopic:* какие ещё есть средства, упрощающие параллельное программирование?