Стрелка (информатика)

В информатике используемый стрелки или болты — это класс типов, в программировании для описания вычислений в чистом и декларативном виде. Стрелки, впервые предложенные ученым-компьютерщиком Джоном Хьюзом как обобщение монад , обеспечивают ссылочно прозрачный способ выражения отношений между логическими шагами вычислений. ^[1] В отличие от монад, стрелки не ограничивают шаги одним и только одним входом. В результате они нашли применение в функциональном реактивном программировании , бесточечном программировании и синтаксических анализаторах среди других приложений. ^[1]^[2]

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

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

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

Связь с теорией категорий

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

Определение

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

Функции

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

Конструктор типа arr, который принимает функции -> из любого типа s другому t и превращает эти функции в стрелку Между этими двумя типами. ^[7]

arr : (s -> t) -> A s t

Метод трубопровода сначала берется стрелка между двумя типами и преобразуется в стрелку между кортежами . Первые элементы в кортежах представляют собой измененную часть ввода и вывода, а вторые элементы относятся к третьему типу. u описывает неизмененную часть, которая обходит вычисления. ^[7]

first : A s t -> A (s,u) (t,u)

Поскольку все стрелки должны быть категориями , они наследуют третью операцию из класса категорий: композиции . оператор >>> это может присоединить вторую стрелку к первой, если выходные данные первой функции и входные данные второй имеют совпадающие типы. ^[7]

(>>>) : A s t -> A t u -> A s u

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

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

Оператор слияния *** , который берет две стрелки, возможно, с разными типами ввода и вывода, и объединяет их в одну стрелку между двумя составными типами. Оператор слияния не обязательно является коммутативным . ^[7]

(***) : A s t -> A u v -> A (s,u) (t,v)

Законы стрелок

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

всех типов. Стрелки всегда должны сохранять идентичность id (по сути, определения всех значений для всех типов в категории). ^[7]

arr id              ==   id

При соединении двух функций е & g , необходимые операции со стрелками должны распределяться по композициям слева. ^[7]

arr (f >>> g)       ==   arr f  >>>  arr g
first (f >>> g)     ==   first f  >>>  first g

В предыдущих законах трубопроводы можно было применять непосредственно к функциям, поскольку порядок не имеет значения, когда трубопроводы и подъем выполняются вместе. ^[7]

arr (first f)       ==   first (arr f)

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

Если идентификатор объединяется со второй функцией для формирования стрелки, присоединение его к конвейерной функции должно быть коммутативным. ^[7]

arr (id *** g)  >>>  first f       ==   first f  >>>  arr (id *** g)

Конвейерная передача функции перед упрощением типа должна быть эквивалентна упрощению типа перед подключением к неконвейерной функции. ^[7]

first f  >>>  arr ((s,t) -> s)     ==   arr ((s,t) -> s)  >>>  f

Наконец, двойная передача функции по конвейеру перед повторным связыванием результирующего кортежа, который является вложенным, должна быть такой же, как и повторное связывание вложенного кортежа перед присоединением одного обхода функции. Другими словами, составные обходы можно сгладить, сначала объединив вместе те элементы, которые не были изменены функцией. ^[7]

first (first f)  >>>  arr ( ((s,t),u) -> (s,(t,u)) )   ==
  arr ( ((s,t),u) -> (s,(t,u)) )  >>>  first f

Приложения

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

Утилита

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

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

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

Ограничения

