FPL 拾遗(1)

functional programming language 的很多 idea 正在扩大自己的应用范围,我们这里将一些常见的 FPL 的 pattern 进行一些介绍。事实上,很多设计的好的 C++ library 都从某种程度上借鉴了这些概念。我们这里以 future 这个简单的概念讨论。

functor pattern

常见的 future 实现(参看 C++11)都会提供一个 get 方法用来获得 future 存放的 value(promise 和 future 是一个 channel 的两端),实际应用中,这个 API 并不方便,很显然 client code 的逻辑里并不知晓“future”这样一个因为 concurrency 发明出来的概念。事实上,类似的问题很多,Google 提出的 FlumeJava(作为 MR 的替代品)也有类似的 setup,经过一段时间在其 C++ 版本上的 coding,窃以为其 API 设计绝对是非常的不 friendly,因为 client code 必须通过 DoFn 与其自己为了处理数据定义的类型 Collection/PTable/PObject 才能发生关系,这导致 composability 下降。

事实上,不少应用里 client code 仅仅在 concurrency 的环境里需要增加一些自己的内容,最后获得结果即可,但是由于 future API 的设计使得他们必须不断的提供一些 adaptor,比如把 B process(const A&) 处理成为 B process(future<A>) 或者 future<B> process(future<A>)。一个好的 API 就会提供类似下面的方法

template <typename T>
class future {
public:
  template <typename F> auto
  next(F f) -> future<typename std::result_of<F(T)>::type> {
    // ...
  }
};

这意味着用户可以轻松的将 domain-specific code 通过 next 方法 compose 起来:

future<A> a = create_A();
auto result = a.next([] (A a) {
  // do something on a
  return b;
}).next(prcess_B).next(...).get();

当然这里没有考虑 exception 等情况,事实上加入这个 exception handling 也并不困难(参看 scala 的 Try)。至此我们看到了一个非常有用的 pattern,它称为 functor pattern(这里的 functor 与 C++ 里面所说的 functor = function object 略有不同):

  • type constructor:对于任意 T,我们可以映射到 F<T>(通常通过 generics 支持)
  • function lifting:对于任意函数 B(A),我们能够将其转换成为 F<B> (F<A>)

我们提供的 next 的本质实际上就是将任意 domain specific 的逻辑(函数)提升到 concurrency domain,它本身完成了 future<A> 到 future<B> 的映射,而其输入是一个 A 到 B 映射的函数。在 Flume 里 MapFn 的角色与此类似,它要求实现一个 B Map(A) 的成员函数而实现 PCollection<A> 到 PCollection<B> 的映射,但是其 API 却要求用户实现 MapFn 这个 flume specific 的类。

monad

仅有 functor pattern 还是会让我们的代码有一些问题:试想如果用户提供了 future<B> async_process(A a),并且试图在 next 里面 compose,我们将会获得 future<future<B>>,对于 future 本身的 semantics 来说 future<B> 和 future<future<B>> 并没有本质的区别,一种简单的策略是为 future 提供一个 unwrap 的方法,它将 future<future<T>> 转换到 future<T>。但是这样一来我们就得 next(…).unwrap().next(…).unwrap()…,格外的啰嗦。

因此在这种情况下,我们需要将一个 future<B>(A) 的函数转换成为 future<B>(future<A>) 的函数,在 C++ 里面我们可以通过模板特化,将这一类函数在 next 的特化里进行特殊对待。这样一来,我们实际上提供了类似 scala 的 flatMap 方法(haskel 称为 bind)。

我们可以如下定义 monad:

  • type constructor
  • function lifting
  • unwrap 完成 M<M<T>> 到 M<T> 的映射
  • value lifting 完成 T 到 M<T> 的映射

但是更加常见的定义是

  • type constructor
  • value lifting
  • bind 完成 M<B>(A) 到 M<B>(M<A>) 的映射

对于 future,value lifting 要求非常简单,我们只要把任意常数或者 variable copy 之后作为 get 的结果就行。

applicative pattern

我们继续拿 future 的一个问题作为例子,某些操作必须等所有被等待的 future 全部结束才能进行,对于同类型的,常见的是用一个 container 表示,如 vector<future<A>>,对于不同类型的,类似一个 tuple,future<A1>, future<A2>…,而 client code 往往是一个 B process(vector<A>) 或者 B process(A1, A2, …) 类型,这时我们需要提供一个 invert 操作将 vector<future<A>> 转换到 future<vector<A>> 或者 tuple<future<A1>, future<A2>, …> 转换到 future<tuple<A1, A2, …>>,有了这个操作,我们就能将 next 方法与其 compose 在一起了

future<A1> a1 = produce_a1();
future<A2> a2 = produce_a2();
when_all_done(a1, a2).next([](const A1& a1, const A2& a2) {
  return a1 + a2;
}).get();

事实上即便 Flume 的 code 里面也有类似的问题,但是却没有对应的 API 还需要我们去为它提供,比较悲哀啊。

说穿了 applicative pattern 就是要求允许 lifting n-ary function。这里的 when_all_done + next 完成了 n-ary function lifting。

monoid pattern

对应于等待所有 future 结束,另一个问题是任意一个结束(这也要求必须是相同类型的)。这个时候我们需要一个映射 M<A>(M<A>, M<A>) 它满足

  • 结合律:f(f(a, b), c) = f(a, f(b, c))
  • 存在幺元:f(a, o) = a、f(o, a) = a,这里的 o 可以是永远不 ready 的 future(称为 never)

很明显,这满足半群(monoid)的定义(群,group 要求所有元素存在逆元)。为此我们可以提供一个如下的 API

when_any(a1, a2).next(do_something).get();

这就是另一个重要的 pattern。

——————
But the Lord was with Joseph, and shewed him mercy, and gave him favour in the sight of the keeper of the prison

Advertisements
FPL 拾遗(1)

猥琐 anagram 程序一枚

很久不写 scala 纯粹练习,经典游戏你画我猜某些情况下因为单词量不够,需要一些程序的帮助,本质上就是个 anagram 搜索,我们用 mac 上的字典文件生成一个字典,然后根据提示的字母搜索可能的单词组合,然后结合图像信息就能更容易求解一些抽象的概念,特别是画画的人画不清楚的 case

object Anagram {
  def narrow(ss: Seq[String]): String = {
    ss.map(_.sorted).reduce(_ intersect _)
  }
}

class Anagram {
  val dict = scala.io.Source.fromFile("/usr/share/dict/words").getLines
    .map { word =>
    (word, word.toLowerCase.sorted)
  }.toList.groupBy(_._2)

  def search(s: String, l: Int): Set[String] = {
    val subs = s.combinations(l).map(_.sorted).toSet
    (for {
      sub <- subs if dict.contains(sub)
    } yield dict(sub)).flatten.map(_._1)
  }
}

object Main extends App {
  var ok = true
  val solver = new Anagram
  while (ok) {
    print("> ")
    val s = readLine()
    if (s.isEmpty) ok = false
    else {
      println("Candidates are")
      val f = s.split(",")
      solver.search(Anagram.narrow(f.tail), f.head.toInt).map(println)
    }
  }
}

执行如下

$ scalac-2.10 anagram.scala
$ scala-2.10 Main
> 5,qiglotyvjrey,uxeolgeyztod
Candidates are
goyle
geoty
goety

——————
And Shechem said unto her father and unto her brethren, Let me find grace in your eyes, and what ye shall say unto me I will give

猥琐 anagram 程序一枚

continuation 的支持

如前文讨论的通过 CPS 可以实现一定程度的 continuation,还有不少语言内置了对 continuation 的支持。在 imperative programming 的世界里,乃至一般性 functional programming 的世界里,函数的基本抽象仍然是主流行为,其实现主要还是依赖调用和返回两个概念,而 continuation 的应用与此是背道而行:与其返回比如执行下一步要干啥,我们比较下面的一个过程:

val b: A = f (a)
val c: C = g (a, b)
val d: D = h (a, b, c)

如果需要改写成为 CPS 的话则为

def f (a: A) (bb: B => Unit) : Unit {
  // do something about a and compute b
  bb (b)
}
def g (a: A, b: B) (cc: C => Unit): Unit {
  // do something about a and b and compute c
  cc (c)
}
def h (a: A, b: B, c: CC) (dd: D => Unit) {
  // do something about a, b and c and compute d
  dd (d)
}

f (a) {b =>
  g (a, b) { c =>
    h (a, b, c) { d =>
      Unit
    }
  }
}

这个过程可以用函数调用本身来书写,但是的确没有必要编译成为函数的调用返回这种形式。因此一种合理的策略是以某种形式暗示编译器这种代码应该编译成为另外一种样子。另外一个问题是 CPS 本身是传染性的,在一个 CPS 不占主导的程序里面如何将这段 CPS 与其他的代码交互(获得输入,产生输出),这也是一个难的问题。事实上,scala 为了解决这个问题使用了 delimited continuation,除了我们需要通过 -P:continuations:enable 打开编译器插件以外,我们还需要使用 scala.util.continuations._ 提供的 DSL。

这个 DSL 中重要的是 reset/shift 这两个东西,reset 这个部分标志着 CPS 的开始,其中有若干 shift 产生的对象,每个这个对象都有点内外颠倒的感觉,因为 shift 本身对应的是 continuation 部分,也就是说其中有个函数表示的是结束后应该干啥,如何产生这个函数的输入却是在 reset 里面实现的:

reset {
  shift { f: (Int => Int) => f(2)
  } + 1
}

这个例子我们看到 shift 产生的对象如果记为 r,则 r + 1 表示的是一个 Int => Int 的函数,这正是 f 的定义,因此这个 continuation 对应的结果就是 2 + 1 = 3。为了将这个 reset 块中的 shift 分离出去,写成“函数”形式以便重用,scala 提供了 @cps/@cpsParam 这个 annotation:

def bar (n: Int) : Int @cps[Int] = shift {f: (Int => Int) => f(2)} + n
def foo (a: Int) = reset { bar(a) }

值得注意的是 reset 中的 shift 具有嵌套性质,shift 对应的那个 f 其实是将 reset 中它之后的所有部分当作一个 closure,因此之后的 shift 就被嵌套在之前的 shift 里面形成了前面我们看到的 CPS 的形式。如此 API 究竟有什么好处呢?有空继续看几个库…

与 scala 不同的是 C++ 并没有提供 continuation 的支持,有人试图为 C++ 提供类似的库,还有人说 boost.phoenix 里面有(即便没有使用 C++11 的 lambda)粗看一下 phoenix 的介绍里面确实是说为 C++ 提供了 functional programming,不知道里面哪个部分实现了 CPS,记得 boost.spirit 用它的 lambda 的… Java 里面尙没有把函数当成 first-type class,不知道到 JDK 8 是否会出现一些这方面的东西。

——————
And said unto them, I see your father’s countenance, that it is not toward me as before; but the God of my father hath been with me.

continuation 的支持