Lesson 3. Introduction to Theory of Categories

[the-homeless-god]

Questions:

• Declarative vs Imperative programming
• What's theory of categories
• Provide a few example unsolvable tasks with usage of Declarative programming
• How to optimize tail recursion?

Materials for self-preparation:

• https://www.youtube.com/watch?v=aCvnUuYaRH8

• https://www.youtube.com/watch?v=7peIaVJj_pg or https://vkvideo.ru/video-91031095_456245200

• https://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D1%8F%D0%BC%D0%B1%D0%B4%D0%B0-%D0%B8%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5

• https://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4%D0%B0_%D1%82%D0%B8%D0%BF%D0%BE%D0%B2_%D0%B2_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B5_%D1%81_%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D1%8B%D0%BC%D0%B8_%D1%82%D0%B8%D0%BF%D0%B0%D0%BC%D0%B8

Что было сделано за прошедший инкремент:

– Пробежались по всей математике
– Заглянули в p ≠ np or p = np
– Пробежались по алгоритмическим сложностям o(n) и O(n)
– Разобрали решение задачи со множествами через императивный и декларативные пути

Рекомендации к прочтению:

– Совершенный алгоритм, Тим Рафгарден
– Гипотеза Пуанкаре-Перельмана
– Декларативные языки программирования
– Оптимизация хвостовой рекурсии
– Реализация head / tail в декларативных языках программирования

[EugeneWWolf]

3-147 Ермакова Ксения

Declarative vs Imperative programming
В декларативном программировании больше упор идёт на то, что надо сделать, а не как. Тем самым компилятор берёт на себя бОльшую ответственность за имплементацию решения, что находится под капотом, чем при императивном программировании. Также код декларативного стиля довольно абстрактный, не имеет сайд-эффектов (как правило, переменные иммутабельные, есть понятие "чистых функций") и, как правило, имеет более простую структуру в целом.

What's theory of categories
Теория категорий строится на симметрии объектов и сколькими способами можно преобразовать данный объект, чтобы он всё ещё сохранял те или иные свойства. Причём необязательно, что в ходе преобразования это будет в точности тот же объект, что и до этого. Теория категорий делает акцент лишь на симметрии, не на самом объекте. Для того, чтобы показать универсальность и сложность теории категорий, создали группу "Монстр", которая содержит в себе очень большое число действий, такое, что "Монстр" не вместится даже в 10000 измерений.

Provide a few example unsolvable tasks with usage of Declarative programming
Declarative programming is often limited in its ability to solve tasks that require detailed control over the execution process, such as real-time game development or complex algorithm optimization. Additionally, tasks that involve extensive state changes or require side effects, like managing user interactions in a dynamic web application, can be challenging to implement effectively using purely declarative approaches.
Декларативным стилем будет сложно решать задачи, в которых важно точно управлять реализацией решения. Например, какая-нибудь сложная оптимизация алгоритма, где нужно выжать всё по максимуму. Сюда можно отнести и компьютерные игры, где нужна хорошая оптимизация (того, чего не хватает современным поделкам на Unreal Engine 5). Также задачи, где требуется частое изменение состояний объектов или нужно иметь много сайд-эффектов (например, взаимодействие большого количества пользователей с каким-нибудь интерактивным веб-приложением) тоже будет довольно сложно реализовать эффективно в декларативном стиле.
Из невозможных задач: нельзя сделать из CSS тюринг-комплит инструмент, так как это полностью декларативный язык, который в добавок не имеет циклов, условий и тому подобного. Для более сложных вычислений нужно использовать JavaScript или какой-нибудь фреймворк, либо использовать препроцессор по типу SCSS, который переведёт код с условиями в код, который будет понятен CSS.

How to optimize tail recursion?
В императивном стиле чаще выгоднее по памати или/и времени использовать цикл , чем рекурсию. Также в декларативном стиле, по моим скромным знаниям Scheme (диалект Lisp), знаю, что сам язык оптимизирует tail-recursion и преобразует её в цикл, только если она правильно написана (хвостовой считается только рекурсия, где последнее действие - это вызов функции самой себя. Если же после вызова происходит ещё и умножение результата, это уже не хвостовая рекурсия).

Хвостовая рекурсия:

(define (factorial-tail n acc)
  (if (= n 0)
      acc
      (factorial-tail (- n 1) (* acc n))))

Не хвостовая рекурсия (перед возвращением результата его необходимо ещё и умножить):

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

[denisbochka]

Смолов 3/147

