Lodash 源码分析（二）“Function” Methods

Posted on Posted on |in tech|by terasum

前言

这是Lodash源码分析的第二篇文章，我们在第一篇Lodash 源码分析（一）“Function” Methods中介绍了基本的_.after，_.map，以及复杂的_.ary函数的实现以及我们自己的自定义轻量级版本。大概清楚了Lodash的整个代码脉络。这次我们继续分析，这次我们讲讲_.reduce和_.curry。

继续阅读 “Lodash 源码分析（二）“Function” Methods”

Go 线程调度器

Posted on Posted on |in tech|by terasum

前言

在Go1.1版本中，加入了由Dmitry Vyukov贡献的新的调度器。新的调度器能够动态地调整Go程序的并发性能，而且表现非常出色。因此我想写篇文章介绍一下这个调度器。

这篇博客里面大多数东西都已经被包含在了原始设计文档中了，这个文档的内容相当详实，但是过于技术化了。

虽然有关新调度器所有东西都在那个设计文档中，但这篇博客有图片配图了，所以比设计文档清晰易懂多了。

Go运行时为什么需要调度器？

在我们开始研究新调度器之前，我们首先需要理解为什么需要调度器。既然操作系统已经能够为我们调度线程了，我们为什么又创造了一个用户实现的调度器？

POSIX的线程API是对现有Unix进程模型在逻辑上的一个强大大的扩展，使得线程得到了很多类似进程的控制能力。比如，线程有它自己的信号码，线程能够被赋予CPU affinity功能(就是指定线程只能在某个CPU上运行），线程能被添加到cgroups中，线程所占用的的资源也能够查询。这些额外特性大大增加了Go 程序在创建goroutine 时所需要的开销，是在线程多达100000的时候尤其明显。

另外一个问题是，操作系统无法针对Go的设计模型给出很好的调度决策。比如，当运行一次垃圾收集的时候，Go的垃圾收集器要求所有线程都被暂停，并且要求内存要处于一致状态（consistent state）。这就要求所有等待所有正在运行的线程到同时达到一个一致点，而我们事先知道在这个一致点内存是一致的。

当很多被调度的线程分散在随机点（random point）上时，你不得不等待他们中的大多数到达一致状态才能进行垃圾回收。而Go调度器却能够只在内存一致的时候进行调度，这就意味着我们只需要等待在一个CPU核心中的活跃线程达到一致即可。

来看看里面的各个角色（Our Cast of Characters）

目前有三个常见的线程模型。一个是N：1的，即多个用户空间线程运行在一个OS线程上。这个模型可以很快的进行上下文切换，但是不能利用多核系统（multi-core systems)的优势。另一个模型是1：1的，即可执行程序的一个线程匹配一个OS线程。这个模型能够利用机器上的所有核心的优势，但是上下文切换非常慢，因为它需要进行系统内核调用。

Go试图通过M：N的调度器去获取这两种模型的全部优势。它在任意数目的OS线程上调用任意数目的goroutines。你可以快速进行上下文切换，并且还能利用你系统上所有的核心的优势。这个模型主要的缺点是它增加了调度器的复杂性。

为了完成调度任务，Go调度器使用了三个实体：

三角形表示OS线程，它是由OS管理的可执行程序的一个线程，而且工作起来特别像你的标准POSIX线程。在运行时代码里，它被成为M，即机器（machine）。

圆形表示一个goroutine。它包括栈、指令指针以及对于调度goroutines很重要的其它信息，比如阻塞它的任何channel。在运行时代码里，它被称为G。

矩形表示调度上下文。你可以把它看作是一个在单线程上进行线程调度的自定义版本。它是让我们从N:1调度器转到M:N调度器的重要部分。在运行时代码里，它被叫做P，即处理器（processor）。这部分将会进行较为详细的介绍。

我们可以从上面的图里看到两个线程（M），每个线程都拥有一个上下文（P），每个线程都正在运行一个goroutine（G）。为了运行goroutines，一个线程必须拥有一个上下文。

上下文的数目在启动时被设置为环境变量GOMAXPROCS的值或者通过运行时函数GOMAXPROCS()来设置。通常，在你的程序执行时它不会发生变化。上下文的数目被固定的意思是，只有GOMAXPROCS个上下文正在任意时刻上运行Go代码。我们可以使用它调整Go进程的调用使其适合于一个单独的计算机，比如一个4核的PC中可以在4个线程上运行Go代码。

外部的灰色goroutines没在运行，但是已经准备好被调度了。它们被安排成一个叫做runqueue的列表。当一个goroutine执行一个go 语句的时候，goroutine就被添加到runqueue的末端。一旦一个上下文已经运行一个goroutine到了一个点上，它就会把一个goroutine从它的runqueue给pop出来，设置栈和指令指针并且开始运行这个goroutine。

为了降低mutex竞争，每一个上下文都有它自己的运行队列。在Go调度器的早期版本中，Go的调度器只有一个全全局的运行队列，并且只有一个互斥锁(mutex)来保护它。这样的设计在32核的多CPU核机器上进行性能压榨时往往会得到较差的表现。

只要有goroutine在运行，调度器就能够以一个稳定的状态运行。然而还是有一些情况能够改变这种状态。

系统调用细节

你可能想问，为什么一定要有上下文？我们能不能去掉上下文而把运行队列直接放到线程上运行？不可以，上下文存在的意义是，如果一个正在运行的线程因为一些原因需要阻塞，我们可以将其挂起并将线程上下文移交给别的线程。

另一种需要阻塞的情况是，在进行系统调用的时候。因为一个线程在进行系统调用的时候不能既执行代码又进行阻塞等待（注：一个M控制多个G,在系统调用的时候不允许其中的某个G阻塞，而另一个G运行，因为系统调用必须是原子性的）。因此我们需要将该上下文冻结以便调度。

从上图我们能够看出，一个线程放弃了它的上下文以便让别的的线程可以运行G0。调度器确保预先有足够的线程来运行所有的上下文。上图中的M1 可能是仅仅为了能够处理系统调用而创建的，也可能来自一个线程池。这个处于系统调用中的线程将会一直持有导致这次系统调用这的goroutine，因为从技术层面上来说，它仍然在执行，尽管可能阻塞在OS里了。

当这个系统调用返回的时候，这个线程必须获取一个上下文来运行这个返回的goroutine。较为常见的操作是从其它线程中“偷取”一个上下文。如果“偷取”不成功，它就会把它的goroutine放回到一个全局运行队列中，然后把自己放回到线程池中然后进入睡眠状态。

这个全局运行队列是各个上下文在运行完自己的本地运行队列后获取新goroutine的地方。上下文也会周期性的检查这个全局运行队列上的以获取goroutine。如果不这样做的话，全局运行队列上的goroutines由于饥渴可能导致无法执行而终止。

