scala - Scala Transducers 和 Clojure Transducers 有什么异同？

Question

Paul Chiusano和 Rúnar Óli写了一本很棒的书 Functional programming in Scala .他们在其中提到了 Scala 社区中一个很少被引用的概念 - Transducers。



在 Clojure 社区 - Transducers得到一个 little more press .

我的问题是: Scala Transducers **有哪些异同(来自《Functional Programming in Scala》一书)和 Clojure 转换器？**

假设:

我知道

换能器是来自 their concept in Electrical Engineering 的常见说法

有一个预先存在的概念 in Computer Science called a Finite State Transducer

有先例in Biology and Psychology adopting the word transduction

有already a history其他技术书籍，如 SICP adopting the word Transducers .

Answer 1

书中的流转换器 Function Programming in Scala (FPiS) 和 Clojure 的传感器非常相似。它们是拥有“机器”(步进函数)将输入流处理为输出流的想法的概括。 FPiS 的传感器被称为 Process es. Rich Hickey also uses the term process在他关于 Clojure 中的换能器的介绍性演讲中。

起源

FPiS 传感器的设计基于 Mealy machines .据说 Mealy 机器具有:

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函数本质上是 Rickey 谈到的种子左归约 in this slide .

上下文不可知

两者都可以在许多不同的上下文中使用(例如列表、流、 channel 等)。

在 FPiS 传感器中，过程类型是:

trait Process[I, O]

它只知道它的输入元素和输出元素。

在 Clojure 中，情况类似。希基称这个 "fully decoupled" .

作品

可以组合两种类型的换能器。

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 的表示不仅仅是幕后的功能。它是一个具有 3 个变体的 case 类(代数数据类型):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 的 reducer->reducer 函数的角色。

停止扮演reduced在 Clojure 中。

Emit 代替调用 Clojure 中的下一步函数。

提前终止

两者都支持提前终止。 Clojure 使用一个名为 reduced 的特殊值来完成它。可以通过 reduced? 进行测试谓词。

FPiS 使用更静态类型的方法，进程可以处于 3 种状态之一:Await、Emit 或 Halt。当“步骤函数”返回状态为 Halt 的进程时，处理函数知道停止。

效率

在某些方面，它们再次相似。两种类型的传感器都是需求驱动的，不会生成中间集合。但是，我认为 FPiS 的传感器在流水线/组合时效率不高，因为内部表示超过 "just a stack of function calls" as Hickey puts it .我只是在这里猜测效率/性能。

调查 fs2 (以前的 scalaz-stream )用于基于 FPiS 中换能器设计的性能更高的库。

例子

这是 filter 的示例在两种实现中:

Clojure, from Hickey's talk slides :

(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 传感器都具有:

相似的起源

在不同上下文中使用的能力(列表、流、 channel 、文件/网络 io、数据库结果)

需求驱动/提前终止

完成/完成(为了资源安全)

tasty :)

它们的底层表示有些不同。 Clojure 风格的转换器似乎有利于效率，而 FPiS 转换器则有利于正确性和组合性。