Логическое программирование в Scala. Контекстные абстракции

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

Контекстные абстракции Scala

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

Алгоритм поиска самостоятельно, без явных указаний программиста решает какое значение будет возвращено, поэтому такие значения в контексте называются неявными. Таким образом, механизма контекстных абстракций имеет два ключевых аспекта — способы размещения неявных значений в контекст и реализация поиска в нём. Рассмотрим их по порядку.

Способы размещения неявных значений

Контексты могут вкладываться один в другой и импортироваться как целиком, так и отдельными значениями. Но в любом случае сперва необходимо неявные значения туда разместить. Для этого в Scala 3 используется ключевое слово given (в более ранних версиях — implicit). Вот типичные примеры такого размещения:

given theAnswer    : Int                                 = 42
given parseArgs    : (args: List[String]) => IO[ScanUrl] = ??? // неявная функция
given headOpt      : [A] => (lst: List[A]) => Option[A]  = ??? // полиморфная неявная функция
given eitherFunctor: [E] => Functor[Either[E, *]]        = ??? // полиморфное значение!

Для удобства отладки рекомендуется всегда указывать имена неявных значений. Но если этого не сделать, то компилятор сгенерирует его сам на основании типа возвращаемого значения и префикса given_, например, given_Functor_Either или given_IO_ScanUrl.

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

import cats.syntax.all.*  
import cats.Monoid  
List(2, 21).combineAll(using Monoid.instance(1, _ * _)) // 42

// далее в контексте нет именно того моноида, что мы передали в функцию

Для классов типов предусмотрен дополнительный синтаксический сахар derives для удобства размещения их экземпляров в контекст. А именно, код вида class MyType derives ClassType порождает в объекте-компаньоне MyType такой код:

given ClassType[MyType] = ClassType.derived

Подразумевается, что в объекте ClassType уже определён макрос derived, который сгенерирует нужную реализацию ClassType[MyType], или приведёт к ошибке компляции.

Есть ещё один нестандартный способ размещения значения в контекст — переопределение (overriding) метода базового класса (трейта) так, чтобы к обычным параметрам добавился модификатор using. В этом случае пользователи будут как обычно вызывать этот метод через интерфейс базового класса, но в реализации наследника переданный аргумент автоматически попадёт в контекст как неявное значение. Такой приём использовался в первой части обзора при демонстрации логического стиля .

Многие полезные неявные значения уже добавлены в различные Scala-пакеты, в том числе и во встроенные. Но для некоторых важных экземпляров всё же не существует конкретных given ни в каком программном коде. При необходимости компилятор сам размещает в контекст такие значения. Вот некоторые примеры:

• встроенные предикаты (параметризированные типы-одиночки):

  • двухаргументные отношения типов: scala.{=:=, <:<},

  • одноаргументный scala.util.NotGiven[_];

• значения для механизма отражений: scala.reflect.{ClassTag, TypeTag, TypeTest}, scala.deriving.Mirror;

• scala.{CanEqual, ValueOf}.

Любопытно, что для встроенных приведений типов (подтипизация, или между примитивными типами, вроде Short => Int) не предусмотрено неявных значений Conversion. Такие преобразования реализованы независимо от того, что называется контекстными абстракциями в Scala и пересекаются с ними зачастую неочевидным образом.

У типов неявных значений, размещаемых посредством given есть одна неожиданная особенность. Когда тип given записан как функциональный (parseArgs, headOpt), то на самом деле описывается неявное значение результата этой функции — этот given будет задействован при поиске неявного значения по типу результата, а все аргументы такой функции будут автоматически вытягиваться из контекста. Замечательно, что тут не имеют значения ни порядок аргументов (нюанс разберём позднее), ни каррированность этой функции: аннотации given типами A => B => C и (B, A) => C аналогичны, так как описывают одно и то же множество аргументов. Если же необходимо разместить в контекст именно значение функционального типа вроде A => B, то достаточно в объявлении given окружить этот тип скобками, или же определить его псевдоним заранее (так и было сделано в первой части обзора).

Способы извлечения неявных значений

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

