Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Stackless Scala

Перевод статьи Runar Oli Bjarnason "Stackless Scala With Free Monads" с небольшими отступлениями.

Для понимания

Исключение абстрактного хвостового вызова (Tail call elimination - TCE) в компиляторе Scala ограничено саморекурсивными методами, но в остальном хвостовые вызовы не исключаются. Это делает функции, состоящие из множества более мелких функций, склонными к переполнению стека. Наличие общего механизма TCE было бы большим преимуществом в Scala, особенно для функционального программирования. Трамплининг — популярный метод, который можно использовать для TCE в языках, изначально его не поддерживающих. В этой статье дается введение в "батуты" в Scala и расширяется это решение, позволяющее устранить любой вызов метода, даже вызов, который вообще не находится в хвостовой позиции. Это полностью исключает использование стека вызовов в программах Scala.

1. Введение

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

case class State[S, +A](runS: S => (A, S)):
  def map[B](f: A => B): State[S, B] =
    State[S, B] { s =>
      val (a, s1) = runS(s)
      (f(a), s1)
    }

  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State[S, B] { s =>
      val (a, s1) = runS(s)
      f(a).runS(s1)
    }

Функция runS принимает некоторое входящее состояние типа S и выводит значение типа A вместе с новым состоянием. Методы map и flatMap позволяют нам передавать состояние через for-comprehension, чтобы писать кажущиеся императивными программы, использующие комбинаторы State, такие как:

def getState[S]: State[S, S] =
  State(s => (s, s))

def setState[S](s: S): State[S, Unit] =
  State(_ => ((), s))

def pureState[S, A](a: A): State[S, A] =
  State(s => (a, s))

Обратите внимание, что pureState и flatMap вместе составляют State монаду.

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

def zipIndex[A](as: List[A]): List[(Int, A)] =
  as.foldLeft(pureState[Int, List[(Int, A)]](List())) { (acc, a) =>
    for {
      xs <- acc
      n  <- getState
      _  <- setState(n + 1)
    } yield (n, a) :: xs
  }.runS(0)
    ._1
    .reverse
@main def runStateZipIndex(): Unit =
  import State.*
  val list = zipIndex[String](List.fill(10000)("el"))
  println("zipped list = " + list) // java.lang.StackOverflowError

Мы используем fold left, чтобы подчеркнуть, что обход списка является хвостовой рекурсией. Fold создает действие состояния, которое начинается с пустого списка и добавляет последовательные элементы в начало, переворачивая исходный список. Состояние — это целое число, которое на каждом шаге увеличивается, и всё действие составного состояния запускается, начиная с нуля, прежде чем вернуть перевернутый результат.

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

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

2. Предыстория: устранение хвостовых вызовов в Scala

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

def foldl[A, B](as: List[A], b: B, f: (B, A) => B): B =
  as match
    case Nil     => b
    case x :: xs => foldl(xs, f(b, x), f)

Когда компилятор обнаруживает, что метод вызывает себя в хвостовой позиции, и если этот метод не может быть переопределен (например, из-за того, что он объявлен private или final), рекурсивный вызов метода заменяется простым переходом в скомпилированном коде. Это эквивалентно переписыванию хвостовой рекурсии в виде цикла:

def foldl[A, B](as: List[A], b: B, f: (B, A) => B): B =
  var z  = b
  var az = as
  while (true)
    az match
      case Nil => return z
      case x :: xs =>
        z = f(z, x)
        az = xs
  z

Этот тип оптимизации имеет два преимущества: переход намного быстрее, чем вызов метода, и он не требует места в стеке.

Но в то время как оптимизировать саморекурсивные вызовы легко, замена хвостовых вызовов переходами в целом является более сложной задачей. В настоящее время (статья написана в 2012) виртуальная машина Java (JVM) допускает только локальные переходы, поэтому нет возможности напрямую реализовать хвостовой вызов другого метода в качестве перехода. Например, эта взаимная рекурсия не может быть оптимизирована компилятором, даже если вызовы находятся в хвостовой позиции:

def even[A](ns: List[A]): Boolean =
  ns match
    case Nil     => true
    case _ :: xs => odd(xs)

