Введение

Кажется, монады в программировании стали загадкой века. И для этого есть две причины:

• недостаточное знание теории категорий;
• многие авторы стараюстся не упоминать категории вообще.

Это как говорить об электричестве не используя мат. анализ. Достаточно для замены предохранителя, не хватит, чтобы спроектировать усилитель.

Мы начнём с простого введения в категории и функторы, затем дадим определение монады, приведём простые примеры монад в категориях и в конце приведём монадическую терминологию используемую в языках программирования.

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

Содержание

1. Категория
2. Функтор
3. Естественное преобразование
4. Монада
5. Монады исключения и состояния
6. Монады в программировании
7. Ссылки

Введение

Как узнать, что человек понял, что такое монады? Он сам вам об этом расскажет в первые 5 минут общения и обязательно попробует объяснить. А ещё напишет об этом текст и по возможности где-нибудь его опубликует, чтобы все остальные тоже поняли, что такое монады.

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

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

Моё изложение во многом основывается на книге Бартоша Милевски "Теория категорий для программистов", которая создавалась как серия блогпостов, доступна в PDF, а недавно вышла в бумаге.

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

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

Первоначально эту нишу занимали крупные инновационные интернет-компании типа Google или Twitter, однако такие требования к приложениям начали всплывать во многих областях индустрии. Финансовые и телекоммуникационные компании первыми начали внедрять новые практики, чтобы удовлетворить новым требованиям, а теперь подтягиваются и остальные.

Новые требования требуют новых технологий. Предыдущие решения делали упор на управляемые сервера и контейнеры. Масштабирование достигалось засчёт покупки более крутых серверов и использования многопоточности. Для добавления новых серверов приходилось применять комплексные, неэффективные и дорогие проприетарные решения.

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

Folly — это открытая С++ библиотека, разрабатываемая Facebook и используемая им во внутренних проектах. С целью оптимизации расходов памяти и процессорных ресурсов библиотека включает собственные реализации некоторых стандартных контейнеров и алгоритмов. Одной из них является folly::fbvector — замена стандартного вектора (std::vector). Реализация от Facebook полностью совместима с оригинальным интерфейсом std::vector, изменения всегда не-негативны, почти всегда измеримы, часто — существенно, а иногда даже грандиозно влияют на производительность и\или расход памяти. Просто включите заголовочный файл folly/FBVector.h и замените std::vector на folly::fbvector для использования его в своём коде.

Пример

folly::fbvector<int> numbers({0, 1, 2, 3});
numbers.reserve(10);
for (int i = 4; i < 10; i++) {
  numbers.push_back(i * 2);
}
assert(numbers[6] == 12);

Мотивация

std::vector — устоявшаяся абстракция, которую многие используют для динамически-аллоцируемых массивов в С++. Также это самый известный и самый часто используемый контейнер. Тем большим сюрпризом оказывается то, что его стандартная реализация оставляет достаточно много возможностей по улучшению эффективности использования вектора. Этот документ объясняет, как реализация folly::fbvector улучшает некоторые аспекты std::vector. Вы можете воспользоваться тестами из folly/test/FBVectorTest.cpp чтобы сравнить производительность std::vector и folly::fbvector.

Вступление

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

Цель этой статьи — рассказать о языке программирования Go (Golang) тем разработчикам, которые смотрят в сторону этого языка, но еще не решились взяться за его изучение. Рассказ будет вестись на примере реального приложения, которое представляет из себя RESTful API веб-сервис.

Как вы, наверное, догадались, эта статья посвящена lock-free очередям.

Очереди бывают разные. Они могут различаться по числу писателей (producer) и читателей (consumer) – single/multi producer — single/multi consumer, 4 варианта, — они могут быть ограниченными (bounded, на основе предраспределенного буфера) и неограниченными, на основе списка (unbounded), с поддержкой приоритетов или без, lock-free, wait-free или lock-based, со строгим соблюдением FIFO (fair) и не очень (unfair) и т.д. Подробно типы очередей описаны в этой и этой статьях Дмитрия Вьюкова. Чем более специализированы требования к очереди, тем, как правило, более эффективным оказывается её алгоритм. В данной статье я рассмотрю самый общий вариант очередей — multi-producer/multi-consumer unbounded concurrent queue без поддержки приоритетов.

Как известно, функциональный подход к программированию имеет свою специфику: в нём мы преобразовываем данные, а не меняем их. Но это накладывает свои ограничения, например при создании программ активно взаимодействующих с пользователем. В императивном языке намного проще реализовать такое поведение, ведь мы можем реагировать на какие либо события «в реальном времени», в то время как в чистых функциональных языках нам придётся откладывать общение с системой до самого конца. Однако относительно недавно стала развиваться новая парадигма программирования, решающая эту проблему. И имя ей — Functional Reactive Programming (FRP). В этой статье я попытаюсь показать основы FRP на примере написания змейки на Haskell с использованием библиотеки reactive-banana.

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

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

Компания, где я работаю, разрабатывает программное обеспечение на C++ под Linux. Долгое время мы использовали Qt Creator, с редкими ребятами работающими из Emacs и Vim. Когда я сам попытался пересесть на Vim, я понял, что ситуация с плагинами для разработки на С++ очень не простая. Поработав немного с CTags, я быстро понял, что без напильника работать в Vim будет очень сложно.
К сожалению, с ростом опыта работы с Vim редактор в Qt Creator в режиме эмуляции устраивал меня все меньше, и в какой-то момент я решил потратить немного времени и разобраться, как же сделать из Vim нормальную среду.
Я очертил для себя четыре вещи, которые я бы хотел от среды разработки, и которых мне бы хватило в Vim, чтобы полностью на него перейти:

1. Автодополнение
2. Навигация по коду
3. Отладка прямо из среды
4. Интеграция с Git (в частности Blame прямо в редакторе, и Git Grep)

Автодополнение в Vim — это решенная проблема, и название у решения YouCompleteMe. Это очень качественный плагин, который реализует автодополнение для большого количества языков программирования, в частности Python и C++. Ходят слухи, что внутри Google YouCompleteMe решает и вторую проблему с навигацией кода, но использует для этого внутренные инструменты гугла для индексирования.

Интеграция с Git в какой-то степени решена с помощью vim-fugitive. Это не такая комплексная интеграция, как бывает у Jet Brains, или в Visual Studio, но сравнимая с тем, что предлагает Qt Creator. Те два сценария, которые нужны были мне: blame и grep — работают хорошо.

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

Это вторая статья в цикле «Теория категорий для программистов».

Категория — очень простая концепция.

Категория состоит из объектов и стрелок, которые направлены между ними. Поэтому, категории так легко представить графически. Объект можно нарисовать в виде круга или точки, а стрелки — просто стрелки между ними. (Просто для разнообразия, я буду время от времени рисовать объекты, как поросят а стрелки, как фейерверки.) Но суть категории — композиция. Или, если вам больше нравится, суть композиции — категория. Стрелки компонуются так, что если у вас есть стрелка от объекта А к объекту B, и еще одна стрелка из объекта B в C, то должна быть стрелка, — их композиция, — от А до С.

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

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