July 27, 2007

functional.js 介绍及源码分析

作者 lichray 对刚刚在网络上现身的 JavaScript 函数式编程库 functional.js 进行了详尽的解读。

functional.js 是模仿 Haskell 语言标准库 Prelude 制作的函数式编程库,主要实现了:

  • 扩展的克里化函数
  • 运算符函数化
  • 紧缩的匿名函数语法
  • 无须指定参数的匿名函数语法
  • 函数向导语法
  • 基本的通用列表操作
  • 部分扩展基于对象化

其中,扩展语法由字符串表示。未能实现的特性有:

  • 尾递归优化
  • 模式匹配(包括参数匹配、列表匹配、情况分析)
  • 惰性运算(包括无穷列表)
  • 列表领悟
  • 扩展绑定、同时绑定
  • 其它列表操作(以及对于列表操作的基于对象化)

下面我们一边分析源代码,一边讲解库的用法。

一、库安装和概览
functional.js 库的所有用户级操作分为3个部分:

  1. 全局操作,绑定在全局对象 Functional 上,主要是高阶函数操作和列表操作,所谓库安装即把这些内容可选的、安全地复制到全局环境
  2. 函数扩展,实现特殊高阶函数特性的工具(特供内部)
  3. 语法扩展,绑定在 String.prototype 上,负责将字符串表示的 lambda 语法翻译为相应的高阶函数(特供内部)

下面是安装函数 Functional.install 的源代码(中文注释为笔者所加,下同):

Functional.install = function(except) { // except 参数是一个对象,不加载这些操作
var source = Functional,
   target = window; // 复制操作到全局环境 window,仅限于浏览器环境
for (var name in source)
   name == 'install' // 当然,不能把 install 复制到 source
   || name.charAt(0) == '_' // 命名开头为 _,私有属性
   || except && name in except
   || {}[name] // work around Prototype
   || (target[name] = source[name]);
}

一般只要执行 Functional.install() 一句即可。

二、高阶函数操作
1. Functional.compose ([Function]) // 匿名的参数类型指的是 arguments 的类型,下同
  接受一列参数个数被认为相等的(允许 Currying 算子)函数为参数,返回一个函数,它接受一定的参数,能够对它们累积倒序 apply 那列函数。
  示例:compose('1+', '2*')(2) => 5
  
2. Functional.sequence ([Function])
  累积 apply 的顺序为参数顺序,为 compose 的反序。
  示例:sequence('1+', '2*')(2) => 6

以上两个操作亦可见于 Function.prototype,用法:'1+'.lambda().sequence('2*')(2) ==> 6

3. Function.prototype.flip ()
  返回一个函数,是原函数对象 this 参数接受顺序颠倒后的版本,不应属于函数扩展类。
  示例:flip('a/b')(1, 2) => 2
  