def odd[A](ns: List[A]): Boolean =
  ns match
    case Nil     => false
    case _ :: xs => even(xs)

Эти функции переполнят стек вызовов, если размер List больше размера стека.

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

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

3. Батуты: обмен стека на кучу

Мы начнем с очень простого типа данных Trampoline. Он идентичен по духу, но отличается по реализации от scala.util.control.TailCalls.TailRec.

sealed trait Trampoline[+A]: 
  self =>
  
  @annotation.tailrec
  final def runT: A =
    self match 
      case More(k) => k().runT
      case Done(v) => v

case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
case class Done[+A](result: A)              extends Trampoline[A]

Trampoline представляет собой пошаговое вычисление, и каждый шаг может иметь только одну из двух форм. Шаг Done(v) возвращает значение v, и в этом случае больше шагов нет. У шага More(k) больше работы: k — это замыкание, которое выполняет некоторую работу и возвращает следующий шаг. Метод runT — это простой метод хвостовой рекурсии, который выполняет все шаги. Он объявлен final, чтобы Scala могла исключить хвостовой вызов.

Это решает проблему взаимной рекурсии, показанную ранее. Все, что нужно сделать, это механически заменить любой возвращаемый тип T на Trampoline[T]. Вот odd и even, измененные таким образом:

def even[A](ns: List[A]): Trampoline[Boolean] =
  ns match
    case Nil     => Done(true)
    case _ :: xs => More(() => odd(xs))

def odd[A](ns: List[A]): Trampoline[Boolean] =
  ns match
    case Nil     => Done(false)
    case _ :: xs => More(() => even(xs))

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

val list = List.fill(100000)(0)
even(list).runT
// true

4. Превращение каждого вызова в хвостовой вызов

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

case class State[S, +A](runS: S => Trampoline[(A, S)])

Как теперь реализовать метод flatMap для составления действий State? Мы могли бы попробовать так:

case class State[S, +A](runS: S => Trampoline[(A, S)]):
  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State[S, B] { s =>
      More { () =>
        val (a, s1) = runS(s).runT
        More(() => f(a) runS s1)
      }
    }

Но этого оказывается недостаточно. Пример zipIndex из раздела 1 по-прежнему будет переполнять стек для больших списков, на этот раз для еще меньших списков. Проблема в том, что вызов runT находится не в хвостовой позиции, поэтому его нельзя оптимизировать или обернуть в Trampoline.

4.1 Trampoline monad?

Попытаемся решить эту проблему, сделав Trampoline монадическим. У него уже есть монадический модуль unit, который является конструктором Done (unit для монады M является функция типа A => M[A] для всех A. Это unit в том смысле, что передача его в flatMap является тождеством: fa.flatMap(unit) == fa). Все, что ему нужно, это monadic bind, то есть flatMap. Давайте добавим метод flatMap непосредственно в Trampoline, чтобы можно было сделать следующее в State.flatMap:

def flatMap[B](f: A => State[S, B]): State[S, B] =
  State[S, B] { s =>
    More { () =>
      runS(s).flatMap { (a, s1) => More(() => f(a).runS(s1)) }
    }
  }

Это определенное улучшение. Проблема переносится на метод flatMap для Trampoline, который может возникнуть соблазн реализовать следующим образом:

def flatMap[B](f: A => Trampoline[B]): More[B] =
  More[B](() => f(runT))

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

4.2 Корректное построение монады

Способ обойти это ограничение — добавить конструктор к типу данных Trampoline, изменив flatMap с вызова метода на вызов конструктора:

case class FlatMap[A, +B](sub: Trampoline[A], k: A => Trampoline[B])
    extends Trampoline[B]

Батут (trampoline) этой формы можно рассматривать как вызов подпрограммы, результат которой возвращается в k.

Метод runT трейта Trampoline теперь должен учитывать этот новый конструктор. Для упрощения давайте отделим задачу перехода к следующему шагу от задачи выполнения всех шагов:

@annotation.tailrec
final def resume: Either[() => Trampoline[A], A] =
  self match
    case Done(v) => Right(v)
    case More(k) => Left(k)
    case FlatMap(a, f) =>
      a match
        case Done(v) => f(v).resume
        case More(k) => Left(() => FlatMap(k(), f))
        case FlatMap(b, g) =>
          FlatMap(b, x => FlatMap(g(x), f)).resume

@annotation.tailrec
final def runT: A =
  resume match
    case Right(a) => a
    case Left(k)  => k().runT

Метод resume выполняется путем сопоставления шаблонов на Trampoline, возвращая либо результат (Right), либо следующий шаг в виде Function0 (Left). То, как мы здесь обрабатываем случай FlatMap(a,f) очень важен. Мы сопоставляем вызов подпрограммы a, и если это Done, то просто запускаем продолжение. Если же обернут конструктором More, то продвинемся на один шаг и обернем FlatMap поверх него. Если сам вызов подпрограммы содержит вызов подпрограммы, у нас есть левоассоциированное вложение FlatMap-ов в таком выражении: FlatMap(FlatMap(b, g), f)

Крайне важно разрешить этот случай таким образом, чтобы оставаться продуктивным без введения новых stack frames. Хитрость заключается в том, чтобы повторно связать справа выражение: FlatMap(b, x => FlatMap(g(x), f)). Когда мы это сделаем, следующая итерация будет соответствовать шаблону b, и поэтому мы сможем сделать эффективный хвостовой вызов, чтобы снова вызвать resume. Также обратите внимание, что когда мы заглядываем внутрь вложенных конструкторов FlatMap, то обнаруживаем, что некоторая информация о типе была утеряна. В таком шаблоне, как FlatMap(FlatMap(b, g), f), тип b не может быть известен, поэтому мы должны принять Any при построении вложения, ассоциированного справа. Это совершенно безопасно, так как можно предположить, что левоассоциированное вложение при его построении было хорошо типизировано. Эта повторная ассоциация использует законы монад. Trampoline — это монада, а монады по определению ассоциативны. Поэтому правоассоциированные продолжения всегда в точности эквивалентны левоассоциированным.

4.3 Легкий способ ошибиться

Здесь следует рассмотреть еще один крайний случай. Теперь resume может переполнить стек, если левая "матрешка" FlatMap-ов выше, чем стек вызовов. Вызов f(v) сделает вызов g(x), который сделает еще один внутренний вызов и т.д. Давайте избежим этого, в первую очередь запрещая построение глубоко вложенных левоассоциированных привязок. Сделаем конструктор FlatMap приватным, открывая вместо него метод flatMap в Trampoline, который перепишем так, чтобы он всегда создавал правоассоциативные привязки:

def flatMap[B](f: A => Trampoline[B]): Trampoline[B] =
  self match
    case FlatMap(a, g) => FlatMap(a, x => g(x).flatMap(f))
    case x             => FlatMap(x, f)

Чтобы заполнить пробел, мы также должны запретить методу resume строить такую "матрешку", заменив вызовы конструктора FlatMap вызовами метода flatMap:

case FlatMap(a, f) =>
  a match
    case Done(v) => f(v).resume
    case More(k) => Left(() => k().flatMap(f))
    case FlatMap(b, g) =>
      b.flatMap(x => g(x).flatMap(f)).resume

Наконец, для того, чтобы использовать нашу монаду Trampoline с for-comprehension Scala, нам также нужно реализовать метод map, который, конечно же, просто определен в терминах flatMap:

def map[B](f: A => B): Trampoline[B] =
  flatMap(a => Done(f(a)))

4.4 Stackless Scala

Предыдущий метод zipIndex теперь может выполняться без StackOverflowError для любого размера входного списка с помощью монады State.

Представленный здесь Trampoline — это общее решение для устранения stack frame в Scala. Теперь мы можем переписать любую программу так, чтобы вообще не использовать пространство стека. Рассмотрим программу такого вида:

val x = f()
val y = g(x)
h(y)

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

for 
  x <- f()
  y <- g(x)
  z <- h(y)
yield z

если учесть следующее неявное преобразование:

