Что такое комбинаторы и как они применяются к программным проектам? (практическое объяснение)

Что такое комбинаторы?

Я ищу:

• практическое объяснение
• примеры того, как они используются
• примеры того, как комбинаторы улучшают качество / универсальность кода

Я не ищу:

• объяснения комбинаторов, которые не помогают мне выполнить работу (например, Y-комбинатор)

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

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

func in_sequence(first, second):
  lambda ():
    first()
    second()

Важнейшей вещью, которая делает этот комбинатор, является анонимная функция (лямбда-функция) во второй строке; когда ты звонишь

a = in_sequence(f, g)

результирующий объект a не является результатом запуска сначала f (), а затем g (), но это объект, который вы можете вызвать позже для выполнения f () и g () в последовательности:

a() // a is a callable object, i.e. a function without parameters

Таким же образом вы можете получить комбинатор, который запускает два кодовых блока параллельно:

func in_parallel(first, second):
  lambda ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    wait(t1)
    wait(t2)

И опять же,

a = in_parallel(f, g)
a()

Круто то, что 'in_parallel' и 'in_sequence' оба являются комбинаторами с одним и тем же типом / сигнатурой, т.е. они оба принимают два беспараметрических функциональных объекта и возвращают новый. На самом деле вы можете написать такие вещи, как

a = in_sequence(in_parallel(f, g), in_parallel(h, i))

и работает как положено.

По сути, комбинаторы позволяют вам строить поток управления вашей программы (среди прочего) процедурным и гибким способом. Например, если вы используете комбинатор in_parallel (..) для запуска параллелизма в вашей программе, вы можете добавить отладку, связанную с этим, к реализации самого комбинатора in_parallel. Позже, если вы подозреваете, что в вашей программе есть ошибка, связанная с параллелизмом, вы можете просто переопределить in_parallel:

in_parallel(first, second):
  in_sequence(first, second)

и одним движением все параллельные секции были преобразованы в последовательные!

Комбинаторы очень полезны при правильном использовании.

Однако Y-комбинатор не нужен в реальной жизни. Это комбинатор, который позволяет создавать саморекурсивные функции, и вы можете легко создавать их на любом современном языке без Y-комбинатора.

Неправильно называть Y-combinator чем-то, что «не поможет выполнить работу». Я нашел это очень полезным в ряде случаев. Наиболее очевидный случай - это когда вам нужно быстро загрузить некоторый встроенный интерпретируемый язык. Если вы предоставляете минимальный набор примитивов, а именно sequence, select, call, constи closure allocation, уже достаточно для построения полного, произвольный сложного языка. Никакой специальной поддержки рекурсии не требуется - ее можно добавить через комбинатор с фиксированной точкой. В противном случае вам понадобятся гораздо более сложные примитивы.

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

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

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

Немного покопавшись, я нашел вопрос StackOverflow, хорошее объяснение «Combinators» (для нематематиков), который является близким родственником этого вопроса. Один из ответов указал на блог Реджинальда Брейтуэйта «Homoiconic» , в котором приведены ссылки на несколько полезных примеров комбинаторов в коде (например, комбинатор K , реализованный методом Руби Object#tap- прочтите страницу с примерами того, почему он полезен).

Страница Wikipedia на Combinatory Logic описывает комбинаторы более глобально.