Функциональное программирование *

Питонисты Новосибирска, приглашаем вас на встречу сообщества Python сообщества — PyNSK.

12-го декабря (суббота) состоится пятая встреча. Она пройдет в новом для нас месте — Культурный Центр «Этаж» и начнется 13-00.
На встрече вас ждет море общения и 2 доклада:

Это пятая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре в переводе Monnoroch:
0. Теория категорий для программистов: предисловие
1. Категория: суть композиции
2. Типы и функции
3. Категории, большие и малые
4. Категории Клейсли

На КДПВ поросенок Петр заводит по одному трактору в каждый объект категории.

Следуй по стрелкам

Древнегреческий драматург Еврипид писал «Всякий человек подобен своему окружению». Это верно и для теории категорий. Выделить определенный объект категории можно только путем описания характера его взаимоотношений с другими объектами (и самим собой), где отношения — это морфизмы.

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

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

Несколько последних месяцев я программирую преимущественно на Scala (по работе) и на Haskell (для души). На этой неделе я, правда, ещё немного пописал на Ruby (по работе) и Clojure (для души).

Ruby вывел меня из равновесия почти сразу. Нет, ну ещё в плане «добавить небольшую фичу к уже имеющемуся коду» писать на нём можно. Вы просто добавляете юнит тест, запускаете его на старом коде, делаете правку, запускаете тест снова — вуаля, готово, забирайте. Но замахиваться на что-то большее становится уже слишком сложно.

Но вот что касается моего новенького, с иголочки, проекта-любимца на Clojure… О, Clojure! Глоток свежего воздуха! Благодатная земля хорошо скомпонованных функций, иммутабельных структур данных и всего такого. Как прекрасен твой синтаксис и как мудра твоя чувствительность! Вся твоя суть в функциях, принимающих мэпы и возвращающих мэпы. И твой SQL-генератор, и слой доступа к БД, и HTML-парсер, и URL-роутер являют собой одну и ту же завораживающую картину мэпов, гоняемых туда-сюда тактами процессора, прекрасную с своём ритме хорошо собранных швейцарских часов.

Вернуться к Clojure после долгого времени это всё равно, что почувствовать себя дома. Это просто окрыляет программиста. Но почему-то в этот раз я ощутил и ещё одно, неожиданное для себя чувство: неопределённость.

Привет, Хабр!

Мы в Хекслете учим людей программировать, но стараемся хитрить: например, под видом простого, на первый взгляд, курса по PHP, рассказываем людям про абстракции, рекурсии, функции первого класса, замыкании, свертку и вообще начинаем «Основы программирования» с МИТ'шного СИКПа, а не с классов и формочек. В этом и других курсах, а также в наших регулярных вебинарах рассказываем о функциональном программировании, о проблемах современных подходов и о главном зле: состоянии. В нашем чате постоянно поднимаются крупные дискуссии, в которых выясняется, что изменяемое состояние в разы повышает сложность в системе.

Сегодня мы публикуем перевод статьи, в которой Пиотр Солница, один из создателей популярного DataMapper для Ruby, рассуждает в подобном ключе о взаимодействии с базой данных.

* * *

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

Но что это вообще означает в Ruby? Запретить изменять любые объекты? Будет слишком медленно, так что — нет. Иммутабельно-ориентированный дизайн означает, что вы избегаете те интерфейсы, которые могут изменять объекты. Да, много методов в Руби изменяют состояние, но когда вы разрабатываете интерфейсы объектов, вы можете создавать их таким способом, что объекты не будут изменяться.

Использование неизменяемых объектов стало для меня шокирующим открытием. Одна из вещей, которую я понял после того открытия, это почему object-relational mapping (ORM) — плохая идея, и из-за нее у нас так много ненужной сложности.

Часть 4. Суровая действительность

Как заставить Parboiled работать еще быстрее? Каких ошибок лучше не допускать? Что делать с наследством в виде Parboiled1? На эти, а так же другие вопросы призвана ответить заключающая статья серии.

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Часть 3: Извлечение данных

В этой статье мы построим парсер для уже описанного нами ранее формата конфигурационных файлов. Также мы реализуем небольшой DSL для упрощенного доступа к элементам полученного дерева. Еще из этой статьи вы узнаете о типах правил, действиях парсера, а так же о «темной материи» Parboiled — стеке значений.

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Часть 2. Сопоставление текста

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