• «магия призыва»:

  • summon[T] — обычное извлечение из контекста значения типа T,

  • summonAll[(T1, T2, …)] — извлечение кортежа неявных значений (этот и следующие «свитки призыва» лежат в пакете scala.compiletime),

  • summonInline[T] — полезен внутри макросов,

  • summonFrom[T](f: Nothing => T) — хитрое колдунство, позволяющее использовать сопоставление с шаблонами для более тонкого управления логикой извлечения;

• контекстный аргумент функции:

  • модификатор аргументов (using a: A) — этот аргумент пробрасывается из вызывающего контекста в контекст тела функции,

  • тип контекстной функции A ?=> B — по сути, синтаксический псевдоним для класса ContextFunction1 с методом def apply(using a: A): B;

• контекстные границы классов типов [A: ClassType as cl] — синтаксический сахар над требованием неявного предоставления экземпляров классов типов: [A](using cl: ClassType[A]);

• неявные преобразования типов: если терм типа A передали туда, где ожидается тип B, то компилятор сам извлекает из контекста функцию Conversion[A, B] и встраивает в программу её вызов с переданным термом (но только если не A <:< B!).

Формально верхнее [A <: B] и нижнее [A >: B] ограничения типа также можно рассматривать как контекстные границы [A: <:<[*, B]] и [A: <:<[B, *]]. Но ранее уже упоминалось, что ООП-шная подтипизация обрабатывается другим механизмом компилятора, поэтому подобные ограничения типов не относятся к контекстным абстракциям Scala.

Вообще, преобразования подтипизации разработчики языка сочли настолько тривиальными, что никаких встроенных неявных Conversion для них не предусмотрено. Если же вручную разместить такой given, то это преобразование никогда не будет задействовано неявно — оно будет просто проигнорировано. С другой стороны, если вручную разместить неявное значение, скажем, Conversion[Short, Int], то оно успешно перекроет встроенное приведение типов, хотя прежде в контексте не существовало подобного преобразования.

Структура контекста

Для задач логического программирования нам интересны прежде всего параметризированные неявные значения, которые разрешаются только если в контексте присутствуют значения типов-параметров. Извлечение производится пошагово — сначала ищется значение целевого типа, а затем тот же алгоритм рекурсивно применяется для всех его неявных параметров. Аналогичным образом работают и рассуждения в Прологе, но здесь есть одно принципиальное отличие. Пролог ищет все возможные свидетельства истинности (найденные подстановки свободных параметров), тогда как в Scala из контекста может быть извлечено лишь единственное значение заданного типа.

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

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

Идея в том, что алгоритм вывода терма работает послойно — если значение типа найдено в текущем слое контекста, то поиск останавливается, иначе поиск продолжается в следующем слое. Ошибка компиляции будет только в том случае, если алгоритм дойдёт до слоя, в котором размещены более одного значения этого типа. Такой подход позволяет приоритезировать неявные значения одного и того же типа, размещая их в разных слоях, тем самым управляя механизмом поиска.

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

• локальные объявления given и using-аргументы могут приводить к конфликтам извлечения, если рядом есть другие неявные значения того же типа или их импорты;

• импорты конкретных неявных значений import someScope.myImplicitValue (самые последние импорты перекрывают более ранние);

• тотальные импорты import someScope.given (самые последние импорты перекрывают более ранние);

• given из определений типов, от которых наследуется класс с текущим блоком;

• объявления given и их импорты из родительских областей (в которые вложен данный блок);

• контекст объекта-компаньона типа;

• контекст базовых типов объекта-компаньона целевого типа.

Чтобы импортировать все неявные значения из экземпляра класса или объекта obj, нужно использовать специальный синтаксис тотального импорта import obj.given. Такой подход считается не очень удобным, поэтому неявные значения, связанные с конкретными типами, предпочитают размещать в объектах-компаньонах этих типов — так они автоматически попадут в контекст поиска без лишних импортов. При этом низкоприоритетные given размещают в базовых трейтах, а высокоприоритетные — в их наследниках, в том числе и в объекте-компаньоне, реализующем эти трейты. Поиск неявных значений будет осуществляться последовательно по слоям, заданным иерархией наследования.

Реализация автоматической композиции программы

Наконец-то мы добрались до секретов магии автоматической композиции программы, показанной в первой части обзора. Там приводился пример простого приложения, напоминающий типичный продуктовый Scala-сервис. Для простоты выбрана экосистема Cats Effect с контейнером IO. Бизнес-логика моделируется конечным автоматом, каждое состояние которого описывается уникальным типом, а переходы между ними реализуются бизнес-функциями вида A => IO[B]. В той статье было показано, что композицию всей программы из таких функций, размещённых в контексте, можно доверить механизму вывода термов компилятора Scala. С точки зрения логического программирования это соответствует автоматическому конструктивному доказательству обитаемости типа программы в теории, заданной аксиомами бизнес-функций.

Композицию можно построить по-разному. Функциональный подход подразумевает прямое бесточечное комбинирование стрелок Клейсли A => F[B]. Но в Cats Effect сигнатура программы фиксируется методом def IOApp.run(args: List[String]): IO[ExitCode], поэтому здесь был выбран более привычный монадический подход. В итоге у нас должна получиться (автоматически, неявно!) программа такого вида:

def run(args: List[String]) =  
  parseArgs(args)           flatMap  
  loadContent               product  
  obtainLimit(())           flatMap  
  extractNumbers            flatMap  
  {_.traverse(printNumber)} map  
  calcExitCode

Для монады F характерны две ключевые возможности: «запаковка» pure[A]: F[A] и преобразование flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]. Первая позволяет стартовать чистые вычисления с эффектом F, а вторая — последовательно комбинировать эффективные шаги f. Эти возможности должны быть доступны в том же контексте, что и бизнес-функции. Нам нужно раздельно управлять типами контейнера F[_] и результата A, поэтому введём вспомогательный трейт:

trait Derive[F[_], A]:  
  val value: F[A]  
  
object Derive:  
  inline def apply[F[_], A](using d: Derive[F, A]): F[A] = d.value

Чтобы «запаковывать» неявные значения args: List[String], достаточно добавить в объект-компаньон такой given:

given pure[F[_]: Monad as F, A: Id as a]: Derive[F, A] = new:  
  val value = F.pure(a)

Теперь нужно добавить преобразования flatMap и map. И вот тут возникает проблема нескольких значений одного типа в контексте. Чтобы её разрешить, вынесем эти и последующие преобразования в отдельный трейт:

object Derive extends LowPriorityDerive { … }

trait LowPriorityDerive:  
  
  // вспомогательные классы типов, «чтоб не скучно было»
  type ReaderT[F[_], A] = [B] =>> A => F[B]  
  type Derived[F[_]] = [A] =>> Derive[F, A]  
  
  given map: [
    F[_]: Functor as F,
    B: ReaderT[Id, A] as f,
    A: Derived[F] as fa
  ] => Derive[F, B] = new:
    val value: F[B] = F.map(fa.value)(f)

  given flatMap: [
    F[_]: Monad as F,
    B: ReaderT[F, A] as f,
    A: Derived[F] as fa,
  ] => Derive[F, B] = new:
    val value: F[B] = F.flatMap(fa.value)(f)

Обратите внимание, сперва в эти функции передаются возможности контейнера F, затем преобразование f и лишь в самом конце «исходное» значение fa. Такой порядок необходим из-за особенностей механизма связывания типов-параметров. Это тот самый алгоритм унификации, о котором говорилось в предыдущей части — он находит такую подстановку свободных параметров, которая доказывает логическую корректность утверждения об обитаемости заданного типа. В данном случае при поиске значения известного типа F[B] тип A не известен заранее, поэтому первым делом в контексте ищется подходящее значение f, которое фиксирует тип A, и лишь затем ищется значение уже этого типа. Если же поменять порядок неявных аргументов и попробовать найти fa раньше f, то это приведёт к знакомой ошибке компиляции — из контекста можно вывести более одного значения F[A] для неизвестного A.

Также нам нужно уметь комбинировать независимые шаги и траверсировать коллекции. Обе эти возможности требуют, чтобы функтор F можно было переставлять с бифунктором произведения (кортежа (*, *)), что в терминах библиотеки Cats описывается классом типов Applicative. Значит, нам достаточно добавить в трейт LowPriorityDerive следующие given:

given tuppled: [  
  F[_]: Applicative as F,  
  A: Derived[F] as fa,  
  B: Derived[F] as fb  
] => Derive[F, (A, B)] = new:  
  val value: F[(A, B)] = F.product(fa.value, fb.value)  
  
given traverse: [  
  F[_]: Monad as F, // Applicative реализуется монадой в Cats 
  G[_]: Traverse as G,  
  B: ReaderT[F, A] as f,  
  A: Derived[F] ∘ G as fga  
] => Derive[F, G[B]] = new:  
  val value: F[G[B]] = F.flatMap(fga.value)(G.traverse(_)(f))

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

// все бизнес-функции (аксиомы теории) уже добавлены в контекст ранее

object myApp extends IOApp:
  override def run(using args: List[String]) =  
    Derive[IO, ExitCode]

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

trait Infer[FA]:  
  type Value  
  def result: Value  
  
object Infer:  
  inline def apply[FA: Infer as i]: i.Value = i.result
  
  given fromDerive[F[_], A](using d: Derive[F, A]): Infer[F[A]] with  
    type Value = F[A]  
    def result: F[A] = d.value

object myApp extends IOApp:
  override def run(using args: List[String]) =  
    Infer[IO[ExitCode]]

Давайте допустим, что требования поменялись и теперь необходимо добавить обработку ошибки загрузки контента. Контейнер IO[_] имеет для этих целей набор методов наподобие handleError(f: Throwable => A): IO[A] => IO[A]. Но все эти методы имеют общий недостаток, не позволяющий использовать их в автоматическом композировании — в контейнере не упоминается тип ошибки, что делает неразличимыми состояния до и после её обработки. Это значит, что нам нужно явно упомянуть ошибку в типе нужного состояния. Самым прямолинейным решением будет такое изменение кода:

// добавляем новое состояние
type ContentOrError = Throwable `Either` Content

// изменяем один переход
type ContentLoader =     ScanUrl             => IO[ContentOrError]
// и добавляем новый
type LoadErrorHandler =  ContentOrError      => Content

// модифицируем реализацию загрузки контента
given loaderContent: ContentLoader = url =>  
  EmberClientBuilder  
    .default[IO].build  
    .use(_.expect[String](url.str))  
    .map(Content.apply)  
    .attempt // добавили эту строчку

// добавляем реализацию нового перехода
given loadErrorHandler: LoadErrorHandler =
  // так не стоит обрабатывать ошибку; просто для демонстрации
  case Left(err)           => Content(s"Ошибка загрузки контента! ${err.getMessage}")  
  case Right(Content(cnt)) => Content(s"Контент: $cnt")

На практике же для декларативного обслуживания бизнес-ошибок в экосистеме Cats часто используется монадный трансформер EitherT с указанием пользовательского типа ошибки — с ним удобно комбинировать вычисления с ошибками до их обработки. Аналогичный подход используется и в экосистеме ZIO. Но в любом случае было бы полезно добавить в контекст дополнительные теоремы параметризированные given, которые позволили бы комбинировать вычисления с бизнес-функциями обработки ошибок.

Выводы

Краткий обзор обзора

Проектирование сложной информационной системы делает необходимым детальное моделирование предметной области в системе типов выбранного языка программирования. Статическая типизация обеспечивает надёжную защиту конечного пользователя от ошибок проектирования. Поведение правильно смоделированной системы описывается конечными автоматами, в которых исполнитель переходит от одного уникального типа состояния к другому. Каждый такой переход — это простая самостоятельная логика, вроде запроса к БД и веб-сервису, локальное вычисление и т.п.

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

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

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

Преимущества логического программирования

Основное преимущество логического программирования заключается в его декларативности — мы просто объявляем, что у нас есть и что мы хотим получить. И если всё сделали правильно, то компилятор сам без лишнего кода построит наиболее простую детерминированную программу. Такой подход минимизирует влияние «человеческого фактора» на качество программного продукта.

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

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

Недостатки логического программирования в Scala

Выделим три наиболее существенных недостатка.

• Большое время компиляции. Алгоритм поиска доказательств может становиться NP-сложным (а то и вовсе расходящимся) относительно объёма контекста — количества известных аксиом и теорем. Программисты, злоупотребляющие классами типов и прочими контекстными абстракциями, часто страдают от экспоненциального роста времени компиляции.

• Сложность отладки. Программный код однозначно фиксирует последовательность действий, но в рамках логической парадигмы она остаётся неявной для программиста. Современные среды Scala-разработки не имеют инструментов удобной навигации по неявно скомпозированной программе. В последних версиях компилятора Scala есть опция -Vprint:typer, показывающая в журналах компиляции всю цепочку неявных вызовов, вот только читать её практически невозможно. Такой инструментальный недостаток является хоть и не блокирующим, но очень весомым.

• Высокий порог входа. В программировании доминирует императивная парадигма, формирующая опредённые паттерны мышления. Другие подходы, вроде функционального или логического программирования, зачастую вызывают своеобразный «культурный шок» и априорное отторжение. Это происходит вовсе не потому, что новые подходы «сложнее», или «не дают ничего принципиально полезного». Просто у состоявшихся программистов, «сосуд и так полон», им психологически сложно взглянуть на программирование с иного ракурса, за рамками привычных стереотипов. Типичным примером подобных стереотипов является тезис из дзена Python «явное лучше неявного», часто воспринимаемый слишком буквально. Именно инерция массового сознания определяет нынешнее положение непопулярных парадигм — и в создании профильных инструментов разработки, и в системе обучения, и на рынке труда. Как следствие, низкий интерес у программистов и высокие риски для менеджмента.

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

Перспективы

Что можно изменить, чтобы устранить перечисленные недостатки или минимизировать их влияние?

Экспоненциальная сложность алгоритма рассуждений является его неотъемлемым свойством. Обычно этот алгоритм выполняет человек, но логическое программирование позволяет переложить нагрузку на компьютер. Так что в любом случае речь идёт лишь о смягчении неизбежных проблем в работе программистов.

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

Кроме того, в Scala существует возможность упростить задачу композиции программы, смоделированной в виде конечного автомата с уникальными типами состояний. Можно записать что-то вроде InferStateMachine[(InitState, State1, State2, FinalState)] и такие подсказки способны превратить экспоненциальную сложность вывода финальной композиции в примерно линейную. Однако реализация правил для такого вывода опирается на зависимые типы и выходит за рамки обзора.

А вот к проблеме сложной отладки требуется более системный подход. Чтобы неявную композицию сделать более явной необходимы новые инструменты, позволяющие её визуализировать для программиста не в журнале компиляции, а в процессе разработки. Это могут быть всплывающие подсказки, или разделение окна на «исходник» и «результат», как в некоторых редакторах Markown или LaTeX. Но в любом случае визуализация должна быть хорошо структурированной, понятной и удобной для повседневных сценариев. Это сложная задача, и для её системного решения требуется как минимум высокий интерес разработчиков к контекстным абстракциям и логическому программированию.

Интерес сообщества подогревается докладами, книгами и статьями, подобными этой. Они знакомят с концепцией, демонстрируют её преимущества на конкретных примерах и в целом привлекают к ней внимание. Также полезна борьба с вредными стереотипами, вроде упомянутого выше принципа «явное лучше неявного». Слепое следование этому принципу не только исключает все основные идеи логического программирования, но даже запрещает механизм вывода типов, успешно используемый в самых разных языках программирования! Такое противоречие обычно разрешается закона Парето: 20% решения лучше описывать явно (контракты и бизнес-функции), тогда как 80% непринципиальной рутины полезно оставлять для неявной автоматизации компилятору и фреймворку.

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