4. Function.prototype.saturate ([]) {
  返回一个函数,是原函数对象 this 忽略自己接受的参数,仅接受指定参数的版本。
  形式:f.saturate(args...)(args2...) == f(args...)
  
5. Function.prototype.aritize (n::Number) // 有名的参数类型由 :: 指定,下同
  返回一个函数,是原函数对象 this 忽略自己接受的参数列表中下标为 n 的参数的版本。
  
6. Function.S (f, g::Function)
  以单个大写字母命名的是函数的原子操作,应被收入 Functional 对象,这个很奇怪。
  形式:S(f, g)(args...) == f(g(args...), args...)
  
三、通用列表操作
1. 绑定在 Functional 对象上的部分完全照抄 Haskell Prelude 以及 Clean 的命名,它们是:

  1. map(f, [x1, x2...]) = [f(x, 0), f(x2, 1), ...]
  2. foldl, reduce(f, init, [x0, x1, x2]) == f(f(f(init, x0), x1), x2)
  3. filer, select('%2', [1,2,3,4]) -> [1, 3]
  4. foldr(f, init, [x0, x1, x2]) == fn(x0, f(x1, f(x2, init)))
  5. some(f, [x1, x2, x3, ...]) == f(x1) || f(x2) || f(x3)...
  6. every(f, [x1, x2, x3, ...]) == f(x1) && f(x2) && f(x3)...

以上操作的介绍网上到处都是,不再赘述;但有一点不同,即它们除了接受正常参数之外,还在最后接受一个可选参数 object::Object,它被用于指定操作执行的对象/环境。
另外,这些操作全部基于命令式风格实现,对于没有尾递归优化的 JavaScript 来说,效率有保障。

四、群体谓词操作
1. Functional.and ([Function])
  接受一列函数为参数,返回一个函数,它接受一个参数,对该参数 apply 那列函数,如结果全为 true,返回 true;否则返回 false。
  形式:and(f1, f2...)(args...) == f1(args...) && f2(args...)...
  示例:and('>1', '>2')(2) => false
  
2. Functional.or ([Function])
  接受一列函数为参数,返回一个函数,它接受一个参数,对该参数 apply 那列函数,如结果全为 false,返回 false;否则返回 true。
  形式:or(f1, f2...)(args...) == f1(args...) || f2(args...)...
  示例:or('>1', '>2')(2) => true
  
3. Functional.not = function(fn::Function)
  返回一个函数,是参数返回的布尔值的函数(谓词,下同) fn 取否的版本。
  形式:f.not()(args...) == !f(args...)
  
4. Functional.equal ([Function])
  接受一列函数为参数,返回一个函数,它接受一个参数,对该参数 apply 那列函数,如结果全部 == ,返回 true;否则返回 false。
  形式:equal(f1, f2...)(args...) == f1(args...) == f2(args...)...
  示例:equal()() => true // 特殊情况

五、函数扩展
  这一章仅仅是介绍内部实现。
1. Function.prototype.bind (object::Object,[])
  返回一个函数,作为 this 函数对象的副本,使其将在 object 环境下执行,并额外携带参数。
  形式:f.bind(obj, args...)(args2...) == f.apply(obj, [args..., args2...])
  
2. Function.prototype.curry ([])
这是实现克里化特性的关键函数,思想来自网络

Function.prototype.curry = function(/*args...*/) {
var fn = this;
var args = [].slice.call(arguments, 0);
return function() {
   return fn.apply(this, args.concat([].slice.call(arguments, 0)));
};
}

  返回那个传说中的可在参数不足时分步调用的函数——Currying 算子。
  形式:f.curry(args1...)(args2...) == f(args1..., args2...)

其它的 curry 类函数有:

  • rcurry,对从右边开始缺少参数的函数作克里化
  • ncurry,不接受全部参数就不 apply 参数的版本
  • rncurry,前者的反序版本
  • uncurry,作者一再强调,这不是 curry 的反转版本。它会拆分出第一个已得参数,形式为:f.uncurry(a, b...) == f(a)(b...)


3. Function.prototype.partial ([])
  在此函数定义之前,有定义 _ = Function._ = {} 。结合它们可以允许你像在 Haskell 中那样在参数列表中用 _ 忽略参数。但现在空谈是没用的,要结合第七章的语法扩展。
  
4. Function.prototype.guard (guard:>Function, otherwise)
  类似的,是一个允许在函数定义中使用向导功能的工具,尚缺少语法扩展支持。
  形式:f.guard(g, h)(args...) == f(args...), when g(args...) is true
    f.guard(g ,h)(args...) == h(args...), when g(args...) is false

六、工具函数
1. Functional.invoke (methodName::String, [])
  示例:invoke('toString')(123) => "123"
  
2. Functional.pluck (name::String)
  示例:pluck('length')("abc") => 3
  
3. Functional.until (pred:>Function, fn:>Function) // 用 :> 表示将参数强制转换类型

Functional.until = function(pred, fn) {
  // 使用时参数会被强制转为 Functional 的函数,参数可为字符串
fn = Function.toFunction(fn);
pred = Function.toFunction(pred);
  // 返回一个接受一个参数的函数,
return function(value) {
    // 它不断对此参数 apply 函数 pred,
   while (!pred.call(null, value))
      // 并用 fn(value) 的值更新 value,
     value = fn.call(null, value);
   return value; // 直到测试结果为 true。
}
}

  类似 Haskell 的 until,是一种函数式的循环,用命令式风格实现。
  
4. Functional.zip ([])
  特别注意,此 zip 并非 Haskell 中的 zip,它接受可变参数列表而不是列表的列表。
  形式:zip(a, b...) == [[a0, b0], [a1, b1], ...]

以上的章节中绑定在 Functional 上函数都可作为 Function 的对象方法直接使用,我们看这一行:

Functional.__initalFunctionState =
Functional._startRecordingMethodChanges(Function.prototype);

前文对它们作出了定义,这里忽略。用法:name(arg, args...) == arg.name(args...)。

七、语法扩展
1. String.prototype.lambda ()
  把字符串表示的字符串翻译为函数扩展可接受的函数,进一步转为 JavaScript 函数。

String.prototype.lambda = function() {
var params = []; // 存储字符串形式的参数的列表
var expr = this;
  // ECMAsplit 是作者为兼容 IE6.0 所写的 split 版本
var sections = expr.ECMAsplit(/\s*->\s*/m); // 使字符串被 '->' 分割
  /* 注意,分割的结果支持超过任意个 '->',下面会发现,
    -> 9 或者
    x -> y -> x+y 这样的代码也会被正确理解。
  */
if (sections.length > 1) {
    // 这就是所谓的“正确理解”了
   while (sections.length) {
     expr = sections.pop();
      // 然后把参数打碎,再重组为 JS 可识别的参数语法
      /* 也就是说,x y -> x*y+2 和
        x,y -> x*y+2 都可被接受。
      */
     params = sections.pop().split(/\s*,\s*|\s+/m);
      // 装配成代码,顺便支持尾递归语法
     sections.length && sections.push('(function('+params+'){return ('+expr+')})');
   }
} else if (expr.match(/\b_\b/)) {
   params = '_'; // 忽略参数的前奏,下文判断
} else {
    // 这里处理运算符表达式参数缺失的情况,相当于运算符函数化
    // 分为前缺失和后缺失两种情况,
   var leftSection = expr.match(/^\s*(?:[+*\/%&|\^\.=<>]|!=)/m);
   var rightSection = expr.match(/[+\-*\/%&|\^\.=<>!]\s*$/m);
    /* 注意,前缺失类似 *2,后缺失类似 2*,复杂表达式同样支持
      此外,前后都缺失也可以,比如 * 甚至是 *3*
    */
   if (leftSection || rightSection) {
      // 翻译缺失代码的技术:用 $1、$2 代换参数
     if (leftSection) {
       params.push('$1');
       expr = '$1' + expr;
     }
     if (rightSection) {
       params.push('$2');
       expr = expr + '$2';
     }
   } else {
      // 这个地方就有点意思了;它使得函数支持参数指定缺失
      /* 比如 x*y 就已经是一个函数了,相当于 x y->x*y
        作者还特别防止了一个 bug,即对象属性访问语法中,
        属性部分不被认为是未指定的参数。例如
        obj.pro + 4 这个函数,只有 obj 一个参数
        而且,this 和 arguments 不会被认为是未知数。
      */
     var vars = this.replace(/(?:\b[A-Z]|\.[a-zA-Z_$])[a-zA-Z_$\d]*|[a-zA-Z_$][a-zA-Z_$\d]*:|this|arguments|'(?:[^'\\]|\\.)*'|"(?:[^"\\]|\\.)*"/g, '')
.match(/([a-z_$][a-z_$\d]*)/gi) || [];
     for (var i = 0, v; v = vars[i++]; )
       params.indexOf(v) >= 0 || params.push(v);
   }
}
return new Function(params, 'return (' + expr + ')'); // 把代码装配成函数对象
}