Для закрепления знаний мы напишем простой распознаватель для несложной грамматики. Именно распознаватель (recognizer), а не полноценный парсер, так как он будет только сопоставлять входной текст c описанными нами правилами (также называемыми продукциями), но не будет извлекать из сопоставленного текста какие-либо значения. Распознаватель может быть полезным и сам по себе, так как может работать в качестве валидатора: если вход оказался некорректным, распознаватель даст об этом знать и расскажет, что пошло не так и где. А совсем классным наш распознаватель станет тогда, когда мы узнаем, как извлекать разобранные значения и причем тут какой-то «value stack». Ну что, поехали?

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Часть 1. Почему Parboiled?

Сегодня, в свете бурного роста популярности функциональных языков программирования, всё чаще находят себе применение комбинаторы парсеров — инструменты, облегчающие разбор текста простым смертным. Такие библиотеки, как Parsec (Haskell) и Planck (OCaml) уже успели хорошо себя зарекомендовать в своих экосистемах. Их удобство и возможности в своё время подтолкнули создателя языка Scala, Мартина Одерски, внести в стандартную библиотеку их аналог — Scala Parser Combinators (ныне вынесены в scala-modules), а знание и умение пользоваться подобными инструментами — отнести к обязательным требованиям к Scala-разработчикам уровня A3.

Эта серия статей посвящена библиотеке Parboiled — мощной альтернативе и возможной замене для Scala Parser Combinators. В ней мы подробно рассмотрим работу с текущей версией библиотеки — Parboiled2, а также уделим внимание Parboiled1, так как большая часть существующего кода всё ещё использует именно её.

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Сейчас я работаю над senjin/gglsl — библиотекой для программирования шейдеров с помощью Groovy, о которой недавно писал.

Здесь я опишу три подхода к анализу AST (abstract syntax tree), все на примерах под-задач, вытекающих одна из другой и связанных общим контекстом: рекурсивные функции, паттерн Visitor, и паттерн-матчинг.
Паттерн-матчинг реализован на Java и доступен на GitHub.

Пару месяцев назад я взяла на себя обязательство по самопросвещению. Есть в иных конторах такая тема — сотрудника, раз в полгода ревьюят и говорят «давай к следующему ревью ты изучишь Spring, паттерны (какие?) и функциональное программирование!» Идея была бы неплоха если бы цели не ставили так размыто. Пропустим пока спринг и паттерны — на выходных я бросилась в атаку на ФП.

Общие-туманные сведения о ФП у меня конечно были — анонимные классы в Java я писать умею — с похожими способностями Python и JavaScript знакома.

Начну с простых упражнений на Scala — решила я. Выбрала Scala поскольку основной рабочий инструмент у нас Java — ну были еще варианты Clojure, Groovy и Java8 (что-то еще?) — но с ними авось попробую потом.

Поставила себе цели (а правильно ли я ФП поняла?):

• Решать задачи в функциональном стиле
• Т.е. по возможности не использовать явных циклов и ветвлений
• А также избегать мутабельных коллекций и т.п.

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

Примечание переводчика. В будущей версии Scala (“Don Giovanni”) анонсирована поддержка типов объединения (union types). Miles Sabin, широко известный в узких кругах как создатель Shapeless, демонстрирует в этой статье 2011 года, как создать типы объединения уже сейчас.
UPD. Представленный в статье подход не позволяет получить настоящих типов объединения и кроме того может существенно повлиять на время компиляции. Типы пересечения (A with B), использованные в статье, также отличаются от классических, поскольку не обладают свойством коммутативности. Подробности об экспериментальном проекте Dotty, в рамках которого будут решены эти и другие проблемы, можно посмотреть в замечательной презентации Дмитрия Петрашко darkdimius — разработчика компилятора Scala в EPFL.

Scala имеет очень выразительную систему типов. Однако она не включает (по крайней мере как примитивы) всех вожделенных элементов. Есть несколько поистине полезных типов, подпадающих под эту категорию — это типы полиморфных функций высшего ранга (higher-rank) и рекурсивные структурные типы. Но о них я расскажу подробнее в следующих постах, а сегодня я собираюсь показать вам, как в Scala мы можем создать типы объединения (union types). В ходе объяснения я пролью немного света на изоморфизм Карри-Ховарда и покажу, как использовать его в наших целях.

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

Я не буду расписывать, что такое монада, я просто покажу одну забавную реализацию монады Maybe (мы же в хабе «Ненормальное программирование»?).

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