Go程序要在多线程上运行就是因为要处理系统调用，哪怕GOMAXPROCS等于1。运行时使用调用系统调用的goroutines，而不是线程。

盗取工作

系统的稳定状态改变的另外一种情况是，当一个上下文运行完要被调度的所有goroutines的时。如果各个上下文的运行队列里的goroutine的数目不均衡，将会改变调度器状态。上述的情况会导致会导致一个上下文在执行完它的运行队列后就结束了，尽管系统中仍然有许多goroutine要执行。因此为了能够一直运行Go代码，一个上下文能够从全局运行队列中获取goroutine，但是如果全局运行队列中也没有goroutine了，那么上下文就不得不从其它地方获取goroutine了。

这里的“其它地方”指的是就是其它的上下文！当一个上下文完成自己的全部任务后，它就会尝试“盗取”另一个上下文运行队列中一半的工作量。这将确保每个上下文总是有活干，同时也能够保证所有的线程都处于最大的负荷。

展望

关于调度器还有许多细节，像cgo线程、LockOSThread()函数以及与系统与网络poller的整合。这些已经超过这篇文章的要探讨的范围了，但是仍然值得去深入研究。在Go运行时库里，仍然有大量有意思的创建工作要做。

原文 Daniel Morsing
翻译 Chen Quan

Releated articles:

Lodash 源码分析（一）“Function” Methods

Posted on Posted on |in tech|by terasum

前言

Lodash一直是我很喜欢用的一个库，代码也十分简洁优美，一直想抽时间好好分析一下Lodash的源代码。最近抽出早上的一些时间来分析一下Lodash的一些我觉得比较好的源码。因为函数之间可能会有相互依赖，所以不会按照文档顺序进行分析，而是根据依赖关系和简易程度由浅入深地进行分析。因为个人能力有限，如果理解有偏差，还请直接指出，以便我及时修改。

源码都是针对4.17.4版本的，源docs写得也很好，还有很多样例。

##_.after

_.after函数几乎是Lodash中最容易理解的一个函数了，它一共有两个参数，第一个参数是调用次数n,第二个参数是n次调用之后执行的函数func。

function after(n, func) {
      if (typeof func != 'function') {
        throw new TypeError(FUNC_ERROR_TEXT);
      }
      n = toInteger(n);
      return function() {
        if (--n < 1) {
          return func.apply(this, arguments);
        }
      };
    }

这个函数的核心代码就是：

func.apply(this,arguments);

但是一定要注意，这个函数中有闭包的应用，就是这个参数n。n本应该在函数_.after返回的时候就应该从栈空间回收，但事实上它还被返回的函数引用着，一直在内存中：

return function() {
        if (--n < 1) {
          return func.apply(this, arguments);
        }
      };

所以一直到返回的函数执行完毕，n所占用的内存空间都无法被回收。

我们再来看看这个apply函数，我们知道apply函数可以改变函数运行时的作用域了，那么问题来了，在在_.after函数中func.apply函数的this，是谁呢？这个东西我们没有办法从源码中看出来，因为this是在运行时决定的。那么this会变吗？如果会的话怎么变呢？这个问题我们需要先弄懂_.after函数怎么用。

_.after函数调用后返回了另一个函数，所以对于_.after函数的返回值，我们是需要再次调用的。所以最好的场景可能是在延迟加载等场景中。当然为了简单起见我给出一个很简单的例子：

const _ = require("lodash");

function foo(func ){
    console.log("invoked foo.");
    func();
}


var done = _.after(2,function bar(){
    console.log("invoke bar");
});

for( var i = 0; i <  4; i++ ){
   foo(done);
}

正如我们前面说的，n的作用域是_.after函数内部，所以在执行过程中n会一直递减，因此输出结果应该是在调用两次foo之后调用一次bar，之后每次调用foo，都会调用一次bar。结果和我们预期的一致：

invoked foo
invoked foo
invoke bar
invoked foo
invoke bar
invoked foo
invoke bar

那么我们再看看this指向的问题，我们修改一下上面的调用函数，让bar函数输出一下内部的this的一些属性：

const _ = require("lodash");

function foo(func ){
    this.name = "foo";
    console.log("invoked foo: " + this.name );
    func();
}


var done = _.after(2,function bar(){
    console.log("invoke bar: " + this.name);
});

for( var i = 0; i <  4; i++ ){
   foo(done);
}

其实想来大家也应该能够猜到，在bar函数中输出的this.name也是foo：

invoked foo: foo
invoked foo: foo
invoke bar: foo
invoked foo: foo
invoke bar: foo
invoked foo: foo
invoke bar: foo

这是因为bar的this应该指向的是_.after创建的函数的this,而这个函数是由foo函数调用的，因此this实际上指向就是foo。

_.map

_.map函数我们几乎随处可见，这个函数应用也相当广泛。

function map(collection, iteratee) {
      var func = isArray(collection) ? arrayMap : baseMap;
      return func(collection, getIteratee(iteratee, 3));
}

为了简化问题，我们分析比较简单的情况：用一个func函数处理数组。

_.map([1,2,3],func);

在处理数组的时候，lodash是分开处理的，对于Array采用arrayMap进行处理，对于对象则采用baseMap进行处理。

我们先看数组arrayMap：

function arrayMap(array, iteratee) {
    var index = -1,
        length = array == null ? 0 : array.length,
        result = Array(length);

    while (++index < length) {
      result[index] = iteratee(array[index], index, array);
    }
    return result;
  }

这个函数是一个私有函数，第一个参数是一个需要遍历的数组，第二个参数是在遍历过程当中进行处理的函数；返回一个进行map处理之后的函数。

在看我们需要进行遍历处理的函数iteratee，这个函数式通过getIteratee函数得到的：

function getIteratee() {
      var result = lodash.iteratee || iteratee;
      result = result === iteratee ? baseIteratee : result;
      return arguments.length ? result(arguments[0], arguments[1]) : result;
    }

如果lodash.iteratee被重新定义,则使用用户定义的iteratee，否则就用官方定义的baseIteratee。需要强调的是，result(arguments[0],arguments[1])是柯里化的函数返回，返回的仍旧是一个函数。不可避免地，我们需要看看官方定义的baseIteratee的实现：

   function baseIteratee(value) {
      // Don't store the `typeof` result in a variable to avoid a JIT bug in Safari 9.
      // See https://bugs.webkit.org/show_bug.cgi?id=156034 for more details.
      if (typeof value == 'function') {
        return value;
      }
      if (value == null) {
        return identity;
      }
      if (typeof value == 'object') {
        return isArray(value)
          ? baseMatchesProperty(value[0], value[1])
          : baseMatches(value);
      }
      return property(value);
    }

我们可以看出来，这个iteratee迭代者其实就是一个函数，在_.map中getIteratee(iteratee, 3)，给了两个参数，按照逻辑，最终返回的是一个baseIteratee，baseIteratee的第一个参数value就是iteratee,这是一个函数，所以，baseIteratee函数在第一个判断就返回了。

所以我们可以将map函数简化为如下版本:

function map(collection,iteratee){
    return arrayMap(collection,getIteratee(iteratee,3));
}

function arrayMap(array, iteratee) {
    var index = -1,
        length = array == null ? 0 : array.length,
        result = Array(length);

    while (++index < length) {
      result[index] = iteratee(array[index], index, array);
    }
    return result;
}

function getIteratee() {
      var result =  baseIteratee;
      return arguments.length ? result(arguments[0], arguments[1]) : result;
}

function baseIteratee(value) {
      if (typeof value == 'function') {
        return value;
      }
}

可以看到，最终调用函数func的时候会传入3个参数。array[index],index,array。我们可以实验，将func实现如下：

function func(){
   console.log(“arguments[0] ” + arguments[0]);
   console.log(“arguments[1] ” + arguments[1]);
   console.log(“arguments[2] ” + arguments[2]);
   console.log("-----")
}

输出的结果也和我们的预期一样，输出的第一个参数是该列表元素本身，第二个参数是数组下标，第三个参数是整个列表：

arguments[0] 6
arguments[1] 0
arguments[2] 6,8,10
-----
arguments[0] 8
arguments[1] 1
arguments[2] 6,8,10
-----
arguments[0] 10
arguments[1] 2
arguments[2] 6,8,10
-----
[ undefined, undefined, undefined ]

上面的分析就是抛砖引玉，先给出数组的分析，别的非数组，例如对象的遍历处理则会走到别的分支进行处理，各位看官有兴趣可以深入研究。

_.ary

这个函数是用来限制参数个数的。这个函数咋一看好像没有什么用，但我们考虑如下场景，将一个字符列表['6','8','10']转为整型列表[6,8,10]，用_.map实现，我们自然而然会写出这样的代码：

const _ = require("lodash");
_.map(['6','8','10'],parseInt);

好像很完美，我们输出看看：

[ 6, NaN, 2 ]

很诡异是不是，看看内部到底发生了什么？其实看了上面的-.map函数的分析，其实原因已经很明显了。对于parseInt函数而言，其接收两个参数，第一个是需要处理的字符串，第二个是进制：

/**
* @param string 必需。要被解析的字符串。
* @param radix  
* 可选。表示要解析的数字的基数。该值介于 2 ~ 36 之间。
* 如果省略该参数或其值为 0，则数字将以 10 为基础来解析。如果它以 “0x” 或 “0X” 开头，将以 16 为基数。
* 如果该参数小于 2 或者大于 36，则 parseInt() 将返回 NaN
*/
parseInt(string, radix)
/**
当参数 radix 的值为 0，或没有设置该参数时，parseInt() 会根据 string 来判断数字的基数。

举例，如果 string 以 "0x" 开头，parseInt() 会把 string 的其余部分解析为十六进制的整数。如果 string 以 0 开头，那么 ECMAScript v3 允许 parseInt() 的一个实现把其后的字符解析为八进制或十六进制的数字。如果 string 以 1 ~ 9 的数字开头，parseInt() 将把它解析为十进制的整数。
*/

那么这样的输出也就不难理解了：

处理第一个数组元素6的时候，parseInt实际传入参数(6,0),那么按照十进制解析，会得到6,处理第二个数组元素的时候传入的实际参数是(8,1)，返回NaN,对于第三个数组元素，按照2进制处理，则10返回的是2。

所以在上述需求的时候我们需要限制参数的个数，这个时候_.ary函数就登场了，上面的函数这样处理就没有问题了：

const _ = require("lodash");
_.map(['6','8','10'],_.ary(parseInt),1);

我们看看这个函数是怎么实现的：

 function ary(func, n, guard) {
      n = guard ? undefined : n;
      n = (func && n == null) ? func.length : n;
      return createWrap(func, WRAP_ARY_FLAG, undefined, undefined, undefined, undefined, n);
    }

这个函数先检查n的值，需要说明的是func.length返回的是函数的声明参数个数。然后返回了一个createWrap包裹函数，这个函数可以说是脏活累活处理工厂了，负责很多函数的包裹处理工作，而且为了提升性能，还将不同的判断用bitflag进行与/非处理，可以说是很用尽心机了。

/**
     * Creates a function that either curries or invokes `func` with optional
     * `this` binding and partially applied arguments.
     *
     * @private
     * @param {Function|string} func The function or method name to wrap.
     * @param {number} bitmask The bitmask flags.
     *    1 - `_.bind` 1                      0b0000000000000001
     *    2 - `_.bindKey`                     0b0000000000000010
     *    4 - `_.curry` or `_.curryRight`...  0b0000000000000100
     *    8 - `_.curry`                       0b0000000000001000
     *   16 - `_.curryRight`                  0b0000000000010000
     *   32 - `_.partial`                     0b0000000000100000
     *   64 - `_.partialRight`                0b0000000001000000
     *  128 - `_.rearg`                       0b0000000010000000
     *  256 - `_.ary`                         0b0000000100000000
     *  512 - `_.flip`                        0b0000001000000000
     * @param {*} [thisArg] The `this` binding of `func`.
     * @param {Array} [partials] The arguments to be partially applied.
     * @param {Array} [holders] The `partials` placeholder indexes.
     * @param {Array} [argPos] The argument positions of the new function.
     * @param {number} [ary] The arity cap of `func`.
     * @param {number} [arity] The arity of `func`.
     * @returns {Function} Returns the new wrapped function.
     */
    function createWrap(func, bitmask, thisArg, partials, holders, argPos, ary, arity) {
      var isBindKey = bitmask & WRAP_BIND_KEY_FLAG;
      if (!isBindKey && typeof func != 'function') {
        throw new TypeError(FUNC_ERROR_TEXT);
      }
      var length = partials ? partials.length : 0;
      if (!length) {
        bitmask &= ~(WRAP_PARTIAL_FLAG | WRAP_PARTIAL_RIGHT_FLAG);
        partials = holders = undefined;
      }
      ary = ary === undefined ? ary : nativeMax(toInteger(ary), 0);
      arity = arity === undefined ? arity : toInteger(arity);
      length -= holders ? holders.length : 0;

      if (bitmask & WRAP_PARTIAL_RIGHT_FLAG) {
        var partialsRight = partials,
            holdersRight = holders;

        partials = holders = undefined;
      }
      var data = isBindKey ? undefined : getData(func);

      var newData = [
        func, bitmask, thisArg, partials, holders, partialsRight, holdersRight,
        argPos, ary, arity
      ];

      if (data) {
        mergeData(newData, data);
      }
      func = newData[0];
      bitmask = newData[1];
      thisArg = newData[2];
      partials = newData[3];
      holders = newData[4];
      arity = newData[9] = newData[9] === undefined
        ? (isBindKey ? 0 : func.length)
        : nativeMax(newData[9] - length, 0);

      if (!arity && bitmask & (WRAP_CURRY_FLAG | WRAP_CURRY_RIGHT_FLAG)) {
        bitmask &= ~(WRAP_CURRY_FLAG | WRAP_CURRY_RIGHT_FLAG);
      }
      if (!bitmask || bitmask == WRAP_BIND_FLAG) {
        var result = createBind(func, bitmask, thisArg);
      } else if (bitmask == WRAP_CURRY_FLAG || bitmask == WRAP_CURRY_RIGHT_FLAG) {
        result = createCurry(func, bitmask, arity);
      } else if ((bitmask == WRAP_PARTIAL_FLAG || bitmask == (WRAP_BIND_FLAG | WRAP_PARTIAL_FLAG)) && !holders.length) {
        result = createPartial(func, bitmask, thisArg, partials);
      } else {
        result = createHybrid.apply(undefined, newData);
      }
      var setter = data ? baseSetData : setData;
      return setWrapToString(setter(result, newData), func, bitmask);
    }

