Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Стрелки

В императивных языках программирования вроде Си словом «функция» называют не совсем то, что под этим словом понимают математики. Функцией называют подпрограмму: алгоритм, принимающий какой-то набор данных фиксированных типов, совершающий некие действия и возвращающий какой-то набор данных фиксированных типов, причём производимые действия могут кроме собственно вычисления результатов иметь т.н. побочные эффекты, к которым причисляют взаимодействие со внешней средой: считывание, сохранение или вывод сохранение какой-то дополнительной информации, например.

В функциональных языках программирования действует принцип строгого отделения мух от котлет и функциями называют алгоритмически заданные функции, а для «функций с побочными эффектами» используется другое название: стрелки. На самом деле, понятие стрелки несколько общее: оно включает не только подпрограммы, но в вообще любые data processing circuits.

Функции «живут» в категории Func, где объекты — типы данных, а переходы — как раз таки алгоритмически заданные функции, вычисляющие из одних данных другие.

Стрелки «живут» в категориях стрелок. Характер побочных эффектов бывает разный, поэтому для детализированного подхода нам понадобятся много разных категорий. Например если кроме проведения вычислений допускается только выводить какую-то информацию в лог, то это будут т.н. LogWriter-стрелки. Если допускается записывать и считывать набор переменных s, то это будут State(s)-стрелки; cчитывание из базы данных или потокового устройства — Reader(db)-стрелки; доступ к базе данных или устройству аналогичного интерфейса — Accessor(db), взаимодействие со стандартными устройствами ввода вывода — IO-стрелки и т.д. Всё это может комбинироваться, поверх указанных типов можно допустить Suspended/OutOfOrder-execution, это будут например Cont(IO|Accessor(db)|Throws(exceptionList))-стрелки. Однако у всех категорий стрелок есть кое-что общее. Объектами категории стрелок являются типы данных, оснащённые «контейнером», несущим всю информацию, доступную через побочные эффекты, равно как информацию о свершившихся побочных эффектах. В случае LogWriter-стрелок, функции «на самом деле» помимо основного результата всякий раз выдают, что они написали в лог, а при композиции Logwriter-стрелок f: A -> B(× LogOutput) и g: B -> C(× LogOutput) выполняется не только комопзиция функций f'∘g': A -> C, но и конкатенация произведённых стрелками записей в журнал.

Функция без побочных эффектов является частным случаем функции с таковыми, так что категория Func должна иметь естественное вложение в каждую категорию стрелок. То есть, для каждой категории стрелок ArrowsX должен быть задан функтор lift, «поднимающий» типы и функции из Func в ArrowsX. Внимание, этот функтор (в отличие от привычных функциональщикам эндофункторов в Func) не является автоматически моноидальным и никак не сообщает нам, как поднимать элементы, только сами типы. Если стрелку снабдить совместимым с остальной структурой поднятием элементов, то такая стрелка называется аппликабельной.)


Вторую особенность категории стрелок объяснить чуть сложнее. В категории Datatypes есть естественная операция A×B, делающая из двух типов A и B новый тип «пара A и B», и ⊗, делающая из двух функций f: A -> B и g: С -> D спаренную функцию f×g: A×B -> C×D. Операция, превращающая f в f×(Id) называется alongside. Она берёт одноаргументную функцию f: A -> B, а возвращает двуаргументную функцию f×(Id): A×T -> C×T, которая второй аргумент просто пропускает нетронутым. Так вот от категории стрелок требуется, чтобы там тоже была задан эндофунктор alongside, выполняющий набор всяких естественных аксиом. Эндофунктор alongside необходим (и достаточен) для того, чтобы вкупе с операцией swap: (a, b) -> (b, a) можно было сплетать поднятые функции любыми способами.


(В Хаскелле lift называется arr, а alongside first по историческим причинам.)

Категория стрелок полностью задаётся своей операцией композиции, функтором lift из Datatypes и эндофунктором alongside. Все остальные операции являются специфичными для каждой конкретной категории: appendLogLine для LogWriter-стрелок, get(var) и set(var, value) для State(var)-стрелок, и так далее. Комбинируя lift, alongside и спецефические опереции-побочные действия можно получить точные аналоги любых императивных программ, с тем, однако, преимуществом, что разные аспекты побочных действий разделены, а законы оперирования порядком действий точно известны, что позволяет (а) гораздо более филигранно оптимизировать код при компиляции и (б) выявлять возможные баги и race conditions на этапе компиляции.

Многие встречающиеся в народном хозяйстве категории стрелок аппликабельные, в каком случае они эквивалентны по выразительности монадам (они являются категориями Клейсли соответствующих монад). Программа написанная на языке таких стрелок может быть переведена в «алгоритм» последовательного выполнения без потери общности.
Многие другие категории стрелок коаппликативны, в этом случае они эквивалентны комонадам и на их языке выражаются stream processors.
Однако в результате комбинирования монадных (напр. exceptions) и комонадных (напр. listener) побочных эффектов получаются нетривиальные виды стрелок. На их языке можно писать программы принципиально новой архитектуры. Например, бипарсеры.

Спорадические случаи
Как нередко случается в теории категорий, под определение категорий стрелок подходят многие объекты, о которых изначально никто не задумывался. Основные примеры идут ещё из случая монад. Каждый контейнерный тип с одним параметром (Maybe a, Set a, List a, ...) канонически является по совместительству монадой. Контейнерные типы с несколькими параметрами (навроде Either a b) являются монадами неканонически, однако канонически порождают категории стрелок.
Subscribe

Recent Posts from This Journal

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments