Добавление эффектов и составление аппликаций

Это заключительная часть серии статей об эффективном программировании с помощью аппликативных функторов. В последних двух постах мы рассмотрели, что такое вычислительные эффекты и как мы можем использовать их в сочетании с аппликативными функторами для захвата побочных эффектов в функциональном коде. В первой части мы сделали это для реализации компонуемых парсеров; во второй части мы реализовали общий аппликатив, представляющий эффект чтения из среды, и использовали его для реализации вычислителя для AST, представляющего арифметические выражения. (Если вы не читали эти посты, я рекомендую сделать это, прежде чем переходить к этому.)

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

Изменение состояния

Теперь, когда наша функция evaluate поддерживает переменные, давайте сделаем еще один шаг и добавим возможность изменять значение переменных в некоторой области. Это позволит нам вычислять такие выражения, как (let x 1 (+ x 2)), которое присваивает значение 1 x и дает 3. Как и раньше, мы добавим новый тип данных к нашему типу Expr:

type Expr
  = Num
  | Plus
  | Times
  | Var
  | Let
  ;
class Let {
  name: string;
  value: number;
  scope: Expr;
  constructor(name: string, value: number, scope: Expr) {
    this.name = name;
    this.value = value;
    this.scope = scope;
  }
}

Добавить поддержку Let в нашу функцию evaluate так же просто, как и для Var: мы просто добавляем еще одну запись в условное выражение. В этом случае мы выгрузим логику в функцию alias, которую мы еще не написали:

