践行

践行

Rest API 的那些事儿

作者/ asterisk

在软件行业快速发展的今天,传统的软件授权已经不能足以满足一个IT类的公司的发展。虽然在大部分公司里,它还是现金池的直接源头。但是在可遇见的未来,受摩尔根理论的失效、物联网的发展等影响,应用的架构会越来越趋于简单化,架构越来越倾向于分布式水平扩展,对外的服务提供也会越来越SaaS化。在这种大背景下,很多公司都开始提供所谓的开放平台。

查阅各个大公司的开放平台,我们不难发现,都是Rest API,都是HTTP请求,响应报文都是大同小异的XML或者是JSON等众多雷同的特点。这是为什么呢?让我们唠唠API平台的那些事。

定义

查看历史,我们惊讶地发现,其实Rest的概念早在2000年就被人提出。用一句话描述它,就是用固定的URI和可变的参数访问某个服务,来完成一系列业务请求。

  • 每一个URI代表一种资源;

  • 客户端和服务器之间,传递这种资源的某种表现层;

  • 客户端通过几个HTTP动词,对服务器端资源进行操作,实现"表现层状态转化"。

Rest API 格式

Rest API,无论它的名字多么高大上,它本质还是一个HTTP请求,POST也好,GET也罢,都是不同的数据提交方式。所以,能够决定一个Rest API的也就:URI、参数、请求方式、请求头等。

我们一般用URI来定义希望对外暴露的服务。结构基本类似 schema://yourCompanyDomain/rest/{version}/{application}/{someService}schema可以是http,也可以是httpsversion指的是你这个API的版本,application一般会指向底层的某个子系统,someService就是这个子系统对外提供的服务。当然,如果按照业务为边界划分,也可将业务维度相同但隶属于底层不同的系统的服务定义为一个application

对于这种Rest请求,常见的响应结果就是XML或者是JSON形式,往往结果中会包含请求状态,和时间戳,业务系统响应结果。

具体的格式约定,可以看底部的参考文献。

API的版本概念

URI 的格式定义中,我们包含了version这个字段,这在早期,其实被认为是不优雅的方式。阮一峰有一篇文章就专门抨击这种设计,后面他又自己打脸说还是拼接version的好。(不知道是不是因为Github的设计缘故)

API设计时常会考虑版本这个概念,无论是在URI还是在请求参数里面,至少有一个地方得指明含版本,为什么呢?

这很简单,就和系统迭代一样,API也是快速迭代开发的。也许初期,你的老大脑袋一热,我们要上API,于是你们就加班加点做,设定了一版请求协议。当时你们想,写完就能赚钱,必然带来一堆问题,比如说,代码难以维护,功能单一。后面这个API的第二版,你们要基于它去做一些新的变更,比如请求参数多了,返回内容多了,必然就有了第二版。但是又不能影响现有的业务。这个API基本的URI没变,但是会同时存在两个版本,老用户继续请求旧版,没问题,你无需动旧版?有需求的新用户,你要请求新版才能提供服务。这样通过版本来区分了不同的服务,便于以后的升级和维护。(就像BAE那货可以毫无压力地废弃掉2.0的API)

所以一开始设计API时,就要定义好版本。其次,版本化可以骗钱。我们可以满怀恶意地猜测,1.0为了抢用户,免费。2.0老牛逼了,你用的爽了,想更爽,付费。233333333

架构特点

API平台的架构,其实和底层公司的业务系统架构有着密切的关系,基于一个好的系统架构写一个Rest API平台基本是水到渠成的。我们先从业务系统的架构变迁说起,再来分析上面的API平台。

业务系统架构变迁

{%}

基本的软件公司的业务系统,一开始都是单机,单节点,单库。慢慢随着业务量的增加。这个系统越来越复杂,机器性能越来越不能满足需求。于是,第一种可能,领导说,换机器。上一台牛逼机器。但是机器性能有限,越牛逼的机器价格越贵,有时候都能买3~5台现有配置机器。于是就有了方案二,三个臭皮匠赛过一个诸葛亮。单应用,多机器,多节点

{%}

但是慢慢过了几年。你发现,这代码写的越来越屎,越来越复杂。基本上新来的开发要熟悉好几个月的业务。就代码因为快速上线。一堆坑,无法改。于是,大家现在都在做的事情,就是拆分。也就是现在常说的SOA。拆分,也有拆的好的,拆的不好的。不好的,就是一个大的恶心系统,变成了一堆恶心的小系统,互相调用,成一团乱码。小系统看似很好。但是某个不起眼的小系统。一挂,那么全部的系统都瘫了。这个时候这个万年不维护的小系统还找不到负责人,他么早就滚了。这就是拆分的技术欠债,你无法避免。

{%}

那么,就谈到拆分的架构设计。其实这块分两个架构,技术架构和业务架构。技术架构,就是要分清技术系统和业务系统。技术系统也可能是一个业务系统,但它一定是一个通用的服务组件。它提供的服务无任何定制需求,就是纯简单服务。比如,发短信发邮件发微信的通知系统,它就是通知。你业务有何特殊需求,就在上面自己实现一个XXX通知系统,那么业务系统的拆分,才是最关键的。就是要划清边界

这个边界问题很可怕,什么你该做,什么你不该做。每个系统的职责都要明确。不要你也实现一个他也实现一个,然后相互调。这种可怕性就是在两个服务都瘫痪的时候,完全都无法启用。最后你的系统架构变成了一个通用技术组件系统,完成各个基础服务,每个产品线,业务端,基于你的技术系统包装出业务定制化服务系统,然后最上层就是业务子系统。业务子系统组合在一起,就是一个大的业务系统,也叫服务化平台。

