[关闭]
@MiloXia 2015-03-23T13:34:09.000000Z 字数 4874 阅读 3371

面向组合子编程

函数式编程

本文是看完系列博文：面向组合子编程系列 ［http://www.blogjava.net/ajoo/category/6968.html］以及自己联系Clojure和Scala之后所总结的

什么是组合子

我们先从组合子逻辑下手
维基百科上对组合子逻辑完整的解释：http://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E5%AD%90%E9%80%BB%E8%BE%91

计算中的组合子逻辑
在计算机科学中，组合子逻辑被用做可计算性理论中计算和证明论的简化模型。这个理论尽管简单，但捕获了计算本质的很多根本特征。

组合子逻辑可以被看作是lambda演算的变体，它把lambda表达式（用来允许函数抽象）替代为组合子的有限集合，它们是不包含自由变量的原始函数。很容易把lambda表达式变换成组合子表达式，并且因为组合子归约比lambda归约要简单，它已经被用做用软件中的某些非严格的函数式编程语言和硬件的图归约机的实现基础。

还可以用很多其他方式来看待它，很多早年的论文证明了各种组合子到各种逻辑公理的等价性[Hindley and Meredith, 1990]。

组合子演算
因为在lambda演算中抽象是制造函数的唯一方式，在组合子演算中必须有某种东西替代它。不再使用抽象，组合子演算提供了有限的基本函数的集合，其他函数可以用它们来构建。

看不懂没关系
组合子逻辑自然就是一组组合子互相组合而组成的逻辑，称之为高阶逻辑（highor-order logic）［后续还会提到］
[本人数学sense有限]
lambda演算： http://blog.csdn.net/feosun/article/details/2110116