看上去太复杂了，把无关的代码削减掉：

function createWrap(func, bitmask, thisArg, partials, holders, argPos, ary, arity) {
      //      0000000100000000 & 0000000000000010
      // var isBindKey = bitmask & WRAP_BIND_KEY_FLAG;
      var isBindKey = 0;
      var length =  0;
      // if (!length) {
        //              0000000000100000 | 0000000001000000
        //            ~(0000000001100000)
        //              1111111110011111
        //             &0000000100000000
        //              0000000100000000 = WRAP_ARY_FLAG 
        // bitmask &= ~(WRAP_PARTIAL_FLAG | WRAP_PARTIAL_RIGHT_FLAG);
      //  bitmask = WRAP_ARY_FLAG;
      //  partials = holders = undefined;
      // }
      bitmask = WRAP_ARY_FLAG;
      partials = holders = undefined;
      ary = undefined;
      arity = arity === undefined ? arity : toInteger(arity);
      // because holders == undefined
      //length -= 0;
      // because isBindKey  == 0
      // var data = isBindKey ? undefined : getData(func);
      var data = getData(func);
      var newData = [
        func, bitmask, thisArg, partials, holders, partialsRight, holdersRight,
        argPos, ary, arity
      ];
      if (data) {
        mergeData(newData, data);
      }
      func = newData[0];
      bitmask = newData[1];
      thisArg = newData[2];
      partials = newData[3];
      holders = newData[4];
      arity = newData[9] = newData[9] === undefined
        ? func.length : newData[9];
      result = createHybrid.apply(undefined, newData);
      var setter = data ? baseSetData : setData;
      return setWrapToString(setter(result, newData), func, bitmask);
    }

简化了一些之后我们来到了createHybrid函数，这个函数也巨复杂，所以我们还是按照简化方法，把我们用不到的逻辑给简化:

   function createHybrid(func, bitmask, thisArg, partials, holders, partialsRight, holdersRight, argPos, ary, arity) {
      var isAry = bitmask & WRAP_ARY_FLAG,
          isBind = bitmask & WRAP_BIND_FLAG,
          isBindKey = bitmask & WRAP_BIND_KEY_FLAG,
          isCurried = bitmask & (WRAP_CURRY_FLAG | WRAP_CURRY_RIGHT_FLAG),
          isFlip = bitmask & WRAP_FLIP_FLAG,
          Ctor = isBindKey ? undefined : createCtor(func);

      function wrapper() {
        var length = arguments.length,
            args = Array(length),
            index = length;

        while (index--) {
          args[index] = arguments[index];
        }
        if (isCurried) {
          var placeholder = getHolder(wrapper),
              holdersCount = countHolders(args, placeholder);
        }
        if (partials) {
          args = composeArgs(args, partials, holders, isCurried);
        }
        if (partialsRight) {
          args = composeArgsRight(args, partialsRight, holdersRight, isCurried);
        }
        length -= holdersCount;
        if (isCurried && length < arity) {
          var newHolders = replaceHolders(args, placeholder);
          return createRecurry(
            func, bitmask, createHybrid, wrapper.placeholder, thisArg,
            args, newHolders, argPos, ary, arity - length
          );
        }
        var thisBinding = isBind ? thisArg : this,
            fn = isBindKey ? thisBinding[func] : func;

        length = args.length;
        if (argPos) {
          args = reorder(args, argPos);
        } else if (isFlip && length > 1) {
          args.reverse();
        }
        if (isAry && ary < length) {
          args.length = ary;
        }
        if (this && this !== root && this instanceof wrapper) {
          fn = Ctor || createCtor(fn);
        }
        return fn.apply(thisBinding, args);
      }
      return wrapper;
    }

把不需要的逻辑削减掉：

   function createHybrid(func, bitmask, thisArg, partials, holders, partialsRight, holdersRight, argPos, ary, arity) {
      var isAry = 1;
      function wrapper() {
        var length = arguments.length,
            args = Array(length),
            index = length;
        while (index--) {
          args[index] = arguments[index];
        }
        var thisBinding = this, fn = func;
        length = args.length;
        if (isAry && ary < length) {
          args.length = ary;
        }
        return fn.apply(thisBinding, args);
      }
      return wrapper;
    }

好了，绕了一大圈，终于看到最终的逻辑了，_.ary函数其实就是把参数列表重新赋值了一下，并进行了长度限制。想想这个函数实在是太麻烦了，我们自己可以根据这个逻辑实现一个简化版的_.ary：

function ary(func,n){
    return function(){
        var length = arguments.length,
            args = Array(length),
            index = length;
        while(index--){
            args[index] = arguments[index];
        }
        args.length = n;
        return func.apply(this,args);
    }
}

试试效果：

console.log(_.map(['6','8','10'],ary(parseInt,1)));

工作得很不错：

[ 6, 8, 10 ]

小结

今天分析这三个函数就花了一整天的时间，但是收获颇丰，能够静下心来好好分析一个著名的开源库，并能够理解透里面的一些逻辑，确实是一件很有意思的事情。我会在有时间的时候把Lodash这个我很喜欢的库都好好分析一遍，尽我最大的努力将里面的逻辑表述清楚，希望能够简明易懂。

Go实时GC——三色算法理论与实践

Posted on Posted on |in tech|by terasum

Go语言能够支持实时的，高并发的消息系统，在高达百万级别的消息系统中能够将延迟降低到100ms以下，着一切很大一部分需要归功于Go的高效的垃圾回收系统。

对于实时系统而言，垃圾回收系统可能是一个极大的隐患，因为在垃圾回收的时候需要将整个程序暂停。所以在我们设计消息总线系统的时候，需要小心地选择我们的语言。Go一直在强调它的低延迟，但是它真的做到了吗？如果是的，它是怎么做到的呢？