В связи с необходимостью определения arr функция для поднятия чистых функций, применимость стрелок ограничена. Например, двунаправленные преобразования не могут быть стрелками, поскольку при использовании arr. ^[8] Это также ограничивает использование стрелок для описания реактивных фреймворков на основе push, которые останавливают ненужное распространение. Аналогичным образом, использование пар для объединения значений в кортеж приводит к сложному стилю кодирования, который требует дополнительных комбинаторов для перегруппировки значений и поднимает фундаментальные вопросы об эквивалентности стрелок, сгруппированных по-разному. Эти ограничения остаются открытой проблемой, и такие расширения, как Generalized Arrows, ^[8] и N-арный FRP ^[9] изучить эти проблемы.

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Хьюз, Джон (май 2000 г.). «Обобщение монад до стрел». Наука компьютерного программирования . 37 (1–3): 67–111. дои : 10.1016/S0167-6423(99)00023-4 . ISSN 0167-6423 .
^ Патерсон, Росс (27 марта 2003 г.). «Глава 10: Стрелки и вычисления» (ПС.ГЗ) . В Гиббонсе, Джереми; де Мур, Оге (ред.). Удовольствие от программирования . Пэлгрейв Макмиллан. стр. 201–222. ISBN 978-1403907721 . Проверено 10 июня 2012 г.
^ Линдли, Сэм; Уодлер, Филип; Яллоп, Джереми (январь 2010 г.). «Стрелочное исчисление» (PDF) . Журнал функционального программирования . 20 (1): 51–69. дои : 10.1017/S095679680999027X . hdl : 1842/3716 . ISSN 0956-7968 . S2CID 7387691 . Проверено 10 июня 2012 г.
^ Джейкобс, Барт; Хойнен, Крис; Хасуо, Ичиро (2009). «Категорическая семантика стрелок». Журнал функционального программирования . 19 (3–4): 403–438. дои : 10.1017/S0956796809007308 . hdl : 2066/75278 .
^ Атки, Роберт (8 марта 2011 г.). «Что такое категориальная модель стрел?» . Электронные заметки по теоретической информатике . 229 (5): 19–37. дои : 10.1016/j.entcs.2011.02.014 . ISSN 1571-0661 .
^ Jump up to: ^а ^б ^с ^д ^и Хьюз, Джон (2005). «Программирование со стрелками» (PDF) . Расширенное функциональное программирование . 5-я Международная летняя школа по продвинутому функциональному программированию. 14–21 августа 2004 г. Тарту, Эстония. Спрингер. стр. 73–129. дои : 10.1007/11546382_2 . ISBN 978-3-540-28540-3 . Проверено 10 июня 2012 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Патерсон, Росс (2002). «Управление.Стрелка» . base-4.5.0.0: Базовые библиотеки . Haskell.org. Архивировано из оригинала 13 февраля 2006 года . Проверено 10 июня 2012 г.
^ Jump up to: ^а ^б Джозеф, Адам Мегач (2014). «Обобщенные стрелки» (PDF) . Технический отчет № UCB/EECS-2014-130 . Департамент EECS, Калифорнийский университет, Беркли . Проверено 20 октября 2018 г.
^ Скалторп, Нил (2011). На пути к безопасному и эффективному функциональному реактивному программированию (PDF) (доктор философии). Университет Ноттингема.

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

Стрелки: общий интерфейс вычислений
Новое обозначение стрелок , Росс Патерсон, в ICFP, сентябрь 2001 г.
Обозначение стрелок: руководство по ghc

[Hughes98-1] Jump up to: ^а ^б ^с ^д ^и Хьюз, Джон (май 2000 г.). «Обобщение монад до стрел». Наука компьютерного программирования . 37 (1–3): 67–111. дои : 10.1016/S0167-6423(99)00023-4 . ISSN 0167-6423 .

[Paterson03-2] Патерсон, Росс (27 марта 2003 г.). «Глава 10: Стрелки и вычисления» (ПС.ГЗ) . В Гиббонсе, Джереми; де Мур, Оге (ред.). Удовольствие от программирования . Пэлгрейв Макмиллан. стр. 201–222. ISBN 978-1403907721 . Проверено 10 июня 2012 г.

[Lindley10-3] Линдли, Сэм; Уодлер, Филип; Яллоп, Джереми (январь 2010 г.). «Стрелочное исчисление» (PDF) . Журнал функционального программирования . 20 (1): 51–69. дои : 10.1017/S095679680999027X . hdl : 1842/3716 . ISSN 0956-7968 . S2CID 7387691 . Проверено 10 июня 2012 г.

[4] Джейкобс, Барт; Хойнен, Крис; Хасуо, Ичиро (2009). «Категорическая семантика стрелок». Журнал функционального программирования . 19 (3–4): 403–438. дои : 10.1017/S0956796809007308 . hdl : 2066/75278 .

[Atkey11-5] Атки, Роберт (8 марта 2011 г.). «Что такое категориальная модель стрел?» . Электронные заметки по теоретической информатике . 229 (5): 19–37. дои : 10.1016/j.entcs.2011.02.014 . ISSN 1571-0661 .

[Hughes05-6] Jump up to: ^а ^б ^с ^д ^и Хьюз, Джон (2005). «Программирование со стрелками» (PDF) . Расширенное функциональное программирование . 5-я Международная летняя школа по продвинутому функциональному программированию. 14–21 августа 2004 г. Тарту, Эстония. Спрингер. стр. 73–129. дои : 10.1007/11546382_2 . ISBN 978-3-540-28540-3 . Проверено 10 июня 2012 г.

[HaskArrows-7] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Патерсон, Росс (2002). «Управление.Стрелка» . base-4.5.0.0: Базовые библиотеки . Haskell.org. Архивировано из оригинала 13 февраля 2006 года . Проверено 10 июня 2012 г.

[Megacz14-8] Jump up to: ^а ^б Джозеф, Адам Мегач (2014). «Обобщенные стрелки» (PDF) . Технический отчет № UCB/EECS-2014-130 . Департамент EECS, Калифорнийский университет, Беркли . Проверено 20 октября 2018 г.

[Sculthorpe11-9] Скалторп, Нил (2011). На пути к безопасному и эффективному функциональному реактивному программированию (PDF) (доктор философии). Университет Ноттингема.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]