Но в то время как функциональный стиль всё больше проникает в массы, и C# уже получил такие функциональные средства как лямбды и LINQ, кажется, что C# всё больше и больше наступает на пятки F#. Так что, как это ни странно, но я стал всё чаще слышать как высказывают такие мысли:

• «C# уже обладает большей частью инструментария F#, и зачем мне напрягаться с переходом?»
• «Нет никакой необходимости что-то менять. Всё, что нам нужно сделать, так это пару лет подождать, и C# получит достаточно от F#, что обеспечит практически все плюшки.»
• «F# только чуть лучше, чем C#, но не настолько, чтобы в самом деле тратить время с переходом на него.»
• «F# кажется действительно неплох, хоть и пугает местами. Но я не могу найти ему практического применения, чтобы использовать вместо C#.»

Не сомневаюсь, что теперь, когда и в Java тоже добавлены лямбды, подобные комментарии зазвучали в экосистеме JVM при обсуждении «Scala и Closure против Java».

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

Предлагаю читателям «Хабрахабра» вольный перевод статьи «Functional programming in Kotlin». Автор публикации — Mike Hearn.



Те, кто используют .NET, наверняка слышали про F#, универсальный функциональный язык программирования для CLR. Программисты же вне .NET сообщества скорее всего знают про функциональное программирование в связи с языком Haskell.

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

Язык Kotlin (kotlinlang.org) от JetBrains может показаться всего лишь подслащенной Java: синтаксические конвенции, автовывод типов (type inference) и тому подобные мелочи. Но под незамысловатой оболочкой в нем можно найти все самые популярные и прогрессивные конструкции функциональных языков.

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

В статье рассматривается

• Как такая абстракция теории категорий как инвариантный функтор (Invariant Functor), который иногда называют экпоненциальным функтором (Exponential Functor), выражается на Scala.
• Два правила (Identity Law, Composition Law), которым доложен следовать каждый инвариантный функтор.
• Приведен пример инвариантного функтора с состоянием (Value Holder)
• Приведен пример инвариантного функтора-отношения между элементами множества (полугруппа)

Публикация является продолжением FP на Scala: Что такое функтор? в которой были рассмотрены следующие вопросы

• Какая имеется связь между теорией категорий, Haskell и Scala.
• Что такое ковариантный функтор.
• Что такое контравариантный функтор.

Содержание

• Введение
• Что такое Invariant Functor
• Invariant Functor — Identity Law
• Invariant Functor — Composition Law
• Пример #1: Value Holder
• Пример #2: Полугруппа
• Инвариантный функтор в библиотеках

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

• Functional C#: Immutability
  
• Functional C#: Primitive obsession
  
• Functional C#: Non-nullable reference types
  
• Functional C#: работа с ошибками
  

Третья статья в серии «Функциональный C#».

• Functional C#: Immutability
  
• Functional C#: Primitive obsession
  
• Functional C#: Non-nullable reference types
  
• Functional C#: работа с ошибками
  

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

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

• ко-вариантный функтор
• контра-вариантный функтор

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

• Exponential (Invariant) Functor, BiFunctor, ProFunctor
• Applicative Functor, Arrow, Monad / Co-Monad
• Monad Transformers, Kleisli, Natural Transformations

Объяснено происхождение категориальной терминологии, указана роль языковых механизмов в реализации категориальных абстракций и рассмотрено несколько ковариантных (Option, Try, Future, List, Parser) и контравариантных (Ordering, Equiv) функторов из стандартной библиотеки Scala.

Первая статья в «категориальной серии»:

1. FP на Scala: что такое функтор?
2. FP на Scala: Invariant Functor

Если Вы желаете сильнее погрузиться в мир Scala, математики и функционального программирования — попробуйте онлайн-курс «Scala for Java Developers» (видео + тесты, всего за 25% цены!).

• Про языковые механизмы абстракции
• Про теорию категорий и Haskell
• Что такое ковариантный функтор
• Примеры ковариантных функторов
• Ковариантный функтор: Identity Law
• Ковариантный функтор: Composition Law
• Ковариантный функтор: используем для оптимизации
• Что такое контравариантный функтор
• Примеры контравариантных функторов
• Контравариантный функтор: Identity Law
• Контравариантный функтор: Composition Law
• Что дальше?

Это вторая статья из миницикла статей про функциональный C#.

• Functional C#: Immutability
  
• Functional C#: Primitive obsession
  
• Functional C#: Non-nullable reference types
  
• Functional C#: работа с ошибками