在这篇文章当中，我们将会看到Go语言的GC是如何实现的（tricolor algorithm，三色算法），以及为什么这种方法能够达到如此之低的GC暂停，以及最重要的是，它是否真的有效（对这些GC暂停进行benchmar测试，以及同其它类型的语言进行比较）。

From Haskell to Go

我们用pub/sub消息总线系统为例说明问题，这些系统在发布消息的时候都是in-memory存储的。在早期，我们用Haskell实现了第一版的消息系统，但是后面发现GHC的gabage collector存在一些基础延迟的问题，我们放弃了这个系统转而用Go进行了实现。

这是我们有关Haskell消息系统的一些实现细节,在GHC中最重要的一点是它GC暂停时间同当前的工作集的大小成比例关系（也就是说，GC时间和内存中存储对象的数目有关）。在我们的例子中，内存中存储对象的数目往往都非常巨大，这就导致gc时间常常高达数百毫秒。这就会导致在GC的时候整个系统是阻塞的。

而在Go语言中，不同于GHC的全局暂停(stop-the-world)收集器，Go的垃圾收集器是和主程序并行的。这就可以避免程序的长时间暂停。我们则更加关注于Go所承诺的低延迟以及其在每个新版本中所提及的延迟提升是否真的向他们所说的那样。

并行垃圾回收是如何工作的?

Go的GC是如何实现并行的呢？其中的关键在于tricolor mark-and-sweep algorithm 三色标记清除算法。该算法能够让系统的gc暂停时间成为能够预测的问题。调度器能够在很短的时间内实现GC调度，并且对源程序的影响极小。下面我们看看三色标记清除算法是如何工作的：

假设我们有这样的一段链表操作的代码：

var A LinkedListNode;
var B LinkedListNode;
// ...
B.next = &LinkedListNode{next: nil};
// ...
A.next = &LinkedListNode{next: nil};
*(B.next).next = &LinkedListNode{next: nil};
B.next = *(B.next).next;
B.next = nil;

第一步

var A LinkedListNode;

var B LinkedListNode;

// ...

B.next = &LinkedListNode{next: nil};

刚开始我们假设有三个节点A、B和C，作为根节点，红色的节点A和B始终都能够被访问到，然后进行一次赋值B.next = &C。初始的时候垃圾收集器有三个集合，分别为黑色，灰色和白色。现在，因为垃圾收集器还没有运行起来，所以三个节点都在白色集合中。

第二步

我们新建一个节点D,并将其赋值给A.next。即：

var A LinkedListNode;

var B LinkedListNode;

// ...

B.next = &LinkedListNode{next: nil};
// ...
A.next = &LinkedListNode{next: nil};

需要注意的是，作为一个新的内存对象，需要将其放置在灰色区域中。为什么要将其放在灰色区域中呢？这里有一个规则，如果一个指针域发生了变化，则被指向的对象需要变色。因为所有的新建内存对象都需要将其地址赋值给一个引用，所以他们将会立即变为灰色。（这就需要问了，为什么C不是灰色？）

第三步

在开始GC的时候，根节点将会被移入灰色区域。此时A、B、D三个节点都在灰色区域中。由于所有的程序子过程(process，因为不能说是进程，应该算是线程，但是在go中又不完全是线程)要么事程序正常逻辑，要么是GC的过程，而且GC和程序逻辑是并行的，所以程序逻辑和GC过程应该是交替占用CPU资源的。

第四步 扫描内存对象

在扫描内存对象的时候，GC收集器将会把该内存对象标记为黑色，然后将其子内存对象标记为灰色。在任一阶段，我们都能够计算当前GC收集器需要进行的移动步数：2*|white| + |grey|,在每一次扫描GC收集器都至少进行一次移动，直到达到当前灰色区域内存对象数目为0。

第五步

程序此时的逻辑为，新赋值一个内存对象E给C.next，代码如下：

var A LinkedListNode;

var B LinkedListNode;

// ...

B.next = &LinkedListNode{next: nil};
// ...
A.next = &LinkedListNode{next: nil};
//新赋值 C.next = &E
*(B.next).next = &LinkedListNode{next: nil};

按照我们之前的规则，新建的内存对象需要放置在灰色区域，如图所示：

这样做，收集器需要做更多的事情，但是这样做当在新建很多内存对象的时候，可以将最终的清除操作延迟。值得一提的是，这样处理白色区域的体积将会减小，直到收集器真正清理堆空间时再重新填入移入新的内存对象。

第六步 指针重新赋值

程序逻辑此时将 B.next.next赋值给了B.next，也就是将E赋值给了B.next。代码如下：

var A LinkedListNode;
var B LinkedListNode;
// ...
B.next = &LinkedListNode{next: nil};
// ...
A.next = &LinkedListNode{next: nil};
*(B.next).next = &LinkedListNode{next: nil};
// 指针重新赋值:
B.next = *(B.next).next;

这样做之后，如图所示，C将不可达。

这就意味着，收集器需要将C从白色区域移除，然后在GC循环中将其占用的内存空间回收。

第七步

将灰色区域中没有引用依赖的内存对象移动到黑色区域中，此时D在灰色区域中没有其它依赖，并依赖于它的内存对象A已经在黑色区域了，将其移动到黑色区域中。

第八步

在程序逻辑中，将B.next赋值为了nil,此时E将变为不可达。但此时E在灰色区域，将不会被回收，那么这样会导致内存泄漏吗？其实不会，E将在下一个GC循环中被回收，三色算法能够保证这点：如果一个内存对象在一次GC循环开始的时候无法被访问，则将会被冻结，并在GC的最后将其回收。

第九步

在进行第二次GC循环的时候，将E移入到黑色区域，但是C并不会移动，因为是C引用了E，而不是E引用C。

第十步

收集器再扫描最后一个灰色区域中的内存对象B，并将其移动到黑色区域中。

第十一步 回收白色区域

现在灰色区域已经没有内存对象了，这个时候就将白色区域中的内存对象回收。在这个阶段，收集器已经知道白色区域的内存对象已经没有任何引用且不可访问了，就将其当做垃圾进行回收。而在这个阶段，E不会被回收，因为这个循环中，E才刚刚变为不可达，它将在下个循环中被回收。

第十二步 区域变色

这一步是最有趣的，在进行下次GC循环的时候，完全不需要将所有的内存对象移动回白色区域，只需要将黑色区域和白色区域的颜色换一下就好了，简单而且高效。

GC三色算法小结

上面就是三色标记清除算法的一些细节，在当前算法下仍旧有两个阶段需要 stop-the-world：一是进行root内存对象的栈扫描；二是标记阶段的终止暂停。令人激动的是，标记阶段的终止暂停将被去除。在实践中我们发现，用这种算法实现的GC暂停时间能够在超大堆空间回收的情况下达到<1ms的表现。

延迟 VS 吞吐

如果一个并行GC收集器在处理超大内存堆时能够达到极低的延迟，那么为什么还有人在用stop-the-world的GC收集器呢？难道Go的GC收集器还不够优秀吗？