八、过滤器生成器
  仅供特别好学的同志们参考。
1. Function.prototype.prefilterObject (filter::Function)
  形式:fn.prefilterObject(filter).apply(object, args...) == fn.apply(filter(object), args...)
  
2. Function.prototype.prefilterAt (index::Number, filter::Function)
  形式:fn.prefilterAt(i, filter)(a1, a2, ..., a_{n}) == fn(a1, a2, ..., filter(a_{i}), ..., a_{n})
  
3. Function.prototype.prefilterSlice (filter::Function, start, end::Number)
  形式:fn.prefilterSlice(i0, i1, filter)(a1, a2, ..., a_{n}) == fn(a1, a2, ..., filter(args_{i0}, ..., args_{i1}), ..., a_{n})

九、其它用户级函数
1. Functional.id = Functional.I = function(x) {return x};

2. Functional.constfn = Functional.K = function(x) {return function() {return x}};

3. .toFunction ()
  在 String.prototype,Function.prototype,Function(需要参数 fn::Function) 上都有绑定,把对象转换为一个合适的 Functional 函数。但你不需要把代码写这样,map('*2'.toFunction(),alist),因为全局用户级函数都会对应为函数的参数自动执行 toFunction(),只要 map('*2',alist) 就行了。另外,String.prototype 上还有 JavaScript-Like 的 call、apply 方法。

十、结语
  functional.js 很强,很有用,很牛X;但同时也很年轻(7.20 发布),很多可以实现的功能还不完善,不说列表领悟什么的吧,至少应该把 Haskell Prelude 库在通用列表操作方面的函数的移植工作完成。我们期待 Oliver Steele 的表现。

No comments: