Data Science/Machine Learning
0,0
рейтинг
15 декабря 2014 в 17:42

Разработка → Теория категорий для программистов: предисловие перевод

Вот уже некоторое время я обдумываю идею написать книгу о теории категорий для программистов. Не компьютерных теоретиков, программистов — скорее инженеров, чем ученых. Я знаю, что это звучит безумно, и я сам достаточно напуган. Я знаю, что есть огромная разница между наукой и техникой, потому, что я работал по обе стороны баррикад. Но у меня всегда был очень сильный порыв объяснить вещи. Я восхищаюсь Ричардрм Фейнманом, который был мастером простых объяснений. Я знаю, я не Фейнман, но я буду стараться изо всех сил. Я начинаю с публикации этого предисловия, которое должно мотивировать читателя изучить теорию категорий, и надеюсь на начало дискуссии и обратную связь.

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

Мой оптимизм основан на нескольких наблюдениях. Во-первых, теория категорий — сокровищница чрезвычайно полезных идей программирования. Haskell-программисты черпали из нее уже долгое время, и эти идеи медленно просачиваются в другие языки, но этот процесс идет слишком медленно. Нам нужно его ускорить.

Во-вторых, есть много различных видов математики, и все они предназначены для разных аудиторий. У вас может быть аллергия на математический анализ или алгебру, но это не означает, что вам не понравится теория категорий. Не побоюсь утверждать, что теория категорий — это именно тот вид математики, который особенно хорошо подходит для мышления программистов. Это потому, что теория категорий вместо того, чтобы иметь дело с деталями, оперирует структурой. Она оперирует такими понятиями, которые делают программы компонуемыми.

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

В-третьих, у меня есть секретное оружие, нож мясника, которым я буду кромсать математику, чтобы сделать ее понятнее для программистов. Когда вы профессиональный математик, вы должны быть очень осторожны, чтобы определить все ваши предположения точно, выписать каждое выражение должным образом, и строить все свои доказательства строго. Это делает математические статьи и книги чрезвычайно трудными для чтения непосвященными. Я по образованию физик, и в физике мы добились удивительных успехов, используя неформальные рассуждения. Математики смеялись над дельта-функцией Дирака, которая была придумана великим физиком, П. А. М. Дираком, чтобы решить некоторые дифференциальные уравнения. Они перестали смеяться, когда придумали совершенно новую отрасль анализа, формализующую идеи Дирака и названую теорией распределений.

Конечно, с помощью размахивания руками вы рискуете сказать что-то откровенно неверное, поэтому я постараюсь убедиться, что позади неформальных аргументов в этой книге есть твердая математическая теория. У меня есть потертая копия книги Сандерса МакЛейна «Теория категорий для математиков» на моей тумбочке.

Поскольку эта книга о теории категорий для программистов, я проиллюстрирую все основные понятия, используя компьютерные программы. Вы, наверное, знаете, что функциональные языки ближе к математике, чем более популярные императивные языки. В них так же можно создавать более мощные абстракции. У меня было естественное искушение сказать: вы должны научиться Haskell, прежде чем теория категорий станет вам доступна, но это означало бы, что теория категорий не имеет никакого применения за пределами функционального программирования, а это просто неправда. Так что, я приведу много примеров на C++. Конечно, придется преодолеть уродливый синтаксис, и увидеть паттерны будет сложнее из за многословия, и вам, возможно, придется делать много copy-paste, вместо использования абстракций высшего порядка, но это и так большая часть жизни C++-программиста.

Однако, не все так просто с Haskell. Не нужно становиться программистом на нем, но придется его освоить в качестве языка для зарисовок идей, которые позже будут реализованы на C++. Именно так я и начал программировать на Haskell. Его краткий синтаксис и мощная система типов очень помогли мне с пониманием и реализацией C++-шаблонов, структур данных и алгоритмов. Однако, так как я не могу ожидать, что читатели уже знают Haskell, я введу его постепенно и объясню все на ходу.

Если вы опытный программист, вы можете думать: я давно программирую и не беспокоюсь ни о какой теории категорий или функциональных методах, зачем же что-то менять? Конечно, вы не можете не заметить, что в императивных языках устойчивый тренд на добавление новых функциональных возможностей. Даже Java, бастион объектно-ориентированного программирования, добавила лямбды. C++ недавно начал развиваться бешеными темпами, — новые стандарты каждые несколько лет, — пытается догнать меняющийся мир. Вся эта деятельность — подготовка к разрушительным изменениям или, как мы, физики, называем это, смена фазы. Если вы нагреваете воду, она в конце концов закипит. Сейчас мы находимся в положении лягушки, которая должна решить, продолжать ли плавание в нагревающейся воде, или начать искать альтернативы.

image

Одна из движущих сил для больших изменений — многоядерная революция. Преобладающая парадигма программирования, — объектно-ориентированное программирование, не дает вам ничего в области параллелизма, а вместо этого поощряет опасный и подверженный ошибкам дизайн. Основные принципы объектной ориентированности: cокрытие, совладение и мутация данных — идеальная среда для гонок данных. Идея объединения данных с мьютексом, который их защищает, хороша, но, к сожалению, блокировки не компонуемы, и сокрытие блокировок делает дедлоки более вероятными и менее отлаживаемыми.

Даже при отсутствии параллелизма, растущая сложность программных систем испытывает пределы масштабируемости императивного программирования. Проще говоря, побочные эффекты выходят из-под контроля. Функции с побочными эффектами легко и удобно писать. Побочные эффекты могут, в принципе, быть закодированы в их названиях и комментариях. Функция с названием SetPassword или WriteFile, очевидно, изменяет некое состояние и имеет побочные эффекты, и мы к этому привыкли. И только тогда, когда мы начинаем писать функции, имеющие побочные эффекты, работающие с другими функциями, имеющими побочные эффекты, и так далее, тогда вещи начинают становиться сложными. Не то чтобы побочные эффекты изначально плохи, плохо то, что они скрыты от глаз. Из за этого, в более крупных масштабах, становится невозможным ими управлять. Побочные эффекты не масштабируемы, а императивное программирование полностью построено на побочных эффектах.

Изменения в железе и растущая сложность программного обеспечения заставляют нас переосмыслить основы программирования. Так же, как строители великих готических соборов Европы, мы, в нашем ремесле, подходим к пределам материалов и структуры. В Бове, во Франции, есть недостроенный готический собор, который стоит свидетелем этой человеческой борьбы с естественными ограничениями. Задумывалось, что он побьет все предыдущие рекорды высоты и легкости, но в процессе постройки произошел ряд обрушений. От полного разрушения его защищают «костыли»: железные прутья и деревянные опоры. С современной точки зрения, чудо, что так много готических сооружений было успешно завершено без помощи современного материаловедения, компьютерного моделирования, анализа методом конечных элементов и общей математики и физики. Я надеюсь, что будущие поколения будут так же восхищены навыками программирования, которые мы демонстрируем, строя сложные операционные системы, веб-сервера и интернет-инфраструктуру. И, честно говоря, они и должны, потому что мы сделали все это на очень хлипкой теоретической основе. Наша задача — улучшить эти основы, если мы хотим двигаться вперед.

image
Костыли, защищающие собор в Бове от разрушения.

Продолжение следует.