这个时候,你需要做开放平台。暴露一套Restful API,就是水到渠成了。

PS,实际的架构远比这个复杂,截图选自《大型网站系统与Java中间件实践》。

基于不同系统架构的 API 平台

一、演变

{%}

初期的API平台往往是上图左侧那种,某个庞大的业务系统希望暴露一套API,于是大家就在这个系统上做,直接设计一套协议。但是,这样子带来的缺点十分明显,第一,它与业务联系太重,理想的API平台是通用的,不是只给你设计一个。第二,它不好扩展,每次变更都得和业务系统一同上线,糟糕的情况下代码还会影响原有正常的业务。第三,性能问题,理论上会降低原有应用的性能。

这种情况下,如果应用部署了多台机器,多个节点,我们就可以独立出来。也就是右边所示的API Gateway,它做的事情本质上就是反向代理,将外部的请求校验完合法性之后反代至内部实际想要对外暴露服务的服务集群上。

所以,这种场景下,API Gateway也就如名称所说,就是一个入口。实际的Rest API的东西还是建立在各个业务子系统上,只是只需要提供最简单的服务,无需考虑授权等东西。用户管理,API注册发布,调用统计等,均由API Gateway实现处理。对于想要快速上线的开发人员而言,实在是一个不错的福音。

{%}

然而,当系统应用拆分到了SOA化之后,API的架构由有了新的变革,我们有了注册中心的概念。因为SOA化,所以每个业务子系统其实都有了对外的统一接口,有了ESB(注册中心)。实际的内部系统间请求也有了较好的路由、熔断等策略。

在这种大背景下,API平台对外暴露的Rest API无需底层的业务专门开发了。直接使用现有的内部接口,选择性暴露即可。问题点就在于,如何根据定义的Rest API请求,实际模拟内部的RPC协议请求。

某种程度上,这时候的API平台,已经不仅仅是HTTP Rest请求了。我们完全可以实现相同RPC协议的透传,比如你就是一个Hessian接口想对外暴露,我只需包上一层认证,直接注册于API Gateway,外部Hessian请求直接透传至内部子系统。

在这个基础上的 Rest API 平台,才是灵活的,可扩展的,易于维护的。然而有得必有失,Mock请求必然会有性能上的损耗,但是这个架构的公司,已经不在乎钱了,上10台虚机,不够加呗。

二、特点

1. C/S结构

2. 无状态(API平台无需存储业务状态,只做认证和转发)

3. 有缓存,API会对指定URI的请求转发做缓存,保证并发性,业务系统也对同样的请求针对性缓存。

4. 结构分层,每层间无法直接访问。

API平台的背后,就是庞大的各个业务子系统。每个API,就相当于一个业务子系统。API平台要做的事,就非常清晰和简单。就是业务子系统注册发布API,对外部请求校验计费,模拟请求内部业务子系统,对子系统结果包装序列化为JSON返回。

交互流程

{%}

上面是一个简单的交互,简单显示了外部系统和内部系统通过Rest API的交互过程:开发者(企业)注册,申请APP_KEY,开通API。按照开发接入,请求签名。转发至后端调用返回结果,API平台计费(预付费或者后收费),统计调用情况。

外部通信本质上还是HTTP,那么必然存在了授权问题,生产的API平台是直接暴露于公网的,如果认证授权策略出现纰漏,影响是可怕的。

比如,这个API是群发短信,你要是没有好的授权体系,允许人随意推送。某个人想搞你,调用发布反共信息,你整个公司都会跨。HTTP协议本质上没有这一块的内容,所以我们必然要在这上面考虑安全策略的内容。

如何保证Rest API的安全性

如果单纯考虑加解密,或者签名方式来保证请求合法,其实是远远不够的。事实上,一个安全的API平台往往需要多方面一起考虑,保证请求安全合法。

一、是不是实际客户端的请求?

1. 设计专门的私有请求头:定义独有的Request headers,标明有此请求头的请求合法。

2. 请求包含请求时间:定义时间,防止中间拦截篡改,只对指定超时范围内(如10秒)的请求予以响应。

3. 请求URI是否合法:此URI是否在API平台注册?防止伪造URI攻击

4. 请求是否包含不允许的参数定义:请求此版本的这个URI是否允许某些字段,防止注入工具。

5. 部分竞争资源是否包含调用时版本(Etag):部分竞争资源,使用If-Match头提供。如用户资金账户查询API,可以返回此时的账户版本,修改扣款时附加版本号(类似乐观锁设计)。

二、API平台是否允许你调用(访问控制)?

访问控制,主要是授权调用部分。API都对外暴露,但是某些公共API可以直接请求,某些,需要授权请求。本质的目的,都是为了验证发起用户合法,且对用户能标识统计计费。

以HMac Auth为例,我们简单设计一个签名算法。开发者注册时获取App Key、App Secret,然后申请部分API的访问权限,发起请求时:

1. 所有请求参数按第一个字符升序排序(先字母后数字),如第一个相同,则看第二个,依次顺延。

2. 按请求参数名及参数值相互连接组成一个字符串。param1=value1&param2=value2...(其中包含App Key参数)

3. 将应用密钥分别添加到以上请求参数串的头部和尾部:secret + 请求参数字符串 + secret。

4. 对该字符串进行 SHA1 运算,得到一个二进制数组。

5. 将该二进制数组转换为十六进制的字符串,该字符串为此次请求的签名。

6. 该签名值使用sign系统级参数一起和其它请求参数一起发送给API平台。

服务端先验证是不是实际客户端的请求,然后按照App Key查找对应App Secret,执行签名算法,比较签名是否一致。签名一致后查看此App Key对应的用户是否有访问此API的权限,有则放行。

执行成功后包装返回指定格式的结果,进行统计计费。

需求与实现

系统需求

目标

1. 支持rest类API接口动态发布及运营,包括但不限于:

  • 安全认证

  • 会话管理

  • 流量统计及限流

  • 计费收费

  • 熔断

2. 支持现有子系统RPC协议的API动态发布及运营,外部请求透传。

3. 支持json、xml响应报文,可以请求时选取所需报文格式。

4. 支持动态直接将后端SOA服务暴露为API。

5. 支持动态将普通Web接口暴露为API。

6. 支持动态将MQ服务暴露为API。

7. 支持多个服务组合编排后暴露为API。

业务需求

一、API管理

所有API可后台查询管理,包括动态发布、参数映射配置、后端服务接口配置、API禁用、启用,多版本、分组、分级别等。

二、应用管理

后台管理开放平台接入的应用(第三方应用),包括查询、禁用、启用、审核。

三、API鉴权&授权

1. 应用申请审核通过后生成公钥,开放平台需提供支持分布式系统的密钥管理

2. 服务可设置为两个安全等级:需授权访问和无需授权访问(后者即任意客户端都可以发起调用),默认所有API都需授权访问。

3. 非正常状态(禁用、停用、黑名单等)的应用直接抛异常不允许访问——熔断机制

  • 调用次数、调用频率、并发数可运行时控制,避免某请求量过大影响其他应用的调用。

  • 可对某个应用某个API设置强制熔断,所有请求无视阀值直接抛出异常。

4. 易用性

  • 与SOA集成,SOA服务一键发布到API平台。

  • 支持后台动态发布API,而不是新上一个API就需上线一次。

四、计费统计

1. API的调用统计,每笔请求时间,响应时间,响应状态。

2. API的计费计算,按照请求量和请求资源计费,实现多种计费模型。(预付费,后收费。按量,按时间周期。)

五、开发者平台

1. API开发者平台,开发者注册、访问、申请API授权、计费统计、调用统计。

2. API文档系统,详细的API文档展示,SDK下载,用户登录后还可专门生成不同编程语言请求,在线模拟请求结果等。

角色定义

一、外部用户

用户

做什么

使用目的

API平台接入方

接入API平台

使用XXXX提供的开放平台服务

二、各个业务产品线

用户

做什么

使用目的

各个业务产品线

作为外部应用接入API平台

使用XXXX提供的开放平台服务

各个业务产品线

提供服务

提供后端服务,发布到API平台供外部应用接入

公司后端应用

提供服务

提供后端服务,发布到API平台供外部应用接入

API平台

API治理

运营,管理API、第三方应用等

请求模型

API 的所有服务请求域名是相同的,区别在于Request Path等。请求参数分为系统级参数和业务级参数两部分,系统级参数是所有 API 都拥有的参数,而业务级参数由具体服务 API 定义。

统一服务 URL

建立API Gateway接受所有请求,按照Request Path,Request Method,Request Head分发所有的请求。

一、 通用统一URL

格式:schema://<API Gateway URI>/DispatcherServlet?method=XXService.xxMethod?xxxObj.xxxParam=xxxValue。

说明:所有请求直接走DispatcherServlet分发,所有内容均定义于URL参数中。method为后端某个子系统的某个方法。xxxObj.xxxParam为方法参数实体的某个属性的值定义。

示例:

http://api.xxxxx.com/router?method=SMSService.sendSMS&user.phoneNumber=18888888888&sign=ds234324sdsad&date=20151229231232

二、Rest类型URL

格式:schema://<API Gateway URI>/rest/{version}/{service}/{method}/{params}

说明:请求按照Gateway定义的Rest地址匹配,动态映射至具体系统具体方法,模拟调用。请求中包含version字段。

示例:

http://api.xxxx.com/rest/v1/XXService/xxMethod/{xxParam}

http://api.xxxx.com/rest/v1/XXService/xxMethod?xxxParam=xxxValue

参数设计

一、系统级参数

系统级参数是由 API 平台定义的一组参数,每个服务都拥有这些参数,用以传送框架级的参数信息。如我们前面提到的 method 就是一个系统级参数,使用该参数指定服务的名称。

二、业务级参数

业务级参数,顾名思义是由业务逻辑需要自行定义的,每个服务 API 都可以定义若干个自己的业务级参数。API Getaway 根据参数名和请求属性名相等的契约,将业务级参数具体的方法请求对象中。

常见框架

1. Kong:https://github.com/Mashape/kong

2. Zuul:https://github.com/Netflix/zuul

3. ROP:https://github.com/itstamen/rop

优劣

好处

1. 跨平台,管你是Java,还是PHP,还是Node.js还是Go,你丫都得支持HTTP请求。我API平台只需要提供这个语言的SDK,保证能按照消息协议调用就好。

2. 将复杂的内部业务系统抽象为通用调用请求。包装了复杂的业务逻辑,对外提供统一的,好管理的接口。并可以定制化设计,计费,授权一类的容易管理。

坏处

1. 协议描述能力弱化RestfulURI无法完全对请求参数做强格式校验。最后的方法参数绑定,模拟内部请求时往往容易出问题,尤其是以Java等强格式语言的系统。不能像WebService一样清晰描述请求报文。

2. 同样的道理,响应结果为了是JSONXML。这当中,编码,正反序列化,等操作,往往就会有性能瓶颈。而且,Java在这块资源消耗极大。以Github的ROP这个框架为例,当年测试时,它在并发请求过高的时候就会有一个内存泄漏问题。

附:参考资料

1. REST Is Not About APIs, Part 1

2. REST Is Not About APIs, Part 2

3. RESTful API 设计指南

4. 理解RESTful架构

5. 撰写合格的REST API

6. Netflix 官网

函数式编程中的常用技巧

作者/ 卢融凯

卢融凯,就职于北京七厘米科技有限公司,负责旗下初页app的后端研发工作,关注函数式编程以及高性能高可用服务的实现,领域驱动设计的忠实拥趸,并对多平台混合架构、程序员生产效率等领域有着浓厚的兴趣。

{%}

在Closure、Haskell、Python、Ruby这些语言越来越流行的今天,我们撇开其在数学纯度性上的不同,单从它们都拥有一类函数特性来讲,讨论函数式编程也显得很有意义。

一类函数为函数式编程打下了基础,虽然这并不能表示可以完整发挥函数式编程的优势,但是如果能掌握一些基础的函数式编程技巧,那么仍将对并行编程、声明性编程以及测试等方面提供新的思路。

很多开发者都有听过函数式编程,但更多是抱怨它太难,太碾压智商。的确,函数式编程中很多的概念理解起来都有一定的难度,最著名的莫过于单子),但是通过一定的学习和实践会发现,函数式编程能让你站在一个更高的角度思考问题,并在某种层面上提升效率甚至是性能。我们都知道飞机比汽车难开,但是开飞机却明显比开汽车快,高学习成本的东西解决的大部分是高回报的需求,这不敢说是定论,但从实践来看这句话基本也正确。

概述

wikipedia上对于函数式编程的解释是这样的:

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

翻译过来是这样的:

在计算机科学中,函数式编程是一种编程范式,一种构建计算机结构和元素的风格,它将计算看作是对数学函数的求值,并避免改变状态以及可变数据。

关键的其实就两点:不可变数据以及函数求值(表达式求值)。由这两点引申出了一些重要的方面。

不变性

FP中并没有变量的概念,东西一旦创建后就不能再变化,所以在FP中经常使用“值”这一术语而非“变量”。

不变性对程序并行化有着深远的影响,因为一切不可变意味着可以就地并行,不涉及竞态,也就没有了锁的概念。

不变性还对测试有了新的启发,函数的输入和输出不改变任何状态,于是我们可以随时使用REPL工具来测试函数,测试通过即可使用,不用担心行为的异常,不变性保证了该函数在任何地方都能以同样的方式工作。事实上,在函数式编程实践中,“编写函数、使用REPL工具测试,使用”三步曲有着强大的生产力。

不变性还对重构有了新的意义,因为它使得对函数的执行有了数学意义,于是乎重构本身成了对函数的化简。FP使代码的分析变的容易,从而使重构的过程也变的轻松了许多。

声明性风格

FP程序代码是一个描述期望结果的表达式,所以可以很轻松、安全的将这些表达式组合起来,在隐藏执行细节的同时隐藏复杂性。可组合性是FP程序的基本能力之一,所以要求每个组合子都有良好的语义,这和声明式风格不谋而合。

我们经常写SQL,它就是一种声明性的语言,声明性只提出what to do而不解决how to do的问题,例如下面:

SELECT id, amount
FROM orders
WHERE create_date > '2015-11-21'
ORDER BY create_date DESC

省去了具体的数据库查询细节,我们只需要告诉数据库要orders表里创建日期大于11月21号的数据,并只要id和amout两个字段,然后按创建日期降序。这是一种典型的声明性风格。

是的,我同意靠嘴是解决不了任何问题的,what to do提出来后总得有地方或有人实现具体的细节,也就是说总是需要有how to do的部分来支持。但是换个思路,假如你每天都在写foreach语句来遍历某个集合数据,难道你没有想过你此时正在重复的how to do吗?就不能将某种通用的“思想”提取出来复用吗?假如你可以提取,那么你会发现,这个提取出来的词语(或函数名)已经是一种what to do层面的思想了。

再比如,对于一个整型数据集合,我们要通过C#遍历并拿到所有的偶数,典型的命令式编程会这么做:

// csharp
var result = new List<int>();
foreach(var item in sourceList) {
    if(item % 2 == 0) {
        result.Add(item);
    }
}
return result;

这对很多人来说都很轻松,因为就是在按照计算机的思维一步一步的指挥。那么声明性的风格呢?

// csharp
return sourceList.Where(item => item %2 == 0);
// or LINQ style
return from item in sourceList where item % 2 == 0 select item;

甚至更进一步,假设我们有声明性原语,可以做到更好:

// csharp
// if we already defined an atom function like below:
public bool NumberIsEven(int number) {
    return number % 2 == 0;
}

// then we can re-use it directly.
return sourceList.Where(NumberIsEven);

说句题外话,我有个数据库背景很深的C#工程师同事,第一次见到LINQ时一脸不屑的说:C#的LINQ就是抄SQL的。其实我并没有告诉它C#的LINQ借鉴的是FP的高阶函数以及monad,只是和SQL长的比较像而已。当然我并不排除这可能是为了避免新的学习成本所以选用了和SQL相近的关键字,但是LINQ的启蒙却真的不是SQL。

我更没有说GC、闭包、高阶函数等先进的东西并不是.NET抄Java或者谁抄谁,大家都是从50多年前的LISP以及LISP系的Scheme来抄。我似乎听到了apple指着ms说:你抄我的图形界面技术…

类型

在FP中,每个表达式都有对应的类型,这确保了表达式组合的正确性。表达式的类型可以是某种基元类型,可以是复合类型,当然,也可以是支持泛型类型的,例如F#、ML、Haskell。类型也为编译时检查提供了基础,同时,也让屌炸天的类型推断有了根据。

F#的类型推断要比C#强太多了,一方面是受益于ML及OCamel的影响,一方面是在CLR层面上泛型的良好设计。很多人并不知道F#的历史可以追溯到.NET第一个版本的发布(2002年),而当时F#作为一个研究项目,对泛型的需求很大,遗憾的是.NET第一版并没有从CLR层面支持泛型。所以,F#团队参与设计了.NET的泛型设计并加入到.NET 2.0开始的后续版本,这也同时让所有.NET语言获益。

那么我们以不同的视角审视一下泛型。何为泛型?泛型是一种代码重用的技术,它使用类型占位符来将真正的类型延迟到运行时再决定,类似一种类型模板,当需要的时候会插入真实的类型。我们换一个角度,将泛型理解为一种包装而非模板,它打包了某种具体的类型,使用类似F#的签名表达会是这样:'T -> M<'T>,转变这种思维很重要,尤其是在编写F#的计算表达式(即Monad)时,经常会使用包装类这个术语。在C#中也可以看到类似的方面,例如int?其实是指Nullable<T>int类型的包装。

表达式求值

由于整个程序就是一个大的表达式,计算机在不断的求值这个表达式的同时也就意味着我们的程序正在运行。那么很有挑战的一方面就是,程序该如何组织?

FP中没有语句的概念,就连常用的绑定值操作也是一个表达式而非语句。那么这一切如何实现呢?假设我们有下面这段C#代码:

// csharp
var a = 11;
var b = a + 9;

我们有两个赋值语句(并且有先后依赖),如何用表达式的方式来重写?

// csharp
// we build this helper function for next use.
public int Eval(int binding, Func<int, int> continues) {
    return contineues(binding);
}

// then, below sample is totally one expression.
Eval(11, a =>
    //now a is binding to 11
    Eval(a + 9, b => b
        // now, b is binding to a + 9,
        // which is evaluate to 11 + 9
    ));

这里使用了函数闭包,我们会在接下来的柯里化部分继续谈到。通过使用continues(延续)技术以及闭包,我们成功的将赋值语句变了函数式的表达式,这也是F#中let的基本工作方式。

高阶函数

一类函数特性使得高阶函数成为可能。何为高阶函数?高阶函数(higher-order function)就是指能函数自身能够接受函数,并可以返回函数的一种函数。我们来看下面两个例子:

// C#
var filteredData = Products.Where(p => p.Price > 10.0);

// javascript
var timer = setInterval(function () {
    console.log("hello world.");
}, 1000);

C#中的Where接受了一个匿名函数(Lambda表达式),所以它是一个高阶函数,javascript的SetInterval函数接受一个匿名的回调函数,因而也是高阶的。

我们用一个更加有表现力的例子来说明高阶函数可以提供的强大能力:

// fsharp
let addBy value = fun n -> n + value
let add10 = addBy 10
let add20 = addBy 20

let result11 = add10 1
let result21 = add20 1

addBy函数接受一个值value,并返回一个匿名函数,该匿名函数对参数n和闭包值value相加后返回结果。也就是说,addBy函数通过传入的参数,返回了一个经过定制的函数。

高阶函数使函数定制变的容易,它可以隐藏具体的执行细节,将可定制的部分(或行为)抽象出来并传给某个高阶函数使用。

是的,这听起来很像是OO设计模式中的模板方法,在FP中并没有模板方法的概念,使用高阶函数就可以达到目的了。

在下节的柯里化部分将会看到,这种定制函数的能力内建在很多FP语言中,Haskell、F#中都有提供。

在FP中最常用的就是mapfilterfold了,我们通过检查在F#中它们的签名就可以推测它们的用途:

map:    ('a -> 'b) -> 'a list -> 'b list
filter: ('a -> bool) -> 'a list -> 'a list
fold:   ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

map通过对列表中的每个元素执行参数函数,得到相应的结果,是一种映射。C#对应的操作为Selectfilter通过对列表中的每个元素执行参数函数,将结果为true的元素返回,是一种过滤。C#对应的操作为Wherefold相对复杂一些,我们可以理解为一种带累加器的化简函数。C#对应的操作为Aggregate

之前我们提到过,泛型本身可以看做是某种类型的包装,所以如果我们面对一个'T list,那么我们可以说这是一个'T类型的包装,注意此处并没有说它是个范型列表。于是乎,我们对map有了一种更加高层次的理解,我们可以尝试一种新的签名:('a -> 'b) -> M<'a> -> M<'b>,这就是说,map将拆开包装,对包装内类型进行转换产生某种新的类型,然后再以同样的包装将其重新打包。

map也叫普通投影,请记住这个签名,我们在最后的延续一节将提出一个新的术语叫平展投影,到时候还会来对比map

如果我们对两个甚至是三个包装类型的值进行投影呢?我们会猜想它的签名可能是这样:

  • lift2: ('a -> 'b -> 'c) -> M<'a> -> M<'b> -> M<'c>

  • lift3: ('a -> 'b -> 'c -> 'd) -> M<'a> -> M<'b> -> M<'c> -> M<'d>

其实这便是FP中为人们广泛熟知的“提升”,它甚至可以称作是一种函数式设计模式。提升允许将一个对值进行处理的函数转换为一个在不同设置中完成相同任务的函数。

柯里化和部分函数应用

在计算机科学中,柯里化(Currying)是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数且返回结果的新函数的技术。

这段定义有些拗口,我们借助前面的一个例子,并通过javascript来解释一下:

// javascript
function addBy(value) {
    return function(n) {
        return n + value;
    };
}

var add10 = addBy(10);
var result11 = add10(1);

javascript版本完全是F#版本的复刻,如果我们想换个方式来使用它呢?

var result11 = addBy(10, 1);

这明显是不可以的(并不是说不能调用,而是说结果并非所期望的),因为addBy函数只接收一个参数。但是柯里化要求我们函数只能接受一个参数,该如何处理呢?

var result11 = addBy(10)(1);
//             ~~~~~~~~~    return an anonymous fn(anonymousFn, e.g)

如此就可以了,addBy(10)将被正常调用没有问题,返回的匿名函数又立即被调用anonymousFn(1),结果正是我们所期望的。

假如javascript在调用函数时可以像Ruby和F#那样省略括号呢?我们会得到addBy 10 1,这和真实的多参数函数调用就更像了。在addBy函数内部,返回匿名函数时带出了value的值,这是一个典型的闭包应用。在addBy调用后,value值将在外部作用域中不可见,而在返回的匿名函数内部,value值仍然是可以采集到的。

闭包(Closure)是词法闭包(Lexical Closure)或函数闭包(function closures)的简称,可参见wikipedia)上的详细解释。

如此看来,是不是所有的多参数函数都能被柯里化呢?我们假想一个这样的例子:

function fakeAddFn(n1) {
    return function(n2) {
        return function(n3) {
            return function(n4) {
                return n1 + n2 + n3 + n4;
            };
        };
    };
}

var result = fakeAddFn(1)(2)(3)(4);
//           ~~~~~~~~~~~~           now is function(n2)
//                       ~~~        now is function(n3)
//                          ~~~     now is function(n4)
//                             ~~~  return n1 + n2 + n3 + n4

但是这样又显得非常麻烦并且经常会出现智商不够用的情况,如果语言能够内建支持currying,那么情况将乐观许多,例如F#可以这样做:

let fakeAddFn n1 n2 n3 n4 = n1 + n2 + n3 + n4

编译器将自动进行柯里化,完全展开形式如下:

let fakeAddFn n1 = fun n2 -> fun n3 -> fun n4 -> n1 + n2 + n3 + n4

并且F#调用函数时可以省略括号,所以对fakeAddFn的调用看上去就像是对多参数函数的调用:let result = fakeAddFn 1 2 3 4。到这里你也许会问,currying到底有什么用呢?答案是:部分函数应用。

由于编译器自动进行currying,所以每一个函数本身是可以部分调用的,举个例子,F#中的+运算符其实是一个函数,定义如下:

let (+) a b = a + b

利用前面的知识我们知道它的完全形式是这样:

let (+) a = fun b -> a + b

所以我们自然可以编写一个表达式只给+运算符一个参数,这样返回的结果是另一个接受一个参数的函数,之后,再传入剩余一个参数。

let add10partial = (+) 10
let result = add10partial 1

同时,由于add10partial函数的签名是int -> int,所以可以直接用于List.map函数,如下:

let add10partial = (+) 10
let result = someIntList |> List.map add10partial

// upon expression equals below
// let result = List.map add10partial someIntList

// or, more magic, make List.map partially:
let mapper = (+) 10 |> List.map
let sameResult = someIntList |> mapper

|>运算符本身也是一个函数,简单的定义就是let (|>) p f = f p,这种类似管道的表达式为FP提供了更高级的表达。

我们知道FP是以Alonzo Church的lambda演算为理论基础的,lambda演算的函数都是接受一个参数,后来Haskell Curry提出的currying概念为lambda演算补充了表示多参数函数的能力。

递归及优化

由于FP没有可变状态的概念,所以当我们以OO的思维来思考时会觉得无从下手,在这个时候,递归就是强有力的武器。

其实并不是说现代的FP语言没有可变状态,其实几乎所有的FP语言都做了一定程度的妥协,诸如F#构建在.NET平台之上,那么在与BCL提供的类库互操作时避免不了要涉及状态的改变,而且如果全部使用递归的方式来处理可变状态,在性能上也是一个严峻的考验。所以F#其实提供了可变操作,但是需要明确的使用mutable关键字来声明或者使用引用单元格

以一个典型的例子为开始,我们实现一个Factorial阶乘函数,如果以命令式的方式来实现是这样的:

// csharp
public int Factorial(int n) {
    var result = 1;
    for(int index = 2; index <= n; index++) {
        result = result * index;
    }
    return result;
}

这是典型的how to do,我们开始尝试用递归并且尽可能的用表达式来解决问题:

// csharp
public int Factorial(int n) {
    return n <= 1
        ? 1
        : n * Factorial(n - 1);
}

这段代码是可以正常工作的,但是如果n的值为10,000呢?会栈溢出。此时便出现了本节要解决的第二个问题:递归优化。

那么这段递归代码为什么会溢出?我们展开它的调用过程:

n               (n-1)       ...      3         2       1  // state
--------------------------------------------------------
n*f(n-1) -> (n-1)*f(n-2) -> ... -> 3*f(2) -> 2*f(1) -> 1  // stack in
                                                       |
n*r      <-  (n-1)*(r-1) <- ... <-   3*2  <-   2*1  <- 1  // stack out

简单来说,因为当n大于1时,每次递归都卡在了n * _上,必须等后面的结果返回后,当前的函数调用栈才能返回,久而久之就会爆栈。那可以做点什么呢?如果我们在递归调用的时候不需要做任何工作(例如不去乘以n),那么就可以从当前的调用栈直接跳到下一次的调用栈上去。这称为尾递归优化。

我们考虑,当前调用时的n,如果以某种形式直接带到下一次的递归调用中,那么是不是就达到了目的?没错,这就是累加器技术,来尝试一下:

private int FactorialHelper(acc, n) {
    return n <= 1
        ? acc
        : FactorialHelper(acc * n, n - 1);
}

public int Factorial(int n) { return FactorialHelper(1, n); }

C#毕竟没有F#那么方便的内嵌函数支持,所以我们声明了一个Helper函数用来达到目的,对应的F#实现如下:

let factorial n =
    let rec helper acc n' =
        if n' <= 1 then acc
        else helper (acc * n') (n' - 1)
    helper 1 n

下面的示意表达了我们想达到的效果:

init        f(1, n)             // stack in
                |               // stack pop, jump to next
n           f(n, n-1)           // stack in
                |               // stack pop, jump to next
n-1         f(n*(n-1), n-2)     // stack in
                |               // stack pop, jump to next
...         ...                 // stack in
                |               // stack pop, jump to next
3           f((k-2), 2)         // stack in
                |               // stack pop, jump to next
2           f((k-1), 1)         // stack in
                |               // stack pop, jump to next
1           k                   // return result

可以看到,调用展开成尾递归的形式,从而避免了栈溢出。尾递归是一项基本的递归优化技术,其中关键的就是对累加器的使用。几乎所有的递归函数都可以优化成尾递归的形式,所以掌握这项技能对编写FP程序是有重要的意义的。

假如我们遇到的是一个非常庞大的列表需要处理,例如找到最大数或者列表求和,那么尾递归技术也将会让我们避免在深度的遍历时发生栈溢出的情形。

在前面我们说过fold是一种自带累加器的化简函数,那么列表求和以及最大数查找是不是可以直接用fold来实现呢?我们来尝试一下。

// fsharp
let sum l = l |> List.fold (+) 0
let times l = l |> List.fold (*) 1

let max l =
    let compare s e = if s > e then s else e
    l |> List.fold compare 0

可以看到,fold抽取了遍历并化简的核心步骤,仅将需要自定义的部分以参数的形式开放出来。这也是高阶函数组合的威力。

还有一个和fold很类型的术语叫reduce,它和fold的唯一区别在于,fold的累加器需要一个初始值需要指定,而reduce的初始累加器使用列表的第一个元素的值。

记忆化

我们知道大多数的FP函数是没有副作用的,这意味着以相同的参数调用同一函数将会返回相同的结果,那么如果有一个函数会被调用很多次,为什么不把对应参数的求值结果缓存起来,当参数匹配时直接返回缓存结果呢?这个过程就是记忆化,也是FP编程中常用的技巧。

我们以一个简单的加法函数为例:

let add (a, b) = a + b

注意这里我们使用了非currying化的参数,它是一个元组。接下来我们尝试使用记忆化来缓存结果:

let memoizedAdd =
    let cache = new Dictionary<_, _>()
    fun p ->
        match cache.TryGetValue(p) with
        | true, result -> result
        | _ ->
            let result = add p
            cache.Add(p, result)
            result

借助一个字典,将已经求值的结果缓存起来,下次以同样的参数调用时就可以直接从字典中检索出值,避免了重新计算。

我们甚至可以设计一个通用的记忆化函数,用于将任意函数记忆化:

let memorize f =
    let cache = new Dictionary<_, _>()
    fun p ->
        match cache.TryGetValue(p) with
        | true, result -> result
        | _ ->
            let result = f p
            cache.Add(p, result)
            result

那么前面的memorizedAdd函数可以写为let memorizedAdd = memorize add。这也是一个高阶函数应用的好例子。

惰性求值

Haskell是一种纯函数语言,它不允许存在任何的副作用,并且在Haskell中,当表达式不必立即求值时是不会主动求值的,换句话说,是延迟计算的。而在大多数主流语言中,计算策略却是即时计算的(eager evaluation),这在某种极端情况下会不经意的浪费计算资源。有没有什么方法能够模拟类似Haskell中的延迟计算?

假如我们需要将表达式n % 2 == 0 ? "right" : "wrong"绑定到标识(即变量名)isEven上,例如var isEven = n % 2 == 0 ? "right" : "wrong";,那么整个表达式是立即求值的,但是isEven可能在某种状况下不会被使用,有没有什么办法能在我们确定需要isEven时再计算表达式的值呢?

假如我们将isEven绑定到某种结构上,这个结构知道如何求值,并且是按需求值的,那么我们的目的就达到了。

// csharp
var isEven = new Lazy<string> (() => n % 2 == 0 ? "right" : "wrong");


// fsharp
let isEven = lazy (if n % 2 = 0 then "right" else "wrong")

当使用isEven时,C#可以直接使用isEven.Value来即时求值并返回结果,而F#的使用方式也是一样的isEven.Value

还有一种更加通用的方式来实现惰性求值,就是通过函数,函数表达了某种可以得到值的方式,但是需要调用才能得到,这和惰性求值的思想不谋而合。我们可以改写上面的例子:

// csharp
var isEven = (Func<string>)(() => n % 2 == 0 ? "right" : "wrong");

// fsharp
let isEven = fun () -> if n % 2 = 0 then "right" else "wrong"

这样,在需要使用isEven的值时就是一个简单的函数调用,C#和F#都是isEven()

延续

如果你之前使用过jQuery,那么在某种程度上已经接触过延续的概念了。 通过jQuery发起ajax调用其实就是一种延续:

$.get('http://test.com/data.json', function(data) {
    // processing.
});

ajax调用成功后会调用匿名回调函数,而此函数表达了我们希望ajax调用成功后继续执行的行为,这就是延续。

现在,我们回顾一下,在概述-表达式求值一节,我们为了将两个C#赋值语句改写成表达式的方式,新增了一个Eval函数:

// csharp
public int Eval(int binding, Func<int, int> continues) {
    return contineues(binding);
}

它也是一种延续,指定了在binding求值后继续执行延续的行为,我们将它稍做修改:

// csharp
public TOutput binding<TEvalValue, TOutput>(
    TEvalValue evaluation,
    Func<TEvalValue, TOutput> continues) {

    return continues(evaluation());
}

// fsharp
let binding v cont = cont v
// binding: 'a -> cont:('a -> 'b) -> 'b

于是我们可以模拟let的工作方式:

// fsharp
binding 11 (fun a -> printfn "%d" a)

那么延续这种技术在实践中有什么用途呢?你可以说它就是个回调函数,这没有问题。深层次的理解在于,它延后了某种行为且该行为对上下文有依赖。

我们考虑这样一个场景,假设我们有一颗树需要遍历并求和,例如:

// fsharp
type NumberTree =
    | Leaf of int
    | Node of NumberTree * NumberTree

let rec sumTree tree =
    match tree with
    | Leaf(n)           -> n
    | Node(left, right) -> sumTree(left) + sumTree(right)

那么问题来了,我们显然可以发现当树的层级太深时sumTree函数会发生栈溢出,我们也自然而然的想到了使用尾递归来优化,但是当我们在尝试做优化时会发现,然并卵。这就是一个无法使用尾递归的场景。

核心的诉求在于,我们希望进行尾递归调用(sumTree(left)),但在尾递归调用完成之后,还有需要执行的代码(sumTree(right))。延续为我们提供了一种手段,在函数调用结束后自动调用指定的行为(函数),于是当前正在编写的函数便仅包含一次递归调用了。我们仍然可以将它看作是一种累加器技术,区别在于,之前是累加值,而延续是累加行为。

我们尝试为sumTree递归函数加上延续功能:

// fsharp
let rec sumTree tree continues =
    match tree with
    | Leaf(n) -> continues n
    | Node(left, right) ->
        sumTree left (fun leftSum ->
            sumTree right (fun rightSum ->
                continues(leftSum + rightSum)))

此时,sumTree的签名从NumberTree -> int变成了NumberTree -> (int -> 'a) -> 'aNode(left, right)分支现在变成了单个函数的调用,所以它是尾递归优化的,每次计算时都会将结束后需要继续执行的行为以函数的方式指定,直到整个递归完成。

使用时,可以以延续的方式来调用sumTree函数,也可以像往常一样从返回值获取结果:

// fsharp
// continues way:
sumTree sampleTree (fun result -> printfn "result: %d" result)

// normal way:
let result = sumTree sampleTree (fun r -> r)

我们甚至可以从延续的思想逐渐推导出类似bind的函数,我们将它与map的签名对比:

// bind
('a -> M<'b>) -> M<'a> -> M<'b>
// map
('a -> 'b)    -> M<'a> -> M<'b>

在高阶函数一节我们说过,map叫普通投影,而新的bind叫做平展投影,它是一种外层匹配模式,在C#中对应的操作是SelectMany,在F#中就是bind,是一种通用函数。

在前面我们定义了一个binding函数,我们稍微调整一下参数顺序,并把它和bind对比:

// binding:
('a -> 'b)    -> 'a -> 'b
// map:
('a -> 'b)    -> M<'a> -> M<'b>
// bind:
('a -> M<'b>) -> M<'a> -> M<'b>

也就是说,如果我们为'a加上某种包装,然后在bind里再做一些转换,那么我们就可以推导出bind函数。

C#的LINQ里SelectMany对应的就是from语句,比如下面:

var result = from a in l1
            from b in l2
            from c in l3
            select { a, b }

这将转换成一系统嵌套的SelectMany调用,而select将转换为某种类似于Return<T>()的操作。对于F#来说,类似的代码可以用计算表达式(或者更加具体的序列表达式):

let result = seq {
    let! a = l1
    let! b = l2
    let! c = l3
    return (a, b)
}

到这里,似乎差不多该结束了,我们不打算继续深究bind,因为再往下走就到了monad了。事实上,大家已经看到了monad,F#的序列表达式以及C#中LINQ的一部分操作,就是monad


希望本文讲述的一些浅显的函数式编程概念可以在实践中对你有所帮助。最重要的是通过对思维的训练,可以从更加抽象的角度思考问题,提取问题最核心的部分以复用,将可变部分提出,从而使问题可组合,并且获得更好的表达性。

有关monad,推荐大家看看Erik Meijer大大在Channel9上的课程Functional Programming Fundamentals,它同时也是Rx库的作者之一,以及LINQ的作者。