这不是绝对的，因为低延迟是有开销的。最主要的开销就是，低延迟削减了吞吐量。并发需要额外的同步和赋值操作,而这些操作将会占用程序的处理逻辑的时间。而Haskell的GHC则针对吞吐量进行了优化，Go则专注于延迟，我们在考虑采用哪种语言的时候需要针对我们自己的需求进行选择，对于推送系统这种实时性要求比较高的系统，选择Go语言则是权衡之下得到的选择。

实际表现

目前而言，Go好像已经能够满足低延迟系统的要求了，但是在实际中的表现又怎么样呢？利用相同的benchmark测试逻辑实现进行比较：该基准测试将不断地向一个限定缓冲区大小的buffer中推送消息，旧的消息将会不断地过期并成为垃圾需要进行回收，这要求内存堆需要一直保持较大的状态，这很重要，因为在回收的阶段整个内存堆都需要进行扫描以确定是否有内存引用。这也是为什么GC的运行时间和存活的内存对象和指针数目成正比例关系的原因。

这是Go语言版本的基准测试代码，这里的buffer用数组实现:

package main

import (
    "fmt"
    "time"
)

const (
    windowSize = 200000
    msgCount   = 1000000
)

type (
    message []byte
    buffer  [windowSize]message
)

var worst time.Duration

func mkMessage(n int) message {
    m := make(message, 1024)
    for i := range m {
        m[i] = byte(n)
    }
    return m
}

func pushMsg(b *buffer, highID int) {
    start := time.Now()
    m := mkMessage(highID)
    (*b)[highID%windowSize] = m
    elapsed := time.Since(start)
    if elapsed > worst {
        worst = elapsed
    }
}

func main() {
    var b buffer
    for i := 0; i < msgCount; i++ {
        pushMsg(&b, i)
    }
    fmt.Println("Worst push time: ", worst)
}

相同的逻辑，不同语言实现(Haskell/Ocaml/Racke、Java)，在同等测试条件下进行的测试结果如下：

Benchmark Longest pause (ms)
OCaml 4.03.0 (map based) (manual timing) 2.21
Haskell/GHC 8.0.1 (map based) (rts timing) 67.00
Haskell/GHC 8.0.1 (array based) (rts timing) 58.60
Racket 6.6 experimental incremental GC (map based) (tuned) (rts timing) 144.21
Racket 6.6 experimental incremental GC (map based) (untuned) (rts timing) 124.14
Racket 6.6 (map based) (tuned) (rts timing) 113.52
Racket 6.6 (map based) (untuned) (rts timing) 136.76
Go 1.7.3 (array based) (manual timing) 7.01
Go 1.7.3 (map based) (manual timing) 37.67
Go HEAD (map based) (manual timing) 7.81
Java 1.8.0_102 (map based) (rts timing) 161.55
Java 1.8.0_102 G1 GC (map based) (rts timing) 153.89

令人惊讶的是Java,表现得非常一般，而OCaml则非常之好，OCaml语言能够达到约3ms的GC暂停时间，这是因为OCaml采用的GC算法是incremental GC algorithm(而在实时系统中不采用OCaml的原因是该语言对多核的支持不好)。

正如表中显示的,Go的GC暂停时间大约在7ms左右，表现也好，已经完全能够满足我们的要求。

一些注意事项

  1. 进行基准测试往往需要多加小心，因为不同的运行时针对不同的测试用例都有不同程度的优化，所以表现往往也有差异。而我们需要针对自己的需求来编写测试用例，对于基准测试应该能够满足我们自己的产品需求。在上面的例子中可以看到，Go已经完全能够满足我们的产品需求。
  2. Map Vs. Array： 最初我们的基准测试是在map中进行插入和删除操作的，但是Go在对大型的map进行GC的时候存在Bug。因此在设计Go的基准测试的时候用可修改的Array作为Map的替代。Go map的Bug已经在1.8版本中得到了修复，但是并不是所有的基准测试都得到了修正，这也是我们需要正视的一些问题。但是不管怎么说，没有理由说GC时间将会因为使用map导致大幅度增长（除去bug和糟糕的实现之外）。
  3. manual timing Vs. rst timing :作为另一个注意事项，有些基准测试则在不同的计时系统下将会有所差异，因为有些语言不支持运行时时间统计，例如Go，而有些语言则支持。因此，我们应该在测试时候都把计时方式设置为manual timing。
  4. 最后一个需要注意的事项是测试用例的实现将会极大地影响基准测试的结果，如果map的插入删除实现方式比较糟糕，则将会对测试结果造成不利影响，这也是用array的另一个原因。

为什么Go的结果不能再好点？

