Каковы сходства и различия между преобразователями Scala и Clojure?

Пол Кьюзано и Рунар Эли написали фантастическую книгу " Функциональное программирование в Scala". В нем упоминается мало упоминаемая концепция в сообществе Scala - Transducers.

Скала Преобразователи в книге Функциональное программирование в Скале

В сообществе Clojure - преобразователи получают немного больше прессы.

Мой вопрос: в чем сходства и различия между преобразователями Scala **(из книги "Функциональное программирование в Scala") и преобразователями Clojure?**

Предположения:

Я знаю что

  1. Преобразователи являются обычным языком от их концепции в электротехнике

  2. В компьютерных науках уже существует концепция, называемая конечным преобразователем состояния.

  3. В биологии и психологии существует прецедент принятия слова трансдукция

  4. Уже есть история других технических книг, таких как SICP, использующих слово Transducers.

Источник

2 ответа

Решение

Я не особенно знаком с концепцией преобразователей в Scala или с тем, насколько распространенной является эта терминология, но из фрагмента текста, который вы разместили выше (и моих знаний о преобразователях), вот что я могу сказать:

  • Они очень разные
  • Они схожи только в том, что они оба связаны с тем, как одна трансформирует одну коллекцию в другую.

Что я могу сказать о преобразователях Scala:

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

Stream[A] -> Stream[B]

Так, например, функция отображения, которая работала с потоками, в этом случае считалась бы преобразователем.

Это оно; довольно просто на самом деле.

Clojure преобразователи:

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

(x, a) -> x

На английском языке дана некоторая стартовая коллекцияxи "следующая вещь"aв сокращаемой коллекции наша сокращающая функция возвращает "следующую итерацию создаваемой коллекции".

Таким образом, если это сигнатура редукционной функции, преобразователь имеет сигнатуру

((x, a) -> x) -> ((x, b) -> x)

Причина, по которой датчики были добавлены в Clojure, заключается в том, что при добавлении илиcore.asyncканалы, Rich Hickey и его друзья обнаружили, что все функции коллекции stanard реализованы для работы с каналами (map, filter,take, так далее.). Р.Х. поинтересовался, нет ли здесь лучшего способа, и принялся за размышления о том, как отделить логику этих различных функций обработки коллекций от механики имеющихся типов коллекций. Объяснение того, как именно преобразователи делают это, я думаю, что выходит за рамки этого вопроса, поэтому я вернусь к сути. Но если вам интересно, есть много литературы по этому вопросу, которую легко найти и проработать.

Так как эти вещи связаны?

Понятно, что это очень разные понятия, но вот как я их вижу:

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

Источник

Потоковые преобразователи из книги " Функциональное программирование в Scala" (FPiS) и "Clojure" очень похожи. Они являются обобщением идеи наличия "машины" (пошаговой функции) для обработки входного потока в выходной поток. Преобразователи FPiS называются Process эс. Рич Хики также использует термин " процесс" в своем вступительном слове о преобразователях в Clojure.

происхождения

Конструкция преобразователей FPiS основана на машинах Мили. Говорят, что машины Мили имеют:

transition function T : (S, I) -> S
output function     G : (S, I) -> O

Эти функции могут быть объединены вместе, чтобы сформировать:

step: (S, I) -> (S, O)

Здесь легко увидеть, что пошаговая функция воздействует на текущее состояние машины и следующий элемент ввода для создания следующего состояния машины и элемента вывода.

Один из комбинаторов от FPiS использует такую ​​пошаговую функцию:

trait Process[I, O] {
  ...
  def loop[S, I, O](z: S)(f: (I,S) => (O,S)): Process[I, O]
  ...
}

это loop По сути, функция - это левое сокращение, о котором говорит Рики на этом слайде.

Контекстно-независимый

Оба могут использоваться во многих различных контекстах (таких как списки, потоки, каналы и т. Д.).

В преобразователях FPiS тип процесса:

trait Process[I, O]

