Теория категорий (не) для программирования?

21

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

Проведя много неудачных попыток связать теорию категорий с проектированием программ, я пришел к выводу, что:

  • Теория категорий полезна при разработке языка программирования .
  • Теория категорий - это не то, что вы используете при разработке программ (даже при использовании языка, который был разработан на основе принципов категорий). Например: при программировании на Haskell вы будете использовать типы, конструктор типов, функции, функции высшего порядка и т. Д. Для разработки своей программы, а не концепции теории категорий.

В итоге мы имеем систему нижнего уровня (порядок от низкого до высокого):

Теория категорий -> Язык программирования -> Программа

На определенном уровне вы используете концепции непосредственного нижележащего уровня .

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

ПРИМЕЧАНИЕ. Под разработкой программ я подразумеваю разработку программ на основе различных концепций, таких как параллелизм, параллелизм, реактивность, передача сообщений и т. Д.

Анкур
источник
1
Считаете ли вы монады частью языка программирования или программ? Стрелы?
Дэйв Кларк
2
Это кажется мне философским вопросом, по крайней мере, частично. Я не уверен, что есть один правильный ответ. Один адепт теории категорий будет применять интуицию, полученную при программировании, а другой - различные способы мышления.
Рафаэль
2
Большинство написанных программ используют языки программирования, не основанные на теории категорий. Насколько я могу судить, рядовой программист не знает теории категорий, и поэтому большинство программ (включая вашу операционную систему и ваш браузер) не вдохновлены высшей математикой.
Юваль Фильмус
1
@YuvalFilmus: Мой вопрос нацелен на функциональные языки программирования
Ankur
1
см. также этот вопрос для некоторых приложений CS моноидов
vzn

Ответы:

13

Ну, это, конечно, зависит от того, какую программу вы пытаетесь создать.

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

Но, конечно, существуют ситуации, в которых теория категорий чрезвычайно полезна при разработке программ (под которыми я также имею в виду структуры данных, библиотеки и т. Д.). Такие ситуации чаще всего возникают, когда участвующие программы имеют математическую природу.

Если вы хотите написать программы, которые вычисляют с точными действительными числами и другими структурами, встречающимися в математическом анализе, первый вопрос, на который вам нужно ответить, - что это означает для правильной реализации сложного математического объекта (такого как дифференцируемая функция, многообразие и т. Д.). ). Здесь очень полезно знать некоторые теории и логику категорий, потому что они дают вам систематический способ перевода определений математических структур в спецификации и реализации соответствующих структур данных. Модное слово, которое вы должны искать, это теория реализуемости . Но это только один пример.

Лучший способ увидеть, как теория категорий пригодится, - это посмотреть программы, написанные людьми, которые много знают теорию категорий (и математику в целом). Очевидным примером этого является Мартин Эскардо и его невозможные функционалы, например:

М. Эскардо и П. Олива: Что есть в последовательных играх, теореме Тихонова и сдвиге двойного отрицания в общем математически структурированном функциональном программировании 2010, ACM Press. (с сопутствующими файлами на Haskell и Agda )

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

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

Андрей Бауэр
источник
Это именно моя точка зрения. Если я проектирую бухгалтерское программное обеспечение, система типов будет моим языком для дизайна. Даже если я разрабатываю математическое программное обеспечение, я буду использовать систему типов для представления концепций теории категорий. Что в основном указывает на то, что теория типов ИЛИ системы типов являются более общими абстракциями, чем теория категорий.
Анкур
1
Это нелепое утверждение. Я думаю, что вы, возможно, должны узнать еще немного, прежде чем делать такие громкие заявления. Возможно, вы можете начать с existentialtype.wordpress.com/2011/03/27/the-holy-trinity
Андрей Бауэр
Я не исследователь, аспирант, ученый, математик или теоретик категорий, поэтому не расстраивайтесь из-за моих утверждений, они не будут опубликованы в каком-либо научном журнале или исследовательской работе. Я просто программист, который пытается понять другую сторону медали. Кстати, спасибо за ссылку.
Анкур
1
Я понимаю это, и именно поэтому я предлагаю вам быть осторожным в том, чтобы делать выводы, как вы: у вас просто нет информации, необходимой для того, чтобы делать такие выводы. И именно поэтому я отсылаю вас к сообщению в блоге Боба Харфера, а не, скажем, к какой-то технической книге о связи между теорией типов и теорией категорий. Я пытаюсь помочь, но я ожидаю от вас немного больше оговорок, когда дело доходит до грандиозных выводов о природе целой отрасли математики.
Андрей Бауэр
Например, вы заявили, что «теория типов является более общей абстракцией, чем теория категорий». Это пример заявления, которое вы должны знать, а не делать, основываясь на небольших знаниях. Я профессионально работаю в этой области, и даже я буду очень осторожен, чтобы сделать такой вывод или противоположный.
Андрей Бауэр
6

Люди использовали CT для описания типов данных.

  1. Тип данных был определен конкретной категорией, чьи объекты представляют собой конечные последовательности типов (языка спецификации), а стрелки которых были проекциями или композициями операций типа данных. Например, объект является доменом и является кодоменом операции push стеков. Это дает вам синтаксис, но у вас все еще нет понятия семантики.
  2. Алгебра, то есть экземпляр типа, является функтором от теории к Ens, категории (малых) множеств. (Мы используем «маленький», чтобы избежать парадокса Рассела, но это не имеет большого значения.)
  3. Оказывается, что замыкающие свойства категорий соответствуют семействам логических теорий. Например, если категория теории замкнута по произведениям, тип данных может быть аксиоматизирован уравнениями. Если категория теории закрыта с помощью откатов, то тип данных может быть аксиоматизирован предложениями Хорна.

Я не совсем уверен, что кто-нибудь больше обращает на это внимание. Я думаю, что это , и ссылки там, объяснят это более подробно.

Vilcxjo
источник