1. В императивном программировании мы указываем как мы хотим получить результат, то есть, например, полностью прописываем поведение функции. В декларативном программировании мы лишь указываем, какой результат мы хотим получить (например, какой-нибудь SQL-запрос SELECT COUNT(*) FROM "tablename" WHERE chto-to = "haha").
2. Категория - ориентированный граф, в котором узлы называются объектами, а рёбра - морфизмами. У каждого объекта есть морфизм в себя. В функциональном программировании программы это категории, где типы — объекты, а функции — морфизмы.
3. Это задачи, которые требуют оптимизации; задачи, для решения которых необходимо иметь доступ к состоянию программы (декларативное программирование не позволяет отслеживать состояние и его изменения); задачи, связанные с вводом-выводом
4. Проще всего заменить хвостовую рекурсию циклом, что уменьшит потребление памяти и сделает код быстрее

[CBEPXPA333YM]

Лебедев Егор 3/147

1. Императивное программирование - подход к программированию, в котором алгоритм программы описывает, каким образом мы получим результат. Декларативное программирование подразумевает, что программа описывает то, как будет выглядеть результат, алгоритм получения нас не интересует.
2. Теория категорий - раздел математики, в котором рассматриваются объекты и их отношения. Существует два основных понятия категории - объекты: некие множества и морфизмы: функции отображающие одни объекты на другие.
3. С помощью декларативного программирования невозможно сделать игры. Во-первых нужно обрабатывать ввод игрока, а это только императивный подход. Во вторых, нужно работать с ресурсами компьютера, это тоже невозможно с помощью декларативного программирования. В третьих, для работы с изменяющимися объектами игры придется также комбинировать декларативный и императивный подходы.
4. Хвостовая рекурсия - рекурсия, в которой вызов функции является последним действием. Чтобы оптимизировать такую функцию, нужно заменить ее на цикл, чтобы избежать переполнения стека

[goutosama]

Чадов Сергей 3/147
Declarative vs Imperative programming
Декларативное программирование подразумевает описание результата программы, а компилятор должен самостоятельно решить задачу, опираясь на это описание. Такими языками (хотя и не все являются языками программирования) можно назвать SQL, HTML/CSS, они отвечают своей конкретной задаче (оперирование базой данных, рисование веб-документа) и позволяют полную свободу действий в рамках этого использования. Императивные языки программирования в отличии от них, описывают последовательность действий для достижения результата, которую компилятор почти не меняет, поэтому императивные языки программирования более универсальны и распространены. В некоторых императивных языках присутствуют функции, позволяющие декларативно решать некоторые задачи, например apply(), map() и др. в javascript позволяют использовать уже готовый внутренний алгоритм для простых задач вроде перебора массива циклом.

What's theory of categories
Теория категорий - раздел математики описывающий переходы и преобразования объектов, основанное на симметрии, не изменяющих их внутреннюю составляющую. Их можно представить как графы, где узлы являются объектами, а рёбра - переходами или морфизмами. В программировании категории можно представить как машину состояний, где программа перемещает объекты из одного состояния в другое с помощью функций переходов.

Provide a few example unsolvable tasks with usage of Declarative programming
Нерешаемыми задачами в декларативном программировании можно назвать любые задачи, где важно описать внутреннюю работу алгоритма, от которой зависит результат: задачи шифрования и расшифрования данных, задачи оптимизации некоторого алгоритма, задачи, которые требуется выполнить параллельно в определённой нужной последовательности.

How to optimize tail recursion?
Хвостовая рекурсия - рекурсия, в которой каждый рекурсивный вызов находится в самом конце функции. Это свойство позволяет преобразовать рекурсию в цикл, тем самым оптимизируя код: уменьшая использование памяти в стеке вызовов и уменьшая количество инструкций процессора, поскольку многократные вызовы функций сложнее чем цикл. Во многих компиляторах такая оптимизация имплементирована и оптимизирует рекурсии автоматически, однако не каждую рекурсию можно преобразовать - хвостовая рекурсия это довольно частый случай, но не единственный.

[Egorius1268]

Фролов Егор 3/42

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

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

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

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

[polinmitrona]

Митронова Полина 3/147

1. В декларативном программировании описывают программу в виде функций. Отличие от функций в императивном программировании в том, что они устанавливают отношение между аргументом и результатом, и не могу изменять никаких переменных во время вычислений. Основоположником декларативного программирования стал Черч, а императивного - Тьюринг
2. Теория категорий возникла из идеи, что для каждого объекта есть набор преобразований, которые этот объект будут сохранять. Это сохранение называется симметрией. Объекты с одним и тем же видом преобразования объединяются в группы
3. Декларативное программирование не подходит для решения задач, связанных с состоянием программы. Например, управление интерфейсами требует отслеживания состояний виджетов, обработки событий и изменения отображаемых данных
4. Оптимизацией хвостовой рекурсии является преобразование ее в «прыжок», то есть переход к ее итерационному аналогу. Это исключает ограничения стека и повышает производительность за счет отсутствия дополнительных затрат на вызов функции

[Alena648]

Брюханова Алена 3/147

1. Декларативное и императивное программирование — это два разных подхода к написанию программ, которые отличаются способом описания задач и управления выполнением кода.
   Императивное программирование фокусируется на том, как достичь результата. Программист явно описывает шаги, которые необходимо выполнить, чтобы решить задачу. Код состоит из последовательности команд, которые изменяют состояние программы.
   Декларативное программирование фокусируется на том, что нужно сделать, а не на том, как это сделать. Программист описывает желаемый результат, а детали выполнения скрыты.
2. Теория категорий — это раздел математики, который изучает структуры и отношения между ними на высоком уровне абстракции. Она предоставляет универсальный язык и инструменты для анализа и сравнения различных математических концепций, таких как множества, группы, топологические пространства и другие. Теория категорий фокусируется на категориях, которые состоят из объектов и морфизмов (стрелок), связывающих эти объекты.
3. Проблема остановки — это классическая неразрешимая задача в теории вычислений. Она формулируется так: можно ли определить, завершится ли выполнение программы за конечное время для произвольного входа?
   Задача определения, эквивалентны ли две программы (т.е. возвращают ли они одинаковые результаты для всех возможных входов), является неразрешимой.
   В языках с зависимыми типами (например, Idris или Agda) задача проверки, удовлетворяет ли программа всем типам для всех возможных входов, может быть неразрешимой.
   В логическом программировании (например, на языке Prolog) задача поиска всех решений для некоторых предикатов может быть неразрешимой из-за бесконечного числа решений или неограниченного времени выполнения.
4. Использование аккумулятора: аккумулятор — это дополнительный параметр, который накапливает результат вычислений. Это позволяет избежать необходимости сохранять состояние на каждом шаге рекурсии.
   Преобразование в итерацию: компиляторы функциональных языков часто преобразуют хвостовую рекурсию в цикл. Это позволяет избежать переполнения стека.
   Использование циклов вместо рекурсии: в языках, которые не поддерживают оптимизацию хвостовой рекурсии (например, Python), можно явно заменить рекурсию на цикл.
   Использование встроенных функций: во многих языках есть встроенные функции, которые уже оптимизированы для работы с рекурсивными структурами (например, foldl, foldr в Haskell).

[MrLobzik]

3/147 Лобанов Дмитрий

1. В императивном программировании тот, кто пишет код, описывает процесс (алгоритм) как получить результат, а в декларативном программировании, какой именно результат он хочет получить оставляя всё, что связанно с процессом получения на систему и то, как она это будет делать. Пример декларативных языков: SQL, CSS, HTML. Пример императивных языков: C++, C#, Java. При этом некоторые библиотеки для императивных языков позволяют писать в декларативном стиле. Например, pandas для Python.
2. Теория категорий - один из разделов математики. Он рассматривает отношения между объектами в виде групп, которые являются совокупностью каких-либо преобразований. Эти преобразования должны соответствовать требованию: применяя преобразование к объекту, с объектом не происходит изменений (например, отражение квадрата по одной из его диагоналей или поворот равностороннего треугольника на 120 градусов). Так как мы говорим о математике, то приведённое выше объяснения является упрощением более абстрактной сущности, которой являются группы в теории групп.
3. Декларативным подходом сложно или не возможно решить задачи требующие реакции на какое-либо событие, так как декларативный подход подразумевает лишь получение желаемого результата, а не описание последовательности действий. К таким задачам относятся создание взаимодействия пользователя с каким-либо интерфейсами, поддерживающими взаимодействие разными путями, (например, графический интерфейс, так как могут присутствовать несколько разных элементов ввода, или какое-нибудь физическое оборудование, тот же ПК, пользовательский ввод может осуществляться через клавиатуру, мышь и прочие периферийные устройства ввода), обработка исключений (так как для случая возникновения исключительной ситуации надо прописать чёткий алгоритм выхода из неё и устранения возникших ошибок, чтобы программа не крашнулась при дальнейшем использовании), реализация задач, требующих высокой производительности.
4. Любой рекурсивный алгоритм можно заменить итерационным алгоритмом. Это самый простой и самый надёжный способ оптимизации рекурсий. Легче сразу записать функцию в итерационном виде, чем сначала узнавать поддерживает ли ваш язык хвостовую рекурсию, и в случае если поддерживает, писать функцию так, чтобы она была хвостовой рекурсией, а в случае если не поддерживает, опять же писать её в итерационном виде.

[kanclusion]

Канашин Дмитрий 3/42

1. При императивном программировании необходимо явно описать как достичь желаемого результат. Код будет выглядеть как последовательный список команд.При декларативном нужно только описать желаемый результат, а язык программирования сделает всё сам, скрыв детали выполнения от разработчика.

2. Теория категорий - это раздел математики, который описывает математические объекты и их связь. В ней есть объекты (например, числа или типы данных) и морфизмы (функции, которые преобразуют одни объекты в другие).

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

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

[Smrll]

Смирнова Лиза 3-42

1. Declarative vs Imperative programming

В декларативном программировании мы описываем желаемый результат без алгоритма его получения. Типичный пример: sql запрос выведи из таблицы собачки количество пушистиков — мы не говорим, как, каким образом, мы говорим «дай». В императивном же, наоборот, упор идет на алгоритм, команды, инструкции

2. What's theory of categories

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

3. Provide a few example unsolvable tasks with usage of Declarative programming

Если в задаче нужно отслеживать состояние объекта, если требуется реакция на какое-то событие, если стоит задача оптимизации кода — любая задача, где от алгоритма выполнения зависит результат

4. How to optimize tail recursion?

Рекурсия — это забитие стека, забитие памяти. Хвостовая рекурсия - это, несложно догадаться, рекурсия, находящаяся в хвосте, при этом в коде:

1. Происходит только один рекурсивный вызов
2. Рекурсивный вызов идет в конце вычислений

В некоторых языках хвостовую рекурсию преобразовывает компилятор: выделяется определённый постоянный объем памяти, в котором выполняются рекурсивные вызовы, что никак не отличается от циклов

В языках, где такого нет, можно заменить рекурсию на итерации

[Kirill-Bokov]

Кирилл Боков 3/42

1. Суть разницы между декларативным и императивным подходами к программированию заключается в названиях. Декларативный подход описывает то, что мы должны сделать, а императивный подход - как. Декларативный стиль описывает желаемый результат, а императивный не описывает результат - он описывает, какие шаги нужно сделать. В целом на человеческом уровне понятнее декларативный стиль, но для сложных программ всё равно используется смесь из этих стилей.
2. Теория категорий - это раздел алгебры, абстрагированный от самих объектов - чисел, функций, и т.д., изучающий отношения между этими объектами. Исходя из предложенной в видео-приложении схемы, теория категорий находится ниже 3 уровня. Этот раздел позволяет понимать фундаментальные темы из более прикладных наук, например физики.
3. В декларативном стиле невозможно создать, например, список, сделанный с помощью цикла, в котором следующие элементы зависят от предыдущих. То есть мы можем столкнуться с ограничениями каждый раз, когда нам нужно детально контролировать процесс создания какого-либо объекта.
4. При хвостовой рекурсии рекурсивный вызов всегда существует только в конце рекурсии. Благодаря этому свойству нет необходимости возвращаться на шаг выше, чтобы произвести новые вычисления, соответственно для данной задачи нет необходимости делать рекурсию. Так как рекурсия требует выделения памяти для того, чтобы хранить каждое промежуточное состояние, современные компиляторы используют преобразование хвостовой рекурсии в цикл. В итеративном алгоритме все промежуточные состояния будут храниться в виде переменных, что сокращает потребление памяти и предотвращает stack overflow.

[Roleng37]

Румянцев Максим 3/42

1. Декларативное программирование - это когда мы описываем, что нужно сделать, а императивное - это когда мы описываем, как это сделать.
2. Теория категорий - это раздел математики, который изучает отношения и структуры между объектами, а не сами объекты. Она предоставляет способ описания и анализа сложных систем и отношений между ними, используя понятия, такие как объекты, морфизмы и композиция.

3)Найти самый короткий путь из Москвы в Иваново, проехав через все города России. Это невозможно, потому что количество городов слишком велико, и декларативное программирование не может решить эту задачу.

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

[N-N0th1n9]

Цыганов Влад 3/42

1. Декларативное - описываешь ЧТО нужно сделать. Не указываешь, как это делать, фокус на конечном результате.
   Императивное - описываешь КАК сделать задачу шаг за шагом. Контролируешь каждый этап выполнения.

2. Теория категорий - это область математики, которая изучает абстракции и взаимосвязи между объектами и их отображениями в разных категориях.

3. Вычисления в real time сложно решить декларативно, потому что они требуют контроля за состоянием системы и быстрой реакции на изменения.

4. Не использовать хвостовую рекусию или