函数式编程(javascirpt)

【 tulaoshi.com - Web开发 】

　　前言

　　Javascript，有人称其为C+LISP,C只怕是尽人皆知，但是一直活跃在人工智能领域的另一个古老而优美的语言LISP，掌握的恐怕不是很多.这个倒不是因为这个语言太难或者用途不广泛，而是大多数人在接受计算机语言启蒙的时候都走的是图灵机模式，而LISP，做为一种函数式编程语言，是另一个体系：lambda演算体系.这个体系的运算能力跟图灵机的运算能力是相当的。

　　所以Javascript本身是一种很自由的，支持函数式编程的一个神奇的语言，在WEB中的应用只是它的以个小小的部分。脚本可以用来脚本化很多东西，最主要的应用是在UI层面，很灵活(这也是Javascript用来脚本化HTML的一个重要原因)。我们这里要说的是一个100%java实现的 javascript引擎rhino，当然重点不是引擎本身，而是在其上解释JavaScript的函数式编程。(rhino可以在此处 http://www.mozilla.org/rhino/找到)。

　　函数式编程概览

　　我们先看几个例子，从感官上对其有一个了解，看一个幂计算函数，用命令式语言书写(命令式语言如C，Java等)，大概就是下面这个样子：

function expt(b, n){
　　　 if(n == 0){return 1;}
　　　 else{
　　　　　　　 return expt(b, n-1)*b;//正常的递归调用
　　　 }
}

　　再看看函数式编程的写法：

function expt(b, n){
　　　 if(n == 0){
　　　　　　　 return 1;
　　　 }else{
　　　　　　　 return mul(expt(b, dec(n)), b);//所有操作均为函数
　　　 }
}

　　可以很明显的看到，有一大堆的括号，没有操作符(如+-*/等)，这是因为，操作符在函数式编程中被认为是函数，与其他函数(数学函数，串处理函数等)的地位是同等的，当然这个不是最主要的，在函数式编程中最主要的是函数可以做为一个基本类型被返回，这一点时命令式语言无法完成的。

　　比如，定义一个函数，输入两个参数，计算这两个数的平方和：

function(x, y){ return add( expt(x, 2), expt(y, 2) ); }

　　你可以将这个函数赋值给一个变量，如下：

var func = function(x, y){ return add( expt(x, 2), expt(y, 2) ); }

　　然后，最神奇的是，下边这样：

　　func(3, 4);//这个表达式将返回25! 此时的func已经是一个函数了!

　　好了，简单的概述就此为止，下面我们看一些更高级的主题：高阶函数。

　　高阶函数

　　事实上，所有的有关函数式编程的文章必须要涉及到这个主题，这是因为，在命令式语言中，我们的抽象是根据"类"(这正是现在流行的OO的基本思想)来进行的，但是，在函数式编程中，没有办法表示类的概念，但是同样可以进行高级的抽象方式，使得一个函数更加泛化，可以被"实例化"成其他的函数，这个就是高阶函数。

　　来看个例子，我们有这样几种求和运算：

function intSum(a, b){
　　　 function inc(x){ return x + 1; }
　　　 function identity(x){ return x; }
　　　
　　　 if(a b){
　　　　　　　 return 0;
　　　 }else{
　　　　　　　 return intSum(inc(a) , b) + identity(a);
　　　 }
}

function cubeSum(a, b){
　　　 function inc(x){ return x + 1; }
　　　 function cube(x){ return x * x * x; }
　　　 if(a b){
　　　　　　　 return 0;
　　　 }else{
　　　　　　　 return cubeSum(inc(a) , b) + cube(a);
　　　 }
}

function piSum(a, b){
　　　 function piTerm(x){ return 1/((x+2)*x); }
　　　 function piNext(x){ return x+4; }
　　　
　　　 if(a b){
　　　　　　　 return 0;
　　　 }else{
　　　　　　　 return piSum(piNext(a) , b) + piTerm(a);
　　　 }
}

　　第一个函数用来计算从a-b的数的总和，步长为1，第二个函数计算a-b的立方和，步长为1，第三个函数计算a-b的一个方程的和(将a-b中的每一个数带入此方程进行计算)，步长为4.

　　从函数的形式以及函数的作用来看，这三个函数有很大的共性，所以我们考虑是否可以将这些共性抽取出来，将每次计算的步长和方程传入，进行求和计算？？答案当然是肯定的，下面我们来抽象：

　　定义下一个参与计算的数(通过步长函数的定义)

　　定义求什么的和(函数体的定义)

　　有了这两个函数，我们就可以计算任意的方程，指定区间的求和操作，将上述的两个函数做为参数传入，输出即为运算结果：

function sum(term, a, next, b){
　　　 if(a b){
　　　　　　　 return 0;
　　　 }else{
　　　　　　　 return sum(term, next(a), next, b)+term(a);
　　　 }
}

　　这个函数需要四个参数，一个是关于计算子的定义term,一个是步长函数next,另外两个即为区间的两个端点a,b，这样我们可以重新定义上述的三个函数如下：

function intSum(a, b){
　　　 function inc(x){return x + 1;}
　　　 function identity(x){return x;}

　　　 return sum(identity, a, inc, b);//调用通用的抽象接口
}

function cubeSum(a, b){
　　　 function inc(x){return x + 1;}
　　　 function cube(x){return x * x * x;}

　　　 return sum(cube, a, inc, b);//调用通用的抽象接口
}

function piSum(a, b){
　　　 function piTerm(x){ return 1/((x+2)*x); }
　　　 function piNext(x){ return x+4; }

　　　 return sum(piTerm, a, piNext, b);//调用通用的抽象接口
}

　　高阶函数提供了更高级的抽象，从而使得程序的结构更加清晰。下面我们再看看函数式语言的优雅的代码，匿名函数：

　　匿名函数

　　我们先对一些简单的操作进行简单的包装(如四则运算，boolean运算等操作)：

function abs(x){ return x0？x:-x;}
function add(a, b){ return a+b; }
function sub(a, b){ return a-b; }
function mul(a, b){ return a*b; }
function div(a, b){ return a/b; }
function rem(a, b){ return a%b; }
function inc(x){ return x + 1; }
function dec(x){ return x - 1; }
function equal(a, b){ return a==b; }
function great(a, b){ return ab; }
function less(a, b){ return ab; }
function negative(x){ return x0; }
function positive(x){ return x0; }

　　然后，在这些共用的语法糖(并非严格意义上的语法糖，但是它们的确是!)的基础上，做一些简单的函数定义:

// n*(n-1)*(n-2)*...*3*2*1
function factorial(n){
　　　 if(equal(n, 1)){
　　　　　　　 return 1;
　　　 }else{
　　　　　　　 return mul(n, factorial(dec(n)));
　　　 }
}

//对上边的函数的另一种定义方式
/*
　*　 product - counter * product
　*　 counter - counter + 1
　* */
function factorial(n){
　　　 function fact_iter(product, counter, max){
　　　　　　　 if(counter max){
　　　　　　　　　　　 return product;
　　　　　　　 }else{
　　　　　　　　　　　 fact_iter(mul(counter, product), inc(counter), max);
　　　　　　　 }
　　　 }

　　　 return fact_iter(1, 1, n);
}

function expt(b, n){
　　　 if(n == 0){
　　　　　　　 return 1;
　　　 }else{
　　　　　　　 return mul(expt(b, dec(n)), b);
　　　 }
}

function gcd(a, b){
　　　 if(b == 0){
　　　　　　　 return a;
　　　 }else{
　　　　　　　 return gcd(b, rem(a, b));
　　　 }
}

function search(fx, neg, pos){
　　　 function closeEnough(x, y){return less( abs( sub(x, y) ), 0.001)};
　　　 var mid = (function(x, y){return div( add(x, y), 2);})(neg, pos);
　　　 if(closeEnough(neg, pos)){
　　　　　　　 return mid;
　　　 }else{
　　　　　　　 var test = fx(mid);
　　　　　　　 if(positive(test)){
　　　　　　　　　　　 return search(fx, neg, mid);
　　　　　　　 }else if(negative(test)){
　　　　　　　　　　　 return search(fx, mid, pos);
　　　　　　　 }else{
　　　　　　　　　　　 return mid;
　　　　　　　 }
　　　 }
}

function halfIntervalMethod(fx, a, b){
　　　 var av = fx(a);
　　　 var bv = fx(b);

　　　 if(negative(av) && positive(bv)){
　　　　　　　 return search(fx, a, b);
　　　 }else if(negative(bv) && positive(av)){
　　　　　　　 return search(fx, b, a);
　　　 }else{
　　　　　　　 print("error happend!!");
　　　 }
}

//计算一个函数的不动点
function fixedPoint(fx, first){
　　　 var tolerance = 0.00001;
　　　 function closeEnough(x, y){return less( abs( sub(x, y) ), tolerance)};
　　　 function Try(guess){
　　　　　　　 var next = fx(guess);
　　　　　　　 //print(next+" "+guess);
　　　　　　　 if(closeEnough(guess, next)){
　　　　　　　　　　　 return next;
　　　　　　　 }else{
　　　　　　　　　　　 return Try(next);
　　　　　　　 }
　　　 };
　　　 return Try(first);
}

// magic function sqrt, a little hard to read, hah？
function sqrt(x){
　　　 return fixedPoint(
　　　　　　　 function(y){
　　　　　　　　　　　 return function(a, b){ return div(add(a, b), 2);}(y, div(x, y));
　　　　　　　 },
　　　　　　　 1.0);
}

　　如果上边的几个都可以完全理解，那么常识看看最下面的这个计算一个函数的平方根的函数sqrt(x)，你会发现这个函数很有意思，其中的那个匿名函数最有意思，我写了个测试函数：

function funcsTester(){
　　//计算两个数的平方和的匿名函数
　　　 var y = (function(x, y){ return add( expt(x, 2), expt(y, 2) ); })(3, 4);
　　　 print(y);
　　　 print(halfIntervalMethod(sin, 2.0, 4.0));
　　　 print(halfIntervalMethod(function(x){return expt(x, 3) - mul(2, x) - 3;}, 1.0, 2.0));//x^3-2x-3
　　　 print(fixedPoint(cos, 1.0));//cos的不动点
　　　 print(fixedPoint(function(x){return add( sin(x), cos(x)); }, 1.0));
　　　 print(sqrt(100));
}

　　运行结果如下：

js funcsTester()
25
3.14111328125
1.89306640625
0.7390822985224024
1.2587315962971173
10
js　

　　好了，关于函数式编程就大概介绍到这里，下面简单说说这个rhino包

　　关于Rhino

　　rhino是一个纯java的javascript引擎的实现，下载之后，将js.jar加入classpath,然后在命令行中输入：

java org.mozilla.javascript.tools.shell.Main

　　即可启动，可以使用load(path/of/script)来加载，加载完成后即可使用脚本中定义的函数，非常方便，当然DOM中的一切是不能用的，比如alert什么的，但是javascript不只是用来脚本化WEB页面的。可以使用print进行打印，使用quit()退出等，下面做一个关于rhino的例子：

user = {
　　　 name:"abruzzi",
　　　 password:"123456",
　　　 address:{
　　　　　　　 zip:"612345",
　　　　　　　 street:"west HuangQuan road"　　　
　　　 },
　　　 getName: function(){return this.name;},
　　　 getPassword: function(){return this.password;},
　　　 getAddress: function(){ return this.address.zip+"n"+this.address.street;}
}

$ java org.mozilla.javascript.tools.shell.Main
Rhino 1.7 release 2 2009 03 22
js load('~/development/myLib/HighOrderFunc/json.js')
js user　　　　　
[object Object]
js user.getName()
abruzzi
js user.getPassword()
123456
js user.getAddress()
612345
west HuangQuan road
js

　　在rhino的发行包中有一些特别有趣的例子，大家不妨自己动手做一下，看看效果，同时体会一下函数式编程的优美，简介。