function evaluate(expr: Expr) : InEnv<string, number, number> {
  return expr instanceof Num ? 
    pure(expr.value)
  : expr instanceof Plus ?
    plus(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Times ?
    times(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Var ?
    fetch(expr)
  : /* expr is a Let */
    alias(expr.name, expr.value, evaluate(expr.scope));
  }

Обратите внимание, что внутри случая Let мы рекурсивно оцениваем область, содержащуюся в блоке let, а затем передаем результаты этой оценки в alias. Если бы мы реализовали evaluate, пропустив среду вручную (как мы сделали в нашей наивной реализации в предыдущем разделе), то нам нужно было бы сначала изменить среду, а затем передать измененную среду в evaluate. Подход, который мы здесь используем, можно рассматривать как «оценку внутренней области видимости, получение значения в контексте InEnv, а затем добавление эффекта изменения состояния в этот контекст». Чтобы смоделировать изменяющееся состояние, alias вернет функцию, которая берет среду, изменяет эту среду, а затем передает эту среду в функцию InEnv, которую alias обертывает. Как обычно, мы выполним эту модификацию, скопировав ввод и изменив копию:

function alias<X, Y, A>(
  name: X, 
  value: Y, 
  contents: InEnv<X, Y, A>) : InEnv<X, Y, A> {
  return env => {
    const newEnvContents = new Map(env.contents);
    newEnvContents.set(name, value);
    return contents(new Env(newEnvContents));
  };
}

При этом мы можем увидеть наше решение в действии:

const env = new Env(new Map([
  ["foo", 2],
  ["bar", 3]
]));
// (+ foo (let bar 5 (+ 1 (* 4 bar))))
const expr = new Plus(
  new Var("foo"),
  new Let(
    "bar", 5,
    new Plus(
      new Num(1),
      new Times(
        new Num(4),
        new Var("bar")))));
console.log(evaluate(expr)(env)); // 23

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

Работа с неудачей путем составления различных аппликативов

Помните это?

if (!env.contents.has(name))
  throw new Error("Referenced an undefined variable!");

Плохо.

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

Мы сделаем это, сказав, что любое вычисление в аппликативе InEnv может завершиться ошибкой. Это легко выразить, немного изменив наши типы:

type InEnv<X, Y, A> = Env<X, Y> => A;

превращается в

type InMaybeEnv<X, Y, A> = InEnv<X, Y, Maybe<A>>;

В моем первом посте об аппликативах я упомянул, что состав аппликативов всегда аппликативен. Если у нас есть аппликативы F<A> и G<A>, то мы можем механически создать функции map, ap и pure для F<G<A>>:

type FG<A> = F<G<A>>
function mapFG<A, B>(fn: A => B, a: FG<A>) : FG<B> {
  return mapF(x => mapG(fn, x), a);
}
function pureFG<A>(a: A) : FG<A> {
  return pureF(pureG(a));
}
function ap<A, B>(fn: FG<A => B>, a: FG<A>) : FG<B> {
  return liftA2F(curry2(apG))(fn, a)
}

В нашем случае мы можем импортировать функции map, ap и pure каждого аппликатива как объекты inEnv и maybe и сделать наш новый составной тип аппликативом следующим образом:

function map<X, Y, A, B>(
  fn: A => B,
  a: InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, B> {
  return inEnv.map(x => maybe.map(fn, x), a);
}
function pure<X, Y, A>(a: A) : InMaybeEnv<X, Y, A> {
  return inEnv.pure(maybe.pure(a));
}
function ap<X, Y, A, B>(
  fn: InMaybeEnv<X, Y, A => B>,
  a: InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, B> {
  return inEnv.liftA2(curry2(maybe.ap))(fn, a)
}

(Опять же, нам нужно определить их только вручную из-за ограничений в системе типов Flow. Используя правильные обходные пути, мы можем написать функцию composeA, которая принимает inEnv и maybe в качестве аргументов и возвращает объект, содержащий map, ap и pure определены для типа InMaybeEnv.)

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

function fetch<X, Y>(name: X) : InMaybeEnv<X, Y, Y> {
  return env => env.contents.has(name) ?
    new Just((env.contents.get(name) : any)) :
    null;
}

Каждый раз, когда мы изменяем структуру аппликации, нам нужно проверять каждую из функций, которые касаются внутренней структуры этого аппликации, на предмет поломки. Мы обновили of и fetch, но в этом случае alias по-прежнему будет работать для нашего вложенного случая без изменений.

Аппликативный контекст отделяет нашу конкретную логику приложения от общей логики эффекта, поэтому для evaluate не требуется никаких изменений, кроме обновления его сигнатуры типа:

function evaluate(expr: Expr) : InMaybeEnv<string, number, number> {
  return expr instanceof Num ? 
    pure(expr.value)
  : expr instanceof Plus ?
    plus(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Times ?
    times(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Var ?
    fetch(expr)
  : /* expr is a Let */
    alias(expr.name, expr.value, evaluate(expr.scope));
  }

Поскольку plus и times определяются в терминах liftA2, который определяется в терминах map и ap, наш код, который объединяет InMaybeExprs, будет соответствующим образом реагировать на влияние приложения Maybe и приведет к сбою всего вычисления, если сбой произойдет в какой-либо части. из них:

const env = new Env(new Map());
// (+ 1 (* foo 2))
const expr = new Plus(
  new Num(1),
  new Times(
    new Var("foo"),
    new Num(2)))
console.log(evaluate(expr2)(env2)); // null

Гораздо лучше, чем выдавать ошибку, и с минимумом дополнительного кода.

Что нам дали аппликации?

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

Наша функция evaluate имеет пять случаев, которые делятся на две отдельные группы:

  1. Дела Plus и Times. Эти функции, вызываемые в этих случаях, производятся с использованием liftA для функций, которые объединяют простые значения, создавая функции, которые объединяют значения внутри аппликативных контекстов.
  2. Дела Num, Var и Let. Эти случаи создают аппликативы, вызывая специальные функции, определенные для InEnv или InMaybeEnv аппликатива. Случай Var вызывает fetch, который обеспечивает эффект состояния чтения, а случай Let вызывает alias, который обеспечивает эффект изменения состояния. Случай Num вызывает pure, который создает значение и «пустой» эффект.

Это строительные блоки аппликативного кода. Функторы InEnv и InMaybEnv обеспечивают контекст, в котором могут существовать эффекты, а функции, которые работают с внутренней структурой этих функторов, создают эффекты. Чтобы узнать, какие эффекты присутствуют или возможны в данном функторе, нам нужно только посмотреть, какие функции, создающие эффекты, доступны. Чтобы делать полезные вещи со значениями внутри нашего эффективного контекста, мы используем liftA для переноса функций обернутых типов в наш контекст. «Магия» аппликативов заключается в том, что независимо от того, какие эффекты обеспечивают наши функции, создающие эффекты, наши поднятые функции смогут составить эти эффекты. (Пока наши реализации map, ap и pure следуют законам функтора.)

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

pure<X, Y, A>(A) : InMaybeEnv<X, Y, A>
fetch<X, Y>(X) : InMaybeEnv<X, Y, Y>
alias<X, Y, A>(X, Y, InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, A>

Поскольку в сигнатурах этих функций нет конкретных типов, их логика не может быть связана с каким-либо конкретным типом. В функциональном программировании эта концепция известна как «параметричность»: гарантия того, что функция, все типы которой являются параметрами типов (обобщенные), будет вести себя одинаково при заданных аргументах любого типа. Когда я прокомментировал в последнем посте, что существует только одна реализация map, ap и pure для InEnv, которая будет проверять тип, причиной этого была параметричность. Есть только один способ поведения этих функций, если они собираются работать со всеми типами, которые им могут быть заданы, и средство проверки типов обеспечивает его соблюдение.

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

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

Чтобы получить менее математическое представление об этом, мы можем просто сравнить наш окончательный код (поддерживающий Var и Let) с нашим исходным кодом без эффектов. Код выглядит так же — никаких дополнительных значений, никаких новых замыканий или изменяемого состояния. Переместившись в аппликативный контекст, мы получили возможность работать с эффектами, просто применяя функции к значениям, точно так же, как мы работаем с чистыми данными без эффектов. Мы также знаем, что мы разделены, потому что, когда мы изменили наш аппликатив InEnv, составив его с аппликативом Maybe, функцию evaluate, которая была написана в терминах InEnv, не нужно было изменять; наши изменения были ограничены функциями создания эффектов, которые воздействовали на внутреннюю структуру InEnv.

На этом мы заканчиваем наш сегодняшний тур по аппликативным функторам. Это был долгий и напряженный путь, поэтому вот краткое изложение основных моментов, которые мы уже видели:

  • Функторы предоставляют контекст, который может содержать значения, и функцию map для применения обычных функций к функциям в значениях. map можно каррировать, чтобы преобразовать функции с одним аргументом над простыми значениями в функции над значениями в контекстах.
  • Аппликативные функторы добавляют к функторам дополнительные функции и ограничения. Аппликатив дает нам функцию pure, которая может преобразовать значение любого типа в функтор, и функцию ap, которая позволяет нам применять функции в контексте к значениям в контексте.
  • Используя ap и map, мы можем определить liftA, который поднимает функции с несколькими аргументами для простых значений до функций для значений в контексте.
  • Реализации map, ap и pure должны следовать определенным законам. Эти законы гарантируют, что то, что мы строим на основе аппликативов, будет составлено ожидаемым образом.
  • Чисто функциональные вычисления возвращают значения. Однако иногда вычисление может возвращать значение плюс что-то еще. Эта дополнительная вещь называется «вычислительным эффектом». Мы можем создавать структуры данных, которые представляют эти эффекты.
  • В программном обеспечении «побочные эффекты» — это чтение или изменение состояния в контексте, который находится за пределами нашего текущего программного компонента. Если мы сможем инкапсулировать это состояние внутри компонента и неизменяемо представлять его модификации, то мы сможем превратить побочный эффект в корректный вычислительный эффект.
  • Когда мы инкапсулируем вычислительный эффект внутри аппликативного функтора, тогда функции, поднятые с помощью liftA, автоматически составят эти эффекты.
  • Для эффективного аппликативного программирования мы пишем функции создания эффектов, которые возвращают экземпляр аппликации, содержащей нужный нам эффект. Наш эффективный код работает с выводом этих функций и никогда напрямую не затрагивает внутреннюю структуру нашего аппликативного контекста.
  • Концепция «параметричности» говорит нам, что универсальные функции гарантированно отделены от конкретных типов. Поскольку все наши функции создания эффектов являются общими, это дает нам математическую гарантию того, что мы отделили наши заботы о реализации эффектов от забот об их использовании.
  • Поскольку композиция аппликативов сама по себе является аппликативом, мы можем составлять аппликативы для добавления дополнительных эффектов. При этом нам может понадобиться изменить наши функции создания эффектов, но наш код, написанный в терминах аппликации, останется неизменным.

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

Все примеры кода из этого поста можно найти здесь.

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

Спасибо Лизз Катснельсон за редактирование этого сообщения.