尽管我们采用的map bugfixed版本或者是array版本的go实现能够达到~7ms的GC暂停表现，这已经很好了，但是根据Go官方发布的“1.5 Garbage Benchmark Latency”](https://talks.golang.org/2015/go-gc.pdf) ， 在200MB的堆内存前提下，能够达到~1ms的GC暂停延时(经管GC暂停时间应该和指针引用数目有关而和堆所占用的容量无关但我们无法得到确切数据)。而Twitch团队也发布文章称在Go1.7中能够达到约1ms的GC延迟。

在联系go-nuts mail list之后得到的答案是，这些暂停实验可能是因为一些未修复的bug导致的。空闲的标记worker可能会对程序逻辑造成阻塞，为了确定这个问题，我采用了go tool trace，一个可视化工具对go的运行时行为进行了跟踪。

正如图所示，这里有近12ms的后台mark worker运行在所有的processor（CPU核?）中。这让我更加确信是上述的bug导致的该问题。

总结

这次调查的重点在于GC要么关注于低延迟，要么关注于高吞吐。当然这些也都取决于我们的程序是如何使用堆空间的(我们是否有很多内存对象？每个对象的生命周期是长还是短？)

理解底层的GC算法对该系统是否适用于你的测试用例是非常重要的。当然GC系统的实际实现也至关重要。你的基准测试程序的内存占用应该同你将要实现的真正程序类似，这样才能够在实践中检验GC系统对于你的程序而言是否高效。正如前文所说的，Go的GC系统并不完美，但是对于我们的系统而言是可以接受的。

尽管存在一些问题，但是Go的GC表现已经优于大部分同样拥有GC系统的语言了，Go的开发团队针对GC延迟进行了优化，并且还在继续。Go的GC确实是有可圈可点之处，无论是理论上还是实践中。

原文 Golang’s Real-time GC in Theory and Practice[en]

从Haskell、JS、go看函数式编程

Posted on Posted on |in tech|by terasum

引言

本文就是我在学习函数式编程的过程当中自己体悟到的一些东西，这里将用go,JavaScript以及Haskell三种语言来分析函数式编程的一些奥秘。JavaScript由于具有的一些优势能够让我们可以实现函数式编程，而go作为一种强类型语言，虽然灵活性又稍有欠缺，但是也能够完成一些高阶函数的实现，Haskell语言作为正统的函数式编程语言，为了解释说明问题，作为对比参照。

正文

函数式编程也算是经常看到了，它的一些优势包括：

  1. 不包括赋值语句(assignment statement),一个变量一旦初始化，就无法被修改(immutable)
  2. 无副作用，函数除了计算结果，将不会产生任何副作用
  3. 因为无副作用，所以任何表达式在任何时候都能够evaluate

虽然上面的优势看看上去好像很厉害的样子，但是，到底厉害在哪里呢？我们可以通过下面的例子进行说明：

求和函数

Haskell

sum [1,2,3]
-- 6
-- sum 的实现其实是
foldr (+) 0 [1,2,3]

在Haskell中flodr的函数定义是：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

函数实现是:

-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

这是一个递归实现，在函数式编程中，递归定义是十分常见的。

foldr函数其实做了这样的事情：foldr接受三个参数，第一个参数是函数f，第二个参数是初始值z,第三个参数是一个列表。如果列表为空则返回初始化值z，否则递归调用 foldr,需要说明的是函数f的类型是接受两个参数，返回一个值，两个参数类型都应该和z相同（强类型语言中）。

在Haskell中我们能够看到一个列表能够这样被求和，那么在JavaScript中，我们是如何实现sum函数的呢？

JavaScript

首先我们实现js版本的foldr

function foldr(f,z,list){
  //为了简洁起见，把类型判断省略了
  // Object.prototype,toString.call(list) === '[object Array]' 
  if(list === null || list.length == 0){
    return z;
  }
  //这里的shift会改变参数的状态，会造成副作用
  //return f(list.shift(),foldr(f,z,list));
  //改用如下写法
  return f(list[0],foldr(f,z,list.slice(1)));
}

然后我们再实现js版本的(+):

function add(a,b){
  return a+b;
}

那么我们的sum就变成：

function sum(list){
  return foldr(add,0,list);
}

最后我们的js版的sum也可以这样用了：

let a = [1,2,3];
sum(a); // 6

像js这样的弱类型的语言较为灵活，函数f可以任意实现，对于foldr函数也能够在多种数据类型之间复用，那么对于像go这样的强类型语言，结果又是怎么样的呢？

go

同样地，我们实现以下go版本的foldr:

func foldr(f func(a,b int) int,z int,list []int)int{
    if len(list) == 0{
        return z
    }
    return f(list[0],foldr(f,z,list[1:]))
}

go因为有数组切片，所以使用起来较为简单，但是go又是强类型的语言，所以在声明函数的时候必须要把类型声明清楚。

再实现一下f函数：

func add(a,b int) int{
    return a+b;
}

依葫芦画瓢我们可以得到go版本的sum函数：

func sum(list []int) int{
    return foldr(add,0,list)
}

可以看出来好像套路都差不多，真正在调用的时候是这样的：

func main(){
    a := []int{1,2,3}
    sum(a) // 6
}

在Haskell中是没有循环的，因为循环可以通过递归实现，在上文我们实现的sum函数中，也没有用到任何循环语句，这和我们原来的编程思维有所不同，刚开始我学写求和函数的时候，都是从for,while开始的，但是函数式给我打开了新世界的大门。

有了上面的基础，我们发现在函数式编程中，代码的重用非常便利：

求积函数

javaScript

function muti(a,b){
  return a*b;
}

function product(list){
  return foldr(muti,1,list);
}

go

func muti(a,b int) int{
    return a*b;
}

func product(list []int) int{
    return foldr(muti,1,list)
}

Haskell

foldr (*) 1 [1,2,3,4] 
-- 24
-- or 
-- product 是Haskell预定义的函数
myproduct xs = foldr (*) 1 xs
-- myproduct [1,2,3,4]

还有很多例如 anyTrue、allTrue的例子,以下仅给出js实现：

anyTure

JavaScript

function or(a,b){
  return a || b;
}

function anyTrue(list){
  return foldr(or,false,list);
}

调用：

let b = [true,false,true];
console.log(anyTrue(b)); // true

allTure

JavaScript

function and(a,b){
  return a && b;
}

function allTrue(list){
  return foldr(and,true,list);
}

调用:

let b = [true,false,true];
console.log(allTrue(b)); // false

当然我们可以看出来这个flodr函数贼好用，但是好像还是有点疑惑，它是怎么工作的呢？看了一圈，flodr就是一个递归函数，但其实在编程世界，它还有一个更加出名的名字——reduce。我们看看在js中是如何使用reduce实现sum函数的：

求和函数reduce版

const _ = require("lodash");
_.reduce([1,2,3],function(sum,n){
  return sum+n;
});

在lodash官方文档是这么定义的：

_.reduce alias _.foldl
_.reduceRight alias _.foldr

好吧，我欺骗了你们，其实foldr应该对应reduceRight。

那么foldl和foldr到底有什么不同呢？

其实这两个函数的不同之处在于结合的方式不同，以求差为例：

Haskell

foldr (-) 0 [1,2,3]
-- 输出: 2
foldl (-) 0 [1,2,3]
-- 输出: -6

为什么两个输出是不同的呢？这个和结合方向有关:

foldr (-) 0 [1,2,3]

相当于：

1-(2-(3-0)) = 2

而

foldl (-) 0 [1,2,3]

相当于：

((0-1)-2)-3) = -6

结合方向对于求和结果而言是没有区别的，但是对于求差，就有影响了：

JavaScript

const _ = require("lodash");
//reduce 相当于 foldl
_.reduce([1,2,3],function(sum,n){
  return sum-n;
});
// 输出 -4

这个和说好的-6好像又不一样了，坑爹呢么不是？！这是因为，在lodash的实现中，reduce的初始值为数组的第一个元素,所以结果是1-2-3 = -4。

那么我们看看reduceRight == foldr的结果：

JavaScript

const _ = require("lodash");
//reduceRight 相当于 foldr
_.reduceRight([1,2,3],function(sum,n){
  return sum-n;
});
// 输出 0

我们看到这个结果是0也算是预期结果，因为3-2-1=0。

注：上文为了易于理解和行文连贯，加入了一些我自己的理解。需要说明的是，在Haskell中，foldl1函数应该是和JavaScript的reduce(lodash)函数是一致的，foldl1函数将会把列表的第一个元素作为初始值。

现在我们总结一下foldr和foldl的一些思路：

如果对列表[3,4,5,6]应用函数f初始值为z进行foldr的话，应该理解为：

f 3 (f 4 (f 5 ( f 6 z)))
-- 当 f 为 +, z = 0 上式就变为：
3 + (4 + (5 + (6 + 0)))
-- 前缀(+)形式则为：
(+)3 ((+)4 ((+)5 ((+)6 0)))

如果对列表[3,4,5,6]应用函数g初始值为z进行foldl的话，应该理解为：

g(g (g (g z 3) 4) 5) 6
-- 当然我们也可以类似地把 g 设为 +, z = 0， 上式就变为：
(((0 + 3) + 4) + 5) + 6
-- 改成前缀形式
(+)((+)((+)((+)0 3) 4) 5) 6

从上面的例子可以看出，左折叠(foldl)和右折叠(foldr)两者有一个很关键的区别，就是，左折叠无法处理无限列表，但是右折叠可以。

前面我们说的都是用预定义的函数+,-,*…,（在函数式编程里，这些运算符其实也都是函数）用这些函数是为了能够让我们更加便于理解，现在我们看看用我们自己定义的函数呢？试试逆转一个列表：

reverse

Haskell

flip' :: (a -> b -> c) -> b -> a -> c
flip' f x y= f y x

上面的flip'函数的作用就是传入第一个参数是一个函数，然后将两个参数的顺序调换一下(flip是预定义函数)。

Hasekll

foldr flip' [] [1,2,3]

那么JavaScript的实现呢？

JavaScript

function flip(f, a, b){
     return f(b,a);
}
//这个函数需要进行柯里化，否则无法在foldr中作为参数传入
var flip_ = _.curry(flip);

function cons(a,b){
     return a.concat(b);
 }

function reverse(list){
  return foldr(flip_(cons),[],list);
}

调用结果又是怎么样的呢？

console.log(reverse([1,2,3]))
// [ 3, 2, 1 ]

好了，现在我们好像又看到了一个新东西——curry，柯里化。简单地说，柯里化就是一个函数可以先接受一部分参数，然后返回一个接受剩下参数的函数。用上面的例子来说，flip函数在被柯里化之后得到的函数flip_，可以先接受第一个参数cons然后返回一个接受两个参数a,b的函数，也就是我们需要的连接函数。

在go语言里面，实现curry是一个很麻烦的事情，因此go的函数式编程支持还是比较有限的。

接着我们试试如何取得一个列表的长度，实现一个length函数：

length

Haskell

-- 先定义实现一个count 函数
count :: a -> b ->c
count a n = n + 1
-- 再实现一个length函数
length' = foldr (count) 0
-- 再调用
length' [1,2,3,4]
-- 4

JavaScript

//先定义一个count函数
function count(a,n){
  return n + 1;
}
//再实现length函数
function length(list){
  return foldr(count,0,list);
}
//调用
console.log(length([1,2,3,4]));
// 4

就是这么简单，好了，reduce我们讲完了，然后我们看看map,要知道map函数是怎么来的，我们要从一个比较简单的函数先入手，这个函数的功能是把整个列表的所有元素乘以2:

doubleall

haskell

-- 定义一个乘以2，并连接的函数
doubleandcons :: a -> [a] -> [a]
doubleandcons x y  = 2 * x : y

doubleall x = foldr doubleandcons []

-- 调用
doubleall [1,2,3]
-- 输出
-- [2,4,6]

JavaScript

function doubleandcons(a,list){
  return [a * 2].concat(list)
}

function doubleall(list){
  return foldr(doubleandcons,[],list)
}

//调用
console.log(doubleall([1,2,3]));
// [2,4,6]

再来看看go怎么写：

go

go 的尴尬之处在于，需要非常明确的函数定义，所以我们要重新写一个foldr函数，来接受第二个参数为列表的f。

func foldr2(f func(a int,b []int) []int,z []int,list []int)[]int{
    if len(list) == 0{
        return z
    }
    return f(list[0],foldr2(f,z,list[1:]))
}

然后我们再实现同上面相同的逻辑：

func doubleandcons(n int,list []int) []int{
    return append([]int{n * 2},list...)
}

func doubleall(list []int) []int{
    return foldr2(doubleandcons,make([]int,0),list)
}
// doubleall([]int{1,2,3,4})
//[2 4 6 8]

go这门强类型编译语言虽然支持一定的函数式编程，但是使用起来还是有一定局限性的，起码代码复用上还是不如js的。

接下来我们关注一下其中的doubleandcons函数，这个函数其实可以转换为这样的一个函数：

fandcons f el [a]= (f el) : [a]
double el = el * 2
-- 只传入部分参数，柯里化
doubleandcons = fandcons double

现在我们关注一下这里的fandcons,其实这里可以通用表述为Cons·f,这里的·称为函数组合。而函数组合有这样的操作：

    \[(f. g) h = f (g\ h)\]

需要注意的是等号右边是函数调用。

那么上面的我们的函数就可以表述为：

    \[fandcons\ f\ el = (Cons.f) \ el = Cons (f\ el)\]

所以：

    \[fandcons\ f\ el \ list = (Cons.f) \ el \ list \ = Cons (f\ el) \ list\]

最终版本就是：

    \[doubleall = foldr\ (Cons . double)\ Nil\]

这里的foldr(Cons.double) 其实就是我们要的map double，那么我们的map的本来面目就是：

    \[map = foldr\ (Cons.f)\ Nil\]

这里的Nil是foldr函数的初始值。

好了map已经现身了，让我们再仔细看看一个map函数应该怎么实现：

map

Haskell

fandcons :: (a->b) ->a -> [b] -> [b]
fandcons f x y= (f x):y

map' :: (a->b) -> [a] -> [b]
map' f x = foldr (fandcons f) [] x

-- 调用 
map' (\x -> 2 * x)  [1,2,3]
-- 输出 [2,4,6]

这里用了Haskell的lambda表达式，其实就是f的double实现。

我们也看看js版本的实现：

JavaScript

function fandcons(f, el, list){
  return [f(el)].concat(list);
}
//需要柯里化
var fandcons_ = _.curry(fandcons);

function map(f, list){
  return foldr(fandcons_(f),[],list);
}
//调用
console.log(map(function(x){return 2*x},[1,2,3,4]));
// 输出[ 2, 4, 6, 8 ]

这些需要柯里化的go我都不实现了，因为go实现柯里化比较复杂。

最后我们再看看map的一些神奇的操作：

矩阵求和

summatrix

Haskell

summatrix :: Num a => [[a]] -> a
summatrix x = sum (map sum x)

-- 调用
summatrix [[1,2,3],[4,5,6]]
-- 21

这里一定要显式声明 参数a的类型，因为sum函数要求Num类型的参数

JavaScript

function sum(list){
  return foldr(add,0,list);
}
function summatrix(matrix){
  return sum(map(sum,matrix));
}
//调用
 mat = [[1,2,3],[4,5,6]];
 console.log(summatrix(mat));
//输出 21

结语

在学习函数式编程的过程中，我感受到了一种新的思维模式的冲击，仿佛打开了一种全新的世界，没有循环，甚至没有分支，语法简洁优雅。我认为作为一名计算机从业人员都应该去接触一下函数式编程，能够让你的视野更加开阔，能够从另一个角度去思考。