Стрелка (информатика) - Arrow (computer science)

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

Мотивация и история

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

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

Отношение к теории категорий

В теории категорий , в категории Клейла все монады образуют собственное подмножество стрелка Hughes. Хотя какое-то время считалось, что категории Фрейда эквивалентны стрелам, с тех пор было доказано, что стрелки носят еще более общий характер. Фактически, стрелки не просто эквивалентны, но прямо равны обогащенным категориям Фрейда.

Определение

Как и все классы типов, стрелки можно рассматривать как набор качеств, которые можно применить к любому типу данных . В языке программирования Haskell стрелки позволяют функциям (представленным в Haskell ->символом) объединяться в овеществленную форму. Однако фактический термин «стрела» может также происходить из-за того, что некоторые (но не все) стрелки соответствуют морфизмам (также известным как «стрелки» в теории категорий) различных категорий Клейсли. Это относительно новая концепция, не имеющая единого стандартного определения, но все формулировки логически эквивалентны, содержат некоторые требуемые методы и строго подчиняются определенным математическим законам.

Функции

Описание, используемое в настоящее время стандартными библиотеками Haskell, требует всего трех основных операций:

  • Конструктор типа обр , который принимает функцию -> от любого типа S к другому т , и поднимает эти функции в виде стрелки А между этими двумя типами.
arr (s -> t)        ->   A s t
  • Сначала метод конвейера, который принимает стрелку между двумя типами и преобразует ее в стрелку между кортежами . Первые элементы в кортежах представляют изменяемую часть ввода и вывода, в то время как вторые элементы представляют собой третий тип u, описывающий неизмененную часть, которая обходит вычисления.
first (A s t)       ->   A (s,u) (t,u)
  • Поскольку все стрелки должны быть категориями , они наследуют третью операцию из класса категорий: оператор композиции >>>, который может присоединять вторую стрелку к первой, если выходные данные первой функции и входные данные второй имеют совпадающие типы.
A s t  >>>  A t u   ->   A s u

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

Еще один полезный метод может быть получен из arr и first (и из которого может быть получен first ):

  • Оператор слияния ***, который берет две стрелки, возможно, с разными типами ввода и вывода, и объединяет их в одну стрелку между двумя составными типами. Оператор слияния не обязательно коммутативен .
A s t  ***  A u v   ->   A (s,u) (t,v)

Законы стрел

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

  • Стрелки всегда должны сохранять идентификаторы идентификаторов всех типов (по сути, определения всех значений для всех типов в категории).
arr id              ==   id
  • При соединении двух функций f и g требуемые стрелочные операции должны распределяться по композициям слева.
arr (f >>> g)       ==   arr f  >>>  arr g
first (f >>> g)     ==   first f  >>>  first g
  • Согласно предыдущим законам, трубопровод может применяться непосредственно к функциям, потому что порядок не должен иметь значения, когда трубопровод и подъем выполняются вместе.
arr (first f)       ==   first (arr f)

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

  • Если идентичность объединяется со второй функцией, чтобы сформировать стрелку, присоединение ее к конвейерной функции должно быть коммутативным.
arr (id *** g)  >>>  first f       ==   first f  >>>  arr (id *** g)
  • Передача функции по конвейеру до упрощения типа должна быть эквивалентна упрощению типа перед подключением к функции без конвейера.
first f  >>>  arr ((s,t) -> s)     ==   arr ((s,t) -> s)  >>>  f
  • Наконец, соединение функции дважды перед повторным связыванием результирующего кортежа, которое является вложенным, должно быть таким же, как повторное связывание вложенного кортежа перед присоединением одного обхода функции. Другими словами, сложенные байпасы можно сгладить, сначала связав вместе эти элементы, не измененные функцией.
first (first f)  >>>  arr ( ((s,t),u) -> (s,(t,u)) )   ==
  arr ( ((s,t),u) -> (s,(t,u)) )  >>>  first f

Приложения

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

Полезность

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

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

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

Ограничения

Из-за необходимости определения arrфункции для поднятия чистых функций применение стрелок ограничено. Например, двунаправленные преобразования не могут быть стрелками, потому что при использовании потребуется предоставить не только чистую функцию, но и ее обратную arr. Это также ограничивает использование стрелок для описания реактивных фреймворков на основе push, которые останавливают ненужное распространение. Точно так же использование пар для объединения значений в кортеж приводит к сложному стилю кодирования, требующему дополнительных комбинаторов для повторной группировки значений, и поднимает фундаментальные вопросы об эквивалентности стрелок, сгруппированных по-разному. Эти ограничения остаются открытой проблемой, и такие расширения, как Generalized Arrows и N-ary FRP, исследуют эти проблемы.

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

Рекомендации

Внешние ссылки