Все, что он знает, - это элементы ввода и элементы вывода.

В Clojure это похожая история. Хики называет это "полностью отделенным".

Состав

Оба типа преобразователей могут быть составлены.

FPiS использует оператор "труба"

map(labelHeavy) |> filter(_.nonFood)

Clojure использует comp

(comp
  (filtering non-food?)
  (mapping label-heavy))

Представление

В Clojure:

reducer:    (whatever, input) -> whatever
transducer: reducer -> reducer

В FPiS:

// The main type is
trait Process[I, O]

// Many combinators have the type
Process[I, O] ⇒ Process[I, O]

Тем не менее, представление FPiS не просто функция под капотом. Это case-класс (алгебраический тип данных) с 3 вариантами: Await, Emit и Halt.

case class Await[I,O](recv: Option[I] => Process[I,O])
case class Emit[I,O](head: O, tail: Process[I,O]
case class Halt[I,O]() extends Process[I,O]
  • Await играет роль функции редуктора-> редуктора от Clojure.
  • Остановка играет роль reduced в Clojure.
  • Emit стоит вместо вызова функции следующего шага в Clojure.

Раннее прекращение

Оба поддерживают досрочное прекращение. Clojure делает это, используя специальное значение, называемое reduced который можно проверить с помощью reduced? сказуемое.

FPiS использует более статически типизированный подход. Процесс может находиться в одном из 3 состояний: Await, Emit или Halt. Когда "пошаговая функция" возвращает процесс состояния Halt, функция обработки знает, что нужно остановиться.

КПД

В некоторых моментах они снова похожи. Оба типа преобразователей зависят от спроса и не генерируют промежуточные коллекции. Тем не менее, я бы предположил, что преобразователи FPiS не так эффективны при конвейерной / компоновке, поскольку внутреннее представление - это больше, чем "просто стек вызовов функций", как выразился Хикки. Я только догадываюсь здесь об эффективности / производительности, хотя.

Заглянуть в fs2 (ранее scalaz-stream) для, возможно, более производительной библиотеки, которая основана на дизайне преобразователей в FPiS.

пример

Вот пример filter в обеих реализациях:

Clojure, из слайдов Хикки:

(defn filter
  ([pred]
    (fn [rf]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
          (if (prod input)
            (rf result input)
            result)))))
  ([pred coll]
    (sequence (filter red) coll)))

В FPiS есть один способ реализовать это:

def filter[I](f: I ⇒ Boolean): Process[I, I] =
  await(i ⇒ if (f(i)) emit(i, filter(f))
            else filter(f))

Как вы видете, filter построен здесь из других комбинаторов, таких как await а также emit,

безопасности

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

  • Если преобразователь получает reduced значение из вложенного вызова шага, он никогда не должен вызывать эту функцию шага снова с вводом.
  • Преобразователи, которым требуется состояние, должны создавать уникальное состояние и могут не иметь псевдонимов.
  • Все пошаговые функции должны иметь вариант arity-1, который не требует ввода.
  • Операция завершения преобразователя должна вызвать его вложенную операцию завершения ровно один раз и вернуть то, что она возвращает.

Конструкция преобразователя от FPiS способствует правильности и простоте использования. Состав трубы и flatMap Операции обеспечивают своевременное выполнение действий по завершению и надлежащую обработку ошибок. Эти проблемы не являются бременем для разработчиков преобразователей. Тем не менее, я полагаю, что библиотека может быть не такой эффективной, как Clojure.

Резюме

Датчики Clojure и FPiS имеют:

  • похожие истоки
  • возможность использования в разных контекстах (список, потоки, каналы, файл / сеть, результаты базы данных)
  • обусловленный спросом / досрочное прекращение
  • завершение / завершение (для безопасности ресурса)
  • вкусно:)

Они несколько отличаются по своему основному представлению. Преобразователи в стиле Clojure, похоже, способствуют эффективности, тогда как преобразователи FPiS - правильности и композиционности.

Источник
Другие вопросы по тегам