Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Всё, дошло

Всё, дошло про эффекты алгебраические и коалгебраические.

Пусть есть полиморфная по эффектам функция f : {X -> Y}, и мы строим цепочку композиций

... ∘ b ∘ a ∘ f ∘ x ∘ y ∘ ...

Алгебраические эффекты это то, что поднимается по цепочке композиций вверх (то есть налево), коалгебраические — то, что прокидывается вниз.

В качестве примера алгебраического эффекта можно взять @Throws(E). Если наша функция это использует, значит что мы требуем от кого-то из caller'ов (т.е. a, или b, или может c, но на каком-то конечном уровне обязательно) хэндлер throws(e).

В качестве примера коалгебраического эффекта можно взять _@Clonable, это значит что мы требуем от нашего аргумента X, чтобы для него была задана операция clone: X -> (X, X), но не обязательно прямо: можно, чтобы для типа X и функции x : PreX -> X этого не было, но было для функции y: PrePreX -> PreX, тогда мы можем склонировать на том уровне, и применить y к каждому из результатов; можно, чтобы это было задано на ещё более далёком уровне, но где-то конечно далеко было.

Эффектные аннотации без проблем взаимодействуют с зависимыми типами, коэффектные аннотации требуют чтобы всё, от чего зависит аннотированный тип/терм, тоже было аннотировано аналогично.

Модальности удобно описывать при помощи эффектов (алгебраических, разумеется), это позволяет органично включить расширяющие логику операции в синтаксис, избегая do-нотации. Комодальности же как раз описываются при помощи коэффектов. Как описывать коэффекты алгебраически? Это мы описываем на типах какую-то структуру вместе с описанием, как она прокидывается по ним контравариантно...

Очень клёв пример пространственной гомотопической теории типов. Там задаются классическая модальность ♯, и классическая комодальность ♭.
Классическая модальность это алгебраический эффект “спросить внешнего оракула про любое утверждение P, истино оно или ложно”.
Классическая комодальность это коалгебраический эффект “потребовать, чтобы аргумент t : T шёл вместе с оракулом, умеющим отвечать на любые вопросы про его свойства P : T -> Prop”.
Subscribe

  • (без темы)

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

  • Прогресс

    Десять дней назад, вторая ступень 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.
  • 6 comments