Справочный запрос: теория категорий в применении к системам типов

13

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

К сожалению, ни один из источников, которые я могу найти, кажется, не связан с системами типов или программированием. Они говорят, что это введение в теорию категорий для компьютерных ученых, но затем отклоняются от общей абстрактной чепухи (я говорю это с любовью), не приводя никаких практических примеров или приложений.

Я предполагаю, что мой вопрос на самом деле состоит из двух частей:

  1. Является ли теория категорий необходимой для понимания «глубоких концепций» в PL?
  2. Какой источник объясняет теорию категорий с точки зрения практического применения к системам типов и программированию?

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

gardenhead
источник
2
@ Рафаэль Плохо было бы задавать вопрос, который состоит из двух разных вопросов, только смутно связанных друг с другом. Но вопрос 1. не субъективен. Это скорее просьба о разъяснениях и объяснениях. Я предполагаю, что вопрос 2. подразумевался в том смысле, что он доволен ссылкой на место, где это объясняется, вместо фактического объяснения тоже.
Томас Климпел
2
В будущем лучше задавать только один вопрос на пост. Вы можете задать вопрос 1, а затем, в зависимости от полученных ответов, решить, стоит ли задавать вопрос 2 отдельно. Это часто заставляет дела идти более гладко.
DW
1
@ Рафаэль Как вопрос один субъективный? Это может быть трудно судить - это то, что вы имеете в виду? И это может быть ответом: «Это зависит от того, какой ты человек». - это то, что вы имели ввиду? Все еще может оказаться, что это определенно необходимо или определенно не обязательно, верно? (И люди, похоже, согласны с тем, что это не существенно.)
k.stm
1
@ k.stm Общая форма вопроса меня беспокоит. Если бы кто-то спросил: «Является ли алгебра необходимой для понимания глубоких понятий формальных языков?», Я точно знаю, что разные люди будут давать разные ответы - исходя из своих предпочтений и вкуса. Я не ожидаю, что здесь будет по-другому.
Рафаэль
1
@ Рафаэль Хорошо, я понял. Но я думаю, что это люди, которые дают субъективные ответы на объективный вопрос. (Чувствуется, что люди говорят: «О, я пью пять чашек в день, и я чувствую себя прекрасно!», Когда меня спрашивают, полезен ли кофе.)
k.stm

Ответы:

15

Теория категорий не обязательна для понимания языков программирования, даже нет необходимости проводить углубленные исследования языков программирования. Большинство людей на языке программирования не знают (много) теории категорий.

Теоретические методы категории были полезны главным образом в небольшой части исследования языка программирования, а именно при анализе функционального программирования, в частности, после великого открытия Могги, что некоторые вычислительные эффекты имеют монадическую структуру. В 1990-х годах, после прорыва Могги, было проведено много исследований, чтобы распространить категориальные методы на другие формы языков программирования. Однако, насколько мне известно, категориальные методы не были найдены такими полезными для ОО, параллельных, параллельных и распределенных вычислений, временных вычислений или компиляторов. По этой причине люди в основном отказались от расширения категориальных методов.

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

В настоящее время ведется большая работа над типами для одновременных процессов (например, типы сеансов), и ни один из них не является категоричным по состоянию на сентябрь 2016 года.

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

Наконец, теория категорий - это красивая математика, и ее стоит изучать просто потому, что она такая аккуратная.


Посмотрите вклад Uday Reddy в этом обсуждении для другого взгляда.

Мартин Бергер
источник
«Однако, насколько мне известно, категорические методы не были найдены все, что полезно для ...» Это именно моя проблема. Операционная семантика может точно описать все эти концепции, поэтому я не чувствовал, что упускаю. Я люблю математику, но мой опыт в абстрактной алгебре, к сожалению, отсутствует. Я только понимаю голые основы общих алгебраических структур. Это сделало понимание теории категорий особенно громоздким.
садовник
2
@gardenhead Тогда, возможно, КТ не так уж полезна для вас. Если вы хотите прочитать много статей в пространстве «Функциональное программирование», включая работу с типами, тогда многие из них будут использовать язык CT.
Мартин Бергер
Является ли это один дубликат?
Рафаэль
2
Я бы дополнительно предложил книгу cs.unibo.it/~asperti/PAPERS/book.pdf «Категории, типы и структуры», которая, по-видимому, больше не печатается, но это ссылка на PDF-файл одного из Домашние страницы авторов, так что я думаю, что это законно.
Джон Форкош
6

Теория изучения категории - это огромные затраты времени, и вопрос о том, стоит ли она того, очень актуален. Я все еще борюсь с этим , и я уже знаю, почему я должен изучить это. Я написал:

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

Идея здесь состоит в том, чтобы использовать категории вместо наборов или «неопределенных битов» в качестве возможной семантики для данной теории типов или языка программирования. Почему нужно это делать? Рассмотрим двойственность между действием и наблюдением. Различные наблюдения (или, по крайней мере, их порядок во времени) не мешают друг другу (вне квантовой механики), но это не обязательно верно для разных действий. Укоренившиеся предрассудки о логике, встроенной в теорию множеств, затрудняют моделирование действий по сравнению с моделированием наблюдений.


Я не уверен, что действительно существует идеальное соответствие между теорией категорий и теорией типов, как утверждается здесь :

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

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


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

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