given conv[A]: Conversion[A, Trampoline[A]] with
  def apply(a: A): Trampoline[A] = More(() => Done(a))

Единственный тип вызова, для которого ступенчатое преобразование не подходит (и неслучайно), — это саморекурсивный вызов. Их легко обнаружить, и в этих случаях мы могли бы вызвать конструктор More явно, как в этой рекурсивной функции для нахождения n-го числа Фибоначчи:

def fib(n: Int): Trampoline[Int] =
  if n <= 1 then Done(n)
  else
    for
      x <- More(() => fib(n - 1))
      y <- More(() => fib(n - 2))
    yield x + y

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

5. Совместная многозадачность

Мы видели, как можно последовательно составлять вычисления Trampoline с помощью flatMap. Но также возможно составить их параллельно путем чередования вычислений:

infix def zip[B](b: Trampoline[B]): Trampoline[(A, B)] =
  (self.resume, b.resume) match
    case (Right(a), Right(b)) =>
      Done((a, b))
    case (Left(a), Left(b)) =>
      More(() => a() zip b())
    case (Left(a), Right(b)) =>
      More(() => a() zip Done(b))
    case (Right(a), Left(b)) =>
      More(() => Done(a) zip b())

Чтобы увидеть всё это в действии, можно ввести побочные эффекты для вывода на консоль:

val hello: Trampoline[Unit] =
  for
    _ <- print(" Hello , ")
    _ <- println(" World !")
  yield ()

Можно увидеть, что произойдет, если вычисление hello чередуется с самим собой:

(hello zip hello).runT
// Hello ,  Hello ,  World !
// World !

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

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

6. Свободные монады: обобщение батута

Мы можем думать о Trampoline как о сопрограмме, которая может быть приостановлена в Function0, а затем возобновлена. Но это не единственный конструктор типа, который мы могли бы использовать для приостановки. Если абстрагироваться от конструктора типа, то получим следующий тип данных:

sealed trait Free[S[+_], A]

object Free:
  private infix case class FlatMap[S[+_], A, B](
      a: Free[S, A],
      f: A => Free[S, B]
  ) extends Free[S, B]

case class Done[S[+_], A](a: A)             extends Free[S, A]
case class More[S[+_], A](k: S[Free[S, A]]) extends Free[S, A]

Теперь Trampoline может быть определен как:

type Trampoline[A] = Free[Function0, A]

Как видно из приведенных выше конструкторов данных Done и FlatMap, Free[S,A] является монадой для любого ковариантного функтора S. С точки зрения теории категорий это в точности свободная монада (Free Monad), порожденная функтором S.

Когда мы говорим, что S должен быть функтором, то имеем в виду, что должен существовать экземпляр Functor[S]:

trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

Для Function0 функтор определяется просто:

given Functor[Function0] with
  def map[A, B](a: () => A)(f: A => B): () => B = () => f(a())

6.1 Функции, определенные для всех свободных монад

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

final def resume(using S: Functor[S]): Either[S[Free[S, A]], A] =
  this match
    case Done(a) => Right(a)
    case More(k) => Left(k)
    case a FlatMap f =>
      a match
        case Done(a)     => f(a).resume
        case More(k)     => Left(S.map(k)(_ flatMap f))
        case b FlatMap g => b.flatMap(x => g(x).flatMap(f)).resume

Обратите внимание, что по существу это определение точно такое же, как и для Trampoline. Единственными отличиями являются сигнатура типа, дополнительный неявный аргумент Functor и тот факт, что мы заменили явную конструкцию Function0 вызовами map для нашего функтора. Это также верно для обобщенных реализаций zip, map и flatMap. Вот zip:

infix def zip[B](b: Free[S, B])(using S: Functor[S]): Free[S, (A, B)] =
  (resume, b.resume) match
    case (Left(a), Left(b)) =>
      More(S.map(a)(x => More(S.map(b)(y => x zip y))))
    case (Left(a), Right(b)) =>
      More(S.map(a)(x => x zip Done(b)))
    case (Right(a), Left(b)) =>
      More(S.map(b)(y => Done(a) zip y))
    case (Right(a), Right(b)) =>
      Done((a, b))