Теория категорий для программистов: предисловие
Категория: суть композиции
Типы и функции
Категории, большие и малые
Категории Клейсли
Перевод: Bartosz Milewski
Max Strakhov @Monnoroch
карма
70,5
рейтинг 0,0
Data Science/Machine Learning
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (24)

  • +2
    С нетерпением жду следующих глав.
    Если бы это был не перевод, мог бы еще предложить автору писать примеры одновременно на Haskell и С++. Они бы прекрасно дополняли друг друга и сильно облегчали бы понимание: привычный синтаксис С++, но примеры громоздкие; компактный и заточенный под ФП код Haskell — но выносящий неподготовленный мозг синтаксис.
    • +3
      Вы знаете, в оригинале периодически так и есть. Возможно, я попробую дополнить их там, где потребуется.
  • +2
    Кстати, Бартош выступит в феврале на конференции в Москве. Доклад будет как раз про теорию категорий и как раз для C++ программистов :)
    • 0
      Очень советую сходить. Недавно была конференция с его участием в Новосибирске — эмоции только положительные, да и сам формат мне показался довольно интересным.
      • 0
        Рад, что Вам понравилось! Мы очень старались :-)
  • +1
    Для понимания ООП категории тоже полезны.
    Если объектами категерии будут классы C++, а морфизмами — static_cast, то виртуальное наследование от невиртуального будет отличаться коммутативностью соответствующего квадрата.
    • +1
      Вы совершенно правы в примере категории! Только врятли этот пример можно назвать очень полезным в понимании ООП, он скорее о потрохах C++, чем об ООП. Да и слишком частный это случай, не тянет на фундаментальную основу языка =)
    • +1
      Есть только один момент, который я не заметил сразу: если диаграмма не коммутативна, то это не морфизм. Так что, морфизмами будут не все возможные static_cast-ы, а только те, для которых она коммутативна.
      • +1
        Имеется в виду транзитивное замыкание всех static_cast.
  • 0
    Отлично, только не понимаю, почему примеры только на C++.
    • 0
      Еще на Haskell!
      • 0
        А, ну понятно. Просто из статьи это (мне) не было ясно.

        Так что, я приведу много примеров на C++. Конечно, придется преодолеть уродливый синтаксис, и увидеть паттерны будет сложнее из за многословия, и вам, возможно, придется делать много copy-paste, вместо использования абстракций высшего порядка, но это и так большая часть жизни C++-программиста.


  • 0
    После большого количества подобных текстов, так и не понял, зачем теоркат программисту. Обещают революцию, а на деле оказывается, что есть пара паттернов типа монад или стрелок, их можно использовать, конец.
    • 0
      Бартош говорит, что важнейшая польза этих паттернов — легкая и безопасная композиция concurrency и parallelism приситивов.
      • 0
        Я не о том говорю. Паттерны полезные, но какая польза теории категорий при этом. Вот у матана есть польза — вместо библиотечного математического метода X я могу подумать с бумажкой и упростить задачу до метода Y, или посчитать его границы применимости. Довольно редкая польза, надо сказать, но я ее понимаю и несколько раз в жизни я сидел в Maple с упрощением интегралов. А вот теория категорий зачем программисту? Учитывая, что работает он все время в одной категории, в которой объектами являются типы, зачем ему этот обобщающий категории матаппарат.
        Пока я в подобных статьях видел только ввод в терминологию (вот видишь этот паттерн, он называется монада в категории, где объектами являются типы данных языка, а стрелками — функции), и все.
        • 0
          Потому, что знать паттерны, но не знать лежащей под ними теории — это быть собакой павлова: жать на кнопки определенным образом при определенных условиях.
          • –1
            Я не нашел в книге Маклейна вообще ничего, что было бы применимо в программировании. Никакой теоремы или приема. Ну диаграммы. Ну коммутативны. Ну и что. Поэтому и спрашиваю.
            • +1
              Поэтому Бартош и затеял писать эту книгу — чтобы донести до программистов на мэйнстрим-парадигмах идеи и пользу от ТК.
    • +2
      Я бы сказал, что еще немного прочищает мозги по теме побочных эффектов у методов (функций). Многие не-функциональщики об этом вообще не задумываются.
  • 0
    1. перевод интересный, книга интересная и буду ждать продолжения
    2. а что это за книга (не могу найти не где её упоминания)? Может быть и сам почитаю…

    Пока читал поймал себя на мысли что не где не видел простого обзора по современным языкам программирования, и классификации языков программирования и т.п. Я понимаю что многие программисты изучают и знают это (чуть ли не впитывают с молоком матери), но не было бы полезным иметь такой обзор. Так что дарю идею, а сам пошел читать википедию для начала.
    • +4
      Книга в процессе написания, Бартош постит по главе в своем блоге. А я их сюда перевожу.
      • 0
        может быть, тогда имеет смысл указать ссылку на сам блог? (так, для тех кто не в теме)
        • 0
          А она указана, как во всех переводах.
          • 0
            все, увидел! спасибо :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.