在 lambda 演算中，每个表达式都代表一个只有单独参数的函数，这个函数的参数本身也是一个只有单一参数的函数，同时，函数的值是又一个只有单一参数的函数。函数是通过 lambda 表达式匿名地定义的，这个表达式说明了此函数将对其参数进行什么操作。
是一种更common的计算表达形式，旨在消除有名函数的数量，看lisp的S-表达式就非常明显：函数的互相嵌套调用的形式（注：lambda演算 不是lambda表达式）
如Clojure：

  1. ;lambda演算
  2. (loop [s 0 coll (for [c (for [c `(1, 2, 3)] (+ 1 c)) 
  3.     :when (> c 2)] c)]
  4.   (if (nil? (first coll)) s
  5.     (recur (+ s (first coll)) (next coll))))
  7. ;=> 7

lambda演算和combinator逻辑是等价的，可以转换的；应用一组组合子可以将lambda演算转换为combinator逻辑；
定义一组组合子

  1. ;一组组合子T[]
  2. (defn c-map [f coll]
  3.   (for [c coll] (f c)))
  5. (defn c-filter [f coll]
  6.   (for [c coll :when (f c)] c))
  8. (defn c-reduce [f coll]
  9.   (if (nil? (first coll)) 0
  10.     (f (c-reduce f (next coll)) (first coll))))

那么就可以将上面的T[]应用在lambda演算中

  1. ;combinator演算
  2. (c-reduce #(+ %1 %2)
  3.     (c-filter #(> % 2) 
  4.         (c-map #(+ % 1) `(1,2,3))))
  6. ;=> 7

T[lambda演算] = combinator演算
也就是维基上写的：T[λx.λy.(y x)] = (S (K (S I)) (S (K K) I))
组合子逻辑必须是一组组合子，而lambda演算则是一组函数的应用和组合，所以很明显：
combinator是process/行为/function 或一组process 而不是obj或class

Clojure和Scala集合库有几个基本的组合子（最简组合子）

  1. map,foreach,filter,fold/reduce zip flatten ...

这才是组合子逻辑
Scala:

  1. List(1, 2, 3).map(_ + 1).filter(_ > 2).reduce(_ + _)

或 Clojure:

  1. (reduce #(+ %1 %2)
  2.     (filter #(> % 2) 
  3.         (map #(+ % 1) `(1,2,3))))

这在我们项目中其实随处可见
这就是高阶逻辑，我们总是在表达我们要干什么，而不像java那样动不动就是开始循环迭代各种分支，表达在干嘛那是一种低阶逻辑
组合子的组合形成高阶逻辑
（暴露底层逻辑 我不觉得不好，但是可读性上肯定会打折扣）
单子也可以是组合子（不一定是最简组合子）
总结：

什么最简组合子

引用ajoo的话:

组合子,英文叫combinator,是函数式编程里面的重要思想。如果说OO是归纳法(分析归纳需 求,然后根据需求分解问题,解决问题),那么 “面向组合子”就是“演绎法”。通过定义最基本的原 子操作,定义基本的组合规则,然后把这些原子以各种方法组合起来。

这里所说的基本原子就是最简组合子
比如map操作，是一种原子操作，代表这映射；注意‘代表’意味这这是一个抽象接口，而不是具体的process；不同类型的map操作语义不同，如List的map和Option的map，这些具体的实现才是真的最简组合子

任何组合子系统的建立，都起步于最最基本最最简单的组合子
比如，布尔代数必然起步于true和false；自然数起步于0，1，然后就可以推演出整个系统。

总结：

Scala面向组合子编程

Scala里组合子应该定义为type class也可以像java一样表达为抽象接口
Clojure表达为多重方法(defmulti)或者协议(defprotocol 允许对现有数据类型进行非侵略性对扩展，解决抽象接口的缺点)
type class 可参考：https://www.zybuluo.com/MiloXia/note/72592
举个例子
有个X类型不支持c操作，怎么让它支持？
typeclass和多重方法相似，typeclass的意义：
对某个类型,在不改动其本身的情况下,具备了扩展其行为的能力
所以typeclass比抽象接口的方式更强大

最简组合子：
表示为 实现不同最简组合子type class的具体高阶类型
组合子：
用[C: TP1 : TP2]的context bind语法来实现最简组合子的组合
使用XXXOps的隐转 使其看上去更自然 以obj.c1.c2的形式调用 而不像Clojure那般的嵌套形式

下面演示一下：

  1. //type class
  2. //map组合子定义
  3. trait CMap[T[_]] {
  4.   def map[A, B](x : T[A])(f : A => B) : T[B]
  5. }
  6. //filter组合子定义
  7. trait CFilter[T[_]] {
  8.   def filter[A](x : T[A])(f: A => Boolean) : T[A]
  9. }
  11. //map组合子具体实现
  12. object CMap {
  13.   implicit object ListMap extends CMap[List] {
  14.     override def map[A, B](x: List[A])(f : A => B) : List[B] = x.map(f(_))
  15.   }
  16.   implicit object SetMap extends CMap[Set] {
  17.     override def map[A, B](x: Set[A])(f : A => B) : Set[B] = x.map(f(_))
  18.   }
  20.   //def map[T[_]: CMap, A, B](x: T[A])(f : A => B): T[B] = {
  21.   //  implicitly[CMap[T]].map(x)(f)
  22.   //}
  23. }
  25. //filter组合子实现
  26. object CFilter {
  27.   implicit object ListFilter extends CFilter[List] {
  28.     override def filter[A](x: List[A])(f : A => Boolean) : List[A] = x.filter(f(_))
  29.   }
  30.   implicit object SetFilter extends CFilter[Set] {
  31.     override def filter[A](x: Set[A])(f : A => Boolean) : Set[A] = x.filter(f(_))
  32.   }
  34.   //def filter[T[_]: CFilter, A](x: T[A])(f : A => Boolean): T[A] = {
  35.   //  implicitly[CFilter[T]].filter(x)(f)
  36.   //}
  37. }
  38. //xxxOps的隐转
  39. object COImplicit {
  40.   implicit def cmapOps[T[_]: CMap, A](m: T[A]) = new {
  41.     val cMap = implicitly[CMap[T]]
  42.     def cmap[B](f: A => B): T[B] = cMap.map(m)(f)
  43.   }
  44.   implicit def cfilterOps[T[_]: CFilter, A](m: T[A]) = new {
  45.     val cFilter = implicitly[CFilter[T]]
  46.     def cfilter(f: A => Boolean): T[A] = cFilter.filter(m)(f)
  47.   }
  48. }
  50. object COTest extends App {
  51.   import COImplicit._
  53.   println(List(1,2,3).cmap(_ + 1).cfilter(_ > 2))
  54.   println(Set(1,2,3).cmap(_ + 1).cfilter(_ > 2))
  55. }

当需要map和filter两个最简组合子组合而成的新组合子，举个例子: InAndMap 在满足一个集合范围的元素才执行map操作

  1. //在COImplicit中新加
  2. implicit def cinAndMapOps[T[_]: CFilter : CMap, A](m: T[A]) = new {
  3.     val cFilter = implicitly[CFilter[T]]
  4.     val cMap = implicitly[CMap[T]]
  5.     def cInAndMap[B](in: Set[A])(f: A => B): T[B] = cMap.map(cFilter.filter(m)(in))(f)
  6.   }
  8. println(List(1,2,3).cInAndMap(Set(2,3))(_ + 1))

总结：

面向组合子设计

这和面向对象一样是有难度的事情，难度在于最简组合子的把握，如何自下而上的定义一套组合子，并且在组合之后满足需求
只能列几条common的rule了
从最简组合子开始，在组合产生新组合子过程中不断重构调整最简
要想一下子明确定义出S，K，I 的组合子还是很难的。

限制和使用范围

组合子是一种自低向上的设计方式，适合表达单一概念
比如Clojure的delay和force宏(特殊的函数)是一组用来做lazy的组合子
同理Scala的view和force
Clojure的并发库定义了一些组合子: ref、ref-set、dosync、alter/commute 实现了STM

  1. (def messages (ref ()))
  2. (defn add-message [msg]
  3.     (dosync (alter messages conj msg)))

或者SQL 那样的select from join where group order 来表达查询
面向组合子编程系列 的例子我没有用Scala写一遍，我打算用面向组合子的方式来实现一个自己的并发库和异步IO库，希望我成功吧^_^

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注