6.2 Общие типы данных как свободные монады

Неформально мы можем рассматривать Free[S, A] как тип любого вычисления, которое может разветвляться по некоторому функтору S и заканчиваться некоторыми данными типа A на концах. Чтобы понять это, рассмотрим обычное бинарное дерево решений. Это свободная монада, функтор которой «разбивает» вычисление на две части в каждой ветви:

type Pair[+A]    = (A, A)
type BinTree[+A] = Free[Pair, A]

Случай Done для BinTree[A] — это лист, которая содержит значение типа A, а случай More — это ветвь, содержащая два значения типа BinTree[A]. Наша свободная монада (в случае с FlatMap) позволяет взять каждый лист дерева, применить к нему функцию создания дерева и привить полученное дерево вместо этого листа. И поскольку это экземпляр Free, работа, которую мы уже проделали над Trampoline, позволяет делать это за постоянное время и с постоянным пространством стека.

Чтобы получить дерево с любым количеством возможных ветвей в каждом узле вместо двух, мы должны разветвляться с помощью функтора List:

type Tree[+A] = Free[List, A]

Действительно, сам List может быть выражен как приложение Free:

type List[A] = Free[[X] =>> (A, X), Unit]

В этом представлении List[A] — это сопрограмма, которая создает значение типа A при каждом возобновлении работы или Unit, если это пустой список. Действие свободной монады здесь — это не действие «монады списка» как таковой (чье монадическое связывание заменяет каждый элемент списка новым списком), а монады, которая позволяет нам присоединять один список к другому. Опять же, поскольку это приложение Free, мы можем выполнять эту операцию за постоянное время и с постоянной памятью.

6.3 Свободная монада для State

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

sealed trait StateF[S, +A]
case class Get[S, A](f: S => A)  extends StateF[S, A]
case class Put[S, A](s: S, a: A) extends StateF[S, A]

В конструкторе Get f — это функция, которая ожидает на вход текущее значение состояния. В конструкторе Put s — это новое состояние, а a — остальная часть вычислений (которые предположительно могут что-то сделать с этим состоянием). Нам понадобятся доказательства того, что наш тип данных на самом деле является функтором:

given statefFun[S]: Functor[[X] =>> StateF[S, X]] = new:
  def map[A, B](m: StateF[S, A])(f: A => B): StateF[S, B] =
    m match
      case Get(g)    => Get(s => f(g(s)))
      case Put(s, a) => Put(s, f(a))

Затем мы можем закодировать монаду, подобную State, непосредственно как свободную монаду, сгенерированную нашим функтором StateF:

type FreeState[S, A] = Free[[X] =>> StateF[S, X], A]

Комбинатор pureState из раздела 1 поставляется "бесплатно" с конструктором Done нашей свободной монады.

def pureState[S, A](a: A): FreeState[S, A] = Done(a)

А два других, для получения и установки состояния, легко определить:

def getState[S]: FreeState[S, S] = More(Get(s => Done(s)))

def setState[S](s: S): FreeState[S, Unit] = More(Put(s, Done(())))

Для запуска действия с заданным начальным состоянием используется простой цикл:

def evalS[S, A](s: S, t: FreeState[S, A]): A =
  t.resume match
    case Left(Get(f))    => evalS(s, f(s))
    case Left(Put(n, a)) => evalS(n, a)
    case Right(a)        => a

Теперь мы можем писать чистые функции, сохраняющие некоторое состояние в этой монаде. Например, вот zipIndex из раздела 1, на этот раз с использованием нашей монады FreeState:

def zipIndex[A](as: List[A]): List[(Int, A)] =
  evalS(
    0,
    as.foldLeft(pureState[Int, List[(Int, A)]](List())) { (acc, a) =>
      for
        xs <- acc
        n  <- getState
        _  <- setState(n + 1)
      yield (n, a) :: xs
    }
  ).reverse

Реализация почти идентична, и она работает в постоянном стеке без необходимости проходить через Trampoline. Вывод состоит в том, что не всегда необходимо или желательно изменять существующую структуру данных. Мы можем изобретать новые свободные монады собственного дизайна a la carte (см. 7.4) и пожинать те же плоды.

7. Существующая работа

Ничто из представленного здесь не является особенно оригинальным, хотя части взяты из разных источников и, насколько мне известно, ранее не собирались таким образом, особенно в Scala (2012 год - на момент написания статьи).

7.1 Батуты

Использование "батутных" функций для реализации хвостовых вызовов в языках, ориентированных на стек, — хорошо известная техника, реализованная во многих языках в виде библиотек или компиляторов.

Стандартная библиотека Scala (в версии 3.2.2) включает объект TailCalls, предоставляющий структуру данных TailRec.

7.2 Операционные монады

Реализация свободных монад в этой статье имеет монадическую привязку, конкретизированную на куче как конструкторе данных, а не на вызове метода в стеке. Это позволило манипулировать привязками как данными и выполнять повторную ассоциацию. Можно назвать эту технику использованием операционной монады, основанной на работе Heinrich Apfelmus. Он обсуждает монады, представляющие программы с явно овеществленным стеком, но не свободные монады или трамплины, представленные здесь.

Наша монада FreeState также является операционной монадой, явно овеществляющей две операции Get и Put.

7.3 Свободные монады и сопрограммы

Идея обобщения батутов пришла из Coroutine Pipelines Блажевича в октябрьском выпуске "The Monad Reader" за 2011 год. Хотя он не делает явных ссылок на свободные структуры, ясно, что его тип Coroutine является преобразованием Free monad. В текущей реализации на Scala необходимо отказаться от параметризации дополнительной монады, чтобы сохранить удаление хвостовых вызовов. Вместо того, чтобы быть написанным как монадный преобразователь, Free может быть преобразован монадным преобразователем для того же эффекта. Например, Coroutine[A, [X] =>> State[S, X], B] становится StateT[S, [X] =>> Free[A, X], B], учитывая: case class StateT[S, M[_], A](run: S => M[(A, S)])

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

7.4 Проблема выражения

Идея монады FreeState, моделирующей переходы состояний с помощью побочного продукта Get и Put, взята из статьи Wouter Swierstra 2008 года "Типы данных на заказ". Swierstra использует свободную монаду для создания специальных рекурсивных типов данных из побочного произведения произвольных функторов и классов типов Haskell для обработки диспетчеризации в различных случаях побочного произведения.

7.5 Кодовая плотность

Акт связывания всех монадических связей справа можно понимать как применение кодовой плотности (application of codensity). Это ключевое понимание пришло из обсуждения с Эдом Кметтом его работы со структурой данных ввода-вывода, выраженной в виде свободной монады.

Janis Voigtlander обсуждает коденсальность свободных монад в своей статье "Асимптотическое улучшение вычислений над свободными монадами", хотя он не называет понятие "коплотность" явным образом. Цель его статьи — не экономия места в стеке как такового, а повышение производительности.

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

7.6 Итерации

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

Iteratees — это не совсем свободные монады, но они представляют собой композицию свободной монады с другим функтором, поэтому их можно выразить как приложение Free. Тип IterV в статье Лато можно очень грубо выразить следующим образом:

type IterV[I, O] = Free[[X] =>> I => X, (I, O)]

Поскольку IterV отслеживает оставшуюся часть ввода (во многом как синтаксический анализатор), технически он не является свободным. Но в статье также обсуждается "внутренний итератор", который они называют enumeratee, преобразующий один поток входных данных в поток выходных данных, и этот тип проще выразить как свободную монаду:

type Enumeratee[I, O, A] = Free[[X] =>> Either[I => X, (O, X)], A]

Этот тип сопрограммы представляет собой преобразователь потока, который может либо запрашивать ввод типа I, либо выдавать вывод типа O каждый раз, когда он возобновляет работу, и завершается со значением типа A.

8. Выводы и дальнейшая работа

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

Мы увидели, как батуты соотносятся с общей идеей свободных монад над функтором и как все наши опасения по поводу батутов, а также все преимущества легко переносятся на любую такую монаду.

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

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

Ссылки: